Operational design for shuttle systems with modular vehicles under oversaturated traffic: Discrete modeling method

Existing peak/off-peak based schedules in urban mass transit systems feature two types of dispatch headways and a fixed vehicle capacity across the operational horizon, which lowers their service quality and causes significant energy waste. A promising cure to this challenge is to jointly design the dispatch headways and vehicle capacities in urban transit schedules. Chen et al. (2018) propose a continuous modeling method to solve the near-optimum solutions to and shed analytical insights into this joint design problem. Based on the theoretical properties discovered in the preceding paper, this paper formulates the joint design problem as a mixed integer linear programming model that can yield exact solutions to the optimal design with a discretized time representation. Further, a customized DP algorithm is proposed to solve this model. Similar to other problems that can be solved by DP algorithms, the “curse of dimensionality” also exists in the investigated problem since the queue length, as a state variable, may have a large set of possible values at each stage, which may lead to dramatically increasing computational time in solving the problem. To expedite the solution speed of the DP algorithm, we propose a set of valid inequalities based on the relationship between the queue length and vehicle capacity. These valid inequalities can reduce the unboundedly increasing state space into a narrow band and thus dramatically expedite the DP algorithm. With two sets of numerical experiments, we show that the discrete model can be solved by the customized DP algorithm to optimality with much less computation time compared with a state-of-the-art commercial solver, Gurobi. The analysis also reveals that the input parameters affect the effectiveness of dynamic capacity design under oversaturated and unsaturated traffic systems in a similar way despite some minor differences.