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

Dorian Dumez, Christian Tilk, Stefan Irnich, Fabien Lehuédé, Katharina Olkis and Olivier Péton

European Journal of Operational Research, 2023, vol. 305, issue 1, 64-84

Abstract: 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 simultaneously 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 facilities, 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 improving 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 systematically 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 capacity of satellites as well as the integration of forward and reverse flows is analyzed.

Keywords: Routing; City logistics; Matheuristic; 2-Echelon Vehicle routing (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722003964
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:305:y:2023:i:1:p:64-84

DOI: 10.1016/j.ejor.2022.05.022

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().