IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v50y2013icp53-67.html
   My bibliography  Save this article

A memetic algorithm for the open capacitated arc routing problem

Author

Listed:
  • Fung, Richard Y.K.
  • Liu, Ran
  • Jiang, Zhibin

Abstract

In this paper, an open capacitated arc routing problem (OCARP) is defined and considered. The OCARP seeks to find a set of minimum-cost open routes that can serve the tasks (i.e., required arcs) of a given graph, subject to the vehicle capacity and travel distance. A mathematical programming formulation and a lower bound are established. An effective memetic algorithm is developed for solving the OCARP. Computational experiments demonstrate that the proposed algorithm can produce high quality solutions within a reasonable computational time span, and the proposed memetic algorithm is superior to the classical genetic algorithm in solution quality.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:transe:v:50:y:2013:i:c:p:53-67
    DOI: 10.1016/j.tre.2012.11.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554512000932
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2012.11.003?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. 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.
    2. Letchford, Adam N. & Lysgaard, Jens & Eglese, Richard W., 2006. "A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem," CORAL Working Papers L-2006-06, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    3. Beasley, JE, 1983. "Route first--Cluster second methods for vehicle routing," Omega, Elsevier, vol. 11(4), pages 403-408.
    4. 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.
    5. Marshall L. Fisher, 1994. "A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem," Operations Research, INFORMS, vol. 42(4), pages 775-779, August.
    6. 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.
    7. 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.
    8. Vigo, Daniele, 1996. "A heuristic algorithm for the asymmetric capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 89(1), pages 108-126, February.
    9. Z Fu & R Eglese & L Y O Li, 2005. "A new tabu search heuristic for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 267-274, March.
    10. D Sariklis & S Powell, 2000. "A heuristic method for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(5), pages 564-573, May.
    11. Chu, Feng & Labadi, Nacima & Prins, Christian, 2006. "A Scatter Search for the periodic capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 586-605, March.
    12. Hertz, Alain & Widmer, Marino, 2003. "Guidelines for the use of meta-heuristics in combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 151(2), pages 247-252, December.
    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.
    14. Toth, Paolo & Vigo, Daniele, 1999. "A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls," European Journal of Operational Research, Elsevier, vol. 113(3), pages 528-543, March.
    15. 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.
    16. Pan, Zhendong & Tang, Jiafu & Fung, Richard Y.K., 2009. "Synchronization of inventory and transportation under flexible vehicle constraint: A heuristics approach using sliding windows and hierarchical tree structure," European Journal of Operational Research, Elsevier, vol. 192(3), pages 824-836, February.
    17. Luc Muyldermans & Patrick Beullens & Dirk Cattrysse & Dirk Van Oudheusden, 2005. "Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem," Operations Research, INFORMS, vol. 53(6), pages 982-995, December.
    18. 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.
    19. 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.
    20. 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.
    21. Kara, Imdat & Laporte, Gilbert & Bektas, Tolga, 2004. "A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(3), pages 793-795, November.
    22. 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.
    23. Fleszar, Krzysztof & Osman, Ibrahim H. & Hindi, Khalil S., 2009. "A variable neighbourhood search algorithm for the open vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 803-809, June.
    24. Vicente Campos & Manuel Laguna & Rafael Martí, 2005. "Context-Independent Scatter and Tabu Search for Permutation Problems," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 111-122, February.
    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. Nguyen, H.N. & Rainwater, C.E. & Mason, S.J. & Pohl, E.A., 2014. "Quantity discount with freight consolidation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 66(C), pages 66-82.
    2. Chebbi, Olfa & Chaouachi, Jouhaina, 2016. "Reducing the wasted transportation capacity of Personal Rapid Transit systems: An integrated model and multi-objective optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 236-258.
    3. Yu, Mingzhu & Jin, Xin & Zhang, Zizhen & Qin, Hu & Lai, Qidong, 2019. "The split-delivery mixed capacitated arc-routing problem: Applications and a forest-based tabu search approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 141-162.

    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. Liu, Ran & Jiang, Zhibin, 2012. "The close–open mixed vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 349-360.
    2. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Luc Muyldermans & Patrick Beullens & Dirk Cattrysse & Dirk Van Oudheusden, 2005. "Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem," Operations Research, INFORMS, vol. 53(6), pages 982-995, December.
    10. Park, Junhyuk & Kim, Byung-In, 2010. "The school bus routing problem: A review," European Journal of Operational Research, Elsevier, vol. 202(2), pages 311-319, April.
    11. 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.
    12. T Bektaş & Seda Elmastaş, 2007. "Solving school bus routing problems through integer programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1599-1604, December.
    13. 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.
    14. D Aksen & Z Özyurt & N Aras, 2007. "Open vehicle routing problem with driver nodes and time deadlines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1223-1234, September.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. Chefi Triki, 2017. "Solving the Periodic Edge Routing Problem in the Municipal Waste Collection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(03), pages 1-13, June.

    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:transe:v:50:y:2013:i:c:p:53-67. 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/wps/find/journaldescription.cws_home/600244/description#description .

    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.