A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows

Gabriel Gutiérrez-Jarpa, Guy Desaulniers, Gilbert Laporte, Vladimir Marianov

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

Abstract

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.

Original languageEnglish
Pages (from-to)341-349
Number of pages9
JournalEuropean Journal of Operational Research
Volume206
Issue number2
DOIs
StatePublished - 16 Oct 2010
Externally publishedYes

Keywords

  • Branch-and-price
  • Deliveries and selective pickups
  • Shortest paths with resources
  • Time windows
  • Transportation
  • Vehicle routing

Fingerprint

Dive into the research topics of 'A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows'. Together they form a unique fingerprint.

Cite this