为降低城市交通中出租车的空驶率，提高出租车运载效率，充分利用城市道路资源，缓解交通拥堵，在已有研究的基础上，将智能交通中多位乘客合乘出租车的路线规划及车辆调度问题分解为合乘乘客分组、行驶路线规划、指派车辆3 个步骤，将乘客间的“顺路”关系转化为有向图中的有向边，通过筛选连通子集构造合乘分组。分别对每一步骤建立整数线性规划模型，使得所需车辆尽量少，乘客等车时间尽可能短，乘客乘车绕行里程尽量少。使用分层序列法求解该多目标规划问题，并提出一种简化问题规模的策略，以提高求解效率。使用纽约实际出租车乘车数据构造模拟数据集测试算法的性能。测试结果表明，该方案具有“零绕行”、合乘率高的特点，能够大大提高出租车运载效率。
Abstract
With the purpose of reducing the vacancy rate of taxis in urban transport, increasing the carrying efficiency of taxis, making full use of urban road resources and easing traffic congestion, the route planning and vehicle scheduling problems of taxi pooling in intelligent transport were divided into three steps: passenger grouping, driving route planning and vehicle assignment. Passengers’“direct route”relationship was transformed into a directed edge, and the passenger grouping was constructed by filtering the connected subsets. Then integer linear programming models were established for each step to minimize the vehicle requirements and make passengers waiting time for the vehicles as short as possible, passengers traveling mileage by taxis as little as possible. The hierarchical sequence method was used to solve the multi-objective programming problem, and a strategy to simplify the problem scale was proposed to improve the solving efficiency. New York taxi data was used to construct a simulation data set to test the performance of the algorithm. The test results show that the program has the characteristics of“zero passing round”and high taxi pooling rate, which can greatly improve carrying efficiency of taxi.
关键词
智能交通 /
整数线性规划 /
分层序列法 /
出租车合乘 /
车辆调度
Key words
intelligent transport /
integer linear programming /
hierarchical sequence method /
taxi pooling /
vehicle scheduling
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] TAO C C, CHEN C Y. Heuristic Algorithms for the Dynamic Taxipooling Problem Based on Intelligent Transportation System Technologies[J]. Transportation Research Part B: Methodological, 2001, 137: 579-594.
[2] YAN S Y, CHEN C Y, WU C C. Solution Methods for the Taxi Pooling Problem[J]. Transportation, 2012, 39(3): 723-748.
[3] 程杰，唐智慧，刘杰，等. 基于遗传算法的动态出租车合乘模型研究[J]. 武汉理工大学学报（交通科学与工程版），2013，37（1）：187-191.
[4] QI X, XIONG J, XU G Q, et al. Taxi-Pooling Scheduling Model and Algorithm Based on Many-to-Many Pickup and Delivery Problems[C]// American Society of Civil Engineers 16th COTA International Conference of Transportation Professionals. Shanghai. 2016: 89-98.
[5] ZHANG R, PAVONE M. Control of Robotic Mobility-on-Demand Systems: A Queueing-Theoretical Perspective[J]. The International Journal of Robotics Research, 2014, 35(1-3): 186-203.
[6] STIGLIC M, AGATZ N, SAVELSBERGH M, et al. Making Dynamic Ride- Sharing Work: The Impact of Driver and Rider Flexibility[J]. Transportation Research Part E: Logistics and Transportation Review, 2016, 91: 190-207.
[7] NOURINEJAD M, ROORDA M J. Agent Based Model for Dynamic Ridesharing[J]. Transportation Research Part C: Emerging Technologies, 2016, 64: 117-132.
[8] ALONSO-MORA J, SAMARANAYAKE S, WALLAR A, et al. On-Demand High-Capacity Ride-Sharing via Dynamic Trip- Vehicle Assignment[J]. Proceedings of the National Academy of Sciences, 2017, 114(3): 462-467.
[9] 冯田. 基于sufferage的动态出租车拼车调度算法[J]. 电脑知识与技术，2011，7（28）：7019-7023.
[10] OU X F, LUO B T, XIANG C Q, et al. Design and Research of Taxi-Pooling Service[J]. Journal of Chengdu Technological University, 2017(2): 43-49.
[11] XIAO Q, HE R C. Carpooling Scheme Selection for Taxi Car-pooling Passengers: A Multi-Objective Model and Optimization Algorithm[J]. Archives of Transport, 2017, 42(2): 85-92.
[12] 佚名. 2017年湖南省高校第三届研究生数学建模竞赛赛题公布与竞赛须知[EB/OL]. (2017-04-21) [2017-09-11].
[13] NYC Taxi & Limousine Commission. Trip Record Data[EB/OL]. (2017-03-13)[2017-09-11].
[14] 张秀利，梁迎春，董申. 多目标结构模糊优化的分层序列法[J]. 机械设计与制造，1999（5）：44-45.
[15] 吴斌，史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J]. 计算机学报，2001，24（12）：1328-1333.
PDF(1676 KB)
京公网安备 11010102003417号
京ICP备17006742号-3
