Two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery

Jiliu Li, Min Xu (Corresponding Author), Peng Sun

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

This paper investigates the two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery (2E-VRPGS), which is a new variant of the classical two-echelon capacitated vehicle routing problem (2E-VRP). In the 2E-VRPGS, customers from the same administrative region are served by vehicles from the same satellite so as to ensure service consistency, with pickup and delivery being performed simultaneously in the second echelon. To solve this problem to optimality, we formulate it as a path-based model and develop a tailored branch-and-cut-and-price algorithm, which can also exactly solve two closely related variants of 2E-VRPGS in the literature: the 2E-VRP with grouping constraints (2E-VRPG), and the 2E-VRP with simultaneous pickup and delivery (2E-VRPS). In particular, a novel dominance rule in the labeling algorithm, together with several customized valid inequalities, has been put forward to effectively accelerate the solution method by exploiting the problem characteristics. To evaluate the efficacy of the proposed algorithm on the problems 2E-VRPG, 2E-VRPS, and 2E-VRPGS, extensive numerical experiments have been conducted on three types of benchmark instances. Computational results on the 2E-VRPGS show that our dominance rule can significantly reduce the number of generated labels and all families of valid inequalities have a great impact on strengthening the path-based model. The algorithm is found to be highly competitive when compared with the existing exact algorithm for the 2E-VRPG and some new findings and managerial insights are derived from sensitivity analysis.

Original languageEnglish
Pages (from-to)261-291
Number of pages31
JournalTransportation Research Part B: Methodological
Volume162
DOIs
Publication statusPublished - Aug 2022

Keywords

  • Branch-and-cut-and-price
  • Grouping constraints
  • Simultaneous pickup and delivery
  • Two-echelon vehicle routing
  • Valid inequalities

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'Two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery'. Together they form a unique fingerprint.

Cite this