IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v238y2014i3p760-773.html
   My bibliography  Save this article

New results for the Directed Profitable Rural Postman Problem

Author

Listed:
  • Colombi, Marco
  • Mansini, Renata

Abstract

We study a generalization of the Directed Rural Postman Problem where not all arcs requiring a service have to be visited provided that a penalty cost is paid if a service arc is not crossed. The problem, known as Directed Profitable Rural Postman Problem, looks for a tour visiting the selected set of service arcs while minimizing both traveling and penalty costs. We add different valid inequalities to a known mathematical formulation of the problem and develop a branch-and-cut algorithm that introduces connectivity constraints both in a “lazy” and in a standard way. We also propose a matheuristic followed by an improvement heuristic (final refinement). The matheuristic exploits information provided by a problem relaxation to select promising service arcs used to solve optimally Directed Rural Postman problems. The ex-post refinement tries to improve the solution provided by the matheuristic using a branch-and-cut algorithm. The method gets a quick convergence through the introduction of connectivity cuts that are not guaranteed to be valid inequalities, and thus may exclude integer feasible solutions.

Suggested Citation

  • Colombi, Marco & Mansini, Renata, 2014. "New results for the Directed Profitable Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 760-773.
  • Handle: RePEc:eee:ejores:v:238:y:2014:i:3:p:760-773
    DOI: 10.1016/j.ejor.2014.05.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714004135
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2014.05.006?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gianfranco Guastaroba & Renata Mansini & M Grazia Speranza, 2009. "Modeling the Pre Auction Stage The Truckload Case," Lecture Notes in Economics and Mathematical Systems, in: Jo A.E.E. Nunen & M. Grazia Speranza & Luca Bertazzi (ed.), Innovations in Distribution Logistics, chapter 11, pages 219-233, Springer.
    2. H. A. Eiselt & Michel Gendreau & Gilbert Laporte, 1995. "Arc Routing Problems, Part II: The Rural Postman Problem," Operations Research, INFORMS, vol. 43(3), pages 399-414, June.
    3. Michael O. Ball & Michael J. Magazine, 1988. "Sequencing of Insertions in Printed Circuit Board Assembly," Operations Research, INFORMS, vol. 36(2), pages 192-201, April.
    4. Ángel Corberán & Elena Fernández & Carles Franquesa & José María Sanchis, 2011. "The Windy Clustered Prize-Collecting Arc-Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 317-334, August.
    5. Deitch, Ray & Ladany, Shaul P., 2000. "The one-period bus touring problem: Solved by an effective heuristic for the orienteering tour problem and improvement algorithm," European Journal of Operational Research, Elsevier, vol. 127(1), pages 69-77, November.
    6. Elena Fernández & Oscar Meza & Robert Garfinkel & Maruja Ortega, 2003. "On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation," Operations Research, INFORMS, vol. 51(2), pages 281-291, April.
    7. Malandraki, Chryssi & Daskin, Mark S., 1993. "The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 65(2), pages 218-234, March.
    8. Aráoz, Julián & Fernández, Elena & Meza, Oscar, 2009. "Solving the Prize-collecting Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 886-896, August.
    9. Côté, Jean-François & Potvin, Jean-Yves, 2009. "A tabu search heuristic for the vehicle routing problem with private fleet and common carrier," European Journal of Operational Research, Elsevier, vol. 198(2), pages 464-469, October.
    10. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    11. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm," Transportation Science, INFORMS, vol. 39(4), pages 539-552, November.
    12. Chu, Ching-Wu, 2005. "A heuristic algorithm for the truckload and less-than-truckload problem," European Journal of Operational Research, Elsevier, vol. 165(3), pages 657-667, September.
    13. H. A. Eiselt & Michel Gendreau & Gilbert Laporte, 1995. "Arc Routing Problems, Part I: The Chinese Postman Problem," Operations Research, INFORMS, vol. 43(2), pages 231-242, April.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Ávila, Thais & Corberán, Ángel & Plana, Isaac & Sanchis, José M., 2016. "A branch-and-cut algorithm for the profitable windy rural postman problem," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1092-1101.
    2. Colombi, Marco & Corberán, Ángel & Mansini, Renata & Plana, Isaac & Sanchis, José M., 2017. "The directed profitable rural postman problem with incompatibility constraints," European Journal of Operational Research, Elsevier, vol. 261(2), pages 549-562.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Archetti, Claudia & Bertazzi, Luca & Laganà, Demetrio & Vocaturo, Francesca, 2017. "The Undirected Capacitated General Routing Problem with Profits," European Journal of Operational Research, Elsevier, vol. 257(3), pages 822-833.
    2. Ávila, Thais & Corberán, Ángel & Plana, Isaac & Sanchis, José M., 2016. "A branch-and-cut algorithm for the profitable windy rural postman problem," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1092-1101.
    3. Colombi, Marco & Corberán, Ángel & Mansini, Renata & Plana, Isaac & Sanchis, José M., 2017. "The directed profitable rural postman problem with incompatibility constraints," European Journal of Operational Research, Elsevier, vol. 261(2), pages 549-562.
    4. Arbib, Claudio & Servilio, Mara & Archetti, Claudia & Speranza, M. Grazia, 2014. "The directed profitable location Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 811-819.
    5. Enrique Benavent & Ángel Corberán & Luís Gouveia & Maria Mourão & Leonor Pinto, 2015. "Profitable mixed capacitated arc routing and related problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(1), pages 244-274, April.
    6. Kasaei, Maziar & Salman, F. Sibel, 2016. "Arc routing problems to restore connectivity of a road network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 177-206.
    7. Claudia Archetti & M. Grazia Speranza & Ángel Corberán & José M. Sanchis & Isaac Plana, 2014. "The Team Orienteering Arc Routing Problem," Transportation Science, INFORMS, vol. 48(3), pages 442-457, August.
    8. Angel Corberán & Gustavo Mejía & José M. Sanchis, 2005. "New Results on the Mixed General Routing Problem," Operations Research, INFORMS, vol. 53(2), pages 363-376, April.
    9. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    10. Aráoz, Julián & Fernández, Elena & Meza, Oscar, 2009. "Solving the Prize-collecting Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 886-896, August.
    11. Julián Aráoz & Elena Fernández & Carles Franquesa, 2009. "The Clustered Prize-Collecting Arc Routing Problem," Transportation Science, INFORMS, vol. 43(3), pages 287-300, August.
    12. Dewil, R. & Vansteenwegen, P. & Cattrysse, D. & Van Oudheusden, D., 2015. "A minimum cost network flow model for the maximum covering and patrol routing problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 27-36.
    13. Elena Fernández & Jessica Rodríguez-Pereira, 2017. "Multi-depot rural postman problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 340-372, July.
    14. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm," Transportation Science, INFORMS, vol. 39(4), pages 539-552, November.
    15. Timo Hintsch & Stefan Irnich & Lone Kiilerich, 2021. "Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem," Transportation Science, INFORMS, vol. 55(3), pages 687-705, May.
    16. Souffriau, Wouter & Vansteenwegen, Pieter & Vanden Berghe, Greet & Van Oudheusden, Dirk, 2011. "The planning of cycle trips in the province of East Flanders," Omega, Elsevier, vol. 39(2), pages 209-213, April.
    17. Summerfield, Nichalin S. & Dror, Moshe & Cohen, Morris A., 2015. "City streets parking enforcement inspection decisions: The Chinese postman’s perspective," European Journal of Operational Research, Elsevier, vol. 242(1), pages 149-160.
    18. Elena Fernández & Gilbert Laporte & Jessica Rodríguez-Pereira, 2018. "A Branch-and-Cut Algorithm for the Multidepot Rural Postman Problem," Transportation Science, INFORMS, vol. 52(2), pages 353-369, March.
    19. Akbari, Vahid & Salman, F. Sibel, 2017. "Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity," European Journal of Operational Research, Elsevier, vol. 257(2), pages 625-640.
    20. Barbara De Rosa & Gennaro Improta & Gianpaolo Ghiani & Roberto Musmanno, 2002. "The Arc Routing and Scheduling Problem with Transshipment," Transportation Science, INFORMS, vol. 36(3), pages 301-313, August.

    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:eee:ejores:v:238:y:2014:i:3:p:760-773. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.