A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties |
| |
| Authors: | Carmine Cerrone Benjamin Dussault Xingyin Wang Bruce Golden Edward Wasil |
| |
| Affiliation: | 1. Department of Biosciences and Territory, University of Molise, Italy;2. End-to-End Analytics, LLC, Palo Alto, CA, USA;3. Engineering Systems and Design, Singapore University of Technology and Design, Singapore;4. Robert H. Smith School of Business, University of Maryland, USA;5. Kogod School of Business, American University, USA |
| |
| Abstract: | In this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time. |
| |
| Keywords: | Routing Heuristics Greedy algorithm Rural postman problem Turn penalties |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
