Branch-and-price-based algorithms for the two-echelon vehicle routing problem with time windows

N.P. Dellaert (Corresponding author), F. Dashty Saridarq (Corresponding author), T. van Woensel (Corresponding author), T.G. Crainic (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)
8 Downloads (Pure)

Abstract

This paper studies the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to intermediate facilities (i.e., satellites), whereas the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We propose two pathbased mathematical formulations for our problem: (1) in one formulation, paths are defined over both first- and second-echelon tours, and (2) in the other one, the first- and second-echelon paths are decomposed. Branch-and-price-based algorithms are developed for both formulations. We compare both formulations and solution methods on a comprehensive set of instances and are able to solve instances up to five satellites and 100 customers to optimality. This paper is the first paper in the literature that solves such large instance sizes.

Original languageEnglish
Pages (from-to)463-479
Number of pages17
JournalTransportation Science
Volume53
Issue number2
DOIs
Publication statusPublished - 1 Mar 2019

Keywords

  • branch-and-price
  • column generation
  • two-echelon vehicle routing problem with time windows

Fingerprint

Dive into the research topics of 'Branch-and-price-based algorithms for the two-echelon vehicle routing problem with time windows'. Together they form a unique fingerprint.

Cite this