基于整数线性规划的合乘出租车调度模型

Scheduling Model of Taxi Pooling Based on Integer Linear Programming

为降低城市交通中出租车的空驶率,提高出租车运载效率,充分利用城市道路资源,缓解交通拥堵,在已有研究的基础上,将智能交通中多位乘客合乘出租车的路线规划及车辆调度问题分解为合乘乘客分组、行驶路线规划、指派车辆3个步骤,将乘客间的"顺路"关系转化为有向图中的有向边,通过筛选连通子集构造合乘分组。分别对每一步骤建立整数线性规划模型,使得所需车辆尽量少,乘客等车时间尽可能短,乘客乘车绕行里程尽量少。使用分层序列法求解该多目标规划问题,并提出一种简化问题规模的策略,以提高求解效率。使用纽约实际出租车乘车数据构造模拟数据集测试算法的性能。测试结果表明,该方案具有"零绕行"、合乘率高的特点,能够大大提高出租车运载效率。

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 trav?eling 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.