The pickup and delivery problem with synchronized en-route transfers for microtransit planning
The pickup and delivery problem with synchronized en-route transfers for microtransit planning
复制标题
DOI：
10.1016/j.tre.2021.102562
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Zhexian Fu;Joseph Y. J. Chow
中科院分区：
文献类型：
--
作者：
Zhexian Fu;Joseph Y. J. Chow
微型交通和其他灵活的交通车队服务可以通过合并接送服务来降低成本。然而，如果用户必须下车并在车站等待另一次接送，那么接送服务的成本就会很高。提出了混合整数线性规划模型（MILP）来解决车辆同步途中转运（PDPSET）的取货和送货问题。传输位置由模型确定，可以位于网络中的任何候选节点，而不是预先定义的静态设施。在硬时间窗口内，车辆之间的转移操作是严格同步的。提出了一种启发式算法，以比商业软件短得多的计算时间以可接受的解决方案来解决问题。测试了两组综合数值实验：基于 5x5 网格网络的小型实例，以及高达 250x250 网格的不同网络大小的大型实例，以测试可扩展性。结果表明，在微交通中添加同步途中换乘可以进一步平均降低总成本10%，在我们的小规模测试实例中最大节省可达19.6%。启发式算法的平均最优性差距小于 1.5%，同时运行时间只占一小部分，并且可以扩展到 250x250 网格，运行时间在 1 分钟内。两个大型实例表明，通过同步途中换乘，可以进一步改善超过 50% 的车辆路线，并且在 200x200 网络上 100 辆车、300 个请求的情况下，最大节省车辆行驶距离可达 20.37%。
Microtransit and other flexible transit fleet services can reduce costs by incorporating transfers. However, transfers are costly to users if they must get off a vehicle and wait at a stop for another pickup. A mixed integer linear programming model (MILP) is proposed to solve pickup and delivery problems with vehicle-synchronized en-route transfers (PDPSET). The transfer location is determined by the model and can be located at any candidate node in the network rather than a static facility defined in advance. The transfer operation is strictly synchronized between vehicles within a hard time window. A heuristic algorithm is proposed to solve the problem with an acceptable solution in a much shorter computation time than commercial software. Two sets of synthetic numerical experiments are tested: small-scale instances based on a 5x5 grid network, and large-scale instances of varying network sizes up to 250x250 grids to test scalability. The results show that adding synchronized en-route transfers in microtransit can further reduce the total cost by 10% on average and maximum savings can reach up to 19.6% in our small-scale test instances. The heuristic on average has an optimality gap less than 1.5% while having a fraction of the run time and can scale up to 250x250 grids with run times within 1 min. Two large-scale examples demonstrate that over 50% of vehicle routes can be further improved by synchronized en-route transfers and the maximum savings in vehicle travel distance that can reach up to 20.37% for the instance with 100 vehicles and 300 requests on a 200x200 network.