A multi-commodity two-Echelon capacitated vehicle routing problem with time windows: Model formulations and solution approach. (March 2021)

• Record Type: Journal Article
• Authors: Dellaert, Nico; Van Woensel, Tom; Crainic, Teodor Gabriel; Dashty Saridarq, Fardin
• Is Part Of: Computers & operations research. Volume 127(2021)
• Publication Date: 2021-03
• Subjects: Distribution -- Multi-commodity -- Two-echelon -- Capacitated vehicle routing problem -- Model formulations -- Exact solution algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105154
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The MC-2E-VRPTW model formulations involve a combined arc-path based model. We obtain better lower bound estimates and new capacity constraints in the 2-path formulation. The numerical evaluation demonstrates the power of the developed models and solution methods. Abstract: This paper studies the multi-commodity two-echelon capacitated vehicle routing problem with time windows. Specifically, we take customer-specific origin to destination, non-substitutable demands into account. The main components are: ( i ) first echelon tours, ( ii ) second echelon tours and ( iii ) movement of commodities from first echelon to second echelon, considering route connection and synchronization. Exploiting the structure of the problem, we propose a decomposition scheme which decouples the first and second echelon routing problems, by deleting the third component, and re-couples them by using constraints ensuring movement of commodities between the two echelons. Based on this decomposition, we present ( i ) a number of model formulations for the MC-2E-VRPTW, and ( ii ) develop an exact solution approach for this real-life problem. A computational study on a comprehensive set of instances shows the effectiveness in terms of computational effort and solution quality.