Electric Vehicle Routing Problem With Capacitated Charging Stations and Dynamic Electricity Prices

With rapid electrification of transportation systems in recent years, the electric vehicle routing problem (EVRP) has received increasing attention. In order to serve a set of valuable transportation tasks using a fleet of electric vehicles (EVs), EVRP intends to jointly determine their routes and the charging schedules, with the aim of optimizing service reward and charging cost under state of charge (SOC) constraints of battery. EVRP is a difficult nonlinear integer program, and due to its intrinsic NP-hardness early EVRP studies often oversimplify the charging process and assume unlimited capacity of charging stations (CSs) and constant electricity price. The contribution of this article lies in twofold. First, to better characterize the practical charging process, this article introduces a new graph model that can take the CS capacity and dynamic electricity price into full consideration. Second, we design a series of transformation techniques, including reformulation SOC dynamics, Lagrangian relaxation, exact linear programming relaxation, etc, which eventually convert the original EVRP into an approximate linear program. Extensive simulations across 14 instances demonstrate that, the proposed approach is capable of solving large-scale instances over 500 nodes, and is 100 times faster than traditional analytic methods while achieving very close optimality. While comparing with the popular heuristic method adaptive large neighborhood search (ALNS), our method is several times faster and obtains much better optimality.