TY - JOUR
T1 - Branch-price-and-cut for the Mixed Capacitated General Routing Problem with Time Windows
AU - Ciancio, Claudio
AU - Laganá, Demetrio
AU - Vocaturo, Francesca
PY - 2018/5/16
Y1 - 2018/5/16
N2 - 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.
AB - 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.
KW - Column generation
KW - General routing problem
KW - Graph transformation
KW - Integer programming
UR - http://www.scopus.com/inward/record.url?scp=85037043858&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85037043858&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2017.11.039
DO - 10.1016/j.ejor.2017.11.039
M3 - Article
AN - SCOPUS:85037043858
VL - 267
SP - 187
EP - 199
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -