IMADA - Department of Mathematics and Computer Science |
The Capacitated Arc Routing Problem (CARP) is a routing problem with applications in street sweeping, mail delivery etc. It is the problem of servicing a set of edges in a graph using a fleet of capacity constrained vehicles. The presentation will be in three parts. I will talk about an online version of CARP, and present dynamic programming algorithms that can be used to solve that online problem offline. Next I will show how these algorithms can be used in a Simulated Annealing setup to give good upper bounds for CARP. Finally I will present a new lower bound for CARP, called the Multiple Cuts Node Duplication Lower Bound. Host: Joan Boyar
SDU HOME | IMADA HOME | Previous Page Last modified: September 23, 2003. Joan Boyar (joan@imada.sdu.dk) |