Networks · 1992 · 160 citations · 18 references
Natural SciencesIndustrial EngineeringCapacity PlanningOptimizationTransportationCombinatorial OptimizationDynamic ProgrammingNetwork OptimizationRoutingRouting AlgorithmsTransportation ProblemsLower BoundsRouting ProblemsTotal Cost Minimization
Abstract 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.
18
Complexity of vehicle routing and scheduling problems
Jan Karel Lenstra, A. H. G. Rinnooy Kan · Networks · 1981 · 1.3K citations
Routing and scheduling of vehicles and crews
Samuel J. Raff · Computers & Operations Research · 1983 · 862 citations
Capacitated arc routing problems
Bruce Golden, Richard T. Wong · Networks · 1981 · 568 citations