Hybrid Algorithm for Route Design on Bus Rapid Transit Systems
Hybrid Algorithm for Route Design on Bus Rapid Transit Systems
复制标题
DOI：
10.1287/trsc.2013.0478
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
J. Walteros;A. Medaglia;G. Riaño
中科院分区：
文献类型：
--
作者：
J. Walteros;A. Medaglia;G. Riaño
近年来，精心设计的快速公交 BRT 系统已成为世界各地更昂贵的铁路公共交通系统的真正替代方案。然而，一旦 BRT 系统投入运行，其成功往往取决于为乘客提供的路线。因此，快速公交路线设计问题BRTRDP是寻找一组路线和频率的问题，使运营成本和乘客成本以及出行时间最小化，同时满足系统的技术约束，例如满足出行、公交车频率和车道容量的需求。为了解决这个问题，我们提出了 BRTRDP 的数学公式，作为具有底层网络结构的混合整数程序 MIP。然而，由于路由数量巨大，通过分支定界求解 MIP 对于大多数实际情况来说是遥不可及的。因此，我们提出了一种分解策略，在给定一组特定路线的情况下，将路线选择决策与 BRT 系统性能评估分离。后者的评估是通过使用列生成方案解决线性优化问题来完成的。我们将这种分解策略嵌入到混合遗传算法 HGA 中，并在 14 个实例中进行了测试，范围从 5 到 40 个车站，具有不同的 BRT 系统拓扑。结果表明，在 14 个问题中的 8 个问题中，HGA 能够获得可证明在 0.20% 范围内最优的解决方案。此外，在 14 个实例中的 4 个实例中，HGA 获得了最优解。
In recent years, well-designed bus rapid transit BRT systems have become a real alternative to more expensive rail-based public transportation systems around the world. However, once the BRT system is operational, its success often depends on the routes offered to passengers. Thus, the bus rapid transit route design problem BRTRDP is the problem of finding a set of routes and frequencies that minimizes the operational and passenger costs travel time while simultaneously satisfying the system's technical constraints, such as meeting the demands for trips, bus frequencies, and lane capacities. To address this problem, we propose a mathematical formulation of the BRTRDP as a mixed-integer program MIP with an underlying network structure. However, because of the vast number of routes, solving the MIP via branch and bound is out of reach for most practical instances. Hence, we propose a decomposition strategy that, given a certain set of routes, decouples the route selection decisions from the BRT system performance evaluation. The latter evaluation is done by solving a linear optimization problem using a column generation scheme. We embedded this decomposition strategy in a hybrid genetic algorithm HGA and tested it in 14 instances ranging from 5 to 40 stations with different BRT system topologies. The results show that in 8 of 14 problems, the HGA was able to obtain a solution that is provably optimal within 0.20%. Additionally, in 4 of 14 instances, HGA obtained the optimal solution.