The Directed Rural Postman Problem with Turn Penalties

Enrique Benavent and David Soler
Additional contact information
Enrique Benavent: Departamento de Estadística e Investigación Operativa, Universitat de Valencia, Dr. Moliner 50, 46100 Burjassot, Valencia, Spain
David Soler: Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, Camino de Vera 15, 46022 Benimaclet, Valencia, Spain

Transportation Science, 1999, vol. 33, issue 4, 408-418

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.

Date: 1999
References: View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.33.4.408 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:33:y:1999:i:4:p:408-418

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().