The electric dial-a-ride problem with capacitated charging stations, multiple depots and customer rejection

Integrating mass transit with demand-responsive service is challenging due to joint optimization of bus routes and multimodal customer trips. State-of-the-art mixed-integer-linear programming (MILP) approaches can solve the problem exactly for less than 10 requests (Posada et al. 2017). This is due to the cumbersome modeling of partial routes of the mass transit network, where the number of arcs is n(n-1)d (n = number of stations, d = number of departure). Besides, using electric vehicles in this problem leads to additional complexity because of charging scheduling and capacitated charging station constraints. This study proposes a novel MILP formulation of an electric integrated dial-a-ride problem with multiple depots and capacitated recharging stations to minimize overall system costs considering transfer synchronization and customer rejection. To address the abovementioned issues , we use time-dependent shortest paths on transit networks to substantially reduce redundant decision variables. With a four-hour computational time limit, we test the model up to 20 requests with different initial battery levels of vehicles. Results show that this model can solve the problem optimally around 95% faster and to a larger problem size if compared to Posada et al. (2017). A more compact arc-based formulation is developed concerning capacitated charging stations. The numerical results can reduce up to two-digit computation time compared to the state-of-the-art arc-based method.