A fast algorithm to optimize meeting-point-based electric first-mile feeder services with capacitated charging stations

This paper addresses the meeting-point-based electric demand-responsive-transport routing and charging scheduling problem under charging synchronization constraints. The problem considered exhibits the structure of the location-routing problem, which is more difficult to solve than conventional electric vehicle routing problems. We propose to model the problem using a mixed integer linear programming approach based on a layered graph structure. A two-stage simulated annealing-based algorithm is proposed to solve the problem efficiently. A mixture of randomness and greedy partial recharge scheduling strategy is proposed to find feasible charging schedules under the synchronization constraints. The algorithm is tested on 20 instances with up to 100 customers and 49 bus stops. The results show that the proposed algorithm outperforms the best solutions found by a commercial mixed-integer linear programming solver (with a 2-hour computational time limit imposed) for 12/20 test instances and with less than 1-minute computational time on average.