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

A Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem

Author

Listed:
  • Alain Hertz

    (Département de Mathématiques, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland)

  • Michel Mittaz

    (Département de Mathématiques, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland)

Abstract

The undirected capacitated arc routing problem (CARP) arises naturally in several applications where streets require maintenance, or customers located along road must be serviced. Basic algorithmic procedures have recently been developed for the design of heuristics in an arc routing context. This article reports on the use of these basic tools in a variable neighborhood descent algorithm for the solution of the undirected CARP.

Suggested Citation

  • Alain Hertz & Michel Mittaz, 2001. "A Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem," Transportation Science, INFORMS, vol. 35(4), pages 425-434, November.
    • Handle: RePEc:inm:ortrsc:v:35:y:2001:i:4:p:425-434
    DOI: 10.1287/trsc.35.4.425.10431
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.35.4.425.10431
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.35.4.425.10431?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    4. Christofides, Nicos, 1973. "The optimum traversal of a graph," Omega, Elsevier, vol. 1(6), pages 719-732, 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. 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.
    2. Faustino Tello & Antonio Jiménez-Martín & Alfonso Mateos & Pablo Lozano, 2019. "A Comparative Analysis of Simulated Annealing and Variable Neighborhood Search in the ATCo Work-Shift Scheduling Problem," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    3. 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.
    4. Gahm, Christian & Brabänder, Christian & Tuma, Axel, 2017. "Vehicle routing with private fleet, multiple common carriers offering volume discounts, and rental options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 192-216.
    5. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    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. Li, Jiliu & Qin, Hu & Shen, Huaxiao & Tsui, Kwok Leung, 2019. "The unilateral transportation problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 1-29.
    8. 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.
    9. 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.
    10. Tan, K.C. & Chew, Y.H. & Lee, L.H., 2006. "A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 855-885, August.
    11. 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.
    12. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    13. Zhang, Zizhen & Qin, Hu & Wang, Kai & He, Huang & Liu, Tian, 2017. "Manpower allocation and vehicle routing problem in non-emergency ambulance transfer service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 45-59.
    14. Chen, Yuning & Hao, Jin-Kao, 2018. "Two phased hybrid local search for the periodic capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 264(1), pages 55-65.
    15. Jesus Gonzalez-Feliu, 2009. "The N-echelon Location routing problem: concepts and methods for tactical and operational planning," Working Papers halshs-00422492, HAL.
    16. Jesica Armas & Peter Keenan & Angel A. Juan & Seán McGarraghy, 2019. "Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics," Annals of Operations Research, Springer, vol. 273(1), pages 135-162, February.
    17. Gilbert Laporte & Roberto Musmanno & Francesca Vocaturo, 2010. "An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 125-135, February.

    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. Amberg, Anita & Domschke, Wolfgang & Vo[ss], Stefan, 2000. "Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees," European Journal of Operational Research, Elsevier, vol. 124(2), pages 360-376, July.
    2. 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.
    3. 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.
    4. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    5. Daniel Berend & Ephraim Korach & Shira Zucker, 2012. "Tabu search for the BWC problem," Journal of Global Optimization, Springer, vol. 54(4), pages 649-667, December.
    6. 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.
    7. Tagmouti, Mariam & Gendreau, Michel & Potvin, Jean-Yves, 2007. "Arc routing problems with time-dependent service costs," European Journal of Operational Research, Elsevier, vol. 181(1), pages 30-39, August.
    8. Pourhejazy, Pourya & Zhang, Dali & Zhu, Qinghua & Wei, Fangfang & Song, Shuang, 2021. "Integrated E-waste transportation using capacitated general routing problem with time-window," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    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. Beullens, Patrick & Muyldermans, Luc & Cattrysse, Dirk & Van Oudheusden, Dirk, 2003. "A guided local search heuristic for the capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 147(3), pages 629-643, June.
    11. Andie Pramudita & Eiichi Taniguchi, 2014. "Model of debris collection operation after disasters and its application in urban area," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 18(2), pages 218-243, July.
    12. Sheu Chen, 2010. "A Heuristic Algorithm for Hierarchical Hub-and-spoke Network of Time-definite Common Carrier Operation Planning Problem," Networks and Spatial Economics, Springer, vol. 10(4), pages 509-523, December.
    13. 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.
    14. LECLUYSE, C. & VAN WOENSEL, Tom & PEREMANS, Herbert, 2007. "Vehicle routing with stochastic time-dependent travel times," Working Papers 2007018, University of Antwerp, Faculty of Business and Economics.
    15. Marianov, Vladimir & Serra, Daniel & ReVelle, Charles, 1999. "Location of hubs in a competitive environment," European Journal of Operational Research, Elsevier, vol. 114(2), pages 363-371, April.
    16. Hachicha, Wafik & Ammeri, Ahmed & Masmoudi, Faouzi & Chachoub, Habib, 2010. "A comprehensive literature classification of simulation optimisation methods," MPRA Paper 27652, University Library of Munich, Germany.
    17. Chiara Gruden & Irena Ištoka Otković & Matjaž Šraml, 2020. "Neural Networks Applied to Microsimulation: A Prediction Model for Pedestrian Crossing Time," Sustainability, MDPI, vol. 12(13), pages 1-22, July.
    18. Chou, Jui-Sheng & Truong, Dinh-Nhat, 2021. "A novel metaheuristic optimizer inspired by behavior of jellyfish in ocean," Applied Mathematics and Computation, Elsevier, vol. 389(C).
    19. Zaraket, Fadi A. & Olleik, Majd & Yassine, Ali A., 2014. "Skill-based framework for optimal software project selection and resource allocation," European Journal of Operational Research, Elsevier, vol. 234(1), pages 308-318.
    20. Sumanta Basu & Ravindra S Gajulapalli & Ghosh, Diptesh, 2008. "Implementing Tabu Search to Exploit Sparsity in ATSP Instances," IIMA Working Papers WP2008-10-02, Indian Institute of Management Ahmedabad, Research and Publication Department.

    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:35:y:2001:i:4:p:425-434. 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: 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.