Paper
Publication Date
Abstract

Two-Echelon Vehicle Routing Problems (2E-VRPs) describe the distribution of goods via two echelons of vehicles and sets of transshipment facilities. They have received growing attention in academic research and their applications are becoming increasingly widespread in modern last-mile logistics systems. This paper introduces a new and extensive variant of the 2E-VRP that combines important real-world features such as time windows, mixed pickup and delivery demand, vehicle range constraints and multiple trips for vehicles on the second echelon. We refer to it as the Two-Echelon Multi-Trip Vehicle Routing Problem with Deliveries, Pickups and Time Windows (2E-MT-VRP-PTW). We present a compact exact formulation that solves small instances to optimality in reasonable time. We present an efficient and customized matheuristic to solve medium and large instances. The solution method integrates an exact formulation for the first-echelon routing into an adaptive large neighborhood search framework for the second-echelon routing. The performance of the matheuristic is evaluated on modified benchmarks from the literature. The heuristic shows strong performance in solution quality and runtime when compared to the exact formulation. Sensitivity analyses over key demand characteristics are performed.