Designing corridor systems with modular autonomous vehicles enabling station-wise docking: Discrete modeling method
Designing corridor systems with modular autonomous vehicles enabling station-wise docking: Discrete modeling method
复制标题
DOI：
10.1016/j.tre.2021.102388
复制
发表时间：
2021-06-25
影响因子：
10.6
通讯作者：
Li, Xiaopeng
中科院分区：
文献类型：
--
作者：
Chen, Zhiwei;Li, Xiaopeng
联合设计车辆调度时距和通行能力是城市轨道交通研究中较新的解决供需不对称问题的方法。本文研究了交通走廊与模块化自动驾驶车辆（MAV）进行分站对接的新问题；也就是说，车辆可以在走廊的任何一个站点改变它们的队形（或容量）。我们将该问题化为一个紧凑的混合整数线性规划模型，其中乘客上车顺序被显式建模。由于多工位系统结构和工位对接操作，模型的求解空间随着实例规模的增加而迅速增大，用现有的商业求解器求解该模型具有很大的挑战性。为了提高求解效率，我们根据所研究问题的理论性质，设计了一种自定义分支定界（B&B）算法。这些性质提供了最优车辆编队的上界和下界，揭示了乘客队列与车辆调度车头时距之间的关系，并确定了所研究问题的任意两个可行解之间的优势规则。它们大大减少了B&B树中节点的数量，如果没有这些属性，B&B树将会急剧增长。进一步，对B&B树的每个节点的目标值的下界和上界进行了解析计算，使我们能够非常快速地搜索解空间。因此，大大提高了B&B算法的计算速度。通过数值实验，我们证明了定制的B&B算法优于最先进的商业求解器Gurobi，并有效地解决了实际应用中相对较大的实例。与现有的固定容量操作相比，站智能对接操作可以降低系统成本。此外，其性能还受到车辆运行成本和乘客等待成本等系统参数的影响。总体而言，本研究将城市公共交通设计方法从传统的固定容量设计扩展到基于mav的不同运行因素（如最小调度时距）下的车站智能对接设计，为文献做出了贡献。该算法可以作为验证求解精度和计算性能的基准，为研究人员开发其他求解算法提供参考。
Jointly designing vehicle dispatch headway and capacity is a relatively new solution to the demand-supply asymmetry in urban mass transportation studies. This paper studies a new problem of this kind where a transportation corridor operates with modular autonomous vehicles (MAV) enabling station-wise docking; i.e., vehicles can change their formations (or capacity) at any station along the corridor. We formulate the problem into a compact mixed integer linear programming model where the passenger boarding order is explicitly modeled. Due to the multiple station system structure and the station-wise docking operation, the solution space of the model increases rapidly with the instance size, making it very challenging to solve the model with existing commercial solvers. To improve the solution efficiency, we design a customized branch and bound (B&B) algorithm with theoretical properties of the investigated problem. These properties offer upper and lower bounds to the optimal vehicle formation, reveal the relationship between the passenger queue and vehicle dispatch headway, and identify a dominance rule between any two feasible solutions to the investigated problem. They greatly reduce the number of nodes in the B&B tree that would grow dramatically without these properties. Further, the lower and upper bounds to the objective value at each node of the B&B tree are computed analytically, allowing us to search through the solution space very quickly. Consequently, the computation speed of the B&B algorithm is greatly improved. With numerical experiments, we show that the customized B&B algorithm outperforms a state-of-the-art commercial solver, Gurobi, and solves relatively large instances in real-world applications efficiently. The station-wise docking operation is shown to reduce system costs compared with existing fixed capacity operation. Further, its performance is affected by system parameters related to the vehicle operational cost and passenger waiting cost. Overall, this study contributes to the literature by extending the urban mass transportation design methodology from traditional fixed capacity design to the MAV-based station-wise docking design under various operational factors (e.g., minimum dispatch headway). The algorithm proposed can be used as a benchmark to verify the solution accuracy and computation performance for research efforts that aim to develop other solution algorithms for the investigated problem.