Article ID: | iaor20031360 |
Country: | Netherlands |
Volume: | 44 |
Issue: | 2 |
Start Page Number: | 249 |
End Page Number: | 266 |
Publication Date: | Feb 2003 |
Journal: | Computers & Industrial Engineering |
Authors: | Greistorfer Peter |
Keywords: | tabu search, postman problem |
We consider a special routing problem which has a variety of practical applications. In a graph-theoretic context it is known as the capacitated Chinese postman problem. Given an undirected network in which the demand is located on edges, the goal is to determine a least-cost schedule of routes. The route demands, which must not exceed the vehicle capacity, are serviced by a fleet of vehicles which is located at a single depot node. We present a metaheuristic based on a tabu search procedure that makes use of the scatter search paradigm. The computational results indicate that the algorithms proposed can keep up with other arc routing heuristics.