The Directed Rural Postman Problem with Turn Penalties

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.