Branch-price-and-cut for the Mixed Capacitated General Routing Problem with Time Windows

Claudio Ciancio, Demetrio Laganá*, Francesca Vocaturo

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The Mixed Capacitated General Routing Problem with Time Windows (MCGRPTW) is defined over a mixed graph, for which some nodes, arcs and edges have strictly positive demand and must be serviced. The problem consists of determining a set of least-cost vehicle routes that satisfy this requirement, while respecting pre-specified time windows and without exceeding the vehicle capacity. In this work, we transform the MCGRPTW into an equivalent node routing problem over a directed graph. Thus, we solve the equivalent problem by using a branch-price-and-cut algorithm which relies on some effective techniques introduced in the field. Computational experiments over instances derived from the Capacitated Arc Routing Problem with Time Windows and from the Mixed Capacitated General Routing Problem are presented. The article also describes experiments over benchmark instances.

Original languageEnglish
Pages (from-to)187-199
Number of pages13
JournalEuropean Journal of Operational Research
Volume267
Issue number1
DOIs
Publication statusPublished - 16 May 2018
Externally publishedYes

Keywords

  • Column generation
  • General routing problem
  • Graph transformation
  • Integer programming

Fingerprint

Dive into the research topics of 'Branch-price-and-cut for the Mixed Capacitated General Routing Problem with Time Windows'. Together they form a unique fingerprint.

Cite this