利用和声分散搜索算法解决动态共乘的乘客选择研究

doi:10.16381/j.cnki.issn1003-207x.2019.05.021

摘要/Abstract

摘要： 动态共乘作为一种配合解决城市交通出行难题的新模式近年来引起了人们越来越多的关注，然而在较大范围内选择合适的乘客，以便获得最佳的综合服务效果却具有相当大的挑战性。本文正是针对这一问题，建立了以乘客效用最大化和司机总行程最短为目标函数，以满足司机与乘客的时间要求和司机参与约束为限制条件的多目标0-1规划共乘模型，用于帮助司机选择最合适的乘客。根据该模型的特点，构造了加入了分散搜索机制的新的和声搜索算法。在仿真实验时，针对司机和乘客效用的两种产生方式，在较大规模的路网环境下利用该算法分别对模型进行了求解，得到了Pareto最优解集。仿真结果不仅表明了模型的合理性和算法的可行性，而且还指出基于效用函数可以发现更多合适的潜在乘客。最后，通过与文献中其它算法的对比进一步展示了本文算法的有效性。

关键词: 动态共乘, 多目标0-1规划模型, 和声分散搜索算法, 效用

Abstract: Dynamic ridesharing (DR), as a new approach to help alleviate the traffic congestion and improve travel experience, has gained lots of attentions in recent years. However, how to smartly choose the suitable passengers from the numerous appliers so as to achieve as high service effectiveness and satisfaction as possible challenges the drivers. Apart from the reason that the participants' travel schedule and the number of seats constrain the matching of passengers and drivers, another important problem is the matching scale. In reality DR service often involves thousands of participants who are located randomly in a large road network. Consequently, to accomplish a match in a short time is a very time-consuming task. A multi-objective 0-1 programming model is built whose objective functions are to maximize passengers' utility and meantime to minimize the travel distance. Such consideration can care about the passengers' most interest but at lowest cost of drivers. The constraints of the model comprise the time limitation to passengers and drivers and driver's reserve utility. An intelligent algorithm which incorporates scattered algorithm into the harmony algorithm is developed to help solve the model because the scale of the model is beyond the capability of the traditional algorithms. Based on a 100*100 road network (more complicated than the real road network, actually), the simulation experiments are carried out twice according to the way of how to specify the passengers and driver's utility. The simulation result shows that the model is reasonable and the algorithm is feasible in terms of the derived Pareto solutions. Moreover, compared with the directly assigned utility value, the utility function is more effective to find the suitable the riders. Finally, the comparison with Tabu search algorithm shows that our algorithm outperforms the rival algorithm, which further indicates that our algorithm is effective and applicable to the reality.

Key words: dynamic ridesharing, multi-objective 0-1programming model, harmony scatter search algorithm, utility

中图分类号:

侯立文, 刘思. 利用和声分散搜索算法解决动态共乘的乘客选择研究[J]. 中国管理科学, 2019, 27(5): 208-216.

HOU Li-wen, LIU Si. Using the Harmony Scattered Search Algorithm to Select Riders in the Dynamic Ridesharing[J]. Chinese Journal of Management Science, 2019, 27(5): 208-216.

参考文献

[1] Furuhata M, Dessouky M, Ordonez F, et al. Ridesharing:The state-of-the-art and future directions[J]. Transportation Research Part B, 2013, 57:28-46.

[2] Agatz N, Erera A, Savelsbergh M, et al. Optimization for dynamic ride-sharing:A review[J]. European Journal of Operational Research, 2012, 223:295-303.

[3] Herbawi W, Weber M. The ridematching problem with time windows in dynamic ridesharing:a model and a genetic algorithm[C]//Proceedings ACM Genetic and Evolutionary Computation Conference, Philadelphia,PA,USA,July 7-11,ACM,2012:1-8.

[4] 程杰,唐智慧,刘杰,等. 基于遗传算法的动态出租车合乘模型研究[J]. 武汉理工大学学报(交通科学与工程版),2013,37(1):187-191.

[5] 肖强,何瑞春,张薇,等.基于模糊聚类和识别的出租车合乘算法研究[J]. 交通运输系统工程与信息,2014,5:119-125.

[6] 张瑾,何瑞春. 解决动态出租车"拼车"问题的模拟退火算法[J]. 兰州交通大学学报,2008,(3):85-88.

[7] Abdel-Naby S, Fante S. Auctions negotiation for mobile rideshare service[C]//IEEE International Conference on Pervasive Computing and Applications, Joronto, Canada, March 19-23,2007.

[8] Winter S, Nittel S. Ad hoc shared-ride trip planning by mobile geosensor networks[J]. International Journal of Geographical Information Science, 2006, 20(8):899-916.

[9] Tao Chichuang, Chen Chunying. Dynamic rideshare matching algorithms for the taxipooling service based on intelligent transportation system technologies[C]//Proceedings of 14th International Conference on Management Science & Engineering, Harbin,China,Aug.20-22,IEEE,2007, 1-3:399-404.

[10] Amey A M. Integrating information on ridesharing opportunities with travel information from other modes[J]. TDM Review, 2010, 17(1):1-8.

[11] 刘书曼,周宗福,张晨,等. 关于合肥市"出租车拼车"问题的优化研究[J]. 重庆工商大学学报(自然科学版),2013,11:70-75.

[12] 邵增珍,王洪国,刘弘,等. 车辆合乘匹配问题中服务需求分派算法研究[J]。清华大学学报(自然科学版),2013,(2):252-258.

[13] Cordeau J F, Laporte G. The dial-a-ride problem:Models and algorithms[J]. Annals of Operations Research, 2007, 153(1):29-46.

[14] Dominik K, Roberto W C. A Granular Tabu Search algorithm for the Dial-a-Ride Problem[J]. Transportation Research Part B:Methodological, 2013, 56:120-135.

[15] Berbeglia G, Cordeau J F, Laporte G. Dynamic pickup and delivery problems[J]. European Journal of Operational Research, 2010, 202(1):8-15.

[16] Cortes C E, Matamala M, Contardo C. The pickup and delivery problem with transfers:Formulation and a branch-and-cut solution method[J]. European Journal of Operational Research, 2010, 200(3):711-724.

[17] 颜瑞,朱晓宁,张群,等.考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学,2017,25(7):67-77.

[18] 符卓,刘文,邱萌.带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J].中国管理科学,2017,25(5):78-86.

[19] 毕笑天,何瑞春.基于出行效用的小汽车合乘可行性研究[J].武汉理工大学学报(交通科学与工程版),2015,39(6):1204-1207.

[20] Geem Z W, Kim J H, Loganathan G V. A new heuristic optimization algorithm:Harmony search[J]. Simulation, 2001, 76(2):60-68.

[21] Mahdavi M, Fesanghary M, Damangir E. An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation, 2007, 188(2):156-159.

[22] Verma A, Panigrahi B K, Bijwe P R. Harmony search algorithm for transmission network expansion planning[J]. IET Generation, Transmission & Distribution, 2010, 4(6):663-673.

[23] 王晓晴,唐加福,韩毅. 分散搜索算法进展[J]. 系统仿真学报,2009,21(11):3155-3160.

[24] Beausoleil R P."MOSS" multi-objective scatter search applied to non-linear multiple criteria optimization[J]. European Journal of Operational Research, 2004, 169:426-449.

[25] Russell R A, Chiang W C. Scatter search for the vehicle routing problem with time windows[J]. European Journal of Operation Research, 2006, 169(2):606-622.

[26] 左忠义,刘津,汪磊.基于几何概型的出租车合乘候车时间分析[J]. 大连交通大学学报, 2015,36(6):1-5.

[27] Xia Jizhe, Curtin K M, Li Weihong, et al. A new model for a carpool matching service[J]. PLoS ONE, 2015, 10(6):1-23.