6533b7dbfe1ef96bd127097c

RESEARCH PRODUCT

Two-phase branch-and-cut for the mixed capacitated general routing problem

Claudia SchlebuschDemetrio LaganàStefan IrnichFrancesca Vocaturo

subject

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceMixed graphManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringSet (abstract data type)Bounding overwatchModeling and SimulationBenchmark (computing)Destination-Sequenced Distance Vector routingRouting (electronic design automation)Integer programmingBranch and cutMathematics

description

The Mixed Capacitated General Routing Problem (MCGRP) is defined over a mixed graph, for which some vertices must be visited and some links must be traversed at least once. The problem consists of determining a set of least-cost vehicle routes that satisfy this requirement and respect the vehicle capacity. Few papers have been devoted to the MCGRP, in spite of interesting real-world applications, prevalent in school bus routing, mail delivery, and waste collection. This paper presents a new mathematical model for the MCGRP based on two-index variables. The approach proposed for the solution is a two-phase branch-and-cut algorithm, which uses an aggregate formulation to develop an effective lower bounding procedure. This procedure also provides strong valid inequalities for the two-index model. Extensive computational experiments over benchmark instances are presented.

yearjournalcountryeditionlanguage
2015-05-01European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2014.11.005