|
GENERAL ARC ROUTING PROBLEMS SOLVED BY A CUTTING PLANE ALGORITHM AND A GENETIC ALGORITHM
P. Lacomme(1), C. Prins(2), W. Ramdane-Chérif(2)
(1) University Blaise Pascal, Laboratory for Computer Science (LIMOS)
Campus Universitaire des Cézeaux, 63177 Aubière Cedex, France
Mail: lacomme@sp.isima.fr
(2) University of Technology of Troyes, Laboratory for Optimization of Industrial Systems
12 Rue Marie Curie, BP 2060, 10010 Troyes Cedex, France
Mail: {prins, ramdane}@utt.fr
This paper considers an extended version of the Capacitated Arc Routing Problem (E-CARP), obtained by adding realistic constraints like prohibited turns to the basic CARP. Two integer linear models are presented, a mono-objective version and a bi-objective one. A cutting plane method for the first version provides either an optimum or a lower bound that are used to benchmark a genetic algorithm on 11 CARP instances from the literature, enriched by additional constraints. The results prove that the GA is nearly optimal for these networks with up to 16 nodes and 52 arcs.
Keywords: transportation, linear programming, arc routing, genetic algorithm
Session slot T-Th-E21: Posters of Transportation and Vehicles/Area code 8e : Transportation Systems
 | 