A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows

Last-mile collection and delivery services often rely on multi-echelon logistic systems with many types of practical spatial, temporal, and resource constraints. We consider three extensions of the basic 2-echelon vehicle routing problem that are of practical interest: First, second-echelon vehicles need to simultane-ously deliver and collect goods at customers within their specified time window. Second, first-echelon vehicles are allowed to perform multiple trips during the planning horizon. Third, the intermediate facil-ities, called satellites, allow temporary storage of goods, but the quantity that can be stored at a time is limited. This paper integrates these complicating features in a single mathematical model. To solve the problem, we design a decomposition-based matheuristic. It employs a reduced and refined mixed-integer programming formulation and two echelon-specific large neighborhood searches (LNS) to produce im-proving routes for the respective echelon. The most important algorithmic component is the feasibility check of LNS that relies on a sequence of constant-time and low-complexity tests. The final test allows re-scheduling of the operations taking place at a satellite. Extensive computational experiments systemat-ically evaluate the new components of the matheuristic and benchmark it against a recent exact method for a related problem. Moreover, the impact of the main problem features such as the number and ca-pacity of satellites as well as the integration of forward and reverse flows is analyzed.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper addresses the logistic challenges in last-mile collection and delivery services and proposes a mathematical model and heuristic algorithm to solve the problem.