Article ID: | iaor2001979 |
Country: | United States |
Volume: | 33 |
Issue: | 4 |
Start Page Number: | 408 |
End Page Number: | 418 |
Publication Date: | Nov 1999 |
Journal: | Transportation Science |
Authors: | Benavent Enrique, Soler David |
Keywords: | programming: travelling salesman |
In this paper, we introduce a generalization of the directed rural postman problem including new features that can be encountered in practice when routes have to be operated on a street network: some turns are forbidden and other turns are allowed but with some penalties. This new problem is called the directed rural postman problem with turn penalties (DRPP-TP); we present some complexity results and three heuristics for the DRPP-TP: two of them are constructive, whereas the third one is an improvement heuristic. We also present a transformation of the DRPP-TP into an asymmetric traveling salesman problem (ATSP) that allows us to solve the problem exactly using an existing ATSP code. Computational results on a set of instances with up to 180 nodes and 666 arcs are given.