6533b839fe1ef96bd12a65f5

RESEARCH PRODUCT

Lower and upper bounds for the mixed capacitated arc routing problem

Philippe LacommeJosé-manuel BelenguerChristian PrinsEnrique Benavent

subject

Mathematical optimizationLower boundGeneral Computer Science0211 other engineering and technologiesMixed graphHeuristic02 engineering and technologyManagement Science and Operations ResearchUpper and lower boundsBounding overwatchMixed graph0502 economics and businessCapacitated arc routing problemConstructive heuristicMathematics050210 logistics & transportation021103 operations researchWaste collectionHeuristic05 social sciencesMemetic algorithm[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]Cutting plane[INFO.INFO-MO]Computer Science [cs]/Modeling and SimulationModeling and SimulationMemetic algorithmArc routingCutting-plane method

description

This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem (MCARP). Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively.

yearjournalcountryeditionlanguage
2006-12-01
10.1016/j.cor.2005.02.009https://hal.science/hal-00119777