Stochastic Charger Location and Allocation Problem in Last-Mile Delivery

Abstract

This paper presents the stochastic charger location and allocation problem in last-mile delivery. The problem belongs to the class of facility location models with congestion. We formulate the problem as a mixed-integer quadratic program and develop a solution methodology that combines Lagrangian relaxation and primal heuristic techniques.  Our framework utilizes a Lagrangian dual decomposition approach, where the resulting sub-problems are solved using a semi-relaxation cutting plane method. To obtain feasible solutions, we propose rounding techniques. This dual approach allows us to generate both lower bounds (via Lagrangian relaxation) and upper bounds (via heuristics) on the optimal solution, and enables the calculation of a heuristic primal-dual gap. Our approach is capable of tackling very large-scale problem instances, aligning with the projected mega-scale needs of future EV infrastructure in the United States. We perform computational experiments and present a case study using Chicago metropolitan data, providing valuable insights for the strategic planning of EV charging networks. This research substantially contributes to the field of sustainable urban logistics and transportation infrastructure optimization.