A Branch-and-Price Algorithm for a Green Two-Echelon Capacitated Location Routing Problem

Abstract

In this paper, we present a new green two-echelon capacitated location routing problem (G-2E-CLRP), which aims to determine simultaneous decisions on locating satellites and routing electric vehicles for city logistics delivery system. The first echelon consists of round trips from the depot to open satellites, the second echelon consists of tours from these satellites to the end customers, whereas battery swapping operations are only allowed at the depot or satellites. The problem is formulated as an arc-based formulation and then we propose a set- partitioning formulation in which routes are defined as second-echelon tours. We develop an branch- and-price (B&P) algorithm to solve this problem and propose a column generation procedure that combines modified Clarke Wright (MCW) savings method and pulse algorithm to provide feasible tours efficiently. The proposed algorithm is validated using extensive computational experiments and is found to perform well when compared against commercial branch-and- bound/cut solvers such as CPLEX. Based on these results, we assess the benefits of integrating locations of satellites and routes of electric vehicles in this new green two- echelon logistics system.