Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

The article deals with the hybrid Ant Colony Optimization algorithm and its application to the Multi-Depot Vehicle Routing Problem (MDVRP). The algorithm combines both probabilistic and exact techniques. The former implements the bio-inspired approach based on the behaviour of ants in the nature when searching for food together with simulated annealing principles. The latter complements the former. The algorithm explores the search space in a finite number of iterations. In each iteration, the deterministic local optimization process may be used to improve the current solution. Firstly, the key parts and features of the algorithm are presented, especially in connection with the exact optimization process. Next, the article deals with the results of experiments on MDVRP problems conducted to verify the quality of the algorithm; moreover, these results are compared to other state-of-the-art methods. As experiments, Cordreau’s benchmark instances were used. The experiments showed that the proposed algorithm overcomes the other methods as it has the smallest average error (the difference between the found solution and the best known solution) on the entire set of benchmark instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Abdulkader MMS, Gajpal Y, ElMekkawy TY (2015) Hybridized ant colony algorithm for the multi compartment vehicle routing problem. Appl Soft Comput 37:196–203

    Article  Google Scholar 

  • Bae H, Moon I (2016) Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles. Appl Math Model 40(13–14):6536–6549

    Article  MathSciNet  MATH  Google Scholar 

  • Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math Prog 120(2):347–380

    Article  MathSciNet  MATH  Google Scholar 

  • Blaha M, Silinger K (2018) Application support for topographical-geodetic issues for tactical and technical control of artillery fire. Int J Circuits Syst Signal Process 12:48–57

    Google Scholar 

  • Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: state of the art classification and review. Comput Ind Eng 99:300–313

    Article  Google Scholar 

  • Brito J, Martinez FJ, Moreno JA, Verdegay JL (2015) An ACO hybrid metaheuristic for close–open vehicle routing problems with time windows and fuzzy constraints. Appl Soft Comput 32:154–163

    Article  Google Scholar 

  • Bullnheimer B, Hartl RF, Strauss C (1999) Applying the ant system to the vehicle routing problem. In: Voß S et al (eds) Meta-heuristics: advances and trends in local search paradigms for optimization. Springer, New York, pp 285–296

    Chapter  Google Scholar 

  • Caldeira TCM (2009) Optimization of the multi-depot vehicle routing problem: an application to logistics and transport of biomass for electricity production. Technical University of Lisbon, Lisbon

    Google Scholar 

  • Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581

    Article  Google Scholar 

  • Cordeau JF, Maischberger M (2012) A parallel iterated tabu search heuristic for vehicle routing problems. Comput Oper Res 39(9):2033–2050

    Article  Google Scholar 

  • Cordeau JF, Gendreau M, Laporte G (1997) A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2):105–119

    Article  MATH  Google Scholar 

  • Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci 6(1):80–91

    Article  MathSciNet  MATH  Google Scholar 

  • de Oliveira FB et al (2016) A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem. Exp Syst Appl 43:117–130

    Article  Google Scholar 

  • Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B (Cybern) 26(1):29–41

    Article  Google Scholar 

  • Drozd J (2016) Analysis results of the military observer training system. Econ Manag 1:24–31

    Google Scholar 

  • Gao J (2016) Automobile chain maintenance parts delivery problem using an improved ant colony algorithm. Adv Mech Eng 8(9):1–13

    Article  Google Scholar 

  • Garey MR, Johnson DS (1979) Computer and intractability: a guide to the theory of NP-completeness, 1st edn. W.H. Freeman, New York

    MATH  Google Scholar 

  • Gillett BE, Johnson JG (1976) Multi-terminal vehicle dispatch algorithm. Omega 4(6):711–718

    Article  Google Scholar 

  • Gülcü Ş, Mahi M, Baykan ÖK, Kodaz H (2018) A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem. Soft Comput 22(5):1669–1685

    Article  Google Scholar 

  • Gulczynski D, Golden BL, Wasil E (2011) The multi-depot split delivery vehicle routing problem: an integer programming-based heuristic, new test problems, and computational results. Comput Ind Eng 61(3):794–804

    Article  Google Scholar 

  • Heinonen J, Pettersson F (2007) Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem. Appl Math Comput 187(2):989–998

    MathSciNet  MATH  Google Scholar 

  • Hodicky J (2018) Standards to support military autonomous system life cycle. In: Kacprzyk J (ed) Advances in intelligent systems and computing, vol 644. Springer, Berlin, pp 671–678

    Google Scholar 

  • Imran A (2011) A variable neighborhood search-based heuristic for the multi-depot vehicle routing problem. J Tek Ind 15(2):95–102

    Google Scholar 

  • Jabir E, Panicker VV, Sridharan R (2017) Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem. Transp Res Part D Transp Environ 57(December):422–457

    Article  Google Scholar 

  • Kalayci CB, Kaya C (2016) An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Exp Syst Appl 66:163–175

    Article  Google Scholar 

  • Karakatic S, Podgorelec V (2015) A survey of genetic algorithms for solving multi depot vehicle routing problem. Appl Soft Comput 37(February):519–532

    Article  Google Scholar 

  • Ma Y et al (2017) An improved ACO for the multi-depot vehicle routing problem with time windows. In: Xu J et al (eds) Proceedings of the tenth international conference on management science and engineering management, advances in intelligent systems and computing, vol 502

  • Maischberger M, Cordeau JF (2011) Solving variants of the vehicle routing problem with a simple parallel iterated Tabu search. In: Voss S, Pahl J, Reiners T (eds) Network optimization, vol 6701. Lecture notes in computer science. Springer, New York, pp 395–400

    Chapter  Google Scholar 

  • Marti R, Laguna M, Glover F (2006) Principles of scatter search. Eur J Oper Res 169(2):359–372

    Article  MathSciNet  MATH  Google Scholar 

  • Montoya-Torres JR, Franco JL, Isaza SN, Jimenez HF, Herazo-Padilla N (2015) A literature review of the vehicle routing problem with multiple depots. Comput Ind Eng 79(January):115–129

    Article  Google Scholar 

  • NEO Web (2017) Networking and emerging optimization. University of Malaga, Spain. http://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/. Accessed 1 Mar 2017

  • Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job-shop problem. Manag Sci 42(6):797–813

    Article  MATH  Google Scholar 

  • Otrisal P, Florus S, Barsan G, Mosteanu D (2018) Employment of simulants for testing constructive materials designed for body surface isolative protection in relation to chemical warfare agents. Rev Chim 69(2):300–304

    Article  Google Scholar 

  • Petrea N, Ginghina R, Pretorian A, Petre R, Barsan G, Otrisal P, Mosteanu D (2018) Experimental survey regarding the dangerous chemical compounds from military polygons that affect the military health and the environment. Rev Chim 69(7):1640–1644

    Article  Google Scholar 

  • Rajappa GP, Wilck JH, Bell JE (2016) An ant colony optimization and hybrid metaheuristics algorithm to solve the split delivery vehicle routing problem. Int J Appl Ind Eng 3(1):1–19

    Google Scholar 

  • Reiners Ch (2015) Constraint programming-based heuristics for the multi-depot vehicle routing problem with a rolling planning horizon, Ph.D. thesis, University of Duisburg-Essen, Duisburg

  • Renaud J, Laporte G, Boctor FF (1996) A tabu search heuristic for the multi-depot vehicle routing problem. Comput Oper Res 23(3):229–235

    Article  MATH  Google Scholar 

  • Riahi V, Kazemi M (2018) A new hybrid ant colony algorithm for scheduling of no-wait flowshop. Oper Res 18(1):55–74

    Google Scholar 

  • Rybansky M (2017) Trafficability analysis through vegetation. In: International conference on military technologies, Brno, pp 207–210

  • Sharma N, Monika M (2015) A literature survey on multi-depot vehicle routing problem. Int J Sci Res Dev 3(4):1752–1757

    Google Scholar 

  • Stodola P (2018) Using metaheuristics on the multi-depot vehicle routing problem with modified optimization criterion. Algorithms 11(5):1–14

    Article  MathSciNet  MATH  Google Scholar 

  • Stodola P, Mazal J (2015) Tactical models based on a multi-depot vehicle routing problem using the ant colony optimization algorithm. Int J Math Models Methods Appl Sci 9(summer):330–337

    Google Scholar 

  • Stodola P, Mazal J (2016a) Applying the ant colony optimisation algorithm to the capacitated multi-depot vehicle routing problem. Int J Bio Inspired Comput 8(4):228–233

    Article  Google Scholar 

  • Stodola P, Mazal J (2016b) Tactical decision support system to aid commanders in their decision-making. In: Hodicky J (ed) Modelling and simulation for autonomous systems. Springer, Rome, pp 396–406

    Chapter  Google Scholar 

  • Surekha P, Sumathi S (2011) Solution to multi-depot vehicle routing problem using genetic algorithms. World Appl Program 1(3):118–131

    Google Scholar 

  • Thangiaha R, Salhi S (2001) Genetic clustering: an adaptive heuristic for the multi-depot vehicle routing problem. Appl Artif Intell 15(4):361–383

    Article  Google Scholar 

  • Tillman FA, Cain TM (1972) An upper bound algorithm for the single and multiple terminal delivery problem. Manag Sci 18(11):664–682

    Article  MATH  Google Scholar 

  • Ting CJ, Chen CH (2008) Combination of multiple ant colony system and simulated annealing for the multi-depot vehicle routing problem with time windows. Transp Res Rec J Transp Res Board 2089:85–92

    Article  Google Scholar 

  • Van Breedam A (2001) Comparing descent heuristics and metaheuristics for the vehicle routing problem. Comput Oper Res 28(4):289–315

    Article  MATH  Google Scholar 

  • Vidal T (2012) A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Oper Res 60(3):611–624

    Article  MathSciNet  MATH  Google Scholar 

  • Vlkovsky M, Ivanusa T, Neumann V, Foltin P, Vlachova H (2017) Optimizating cargo security during transport using dataloggers. J Transp Secur 10(3–4):63–71

    Article  Google Scholar 

  • Wen M (2010) Rich vehicle routing problems and applications. Ph.D. thesis, DTU Management, Kongens Lyngby

  • Wren A, Holliday A (1972) Computer scheduling of vehicles from one or more depots to a number of delivery points. Oper Res Q 23(3):333–344

    Article  Google Scholar 

  • Yalian T (2016) An improved ant colony optimization for multi-depot vehicle routing problem. Int J Eng Technol 8(5):385–388

    Article  Google Scholar 

  • Yao B et al (2014) Improved ant colony optimization for seafood product delivery routing problem. Promet Traffic Transp 26(1):1–10

    MathSciNet  Google Scholar 

  • Yu B, Yang ZZ, Yao BZ (2009) An improved ant colony optimization for vehicle routing problem. Eur J Oper Res 196(1):171–176

    Article  MATH  Google Scholar 

  • Yu B, Yang ZZ, Xie JX (2010) A parallel improved ant colony optimization for multi-depot vehicle routing problem. J Oper Res Soc 62(1):183–188

    Article  Google Scholar 

  • Zhang X, Tang L (2009) A new hybrid ant colony optimization algorithm for the vehicle routing problem. Pattern Recognit Lett 30(9):848–855

    Article  Google Scholar 

  • Zouari W, Alaya I, Tagina M (2017) A hybrid ant colony algorithm with a local search for the strongly correlated knapsack problem. In: International conference on computer systems and applications. IEEE, pp 527–533

Download references

Author information

Authors and Affiliations

  1. University of Defence, Brno, Czech Republic

    Petr Stodola

Authors
  1. Petr Stodola
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Petr Stodola.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Stodola, P. Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem. Nat Comput 19, 463–475 (2020). https://doi.org/10.1007/s11047-020-09783-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-020-09783-6

Keywords

Search

Navigation