A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method

In last-mile delivery, the turbulence of traffic uncertainties is often solved by establishing and utilizing multiple buffering warehouses (satellites) with setup and operational costs, which are very costly in implementation. This distribution system involving satellites is often derived as the two-echelon location routing problem (2E-LRP). This study proposes a new variety of 2E-LRP problems with mobile satellites, called 2E-LRP-MS, which aims to reduce the cost of 2E-LRP by replacing fixed-located satellites with mobile satellites. Rather than utilizing fixed-location satellites, 2E-LRP-MS employs the first echelon vehicles (CT) as the mobile satellites moving around the city to replenish multiple second echelon vehicles (CF) en-route. For the cargo replenishment process, CT and CF can temporarily park at the consolidation points (CP), such as public parking lots or paid loading-unloading zones. With this flexibility, the high operational costs of the fixed-location satellites can be exchanged with CP’s relatively low maintenance or renting fees, such as parking expenses. In this work, we introduce a heuristic method called clustering-based simultaneous neighborhood search (CSNS) to solve the proposed 2E-LRP-MS problem. The proposed CSNS considers the probabilistic mechanism and k-means clustering algorithm for facility selection, simultaneous neighborhood search to generate the routing solution, and local searches for optimizing the routing solution. Experimental results highlight the flexibility advantage of 2E-LRP-MS over 2E-LRP models and the searching efficiency of the proposed CSNS over the recent heuristic methods for two-echelon routing problems and commercial solver CPLEX.