The electric location-routing problem with heterogeneous fleet: Formulation and Benders decomposition approach

In this paper, we focus on a problem that requires the location of recharging stations and the routingof electric vehicles in a goods distribution system. The goods are disseminated from a depot anddistributed to the customers via a heterogeneous fleet of electric vehicles with limited capacity.Differently from the classical vehicle routing problem, the vehicles have battery restrictions thatneed to be recharged at some stations if a trip is longer than their range. The problem reducesto finding the optimal locations of the recharging stations and their number to minimize the totalcost, which includes the routing cost, the recharging cost, and the fixed costs of opening stationsand operating vehicles. We propose a novel mathematical formulation and an efficient Bendersdecomposition algorithm embedded into a two-phase general framework to solve this environmentallogistics problem. Phase I solves a restricted problem to provide an upper bound for the originalproblem which is later solved in Phase II. Between the two phases, an intermediate processingprocedure is introduced to reduce the computations of the Phase II problem. This is achieved bya combination of the Phase I upper bound and several lower bounds obtained via exploiting theunderlying network structure. Our approach solves the problem in a general setting with nonidentical stations and vehicles by allowing multiple visits to the stations and partial recharging.The computational study provides both managerial and methodological insights.Keywords: Recharging Station Location, Electric Vehicle Routing, Environmental Logistics,Integer Programming, Benders Decomposition