Benders Decomposition for the Design of a Hub and Shuttle Public Transit System
Benders Decomposition for the Design of a Hub and Shuttle Public Transit System
复制标题
DOI：
10.1287/trsc.2017.0756
复制
发表时间：
2019-01-01
影响因子：
4.6
通讯作者：
Van Hentenryck, Pascal
中科院分区：
文献类型：
--
作者：
Maheo, Arthur;Kilby, Philip;Van Hentenryck, Pascal
BusPLUS项目旨在改善澳大利亚堪培拉非高峰时段的公共交通服务。为了解决覆盖大范围地理区域的困难，BusPLUS提出了一种枢纽和班车模式，该模式由关键枢纽之间的几条高频公交线路和大量班车组成，这些班车将乘客从出发地带到最近的枢纽，并将他们从最后一个巴士站带到目的地。本文以公交网络设计为研究对象，提出了一种基于Benders分解方法的多模式公交网络设计的有效求解方法。从一个混合整数规划（MIP）制定的问题，本文提出了一种Benders分解方法，使用专用的解决方案技术解决独立的子问题，帕累托最优切割，切割捆绑，和核心点更新。从堪培拉的公共交通系统的实际数据的计算结果证明了设计的选择，并表明该方法优于MIP制定两个数量级。此外，研究结果表明，枢纽和穿梭模型可以减少运输时间的两倍，同时保持在现有的交通系统的成本。
The BusPLUS project aims at improving the off-peak hours public transit service in Canberra, Australia. To address the difficulty of covering a large geographic area, BusPLUS proposes a hub and shuttle model consisting of a combination of a few high-frequency bus routes between key hubs and a large number of shuttles that bring passengers from their origin to the closest hub and take them from their last bus stop to their destination. This paper focuses on the design of the bus network and proposes an efficient solving method to this multimodal network design problem based on the Benders decomposition method. Starting from a mixed-integer programming (MIP) formulation of the problem, the paper presents a Benders decomposition approach using dedicated solution techniques for solving independent subproblems, Pareto-optimal cuts, cut bundling, and core point update. Computational results on real-world data from Canberra's public transit system justify the design choices and show that the approach outperforms the MIP formulation by two orders of magnitude. Moreover, the results show that the hub and shuttle model may decrease transit time by a factor of two, while staying within the costs of the existing transit system.