Can I read A tabu search algorithm for the min–max k-Chinese postman problem on EtoBox?

A tabu search algorithm for the min–max k-Chinese postman problem by Dino Ahr; Gerhard Reinelt is a Engineering article available to read on EtoBox.

What is A tabu search algorithm for the min–max k-Chinese postman problem about?

In this paper we present a tabu search algorithm for the min-max k-Chinese postman problem (MM k-CPP). Given an undirected edge-weighted graph and a distinguished depot node, the MM k-CPP consists of finding k > 1 tours (starting and ending at the depot node) such that each edge is traversed by at least one tour and the length of the longest tour is minimized. A special emphasis is put on investigating the trade-off between running time effort and solution quality when applying different improvement procedures in the course of the neighborhood construction. Furthermore, different neighborhoods are analyzed. Extensive computational results show that the tabu search algorithm outperforms all known heuristics and improvement procedures. Scope and purpose Given a road network, the Chinese postman problem (CPP) is to find the shortest postman tour covering all the roads in the network. Applications of the CPP include road maintenance, garbage collection, mail delivery, etc. Since usually large road networks have to be serviced the work load must be distributed among k 2 vehicles. In contrast to the usual objective to minimize the total distance traveled by the k vehicles (k-CPP), for th

Who reads A tabu search algorithm for the min–max k-Chinese postman problem?

Author

Dino Ahr; Gerhard Reinelt

Publisher

Elsevier Science; Elsevier ; Elsevier Ltd.; Elsevier BV (ISSN 0305-0548)

Published

2006

Language

EN

Field

Engineering (Physical Sciences)