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

A parallel improved ant colony optimization for multi-depot vehicle routing problem

Author

Listed:
  • B Yu

    (Transportation Management College, Dalian Maritime University)

  • Z-Z Yang

    (Transportation Management College, Dalian Maritime University)

  • J-X Xie

    (College of Mechanical and Electronic Engineering, Hebei Agricultural University)

Abstract

This paper presents a method for solving multi-depot vehicle routing problem (MDVRP). First, a virtual central depot is added to transfer MDVRP to the multi-depot vehicle routing problem with the virtual central depot (V-MDVRP), which is similar to a vehicle routing problem (VRP) with the virtual central depot as the origin. An improved ant colony optimization with coarse-grain parallel strategy, ant-weight strategy and mutation operation, is presented for the V-MDVRP. The computational results for 23 benchmark problems are reported and compared to those of other ant colony optimizations.

Suggested Citation

  • B Yu & Z-Z Yang & J-X Xie, 2011. "A parallel improved ant colony optimization for multi-depot vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 183-188, January.
    • Handle: RePEc:pal:jorsoc:v:62:y:2011:i:1:d:10.1057_jors.2009.161
    DOI: 10.1057/jors.2009.161
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/jors.2009.161
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/jors.2009.161?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. Albritton, M. David & McMullen, Patrick R., 2007. "Optimal product design using a colony of virtual ants," European Journal of Operational Research, Elsevier, vol. 176(1), pages 498-520, January.
    2. Frank A. Tillman & Thomas M. Cain, 1972. "An Upperbound Algorithm for the Single and Multiple Terminal Delivery Problem," Management Science, INFORMS, vol. 18(11), pages 664-682, July.
    3. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    4. Raft, Ole M., 1982. "A modular algorithm for an extended vehicle scheduling problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 67-76, September.
    5. Gillett, Billy E & Johnson, Jerry G, 1976. "Multi-terminal vehicle-dispatch algorithm," Omega, Elsevier, vol. 4(6), pages 711-718.
    6. Yu, Bin & Yang, Zhong-Zhen & Yao, Baozhen, 2009. "An improved ant colony optimization for vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 196(1), pages 171-176, July.
    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. Zong, Fang & Yu, Ping & Tang, Jinjun & Sun, Xiao, 2019. "Understanding parking decisions with structural equation modeling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 408-417.
    2. Li, Junsong & Rong, Gang & Feng, Yiping, 2015. "Request selection and exchange approach for carrier collaboration based on auction of a single request," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 23-39.
    3. Huiyuan Xiong & Xionglai Zhu & Ronghui Zhang, 2018. "Energy Recovery Strategy Numerical Simulation for Dual Axle Drive Pure Electric Vehicle Based on Motor Loss Model and Big Data Calculation," Complexity, Hindawi, vol. 2018, pages 1-14, August.
    4. Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
    5. Weiheng Zhang & Yuvraj Gajpal & Srimantoorao. S. Appadoo & Qi Wei, 2020. "Multi-Depot Green Vehicle Routing Problem to Minimize Carbon Emissions," Sustainability, MDPI, vol. 12(8), pages 1-19, April.
    6. Baozhen Yao & Chao Chen & Xiaolin Song & Xiaoli Yang, 2019. "Fresh seafood delivery routing problem using an improved ant colony optimization," Annals of Operations Research, Springer, vol. 273(1), pages 163-186, February.
    7. Schmidt, Carise E. & Silva, Arinei C.L. & Darvish, Maryam & Coelho, Leandro C., 2023. "Time-dependent fleet size and mix multi-depot vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 255(C).
    8. Yiwei Fan & Gang Wang & Xiaoling Lu & Gaobin Wang, 2019. "Distributed forecasting and ant colony optimization for the bike-sharing rebalancing problem with unserved demands," PLOS ONE, Public Library of Science, vol. 14(12), pages 1-26, December.
    9. José M. Ferrer & M. Teresa Ortuño & Gregorio Tirado, 2020. "A New Ant Colony-Based Methodology for Disaster Relief," Mathematics, MDPI, vol. 8(4), pages 1-23, April.
    10. Grigorios D. Konstantakopoulos & Sotiris P. Gayialis & Evripidis P. Kechagias, 2022. "Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification," Operational Research, Springer, vol. 22(3), pages 2033-2062, July.
    11. Md. Anisul Islam & Yuvraj Gajpal, 2021. "Optimization of Conventional and Green Vehicles Composition under Carbon Emission Cap," Sustainability, MDPI, vol. 13(12), pages 1-20, June.
    12. Wang, Yuan & Lei, Linfei & Zhang, Dongxiang & Lee, Loo Hay, 2020. "Towards delivery-as-a-service: Effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 38-63.
    13. Schryen, Guido, 2020. "Parallel computational optimization in operations research: A new integrative framework, literature review and research directions," European Journal of Operational Research, Elsevier, vol. 287(1), pages 1-18.
    14. Wan Fang & Guo Haixiang & Li Jinling & Gu Mingyun & Pan Wenwen, 2021. "Multi-objective Emergency Scheduling for Geological Disasters," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 105(2), pages 1323-1358, January.

    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. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    2. Baozhen Yao & Bin Yu & Ping Hu & Junjie Gao & Mingheng Zhang, 2016. "An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot," Annals of Operations Research, Springer, vol. 242(2), pages 303-320, July.
    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. Baozhen Yao & Chao Chen & Xiaolin Song & Xiaoli Yang, 2019. "Fresh seafood delivery routing problem using an improved ant colony optimization," Annals of Operations Research, Springer, vol. 273(1), pages 163-186, February.
    5. Salhi, S. & Sari, M., 1997. "A multi-level composite heuristic for the multi-depot vehicle fleet mix problem," European Journal of Operational Research, Elsevier, vol. 103(1), pages 95-112, November.
    6. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Economic and environmental concerns in planning recyclable waste collection systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 34-54.
    7. Tu, Wei & Fang, Zhixiang & Li, Qingquan & Shaw, Shih-Lung & Chen, BiYu, 2014. "A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 84-97.
    8. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    9. Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2018. "Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 125-157, January.
    10. CASTRO, Marco & SÖRENSEN, Kenneth & VANSTEENWEGEN, Pieter & GOOS, Peter, 2012. "A simple GRASP+VND for the travelling salesperson problem with hotel selection," Working Papers 2012024, University of Antwerp, Faculty of Business and Economics.
    11. Van den Broeke, Maud & Boute, Robert & Cardoen, Brecht & Samii, Behzad, 2017. "An efficient solution method to design the cost-minimizing platform portfolio," European Journal of Operational Research, Elsevier, vol. 259(1), pages 236-250.
    12. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    13. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    14. Evan Rash & Karl Kempf, 2012. "Product Line Design and Scheduling at Intel," Interfaces, INFORMS, vol. 42(5), pages 425-436, October.
    15. Jan Zazgornik & Manfred Gronalt & Patrick Hirsch, 2012. "A comprehensive approach to planning the deployment of transportation assets in distributing forest products," International Journal of Revenue Management, Inderscience Enterprises Ltd, vol. 6(1/2), pages 45-61.
    16. Gläser, Sina & Stücken, Mareike, 2021. "Introduction of an underground waste container system–model and solution approaches," European Journal of Operational Research, Elsevier, vol. 295(2), pages 675-689.
    17. Markov, Iliya & Varone, Sacha & Bierlaire, Michel, 2016. "Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 256-273.
    18. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    19. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2018. "Vehicle routing problems with multiple trips," Annals of Operations Research, Springer, vol. 271(1), pages 127-159, December.
    20. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "Vehicle routing problems with multiple trips," 4OR, Springer, vol. 14(3), pages 223-259, September.

    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:62:y:2011:i:1:d:10.1057_jors.2009.161. 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.