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.

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

Ciancio C;Lagana' D;Vocaturo F
2018-01-01

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.
2018
General routing problem; Graph transformation; Integer programming; Column generation
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/269191
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 21
social impact