IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v23y2015i1p244-274.html
   My bibliography  Save this article

Profitable mixed capacitated arc routing and related problems

Author

Listed:
  • Enrique Benavent
  • Ángel Corberán
  • Luís Gouveia
  • Maria Mourão
  • Leonor Pinto

Abstract

Mixed capacitated arc routing problems aim to identify a set of vehicle tours that, starting and ending at a depot node, serve a given number of links at minimum cost, while satisfying the vehicles capacity. If both profits and costs on arcs are considered, we may define the profitable mixed capacitated arc routing problem (PMCARP). In this paper we present compact flow-based models for the PMCARP, where two types of services are tackled, mandatory and optional. Adaptations of the models to fit into some other related problems are also proposed. The models are evaluated, according to their bounds quality as well as to the CPU times, over large sets of test instances. New instances have been created for some variants that have been introduced here for the first time. Results show the new models performance within CPLEX and compare, whenever available, the proposed models against other resolution methods. Copyright Sociedad de Estadística e Investigación Operativa 2015

Suggested Citation

  • 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.
    • Handle: RePEc:spr:topjnl:v:23:y:2015:i:1:p:244-274
    DOI: 10.1007/s11750-014-0336-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11750-014-0336-x
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11750-014-0336-x?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. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    2. Degraeve, Zeger & Gochet, Willy & Jans, Raf, 2002. "Alternative formulations for a layout problem in the fashion industry," European Journal of Operational Research, Elsevier, vol. 143(1), pages 80-93, November.
    3. 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.
    4. Alain Hertz & Gilbert Laporte & Pierrette Nanchen Hugo, 1999. "Improvement Procedures for the Undirected Rural Postman Problem," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 53-62, February.
    5. Zachariadis, E.E. & Kiranoudis, C.T., 2011. "Local search for the undirected capacitated arc routing problem with profits," European Journal of Operational Research, Elsevier, vol. 210(2), pages 358-367, April.
    6. Dorit S. Hochbaum & Eli V. Olinick, 2001. "The Bounded Cycle-Cover Problem," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 104-119, May.
    7. 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.
    8. 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.
    9. 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.
    10. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    11. 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.
    12. Stenger, A. & Schneider, M. & Goeke, D., 2013. "The Prize-Collecting Vehicle Routing Problem with Single and Multiple Depots and Non-Linear Cost," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62372, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    13. Pearn, W. L. & Wang, K. H., 2003. "On the Maximum Benefit Chinese Postman Problem," Omega, Elsevier, vol. 31(4), pages 269-273, August.
    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. Ferreira, Reinaldo & Móra, Vasco & Mourão, Maria Cândida & Moz, Margarida & Pinto, Leonor S. & Ribeiro, João, 2022. "Arc Routing for Parking Enforcement Officers: Exact and heuristic solutions," European Journal of Operational Research, Elsevier, vol. 299(1), pages 283-301.
    3. 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.

    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. Á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.
    3. 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.
    4. 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.
    5. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    6. 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.
    7. Ruiz-Meza, José & Montoya-Torres, Jairo R., 2022. "A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines," Operations Research Perspectives, Elsevier, vol. 9(C).
    8. Archetti, Claudia & Corberán, Ángel & Plana, Isaac & Sanchis, José Maria & Speranza, M. Grazia, 2015. "A matheuristic for the Team Orienteering Arc Routing Problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 392-401.
    9. Claudia Archetti & Natashia Boland & Grazia Speranza, 2017. "A Matheuristic for the Multivehicle Inventory Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 377-387, August.
    10. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2014. "Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 103-120, February.
    11. 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.
    12. Oruc, Buse Eylul & Kara, Bahar Yetis, 2018. "Post-disaster assessment routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 76-102.
    13. Riera-Ledesma, Jorge & Salazar-González, Juan José, 2017. "Solving the Team Orienteering Arc Routing Problem with a column generation approach," European Journal of Operational Research, Elsevier, vol. 262(1), pages 14-27.
    14. Dang, Duc-Cuong & Guibadj, Rym Nesrine & Moukrim, Aziz, 2013. "An effective PSO-inspired algorithm for the team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 332-344.
    15. 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.
    16. Akhundov, Najmaddin & Ostrowski, James, 2024. "Exploiting symmetry for the job sequencing and tool switching problem," European Journal of Operational Research, Elsevier, vol. 316(3), pages 976-987.
    17. Á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.
    18. Dang, Quang-Vinh & van Diessen, Thijs & Martagan, Tugce & Adan, Ivo, 2021. "A matheuristic for parallel machine scheduling with tool replacements," European Journal of Operational Research, Elsevier, vol. 291(2), pages 640-660.
    19. 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.
    20. Dontas, Michael & Sideris, Georgios & Manousakis, Eleftherios G. & Zachariadis, Emmanouil E., 2023. "An adaptive memory matheuristic for the set orienteering problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1010-1023.

    More about this item

    Keywords

    Routing; Arc routing problems; Profits; Flow-based models; 90B10;
    All these keywords.

    JEL classification:

    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:spr:topjnl:v:23:y:2015:i:1:p:244-274. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.