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

GABRIEL EUGENIO GUTIERREZ JARPA, Guy Desaulniers, Gilbert Laporte, Vladimir Marianov

Research output: Contribution to journalArticlepeer-review

69 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

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