The directed rural postman problem with turn penalties

The directed rural postman problem with turn penalties

0.00 Avg rating0 Votes
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: ,
Keywords: programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.