Solving an urban routing problem using heuristics: A successful case study

Practical routing problems involving the distribution or collection of products, services or persons which are distributed along city streets are very common. In this case, taking a network that corresponds to the city streets, the design of efficient routes consists of finding a set of minimal cost cycles, each passing through the domicile, satisfying all arc demands without exceeding the capacity limit of each vehicle as well as other practical constraints such as turn duration, etc. This kind of optimization problem is very closely related to the Capacitated Arc Routing Problem (CARP). Due to the computational complexity of the problem, there is a need to use heuristic procedures which make that good solutions in an acceptable computational time may be obtained. In this paper a comparison of heuristics to solve the CARP and a real case study of routing of municipal sanitation trucks with a conveniently improved heuristic are presented.