摘 要
网约车共享在很大程度上缓解了出行、环境和资源压力，网约车共享工作主要有两个方面：订单指派和路径规划。本文从这两方面出发，同时兼顾乘客和司机的利益，提出了基于矩阵划分的多目标订单指派算法（Matrix Partition-based Multi-ObjectiveOrder Assignment Algorithm, MPB-MOOAA）和基于地标分段的多目标路径规划算法（ Landmark Segmentation-based Multi-Objective Route Planning Algorithm ， LSB-MORPA），从而解决共享环境下的订单指派和路径规划问题，主要研究工作如下：
1.以最大服务质量和最大共享里程率为目标，建立了多目标订单指派问题优化模型，并提出 MPB-MOOAA 对该模型进行求解。该算法首先采用两点间近似最短距离以代替计算昂贵的最短路径距离，从而降低了算法的时间复杂度；其次采用关系矩阵划分算法，使具有相似旅程的乘客和司机聚集起来，从而将一个矩阵分解为多个小矩阵进行处理，大幅度缩小了问题规模；最后提出了矩阵压缩机制减少了解的存储空间，从而降低了算法的空间复杂度。实验结果表明，MPB-MOOAA 适用于不同实际场景，相比其他经典的多目标进化算法在处理订单指派问题上更具优势。
2.以最小行驶距离和最大可兼容乘客数为目标，建立了多目标路径规划问题优化模型，并提出了 LSB-MORPA 对该模型进行求解。该算法以进化算法为基本算法，在初始解构造中引入双向随机游走思想，设计了全新的交叉和变异算子，预测了非支配解集，从而平衡了行驶距离和载客数之间的关系。为了提高推荐路径的效率和多样性，该算法通过引入地标对路径进行了分段处理，提高了路径覆盖乘客率。实验结果表明，LSB-MORPA 解的多样性和收敛性较好，相比未引入地标的算法，引入地标的算法非支配路径推荐成功率明显提高。
3. 实现了网约车路径规划系统。基于开源的j Metal框架实现了MPB-MOOAA和LSB-MORPA，为了使其更适合处理路径规划问题，在j Metal框架中增加了新的交叉算子和变异算子。使用JSP结合Servlet实现了网约车共享路径规划系统可视化展示。
关键词 ： 订单指派；路径规划；多目标；进化算法；矩阵划分 。
ABSTRACT
Online ride-sharing has largely alleviated the pressure on travel, environment andresources. The ride-sharing work mainly has two aspects: ride-matching and route planning.
Starting from these two aspects and taking into account the interests of riders and drivers,this paper proposes Matrix Partition-based Multi-Objective Order Assignment Algorithm（MPB-MOOAA）and Landmark Segmentation-based Multi-Objective Route PlanningAlgorithm（LSB-MORPA）to solve the problem of ride-matching and route planning in theride-sharing environment, and the main important work of this paper:
1. An optimization model of the multi-objective order assignment problem wasestablished with the objectives of maximizing service quality and maximizing sharedmileage rate, MPB-MOOAA was proposed. First, the approximate shortest distance betweentwo points is proposed to replace the computationally expensive shortest path distance. Thus,the time complexity of the algorithm is reduced; then the partition is adopted to gather ridersand drivers with similar journeys, the relation matrix construction algorithm is proposed,which decomposes a matrix into multiple small matrices for processing and greatly reducesthe scale of the problem; finally, the matrix compression mechanism is proposed to reducethe storage space, reducing the space complexity of the algorithm. The experimental resultsshow that MPB-MOOAA is suitable for different practical scenarios and has moreadvantages in order assignment than other classic multi-objective evolutionary algorithms.
2. An optimization model of the multi-objective path planning problem was establishedwith the objectives of the minimum travel distance and the maximum number of compatiblepassengers, and LSB-MORPA was proposed. The algorithm takes the evolutionary algorithmas the basic algorithm. introduces bi-directional random walk in the initial populationstructure, designs a new crossover and mutation operator and predicts the non-dominatedsolution set to provide drivers with multiple route options. In order to improve the efficiencyand diversity of recommended routes, the algorithm segmented the route by introducinglandmarks to improve the route coverage rate of passengers. Experimental results show thatthe diversity and convergence of LSB-MORPA solutions are better. Compared with thealgorithm without landmarks, LSB-MORPA has significantly improved the success rate ofnon-dominated path recommendation.
3. Implement the online car-hailing route planning system. MPB-MOOAA and LSB-MORPA are implemented based on the open-source j Metal framework. To make it moresuitable for route planning, a new crossover operator and mutation operator are added. UseJSP combined with Servlet to implement the visual interface.
Keywords : ride-matching; route planning; multi-objective; evolutionary algorithm;matrix partition。
第1章 绪论
本章节讲述了本文研究工作的研究背景及意义、国内外现状以及文章组织结构，主要针对本文的研究内容进行先导概述，为本研究进行了铺垫，对后面章节提供了理论支撑。
1.1、研究背景及意义。
近年来，城市交通拥堵问题越来越严重。交通拥堵会造成能源浪费、环境污染、打车难等诸多问题。高峰时段汽车交通需求量大，座位占有率低，导致许多城市交通拥堵，特别是当出租车空载时，会造成不必要的资源浪费，增加环境负担。基于环境、能源和交通压力等方面的考虑，每日出行的车辆是有限制的，而这些有限的车辆在满足大量人群出行方面显得有些力不从心。在传统的叫车服务中，每位司机在某一时间段内通常只被分配服务于一个订单，这使得出租车平均座位占有率偏低。如果能共享出租车服务，使得出行的出租车座位被大量占用，便可使空余资源得到合理的利用，从而有利于缓解经济、环境和交通等方面的压力。为了共享出租车减少服务出租车的空座率，使大量的人力与环境资源得到充分的利用，各个领域的学者不断地进行探索和研究。
1981年，Daqanzo[1]最先提出“拼车”作为缓解交通出行压力的方法。拼车在解决环境污染、交通拥堵及资源紧张等方面具有巨大的潜力，也因其便宜、方便、环保且不降低出行效率而越来越被人们接受。在移动互联网与普适计算的推动下，拼车体现出数据量大、动态性强、目标多样、应用范围广等新特点[2]据调查研究表明，私家车的座位使用率相对偏低，在欧洲用于休闲旅行的车辆平均座位使用率为1.8，用于工作上班的车辆平均座位使用率占1.1[3]，美国也存在相同情况[4] [5]，高峰期对汽车运输的巨大需求和较低的座位使用率导致了许多城市地区的交通拥堵[6]，尤其是节假日上下班高峰期，许多乘客为了避免打车时间过长而会选择接受拼车，拼车已逐渐改变着人们日常出行方式。近年来车辆共乘问题逐渐获得了学术界[7] [8] [9]和工业界[10] [11]的广泛重视。车辆共乘问题分为静态共乘和动态共乘，静态共乘是指车辆出发之前，综合考虑司机和乘客的上车地点、出发时间和最大等待时间等因素，事先已确定匹配关系并且已规划好行驶路径。动态共乘是指车辆在行驶的过程中，实时进行匹配司机与乘客。如今车辆共享问题主要工作分为两方面：订单指派和路径规划。
订单指派问题是双边匹配决策问题的扩展，双边匹配决策问题的起源是为了解决高校学生选择学校和实际生活中男女婚姻的匹配问题。在实际生活中，有很多实际问题可以用双边匹配决策的方法来解决。例如男性和女性互相选择伴侣进行婚姻匹配的问题、应聘人员与公司提供岗位的双向匹配问题、电子商务中网商中介对于买家和卖家双方交易匹配问题[12]等。双边匹配决策是典型的多指标和多目标决策问题，双边匹配决策的过程中，一个群体对另一个群体的要求基本都不是一个，而是同时要满足好几个，例如婚姻匹配中女性对男性的要求包括身高、体重、金钱财富和素质修养等众多指标，而且双边匹配决策需要同时满足双方的要求。本文要解决问题是大规模出行订单的背景下，如何快速高效地匹配司机和乘客的出行订单问题，其可建模为二部图匹配模型，经典的数学算法（Kuhn-Munkres，KM）[13]算法可解决二分图匹配问题。但因其计算复杂度较高，往往不能用来直接求解大规模的二分图匹配问题，于是许多启发式算法被用来解决该问题。
路径规划问题本质上属于车辆路径问题（Vehicle Routing Problem, VRP），VRP指对一系列装货点和卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间等）下，达到一定问题的目标（如路程最短、费用最少、时间尽量少等）。由于在大规模路网中寻路问题属于NP难问题，现有大量工作主要在于降低该问题求解的算法计算复杂度，以启发式算法为主如蚁群算法、遗传算法等。本文研究的路径规划问题为在满足司机和乘客的要求下，寻找多条乘客覆盖率大的路径。车辆共乘问题的参与者有三：乘客、司机和服务平台。这三者的利益关系环环相扣紧密相关，从单一角度考虑车辆共乘问题显得有些片面单薄，故如今多数文章从多目标的角度对该问题进行建模并求解。
【由于本篇文章为硕士论文，如需全文请点击底部下载全文链接】
1.2、国内外研究现状.
1.2.1、 订单指派
1.2.2、路径规划.
1.3 、本文组织结构
1.4、 本章小结
第2章 多目标进化算法
2.1、 进化算法
2.2、多目标优化问题
2.3、多目标进化算法分类
2.3.1 、基于Pareto的多目标进化算法
2.3.2、 基于分解的多目标进化算法，
2.3.3、基于指标的多目标进化算法.
2.4 、本章小结
第3章 基于矩阵划分的多目标订单指派
3.1、相关概念定义及描述
3.2、多目标订单指派模型
3.3、基于矩阵划分的多目标订单指派算法
3.3.1、近似最短距离
3.3.2、关系矩阵划分算法
3.3.3、矩阵压缩
3.3.4、算法流程
3.4、实验结果及分析.
3.4.1、数据集
3.4.2、实验结果及分析
3.5、本章小结
第4章 基于地标分段的多目标路径规划
4.1 、 相关概念描述
4.2、多目标路径规划模型
4.3、基于地标分段的多目标路径规划算法.
4.3.1、 编码
4.3.2、初始解的构造.
4.3.3 、交叉算子
4.3.4 、变异算子
4.3.5、地标选取
4.3.6、 算法流程
4.4、实验结果及分析，
4.4.1、评价标准
4.4.2、数据集.
4.4.3、实验结果与分析
4.5、本章小结
第5章 网约车共享路径规划系统设计及实现.
5.1、 开发工具及环境.
5.2、系统设计.
5.2.1、 算法实现.
5.2.2、网页设计，
5.3、功能展示
5.4、本章小结.
第6章 结 论
网约车共享路径在解决环境污染、交通拥堵及资源紧张等方面具有巨大潜力，尤其是节假日上下班高峰期，许多乘客为了避免打车时间过长而会选择接受拼车。为了避免交通拥堵，每日可出行的车辆数量是有限制的，出于环保意识或者经济利益，越来越多的私家车司机愿意与乘客分享自己的旅程。而如何在快速时间内匹配乘客与司机的出行订单并且在匹配成功后推荐给司机多条路径变得尤为重要。本文针对这两个问题分别提出了快速高效的算法并且建立了一套完备的系统。本文主要做了以下工作：
（1）本文建立了多目标订单指派模型，针对该模型提出了MPB-MOOAA，针对不同的实际场景提供相应的匹配策略。利用K-means算法对路网进行聚类，在构建乘客或者司机的候选集时，通过判断是否在同一簇而缩小地理区域范围，排除了响应距离较远的订单从而提高查找速度。利用上下界逼近思想，提出近似最短距离来替代复杂耗时的最短路径距离的计算。为了缩小问题规模提出了关系矩阵划分算法，将紧密度大的乘客和司机聚集起来，组成多个较小的集合，从而提高匹配效率。设计实验以接近程度为评价标准选取了合适的聚类簇数，从共享里程率、服务质量、耗时和匹配成功率等方面讨论了ɑ的取值对实验结果的影响，相比经典传统的KM算法求解匹配问题，采用MPB-MOOAA求解，很大程度上提高了求解效率且运行时间不随问题规模增大。实验证明，本文提出的MPB-MOOAA具有较好的效率和性能，适合快速高效地处理大规模订单。
（2）本文建立了多目标路径推荐模型，针对该模型提出了LSB-MORPA，为司机提供多条非支配解集。在初始解构造过程中引入双向的随机游走思想提高了效率。针对路径推荐问题，设计了全新的交叉、变异方法，使种群朝着更好的方向进化。本文对整个路网中地标个数和选取规则给予充分的说明，并且通过对比实验最终确定规则中参数W取1.0时效果达到最好，详细阐述了订单中依次经过的地标选取规则，通过在三个不同规模的真实路网上进行实验，实验结果表明该多目标路径规划算法有着较好的性能与效率，推荐的非支配路径有良好的收敛性和多样性。
（3）本文实现了网约车路径共享系统，采用Java语言编写。后台数据处理及算法在修改添加后的j Metal框架上实现，可视化网页展示使用JSP结合Servlet实现。Servlet调用j Metal处理完的数据，将结果显示在JSP上。该系统能快速高效地对大规模出行订单进行匹配、可提供司机不同线路并且能将路径真实地在地图上标记出来。
参考文献
[1] Daganzo, C arlos F. EQUILIBRIUM MODEL FOR CARPOOLS ON AN URBAN NETWORK[M]Washington, US: Transpartation Rese arch Board.1981 :74-79.
[2]徐毅,童咏昕,李未 大规模拼车算法研究进展[J].计算机研究与发展, 2020,57(01)32-52.
[3] EEA. occupancy rates of passenger vehicles[R]. Indicatar fact sheet. C openhagen D enm ark:Eur opean Environm ental Agency.2010:1-6.
[4] Santos A, Mcguckin N, N akam.oto H Y, et al. Sumn ary of Travel Tr ends: 2009 N ati onal H ousehold Travel Survey[J]. D emographics.20117):19-31 .
[5] 张明杰，毋建宏信息化管理视角下的西安市交通拥堵研究[J].西安邮电大学学报, 2012,17(001):114-117.
[6] Hasan M H, H entenryck P V, Legrain A. The C ommute Trp-Sharing Problem[J]. TranspartationS cience.2020, 54(6) :1640-1675.
[7] LiuX, Tithenidge H, YanX, et al. A pass enger-todriver m atching m ode1 for cam mnuter carpoaling Case study and snsitivity analyss[]. Tr ansportation Research Part C Emereng Technologies. 2020,117(4):102702(1)-102702(21).
[8] A, Niels Agat, et al. Optim z ation for dynamnic nide- sharing Arevi ew - Sci enceDirect[J]. EuropeanJ ournal ofOper ati onal Research. 2012, 223(2):295-303.
[9]郭羽含,张宇，沈学利,于俊宇.即时车辆共乘问题的多策略解空间图搜索算法[].计算机研究与发展,2020,5706):1269-1283 .
[10]D'Orey P M, F emnandes R, Ferreira M. Empirical evaluation of a dynanic and di stributed taxi-sharing system [C]. Internati anal IEEE C onf erence on Intelligent Transportati an Systems. H awaii United States. IEEE. 2012:140-146.
[11]Ma s, Zheng Y, Wolfson 0. T share: A large- scale dynanic taxi nide sharing service[C]. IEeE Inemational C anfer ence on Data Engineening DC, Unted Stats: IEEE, 2013: 410-421.
[12]曹媛媛.双边市场的用户信息技术接受问题研究[]西安邮电大学学报, 2013(04) 100- 104.
[13] KuhnH W. The Hungani an method for the assi gun ent problen [J]. N aval Resear chLogstics 2010,522)7-21.
[14] Huang Y, Jin R, Bastani F, et al. Large Scale Real-time Ri desharing with Service G uar antee on Road Netw arks[J] Proceedings of the V 1db Endowment 2013, 7(14).2017-2028.
[15] TaN, Li G, Zhao T, et al An Efici ent Ride Sharing F ran ew ork for Maximizing Shared Route[].IEE Transactions on Knowledge and Data Engineering 2018, 30(2):219-233.
[16] Zheng L, Chen L, Ye J. Order di spatch in pnice- aw are nidesharing[]. Proceedings of the VLDBEndowm ent.2018, 11(8):853-865 .
[17] Kline C P. Relational C osts and the Production of Social Capita1: Evidence from Carpooing[J]Econamic Journal. 2006, 116(511):581-604.
[18] PengZ, ShanW, JiaP, et al. Stable nide- sharing m atchingfo the commuterswith payn ent desi gnl[]Transportation 2020,47(1):1-21.
[19] Tafreshi an A Masoud N . Trip- based graph partiti aning in dynam ic ridesharing[J]. Transportation Rese: archP art C: Em ergngTechnologes. 2020, 114(3):532-53.
[20] J elokhani N iar aki M, S am anyN N, Moham madi M, et al. A hybri dri de sharing algarithm based on GIS and ant col any optim iz ation thr ough geosoci al netw orks[]. Jounal of Ambient Intelligence and Hum anized C omputing.2020(11):1-21.
[21] B aldacci R, Mingozzi M A An Ex act Method for the C ar Poling Problem Based on LagrangeanC olumn Generation[J]. Operations Research. 2004, 52(3):422- 439.
[22] Jung J, JayalkrishnanR, Park JY. Dynamic Shared-Taxi Disp atchA1goritlm with Hybri d-Simul ated Anne aling[]. Comnputer- Aided Civil and Infrastructure Engneering. 2016, 31(4)275-291.
[23] Kleiner A, Nebel B, Ziparo V A. A Mechani sm for Dynarmic Ride Sharing Based on Parallel Auctions[C] IJCAI 2011, Proceedings of the 22nd International Joint C onference on Artifi cial Itelligence. C atal oni a, Spain: AAAI Press 2011266-272.
[24] Agatz, N, Erera, A, Savelsbergh, M Wang X Optimiz ation for dynanic nide- sharing areview[].E uropean Journal of Operational Research 2012, 223(2)295-303.
[25]李哲、彭鹏、黄海生可拉伸障碍物磁导率过渡带的路径规划算法[D]西安邮电大学学报,2020, v.25 ;No.1 43(02):56-61.
[26]Chak Fai Yuen, Abhishek Pratap Singh et al . B eyond Shortest P aths: R oute R ecomm endati ans far Ride- sharing[C] www 19: The World Wde Web C onference. NY, United states: ACM 2019:2258-2269
[27] Garg N, RanuS. Route Recomm endati ons for Idle Taxi Divers: Find Me the Shortest Route to a Customer! [C] the 24thACM SIGKDD Intermnati onal C onference. London, UK: ACM, 2018:1425-1 434.
[28] HuangY, JinR, Bastani F, et al. L arge Scale Real-time Ridesharing with Service Guarantee on Road N etw arks[J]. Proceedi ngs of the V1db Endowment. 2013, 7(14):2017-2028.
[29] KatagriH, U no T, Kato K et al. An intr active m ultiobjective prog amming approach to tour routeplarning probl ems[C] 2013 IEEE 6th International Workshop on C am putati onal Intelligence and Applications (IWCIA) . Hiroshin a, J aqpan: IEEE 2013:167-171
[30]樊守伟，严艳,张少杰,等. Djkstra算法与旅游路径优化[J]西安邮电大学学报, 2014,019(001):P121-124
[31] Kanoh H, Hara K. Hybrid genetic algorithm for dynamnic multi- objective route pl anning with predicted taffc in a real-w orld road network[C]. GECCO 2008: Proceeding: of the Genetic andE voluti onary C omputation C anference. Atlanta, USA: ACM,2008:657-664.
[32]闫兴亚,吴加贺,石云平.基于遗传算法的虚拟校园漫游路径规划[]西安邮电大学学报,2013, 18006):80-84.
[33] Osman I H. Metastr ategy sin ul ated annealing and talbu search algorithms for the velhicle routingproblem [J]. Annals of Oper ati ons Research. 1993, 41 (4):421 -451.
