Designing corridor systems with modular autonomous vehicles enabling station-wise docking: Discrete modeling method

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.