Electric integrated dial-a-ride services with capacitated charging stations, multiple depots, and customer rejections

This study addresses the integrated dial-a-ride problem using a fleet of electric vehicles. We propose a mixed-integer-linear programming modelling approach considering multiple depots, customer rejection, partial recharge policy and capacitated charging stations. State-of-the-art mixed-integer-linear programming approaches can solve the problem exactly for only less than 10 requests. This is due to the cumbersome modeling of partial routes in a mass transit network, where the number of arcs expands rapidly with the network size. We developed an efficient departure-expanded transit graph to model the problem efficiently by trimming off unnecessary arcs, and we include a preprocessing step based on time-window tightening on the timetabled transit network. We test the proposed method on a set of test instances with up to 50 requests and different initial battery levels of vehicles within a four-hour computational time limit. The results show that the problem can be solved optimally to a larger problem size and about 95% faster compared to the state-of-the-art. We developed a novel compact arc-based formulation for optimizing electric vehicle routing problems with capacitated charging stations. Our computational results provide a reduction in computational time by up to two digits compared to the state-of-the-art replication-based method.