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

Using the Harmony Scattered Search Algorithm to Select Riders in the Dynamic Ridesharing

作　　者：侯立文[1] 刘思 HOU Li-wen;LIU Si(Shanghai Jiaotong University,School of Antai Economic & Management,Shanghai 200030,China;Shanghai University for Science & Technology?School of Management,Shanghai 200093,China)

机构地区：[1]上海交通大学安泰经济管理学院，上海 200030 [2]上海理工大学管理学院，上海 200093

出　　处：《中国管理科学》2019年第5期208-216,共9页Chinese Journal of Management Science

基　　金：国家自然科学基金资助项目(71372108);教育部人文社科资助项目(12YJC630059)

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

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

分 类 号：C91[经济管理]