In this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution to the DRPP-TP is a tour that traverses all required arcs of the graph. The cost of the solution is the sum of the lengths of the traversed arcs plus the penalties associated with the turns made at the nodes. The DRPP-TP arises from real-world applications. For example, truck drivers prefer going straight as far as they can because turning left or even right can be dangerous and time consuming. U-turns are not possible for long trucks.
One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach without graph transformation has been proposed in the literature. The direct approach has two stages. First, the turn penalties are ignored and the problem is solved as a rural postman problem to obtain an Eulerian graph. Second, an end-pairing algorithm is used to generate an Eulerian tour taking the penalties of the turns into consideration. The first part of our paper investigates the applicability of the direct approach. We identify several characteristics of the input instances that make this approach effective and present several limitations of this approach.
In the second part of this paper, we improve the direct approach using an integer linear program in the first stage and a local search algorithm in the second stage to solve the DRPP-TP. This combination produces high-quality solutions in a reasonable amount of computing time.
| Subject : | : | Abstracts |
| Topics | : | Heuristics |
| Keywords | : | Arc routing ; Heuristic ; Greedy algorithm ; Rural postman problem ; Turn penalties |
| PDF version | : |  PDF version |
