IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v61y2010i7d10.1057_jors.2009.58.html
   My bibliography  Save this article

A heuristic method for the capacitated arc routing problem with refill points and multiple loads

Author

Listed:
  • C-A Amaya

    (Universidad de Los Andes)

  • A Langevin

    (École Polytechnique de Montréal)

  • M Trépanier

    (École Polytechnique de Montréal)

Abstract

We describe a solution procedure for a capacitated arc routing problem with refill points and multiple loads. This problem stems from the road network marking in Quebec, Canada. Two different types of vehicles are used: the first type (called servicing vehicle—SV) with a finite capacity to service the arcs and the other (called refilling vehicle—RV) to refill the SV vehicle. The RV can deliver multiple loads, which means that it meets the SV several times before returning to the depot. The problem consists of simultaneously determining the vehicle routes that minimize the total cost of the two vehicles. We present an integer formulation and a route first-cluster second heuristic procedure. Computational results are provided.

Suggested Citation

  • C-A Amaya & A Langevin & M Trépanier, 2010. "A heuristic method for the capacitated arc routing problem with refill points and multiple loads," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1095-1103, July.
    • Handle: RePEc:pal:jorsoc:v:61:y:2010:i:7:d:10.1057_jors.2009.58
    DOI: 10.1057/jors.2009.58
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/jors.2009.58
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/jors.2009.58?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. Ulusoy, Gunduz, 1985. "The fleet size and mix problem for capacitated arc routing," European Journal of Operational Research, Elsevier, vol. 22(3), pages 329-337, December.
    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. Jesus Gonzalez-Feliu, 2013. "Multi-stage LTL transport systems in supply chain management," Post-Print halshs-00796714, HAL.
    2. repec:hal:wpaper:halshs-00796714 is not listed on IDEAS
    3. Hocke, Stephan & Gajewski, Christina & Kasper, Mathias, 2017. "A genetic algorithm for vehicle routing problems with temporal synchronization constraints," Discussion Papers 2/2017, Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics.
    4. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    5. Julian Hof & Michael Schneider, 2021. "Intraroute Resource Replenishment with Mobile Depots," Transportation Science, INFORMS, vol. 55(3), pages 660-686, May.
    6. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.

    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. Hashemi Doulabi, Seyed Hossein & Seifi, Abbas, 2013. "Lower and upper bounds for location-arc routing problems with vehicle capacity constraints," European Journal of Operational Research, Elsevier, vol. 224(1), pages 189-208.
    2. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    3. Richárd Ladányi, 2013. "Optimization Of Separated Household Waste Collection Systems On The Base Of Gis Modelling," Advanced Logistic systems, University of Miskolc, Department of Material Handling and Logistics, vol. 7(2), pages 49-56, December.
    4. Enrico Bartolini & Jean-François Cordeau & Gilbert Laporte, 2013. "An Exact Algorithm for the Capacitated Arc Routing Problem with Deadheading Demand," Operations Research, INFORMS, vol. 61(2), pages 315-327, April.
    5. 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.
    6. 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.
    7. Maria Cieśla & Piotr Nowakowski & Mariusz Wala, 2024. "The Impact of Variable Ambient Temperatures on the Energy Efficiency and Performance of Electric Vehicles during Waste Collection," Energies, MDPI, vol. 17(17), pages 1-21, August.
    8. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    9. Imran, Arif & Salhi, Said & Wassan, Niaz A., 2009. "A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 197(2), pages 509-518, September.
    10. Chen, Yuning & Hao, Jin-Kao & Glover, Fred, 2016. "A hybrid metaheuristic approach for the capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 253(1), pages 25-39.
    11. Alain Hertz & Gilbert Laporte & Michel Mittaz, 2000. "A Tabu Search Heuristic for the Capacitated arc Routing Problem," Operations Research, INFORMS, vol. 48(1), pages 129-135, February.
    12. 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.
    13. Porumbel, Daniel & Coelho, Igor M. & Talbi, El-Ghazali, 2024. "Using an exact bi-objective decoder in a memetic algorithm for arc-routing (and other decoder-expressible) problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 25-43.
    14. Zsuzsanna Nagy & Ágnes Werner-Stark & Tibor Dulai, 2022. "An Artificial Bee Colony Algorithm for Static and Dynamic Capacitated Arc Routing Problems," Mathematics, MDPI, vol. 10(13), pages 1-38, June.
    15. Santos, Luís & Coutinho-Rodrigues, João & Current, John R., 2010. "An improved ant colony optimization based algorithm for the capacitated arc routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(2), pages 246-266, February.
    16. Porumbel, Daniel & Goncalves, Gilles & Allaoui, Hamid & Hsu, Tienté, 2017. "Iterated Local Search and Column Generation to solve Arc-Routing as a permutation set-covering problem," European Journal of Operational Research, Elsevier, vol. 256(2), pages 349-367.

    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:pal:jorsoc:v:61:y:2010:i:7:d:10.1057_jors.2009.58. 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.palgrave-journals.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.