Exact methods based on node-routing formulations for undirected arc-routing problems

Exact methods based on node-routing formulations for undirected arc-routing problems

0.00 Avg rating0 Votes
Article ID: iaor2007377
Country: United States
Volume: 47
Issue: 1
Start Page Number: 52
End Page Number: 60
Publication Date: Jan 2006
Journal: Networks
Authors: ,
Keywords: programming: branch and bound
Abstract:

This article proposes a new transformation of undirected arc-routing problems into equivalent node-routing problems, with emphasis on the transformation of Capacitated Arc Routing Problems (CARP) into Capacitated Vehicle Routing Problems (CVRP). For this last case, an analogue transformation has already been proposed in Pearn et al., where each required CARP edge is mapped onto a triplet of CVRP nodes. In our case, only two CVRP nodes are needed for every CARP required edge. The transformed instances have a structure and a dimension that make most CARP benchmarks solvable by state of the art CVRP techniques. We thus propose a general purpose transformation of arc into node-routing problems and new results on lower bounds and exact methods for CARP instances.

Reviews

Required fields are marked *. Your email address will not be published.