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

The mixed capacitated arc routing problem with non-overlapping routes

Author

Listed:
  • Constantino, Miguel
  • Gouveia, Luís
  • Mourão, Maria Cândida
  • Nunes, Ana Catarina

Abstract

Real world applications for vehicle collection or delivery along streets usually lead to arc routing problems, with additional and complicating constraints. In this paper we focus on arc routing with an additional constraint to identify vehicle service routes with a limited number of shared nodes, i.e. vehicle service routes with a limited number of intersections. This constraint leads to solutions that are better shaped for real application purposes. We propose a new problem, the bounded overlapping MCARP (BCARP), which is defined as the mixed capacitated arc routing problem (MCARP) with an additional constraint imposing an upper bound on the number of nodes that are common to different routes. The best feasible upper bound is obtained from a modified MCARP in which the minimization criteria is given by the overlapping of the routes. We show how to compute this bound by solving a simpler problem. To obtain feasible solutions for the bigger instances of the BCARP heuristics are also proposed. Computational results taken from two well known instance sets show that, with only a small increase in total time traveled, the model BCARP produces solutions that are more attractive to implement in practice than those produced by the MCARP model.

Suggested Citation

  • Constantino, Miguel & Gouveia, Luís & Mourão, Maria Cândida & Nunes, Ana Catarina, 2015. "The mixed capacitated arc routing problem with non-overlapping routes," European Journal of Operational Research, Elsevier, vol. 244(2), pages 445-456.
  • Handle: RePEc:eee:ejores:v:244:y:2015:i:2:p:445-456
    DOI: 10.1016/j.ejor.2015.01.042
    as

    Download full text from publisher

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

    File URL: https://libkey.io/10.1016/j.ejor.2015.01.042?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. A Poot & G Kant & A P M Wagelmans, 2002. "A savings based method for real-life vehicle routing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(1), pages 57-68, January.
    2. Perrier, Nathalie & Langevin, André & Campbell, James F., 2008. "The sector design and assignment problem for snow disposal operations," European Journal of Operational Research, Elsevier, vol. 189(2), pages 508-525, September.
    3. Muyldermans, L. & Cattrysse, D. & Van Oudheusden, D. & Lotan, T., 2002. "Districting for salt spreading operations," European Journal of Operational Research, Elsevier, vol. 139(3), pages 521-532, June.
    4. Bozkaya, Burcin & Erkut, Erhan & Laporte, Gilbert, 2003. "A tabu search heuristic and adaptive memory procedure for political districting," European Journal of Operational Research, Elsevier, vol. 144(1), pages 12-26, January.
    5. M. Salazar-Aguilar & Roger Ríos-Mercado & José González-Velarde & Julián Molina, 2012. "Multiobjective scatter search for a commercial territory design problem," Annals of Operations Research, Springer, vol. 199(1), pages 343-360, October.
    6. L Muyldermans & D Cattrysse & D Van Oudheusden, 2003. "District design for arc-routing applications," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(11), pages 1209-1221, November.
    7. Mourgaya, M. & Vanderbeck, F., 2007. "Column generation based heuristic for tactical planning in multi-period vehicle routing," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1028-1041, December.
    8. Teixeira, Joao & Antunes, Antonio Pais & de Sousa, Jorge Pinho, 2004. "Recyclable waste collection planning--a case study," European Journal of Operational Research, Elsevier, vol. 158(3), pages 543-554, November.
    9. Mourão, Maria Cândida & Nunes, Ana Catarina & Prins, Christian, 2009. "Heuristic methods for the sectoring arc routing problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 856-868, August.
    10. T R P Ramos & R C Oliveira, 2011. "Delimitation of service areas in reverse logistics networks with multiple depots," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1198-1210, July.
    11. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, December.
    12. Mourao, Maria Candida & Amado, Ligia, 2005. "Heuristic method for a mixed capacitated arc routing problem: A refuse collection application," European Journal of Operational Research, Elsevier, vol. 160(1), pages 139-153, January.
    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. 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.
    2. Oliver Lum & Bruce Golden & Edward Wasil, 2018. "An Open-Source Desktop Application for Generating Arc-Routing Benchmark Instances," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 361-370, May.
    3. Jens Van Engeland & Jeroen Beliën, 2021. "Tactical waste collection: column generation and mixed integer programming based heuristics," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 89-126, March.
    4. Cortinhal, Maria João & Mourão, Maria Cândida & Nunes, Ana Catarina, 2016. "Local search heuristics for sectoring routing in a household waste collection context," European Journal of Operational Research, Elsevier, vol. 255(1), pages 68-79.

    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. Cortinhal, Maria João & Mourão, Maria Cândida & Nunes, Ana Catarina, 2016. "Local search heuristics for sectoring routing in a household waste collection context," European Journal of Operational Research, Elsevier, vol. 255(1), pages 68-79.
    2. Alexander Butsch & Jörg Kalcsics & Gilbert Laporte, 2014. "Districting for Arc Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 809-824, November.
    3. T R P Ramos & R C Oliveira, 2011. "Delimitation of service areas in reverse logistics networks with multiple depots," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1198-1210, July.
    4. Mourão, Maria Cândida & Nunes, Ana Catarina & Prins, Christian, 2009. "Heuristic methods for the sectoring arc routing problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 856-868, August.
    5. Rui Fragoso & Conceição Rego & Vladimir Bushenkov, 2016. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," Journal of Quantitative Economics, Springer;The Indian Econometric Society (TIES), vol. 14(2), pages 179-198, December.
    6. Steiner, Maria Teresinha Arns & Datta, Dilip & Steiner Neto, Pedro José & Scarpin, Cassius Tadeu & Rui Figueira, José, 2015. "Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil," Omega, Elsevier, vol. 52(C), pages 53-64.
    7. Rodríguez-Martín, Inmaculada & Salazar-González, Juan-José & Yaman, Hande, 2019. "The periodic vehicle routing problem with driver consistency," European Journal of Operational Research, Elsevier, vol. 273(2), pages 575-584.
    8. Perrier, Nathalie & Langevin, André & Campbell, James F., 2008. "The sector design and assignment problem for snow disposal operations," European Journal of Operational Research, Elsevier, vol. 189(2), pages 508-525, September.
    9. Antonio Diglio & Stefan Nickel & Francisco Saldanha-da-Gama, 2020. "Towards a stochastic programming modeling framework for districting," Annals of Operations Research, Springer, vol. 292(1), pages 249-285, September.
    10. 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.
    11. Juan A. Díaz & Dolores E. Luna, 2017. "Primal and dual bounds for the vertex p-median problem with balance constraints," Annals of Operations Research, Springer, vol. 258(2), pages 613-638, November.
    12. Camacho-Collados, M. & Liberatore, F. & Angulo, J.M., 2015. "A multi-criteria Police Districting Problem for the efficient and effective design of patrol sector," European Journal of Operational Research, Elsevier, vol. 246(2), pages 674-684.
    13. Sebastián Moreno & Jordi Pereira & Wilfredo Yushimito, 2020. "A hybrid K-means and integer programming method for commercial territory design: a case study in meat distribution," Annals of Operations Research, Springer, vol. 286(1), pages 87-117, March.
    14. Bogh, Morten Bie & Mikkelsen, Hardy & Wøhlk, Sanne, 2014. "Collection of recyclables from cubes – A case study," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 127-134.
    15. Maria da Conceição Rego & Rui Fragoso & Vladimir Bushenkov, 2014. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," ERSA conference papers ersa14p218, European Regional Science Association.
    16. Rodríguez-Martín, Inmaculada & Yaman, Hande, 2022. "Periodic Vehicle Routing Problem with Driver Consistency and service time optimization," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 468-484.
    17. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    18. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Assessing and improving management practices when planning packaging waste collection systems," Resources, Conservation & Recycling, Elsevier, vol. 85(C), pages 116-129.
    19. Fernando Tavares-Pereira & José Figueira & Vincent Mousseau & Bernard Roy, 2007. "Multiple criteria districting problems," Annals of Operations Research, Springer, vol. 154(1), pages 69-92, October.
    20. Ouyang, Zhiyuan & Leung, Eric Ka Ho & Huang, George Q., 2022. "Community logistics for dynamic vehicle dispatching: The effects of community departure “time” and “space”," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).

    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:244:y:2015:i:2:p:445-456. 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.