IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v33y1999i4p408-418.html
   My bibliography  Save this article

The Directed Rural Postman Problem with Turn Penalties

Author

Listed:
  • 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)

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.

Suggested Citation

  • Enrique Benavent & David Soler, 1999. "The Directed Rural Postman Problem with Turn Penalties," Transportation Science, INFORMS, vol. 33(4), pages 408-418, November.
    • Handle: RePEc:inm:ortrsc:v:33:y:1999:i:4:p:408-418
    DOI: 10.1287/trsc.33.4.408
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.33.4.408
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.33.4.408?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Cerrone, Carmine & Dussault, Benjamin & Wang, Xingyin & Golden, Bruce & Wasil, Edward, 2019. "A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties," European Journal of Operational Research, Elsevier, vol. 272(2), pages 754-765.
    2. Vasco Barbosa & Inés Santé-Riveira & Rafael Crecente-Maseda & Carlos Díaz Redondo & Juan Porta Trinidad & Jorge Parapar López & Ramón Doallo Biempica & José Ambrósio Ferreira Neto, 2022. "A New Spatial Criteria Method to Delimit Rural Settlements towards Boundaries Equity: Land Use Optimization for Decision Making in Galicia, NW Spain," Land, MDPI, vol. 11(6), pages 1-19, May.
    3. Irnich, Stefan, 2008. "Solution of real-world postman problems," European Journal of Operational Research, Elsevier, vol. 190(1), pages 52-67, October.
    4. Lacomme, Philippe & Prins, Christian & Ramdane-Cherif, Wahiba, 2005. "Evolutionary algorithms for periodic arc routing problems," European Journal of Operational Research, Elsevier, vol. 165(2), pages 535-553, September.
    5. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    6. Thibaut Vidal, 2017. "Node, Edge, Arc Routing and Turn Penalties: Multiple Problems—One Neighborhood Extension," Operations Research, INFORMS, vol. 65(4), pages 992-1010, August.
    7. Kaj Holmberg, 2019. "The (Over)zealous Snow Remover Problem," Transportation Science, INFORMS, vol. 53(3), pages 867-881, May.
    8. Debdatta Sinha Roy & Adriano Masone & Bruce Golden & Edward Wasil, 2021. "Modeling and Solving the Intersection Inspection Rural Postman Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1245-1257, July.
    9. Nathalie Perrier & André Langevin & Ciro-Alberto Amaya, 2008. "Vehicle Routing for Urban Snow Plowing Operations," Transportation Science, INFORMS, vol. 42(1), pages 44-56, February.
    10. Eliécer Gutiérrez & Andrés Medaglia, 2008. "Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks," Annals of Operations Research, Springer, vol. 157(1), pages 169-182, January.
    11. Albiach, José & Sanchis, José Marí­a & Soler, David, 2008. "An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation," European Journal of Operational Research, Elsevier, vol. 189(3), pages 789-802, September.
    12. D Soler & E Martínez & J C Micó, 2008. "A transformation for the mixed general routing problem with turn penalties," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(4), pages 540-547, April.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:33:y:1999:i:4:p:408-418. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.