6533b86ffe1ef96bd12cdb4d

RESEARCH PRODUCT

The Capacitated Arc Routing Problem: Lower bounds

Enrique MotaVicente CamposÁNgel CorberánEnrique Benavent

subject

Dynamic programmingMathematical optimizationComputer Networks and CommunicationsHardware and ArchitectureTotal costAlgorithmArc routingSoftwareGraphInformation SystemsMathematics

description

In this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds are compared on a set of test problems, are included.

yearjournalcountryeditionlanguage
1992-12-01Networks
https://doi.org/10.1002/net.3230220706