Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Start single access now
Request access for companies
EXTENDED SEARCH
Log in
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Adaptive and Multilevel Metaheuristics Read chapter Read first chapter

2018 | OriginalPaper | Chapter

40. Particle Swarm Optimization for the Vehicle Routing Problem: A Survey and a Comparative Analysis

Authors : Yannis Marinakis, Magdalene Marinaki, Athanasios Migdalas

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

Log in

Abstract

In the last few years, a number of books and survey papers devoted to the vehicle routing problem (VRP) or to its variants or to the methods used for the solution of one or more variants of the VRP have been published. Also, in these years, the field of swarm intelligence algorithms has had a significant growth. One of the most important swarm intelligence algorithms is the particle swarm optimization (PSO). Although the particle swarm optimization was first published in 1995, it took around 10 years in order researchers to publish papers using a PSO algorithm for the solution of variants of the VRP. However, in the last 10 years, many journal papers, conference papers, and book chapters have been published where a variant of VRP is solved using a PSO algorithm. Thus, it is significant to present a survey paper where a review and brief analysis of the most important of these papers will be given. This is the main focus of this chapter.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Optimization Problems, Models, and Heuristics in Wireless Sensor Networks
next chapter Scheduling Heuristics
Literature
1.
Adulyasak Y, Cordeau JF, Jans R (2014) Optimization-based adaptive large neighborhood search for the production routing problem. Transport Sci 48(1):20–45
2.
Ai TJ, Kachitvichyanukul V (2009) A particle swarm optimisation for vehicle routing problem with time windows. Int J Oper Res 6(4):519–537
3.
Ai TJ, Kachitvichyanukul V (2009) A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Comput Oper Res 36:1693–1702
4.
Ai TJ, Kachitvichyanukul V (2009) Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Comput. Ind. Eng. 56:380–387
5.
Angelelli E, Speranza MG (2002) The periodic vehicle routing problem with intermediate facilities. Eur J Oper Res 137(2):233–247
6.
Archetti C, Speranza MG, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1):64–73
7.
Archetti C, Speranza MG (2008) The split delivery vehicle routing problem: a survey. In: Golden B, Raghavan S, Wasil E (eds) The vehicle routing problem: latest advances and new challenges. Springer, Boston, pp 103–122
8.
Archetti C, Speranza MG, Vigo D (2014) Vehicle routing problems with profits. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications. MOS-SIAM series on optimization. SIAM, Philadelphia, pp 273–298
9.
Assad AA, Golden BL (1995) Arc routing methods and applications. In: Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing, handbooks in operations research and management science, vol 8. Elsevier Science B V, Amsterdam, pp 375–483
10.
Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing, handbooks in operations research and management science, vol 8. Elsevier Science B V, Amsterdam
11.
Banks A, Vincent J, Anyakoha C (2007) A review of particle swarm optimization. Part I: background and development. Nat Comput 6(4):467–484
12.
Banks A, Vincent J, Anyakoha C (2008) A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Nat Comput 7:109–124
13.
Bard, JF, Nananukul N (2009) The integrated production inventory distribution routing problem. J Sched 12(3):257–280
14.
Bashiri M, Fallahzade E (2012) A Particle swarm optimization algorithm for multi-depot capacitated location-routing problem with inventory decisions in supply chain network design. In: CIE42 proceedings, Cape Town, 16–18 July 2012. CIE and SAIIE, pp 25-1–25-9
15.
Bektas T, Laporte G (2011) The pollution-routing problem. Transp Res B Methodol 45(8):1232–1250
16.
Belmecheri F, Prins C, Yalaoui F, Amodeo L (2013) Particle swarm optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows. J Intell Manuf 24(4):775–789
17.
Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: a classification scheme and survey. TOP 15(1):1–31
18.
Bianchi L, Birattari M, Manfrin M, Mastrolilli M, Paquete L, Rossi-Doria O, Schiavinotto T (2006) Hybrid metaheuristics for the vehicle routing problem with stochastic demands. J Math Model Algorithm 5(1):91–110
19.
Bodin L, Golden B (1981) Classification in vehicle routing and scheduling. Networks 11: 97–108
20.
Bodin L, Golden B, Assad A, Ball M (1983) The state of the art in the routing and scheduling of vehicles and crews. Comput Oper Res 10:63–212
21.
Bortfeldt A (2012) A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Comput Oper Res 39(9):2248–2257
22.
Bozorgi-Amiri A, Jabalameli MS, Alinaghian M, Heydari M (2012) A modified particle swarm optimization for disaster relief logistics under uncertain environment. Int J Adv Manuf Technol 60(1–4):357–371
23.
Braysy O, Gendreau M (2005) Vehicle routing problem with time windows, Part I: route construction and local search algorithms. Transp Sci 39(1): 104–118
24.
Braysy O, Gendreau M (2005) Vehicle routing problem with time windows, Part II: metaheuristics. Transp Sci 39(1): 119–139
25.
Brito J, Exposito A, Moreno-P \(\acute {e}\)rez JA (2015) Bi-objective discrete PSO for service-oriented VRPTW (Chapter 29). In: Greiner D et al (eds) Advances in evolutionary and deterministic methods for design, optimization and control in engineering and sciences. Computational methods in applied sciences, vol 36. Springer International Publishing, Cham, pp 445–460. https://​doi.​org/​10.​1007/​978-3-319-11541-2_​29
26.
Campbell A, Clarke L, Kleywegt A, Sawelsberg M (1998) The inventory routing problem. In: Crainic TG, Laporte G (eds) Fleet management and logistics. Kluwer Academic Publishers, Boston, pp 95–113
27.
Campbell A, Clarke L, Sawelsberg M (2002) Inventory routing in practice. In: Toth P, Vigo D (eds) The vehicle routing problem. Monographs on discrete mathematics and applications. Siam, Philadelphia, pp 309–330
28.
Caceres-Cruz J, Arias P, Guimarans D, Riera D, Juan AA (2015). Rich vehicle routing problem: survey. ACM Comput Surv (CSUR) 47(2):32
29.
Caretto C, Baker B (2002) A GRASP interactive approach to the vehicle routing problem with backhauls. In: Ribeiro CC, Hansen P (eds) Essays and surveys on metaheuristics. Kluwer Academic Publishers, Norwell, pp 185–199
30.
Casco DO, Golden BL, Wasil EA (1988) Vehicle routing with backhauls: models, algorithms, and case studies. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North Holland, Amsterdam, pp 127–147
31.
Castro JP, Landa-Silva D, Moreno Perez JA (2009) Exploring feasible and infeasible regions in the vehicle routing problem with time windows using a multi-objective particle swarm optimization approach (Chapter 9). In: Krasnogor N et al (eds) Nature inspired cooperative strategies for optimization. SCI, vol 236. Springer, Berlin/Heidelberg, pp 103–114
32.
Chao IM, Golden BL, Wasil E (1993) A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. Am J Math Manag Sci 13(3–4):371–406
33.
Chen A-L, Yang G-K, Wu Z-M (2006) Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J Zhejiang Univ Sci A 7(4):607–614
34.
Chen J-Q, Li W-L, Murata T (2013) Particle swarm optimization for vehicle routing problem with uncertain demand. In: Proceedings of 2013 4th IEEE international conference on software engineering and service science (ICSESS), Beijing, 23–25 May 2013, pp 857–860
35.
Chen S-K, Wu G-H, Ti Y-W, Wang R-Z, Fang W-P, Lu C-J (2014) Hierarchical particle swarm optimization algorithm of IPSVR problem. In: Pan J-S et al (eds) Genetic and evolutionary computing. Advances in intelligent systems and computing, vol 238. Springer International Publishing, Cham, pp 231–238. https://​doi.​org/​10.​1007/​978-3-319-01796-9_​24
36.
Chen MC, Hsiao YH, Reddy RH, Tiwari MK (2016) The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks. Transp Res E 91:208–226
37.
Christiansen M, Fagerholt K, Ronen D (2004) Ship routing and scheduling: status and perspectives. Transp Sci 38(1):1–18
38.
Christiansen M, Fagerholt K, Nygreen B, Ronen D (2013) Ship routing and scheduling in the new millennium. Eur J Oper Res 228:467–483
39.
Christofides N (1985) Vehicle routing. In: Lawer EL, Lenstra JK, Rinnoy Kan AHG, Shmoys DB (eds) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, Chichester, pp 431–448
40.
Christofides N, Mignozzi A, Toth P (1979) The vehicle routing problem. In: Christofides N (ed) Combinatorial optimization. Wiley, Chichester, pp 315–338
41.
Clerc M (2006) Particle swarm optimization. ISTE, London
42.
Clerc M, Kennedy J (2002) The particle swarm: explosion, stability and convergence in a multi-dimensional complex space. IEEE Trans Evol Comput 6:58–73
43.
Cordeau JF, Deasulniers G, Desrosiers J, Solomon MM, Soumis F (2002) VRP with time windows. In: Toth P, Vigo D (eds) The vehicle routing problem. Monographs on discrete mathematics and applications. SIAM, Philadelphia, pp 157–193
44.
Dallard H, Lam SS, Kulturel-Konak S (2007) Solving the orienteering problem using attractive and repulsive particle swarm optimization. In: Proceedings of IEEE international conference on Information Reuse and Integration (IRI 2007), Las Vegas, 13–15 Aug 2007, pp 2–17
45.
Dang D-C, Guibadj RN, Moukrim A (2011) A PSO-based memetic algorithm for the team orienteering problem. In: Di Chio C et al (eds) EvoApplications 2011, Part II. LNCS, vol 6625. Springer, Berlin/Heidelberg, pp 471–480
46.
Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci 6(1):80–91
47.
Daskin M (1995) Network and discrete location. Models, algorithms and applications. Wiley, New York
48.
De A, Mamanduru VKR, Gunasekaran A, Subramanian N, Tiwari MK (2016) Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimization. Comput Ind Eng 96:201–215
49.
Desrochers M, Lenstra JK, Savelsberg MWP, Soumis F (1988) Vehicle routing with time windows: optimization and approximation. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North Holland, Amsterdam, pp 65–84
50.
Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) Time constraint routing and scheduling. In: Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing, handbooks in operations research and management science, vol 8. Elsevier Science B V, Amsterdam, pp 35–140
51.
Di-Ming A, Zhe Z, Rui Z, Feng P (2011) Research of pareto-based multi-objective optimization for multi-vehicle assignment problem based on MOPSO. In: Tan Y et al (eds) ICSI 2011, Part II. LNCS, vol 6729. Springer, Berlin/Heidelberg, pp 10–16
52.
Eksioglu B, Vural AV, Reisman, A (2009) The vehicle routing problem: a taxonomic review. Comput Ind Eng 57(4):1472–1483
53.
Engelbrecht AP (2007) Computational intelligence: an introduction, 2nd edn. Wiley, Chichester
54.
Fedegruen A, Simchi-Levi D (1995) Analysis of vehicle routing and inventory routing problems. In: Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing. Handbooks in operations research and management science, vol 8. Elsevier Science B V, Amsterdam, pp 297–373
55.
Fisher ML (1995) Vehicle routing. In: Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing. Handbooks in operations research and management science, vol 8. North Holland, Amsterdam, pp 1–33
56.
Francis PM, Smilowitz KR, Tzur M (2008) The period vehicle routing problem and its extensions. In: Golden B et al (eds) The vehicle routing problem: latest advances and new challenges. Springer LLC, Boston, pp 73–102
57.
Gan X, Wang Y, Yu Y, Niu B (2013) An emergency vehicle scheduling problem with time utility based on particle swarm optimization. In: Huang D-S et al (eds) ICIC 2013. LNAI, vol 7996. Springer, Berlin/Heidelberg, pp 614–623
58.
Gan X, Kuang J, Niu B (2014) Particle swarm optimizations for multi-type vehicle routing problem with time windows. In: Huang D-S et al (eds) ICIC 2014. LNAI, vol 8589. Springer International Publishing, Cham, pp 808–815
59.
Gan X, Liu LJ, Chen JS, Niu B (2016) Comprehensive learning PSO for solving environment heterogeneous fixed fleet VRP with time windows. In: Tan Y et al (eds) ICSI 2016, Part II. LNCS, vol 9713. Springer, Cham, pp 424–432
60.
Gavalas D, Konstantopoulos C, Mastakas K, Pantziou G (2014) A survey on algorithmic approaches for solving tourist trip design problems. J Heuristics 20(3):291–328
61.
Gendreau M, Potvin JY (1998) Dynamic vehicle routing and dispatching. In: Crainic TG, Laporte G (eds) Fleet management and logistics. Kluwer Academic Publishers, Boston, pp 115–125
62.
Gendreau M, Laport G, Seguin R (1996) Stochastic vehicle routing. Eur J Oper Res 88:3–12
63.
Gendreau M, Laporte G, Potvin J-Y (1997) Vehicle routing: modern heuristics. In: Aarts EHL, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, Chichester, pp 311–336
64.
Gendreau M, Laporte G, Musaraganyi C, Taillard ED (1999) A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput Oper Res 26:1153–1173
65.
Gendreau M, Laporte G, Potvin J-Y (2002) Metaheuristics for the capacitated VRP. In: Toth P, Vigo D (eds) The vehicle routing problem. Monographs on discrete mathematics and applications. SIAM, Philadelphia, pp 129–154
66.
Gendreau M, Iori M, Laporte G, Martello S (2008) A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51(1):4–18
67.
Glover F, Laguna M, Marti R (2003) Scatter search and path relinking: advances and applications. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Kluwer Academic Publishers, Boston, pp 1–36
68.
Goksal FP, Altiparmak F, Karaoglan I (2010) A hybrid particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. In: Proceedings of 2010 40th international conference on Computers and Industrial Engineering (CIE), Awaji, 25–28 July 2010, pp 1–6
69.
Goksal FP, Karaoglan I, Altiparmak F (2013) A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Comput Ind Eng 65: 39–53
70.
Golden BL, Assad AA (1988) Vehicle routing: methods and studies. North Holland, Amsterdam
71.
Golden BL, Wasil EA, Kelly JP, Chao IM (1998) The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In: Crainic TG, Laporte G (eds) Fleet management and logistics. Kluwer Academic Publishers, Boston, pp 33–56
72.
Golden BL, Raghavan S, Wasil EA (eds) (2008) The vehicle routing problem: latest advances and new challenges. Operations research/computer science interfaces series, vol 43. Springer LLC, Boston
73.
Gong Y-J, Zhang J, Liu O, Huang R-Z, Chung HS-H, Shi Y-H (2012) Optimizing the vehicle routing problem with time windows: a discrete particle swarm optimization approach. IEEE Trans Syst Man Cybern C Appl Rev 42(2):254–267
74.
Hansen P, Mladenovic N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130:449–467
75.
Hu F, Wu F (2010) Diploid hybrid particle swarm optimization with differential evolution for open vehicle routing problem. In: Proceedings of the 8th world congress on intelligent control and automation, Jinan, 6–9 July 2010
76.
77.
Jaillet P, Odoni AR (1988) The probabilistic vehicle routing problem. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North Holland, Amsterdam, pp 293–318
78.
Javid AA, Azad N (2010) Incorporating location, routing and inventory decisions in supply chain network design. Transport Res E Log Transp Rev 46(5):582–597
79.
Jian L (2009) Solving capacitated vehicle routing problems via genetic particle swarm optimization. In: Proceedings of 2009 third international symposium on intelligent information technology application, Nanchang, 21–22 Nov 2009, pp 528–531
80.
Jiang W, Zhang Y, Xie J (2009) A particle swarm optimization algorithm with crossover for vehicle routing problem with time windows. In: IEEE symposium on computational intelligence in scheduling (CI-Sched ’09), Nashville, 30 Mar 2009–2 Apr 2009, pp 103–106
81.
Jozefowiez N, Semet F, Talbi EG (2008) Multi-objective vehicle routing problems. Eur J Oper Res 189(2):293–309
82.
Kachitvichyanukul V, Sombuntham P, Kunnapapdeelert S (2015) Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO. Comput Ind Eng 89:125–136
83.
Kanthavel K, Prasad P (2011) Optimization of capacitated vehicle routing problem by nested particle swarm optimization. Am J Appl Sci 8(2):107–112
84.
Kechagiopoulos PN, Beligiannis GN (2014) Solving the urban transit routing problem using a particle swarm optimization based algorithm. Appl Soft Comput 21:654–676
85.
Kennedy J (1997) The particle swarm: social adaptation of knowledge. In: Proceedings of the IEEE international conference on evolutionary computation, Indianapolis, 13–16 Apr 1997, pp 303–308
86.
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of 1995 IEEE international conference on neural networks, vol 4, pp 1942–1948
87.
Kennedy J, Eberhart R (1997) A discrete binary version of the particle swarm algorithm. In: Proceedings of 1997 IEEE international conference on systems, man, and cybernetics, vol 5, pp 4104–4108
88.
Kirkpatrick S (1984) Optimization by simulated annealing – quantitative studies. J Stat Phys 34:975–986
89.
Khouadjia MR, Alba E, Jourdan L, Talbi E-G (2010) Multi-swarm optimization for dynamic combinatorial problems: a case study on dynamic vehicle routing problem. In: Dorigo M et al (eds) ANTS 2010. LNCS, vol 6234. Springer, Berlin/Heidelberg, pp 227–238
90.
Khouadjia MR, Jourdan L, Talbi E-G (2010) Adaptive particle swarm for solving the dynamic vehicle routing problem. In: Proceedings of 2010 IEEE/ACS international conference on computer systems and applications (AICCSA), Hammamet, 16–19 May 2010, pp 1–8
91.
Khouadjia MR, Sarasola B, Alba E, Jourdan L, Talbi E-G (2012) A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests. Appl Soft Comput 12:1426–1439
92.
Kim B-I, Son S-J (2012) A probability matrix based particle swarm optimization for the capacitated vehicle routing problem. J Intell Manuf 23(4):1119–1126
93.
Kou M, Ye C, Chen Z (2011) A bee evolutionary particle swarm optimization algorithm for vehicle routing problem. In: Proceedings of 2011 6th IEEE joint international information technology and artificial intelligence conference (ITAIC), Chongqing, vol 2, 20–22 Aug 2011, pp 398–401
94.
Kumar RS, Kondapaneni K, Dixit V, Goswami A, Thakur LS, Tiwari MK (2016) Multi-objective modeling of production and pollution routing problem with time window: a self-learning particle swarm optimization approach. Comput Ind Eng 99:29–40
95.
Kuo RJ, Zulvia FE, Suryadi K (2012) Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand – a case study on garbage collection system. Appl Math Comput 219:2574–2588
96.
Lahyani R, Khemakhem M, Semet F (2015) Rich vehicle routing problems: from a taxonomy to a definition. Eur J Oper Res 241:1–14
97.
Laporte G (1988) Location routing problems. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North Holland, Amsterdam, pp 163–198
98.
Laporte G, Semet F (2002) Classical heuristics for the capacitated VRP. In: Toth P, Vigo D (eds) The vehicle routing problem. Monographs on discrete mathematics and applications. SIAM, Philadelphia, pp 109–128
99.
Laporte G, Nobert Y, Taillefer S (1988) Solving a family of multi-depot vehicle routing and location routing problems. Transp Sci 22:161–172
100.
Laporte G, Gendreau M, Potvin, J-Y, Semet F (2000) Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res 7:285–300
101.
Li Y, Li D, Wang D ( 2012) Quantum-behaved particle swarm optimization algorithm based on border mutation and chaos for vehicle routing problem. In: Tan Y, Shi Y, Ji Z (eds) ICSI 2012, Part I. LNCS, vol 7331, Springer, Berlin/Heidelberg, pp 63–73
102.
Lichtblau D (2002) Discrete optimization using mathematica. In: Callaos N, Ebisuzaki T, Starr B, Abe JM, Lichtblau D (eds) World multi-conference on systemics, cybernetics and informatics (SCI 2002), vol 16. International Institute of Informatics and Systemics, pp 169–174
103.
Lin C, Choy KL, Ho GTS, Chung SH, Lam HY (2014) Survey of green vehicle routing problem: past and future trends. Expert Syst Appl 41:1118–1138
104.
105.
Liu X, Jiang W, Xie J (2009) Vehicle routing problem with time windows: a hybrid particle swarm optimization approach. In: Proceedings of 2009 fifth international conference on natural computation, Tianjin, 14–16 Aug 2009, pp 502–506
106.
Liu SC, Lu MC, Chung CH (2016) A hybrid heuristic method for the periodic inventory routing problem. Int J Adv Manuf Technol 85:2345–2352
107.
Marinakis Y (2015) An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands. Appl Soft Comput 37:680–701
108.
Marinakis Y, Marinaki M (2008) A particle swarm optimization algorithm with path relinking for the location routing problem. J Math Model Algorithms 7(1):59–78
109.
Marinakis Y, Marinaki M (2010) A hybrid genetic – particle swarm optimization algorithm for the vehicle routing problem. Expert Syst Appl 37:1446–1455
110.
Marinakis Y, Marinaki M (2012) A hybrid particle swarm optimization algorithm for the open vehicle routing problem. In: Dorigo M et al (eds) ANTS 2012. LNCS, vol 7461. Springer, Berlin/Heidelberg, pp 180–187
111.
Marinakis Y, Marinaki M (2013) Combinatorial neighborhood topology particle swarm optimization algorithm for the vehicle routing problem. In: Middendorf M, Blum C (eds) EvoCOP 2013. LNCS, vol 7832, pp 133–144
112.
Marinakis Y, Marinaki M (2013) Combinatorial expanding neighborhood topology particle swarm optimization for the vehicle routing problem with stochastic demands. In: Proceedings of GECCO 2013, genetic and evolutionary computation conference, Amsterdam, 6–10 July 2013, pp 49–56
113.
Marinakis Y, Migdalas Á (2002) Heuristic solutions of vehicle routing problems in supply chain management. In: Pardalos PM, Migdalas A, Burkard R (eds) Combinatorial and global optimization. World Scientific Publishing Co, Singapore, pp 205–236
114.
Marinakis Y, Migdalas A, Pardalos PM (2005) Expanding neighborhood GRASP for the traveling salesman problem. Comput Optim Appl 32:231–257
115.
Marinakis Y, Migdalas A, Pardalos PM (2009) Multiple phase neighborhood search GRASP based on lagrangean relaxation and random backtracking Lin-Kernighan for the traveling salesman problem. J Comb Optim 17:134–156
116.
Marinakis Y, Marinaki M, Dounias G (2010) A hybrid particle swarm optimization algorithm for the vehicle routing problem. Eng Appl Artif Intel 23:463–472
117.
Marinakis Y, Iordanidou G, Marinaki M (2013) Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl Soft Comput 13(4):1693–1704
118.
Marinakis Y, Marinaki M, Migdalas A (2014) An adaptive particle swarm optimization algorithm for the vehicle routing problem with time windows. In: Proceedings of LOT 2014, logistics, optimization and transportation conference, Molde, 1–2 Nov 2014
119.
Min H, Jayaraman V, Srivastava R (1998) Combined location-routing problems: a synthesis and future research directions. Eur J Oper Res 108:1–15
120.
MirHassani SA, Abolghasemi N (2011) A particle swarm optimization algorithm for open vehicle routing problem. Expert Syst Appl 38:11547–11551
121.
Moghaddam BF, Ruiz R, Sadjadi SJ (2012)Vehicle routing problem with uncertain demands: an advanced particle swarm algorithm. Comput Ind Eng 62:306–317
122.
Montoya-Torres JR, Franco JL, Isaza SN, Jimenez HF, Herazo-Padilla N (2015) A literature review on the vehicle routing problem with multiple depots. Comput Ind Eng 79: 115–129
123.
Mosheiov G (1998) Vehicle routing with pickup and delivery: tour – partitioning heuristics. Comput Ind Eng 34:669–684
124.
Mu \(\tilde {n}\)oz-Zavala A, Hern \(\acute {a}\)ndez-Aguirre A, Villa-Diharce E (2009) Particle evolutionary swarm multi-objective optimization for vehicle routing problem with time windows. In: Coello Coello CA et al (eds) Swarm intelligence for multi-objective problems in data mining. SCI, vol 242. Springer, Berlin/Heidelberg, pp 233–257
125.
Muthuswamy S, Lam SS (2011) Discrete particle swarm optimization for the team orienteering problem. Memetic Comput 3:287–303
126.
Nagy G, Salhi S (2007) Location-routing: issues, models and methods. Eur J Oper Res 177:649–672
127.
Ngueveu SU, Prins C, Calvo RW (2010) An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput Oper Res 37(11):1877–1885
128.
Norouzi N, Tavakkoli-Moghaddam R, Ghazanfari M, Alinaghian M, Salamatbakhsh A (2012) A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization. Netw Spat Econ 12(4):609–633
129.
Norouzi N, Sadegh-Amalnick M, Mehdi A (2015) Evaluating of the particle swarm optimization in a periodic vehicle routing problem. Measurement 62:162–169
130.
131.
Okulewicz M, Ma \(\acute {n}\)dziuk J (2013) Application of particle swarm optimization algorithm to dynamic vehicle routing problem. In: Rutkowski L et al (eds) ICAISC 2013, Part II. LNAI, vol 7895. Springer, Berlin/Heidelberg, pp 547–558
132.
Okulewicz M, Ma \(\acute {n}\)dziuk J (2017) The impact of particular components of the PSO-based algorithm solving the dynamic vehicle routing problem. Appl Soft Comput 58:586–604
133.
134.
Peng Y (2009) Hybrid particle swarm optimization for vehicle routing problem with reverse logistics. In: Proceedings of 2009 international conference on intelligent human-machine systems and cybernetics, Hangzhou, 26–27 Aug 2009, pp 462–465
135.
Peng Y, Chen Z-X (2009) Two-phase particle swarm optimization for multi-depot location-routing problem. In: Proceedings of 2009 international conference on new trends in information and service science, Beijing, 30 June 2009–2 July 2009, pp 240–245
136.
Peng Y, Chen J (2010) Vehicle routing problem with fuzzy demands and the particle swarm optimization solution. In: Proceedings of 2010 international conference on management and service science (MASS), Wuhan, 24–26 Aug 2010, pp 1–4
137.
Peng Y, Zhu H-Y (2008) Research on vehicle routing problem with stochastic demand and PSO-DP algorithm with inver-over operator. Syst Eng Theory Pract (SETP) 28(10):76–81
138.
Pereira FB, Tavares J (2008) Bio-inspired algorithms for the vehicle routing problem. Studies in computational intelligence, vol 161. Springer, Berlin/Heideberg
139.
Perwira Redi AAN, Maghfiroh MFN, Yu VF (2013) Discrete particle swarm optimization with path-relinking for solving the open vehicle routing problem with time windows. In: Lin Y-K et al (eds) Proceedings of the institute of industrial engineers Asian conference 2013. Springer Science+Business Media, Singapore, pp 853–859. https://​doi.​org/​10.​1007/​978-981-4451-98-7_​102
140.
Pillac V, Gendreau M, Gueret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur J Oper Res 225:1–11
141.
Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization. An overview. Swarm Intell 1:33–57
142.
Powell WB, Jaillet P, Odoni A (1995) Stochastic and dynamic networks and routing. In: Ball MO, Magnanti TL, Momma CL, Nemhauser GL (eds) Network routing. Handbooks in operations research and management science, vol 8. Elsevier Science B V, Amsterdam, pp 141–295
143.
Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31:1985–2002
144.
Prodhon C, Prins C (2014) A survey of recent research on location-routing problems. Eur J Oper Res 238:1–17
145.
Psaraftis HN (1988) Dynamic vehicle routing problems. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North Holland, Amsterdam, pp 223–248
146.
Psaraftis HN (1995) Dynamic vehicle routing: status and prospects. Ann Oper Res 61: 143–164
147.
Qi C (2011) Application of improved discrete particle swarm optimization in logistics distribution routing problem. Proc Eng Adv Control Eng Inf Sci 15:3673–3677
148.
Rabbani M, Manavizadeh N, Shamekhi A (2013) A particle swarm optimization method for periodic vehicle routing problem with pickup and delivery in transportation. Adv Railw Eng Int J 1(1):51–60
149.
Renaud J, Laporte G, Boctor FF (1996) A Tabu search heuristic for the multidepot vehicle routing problem. Comput Oper Res 23(3):229–235
150.
Ronen D (1983) Cargo ships routing and scheduling: survey of models and problems. Eur J Oper Res 12:119–126
151.
Ronen D (1993) Ships scheduling: the last decade. Eur J Oper Res 71(3):325–333
152.
Sariklis D, Powell S (2000) A heuristic method for the open vehicle routing problem. J Oper Res Soc 51(5):564–573
153.
Sevkli Z, Sevilgen FE (2010) Discrete particle swarm optimization for the orienteering problem. In: Proceedings of 2010 IEEE Congress on Evolutionary Computation (CEC), Barcelona, 18–23 July 2010, pp 1–8
154.
Sevkli AZ, Sevilgen FE (2012) Discrete particle swarm optimization for the team orienteering problem. Turk J Electr Eng Comput Sci 20(2):231–239
155.
Shao Z-J, Gao S-P, Wang S-S (2009) A hybrid particle swarm optimization algorithm for vehicle routing problem with stochastic travel time. In: Cao B-Y, Zhang C-Y, Li T-F (eds) Fuzzy information and engineering. ASC, vol 54. Springer, Berlin/Heidelberg, pp 566–574
156.
Shen H, Zhu Y, Liu T, Jin L (2009) Particle swarm optimization in solving vehicle routing problem. In: Proceedings 2009 second international conference on intelligent computation technology and automation, Changsha, 10–11 Oct 2009, pp 287–291
157.
Shi Y, Eberhart R (1998) A modified particle swarm optimizer. In: Proceedings of 1998 IEEE world congress on computational intelligence, pp 69–73
158.
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265
159.
Solomon MM, Desrosiers J (1988) Time window constrained routing and scheduling problems. Transp Sci 22(1):1–13
160.
Solomon MM, Baker EK, Schaffer JR (1988) Vehicle routing and scheduling problems with time windows constraints. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North Holland, Amsterdam, pp 85–105
161.
Sombuntham P, Kachitvichayanukul V (2010) A particle swarm optimization algorithm for multi-depot vehicle routing problem with pickup and delivery Requests. In: Proceedings of the international multiconference of engineers and computer scientists (IMECS 2010), vol III, Hong Kong, 17–19 Mar 2010. ISBN:978-988-18210-5-8
162.
Stewart WR, Golden BL (1983) Stochastic vehicle routing: a comprehensive approach. Eur J Oper Res 14:371–385
163.
Tang H (2011) Vehicle route optimization in logistics distribution based on extension-coded particle swarm algorithm. In: Proceedings of 2011 international conference on computer science and network technology, Harbin, 24–26 Dec 2011, pp 2350–2354
164.
Tang C, Wang T (2011) An improved particle swarm optimization for the vehicle routing problem with simultaneous deliveries and pick-ups. In: Shen G, Huang X (eds) CSIE 2011, Part II. CCIS, vol 153. Springer, Berlin/Heidelberg, pp 294–300
165.
Tarantilis CD (2005) Solving the vehicle routing problem with adaptive memory programming methodology. Comput Oper Res 32(9):2309–2327
166.
Tavakkoli Moghaddam R, Mohmmad Zohrevand A, Rafiee K (2012) Solving a new mathematical model for a periodic vehicle routing problem by particle swarm optimization. Transp Res J 1:77–87
167.
Tavakoli MM, Sami A (2013) Particle swarm optimization in solving capacitated vehicle routing problem. Buletin Teknik Elektro dan Informatika (Bull Electr Eng Inf) 2(4):252–257
168.
Ting C-J, Wu K-C, Chou H (2014) Particle swarm optimization algorithm for the berth allocation problem. Expert Syst Appl 41:1543–1550
169.
Tlili T, Faiz S, Krichen S (2014) A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem. Procedia – social and behavioral sciences, 2nd world conference on business, economics and management-WCBEM 2013, vol 109, pp 779–783
170.
Toth P, Vigo D (2002) The vehicle routing problem. Monographs on discrete mathematics and applications. SIAM, Philadelphia
171.
Toth P, Vigo D (2002) VRP with backhauls. In: Toth P, Vigo D (eds) The vehicle routing problem. Monographs on discrete mathematics and applications. SIAM, Philadelphia, pp 195–224
172.
Toth P, Vigo D (2014) Vehicle routing: problems, methods and applications, 2nd edn. MOS-SIAM series on optimization. SIAM, Philadelphia
173.
Vahdani B, Tavakkoli-Moghaddam R, Zandieh M, Razmi J (2012) Vehicle routing scheduling using an enhanced hybrid optimization approach. J Intel Manuf 23(3):759–774 CrossRef
174.
Vansteenwegen P, Souffriau W, Berghe GV, Oudheusden DV (2009) A guided local search metaheuristic for the team orienteering problem. Eur J Oper Res 196:118–127 CrossRef
175.
Varthanan PA, Murugan N, Kumar GM (2012) A simulation based heuristic discrete particle swarm algorithm for generating integrated production-distribution plan. Appl Soft Comput 12:3034–3050 CrossRef
176.
Venkatesan SR, Logendran D, Chandramohan D (2011) Optimization of capacitated vehicle routing problem using PSO. Int J Eng Sci Technol (IJEST) 3(10):7469–7469
177.
Vidal T, Crainic TG, Gendreau M, Prins C (2013) Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur J Oper Res 231(1):1–21 MathSciNetCrossRef
178.
Vigo D (1996) A heuristic algorithm for the asymmetric capacitated vehicle routing problem. Eur J Oper Res 89(1):108–126 CrossRef
179.
Wang T-J, Wu K-J (2012) Adaptive particle swarm optimization based on population entropy for MDVRPTW. In: Proceedings of 2012 2nd international conference on computer science and network technology, Changchun, 29–31 Dec 2012, pp 753–756
180.
Wang W, Wu B, Zhao Y, Feng D (2006) Particle swarm optimization for open vehicle routing problem. In: Huang D-S, Li K, Irwin GW (eds) ICIC 2006. LNAI, vol 4114. Springer, Berlin/Heidelberg, pp 999–1007
181.
Wang S, Wang L, Yuan H, Ge M, Niu B, Pang W, Liu Y (2009) Study on multi-depots vehicle scheduling problem and its two-phase particle swarm optimization. In: Huang D-S et al (eds) ICIC 2009. LNAI, vol 5755. Springer, Berlin/Heidelberg, pp 748–756 CrossRef
182.
Wang Z, Li J, Fan J, Fan C (2010) Research on improved hybrid particle swarm optimization for vehicle routing problem with time windows. In: Proceedings of 2010 international conference on artificial intelligence and computational intelligence, Sanya, 23–24 Oct 2010, pp 179–183
183.
Wang B, Wang K, Bao F, Zhang L, Shen L (2012) Mixed climbing particle swarm algorithm in the VRP. In: Proceedings of 2012 second international conference on business computing and global informatization, pp 554–557
184.
Wei R, Zhang T, Tang H (2010) An improved particle swarm optimization algorithm for vehicle routing problem with simultaneous pickup and delivery. In: Zhu R et al (eds) ICICA 2010, Part I. CCIS, vol 105. Springer, Berlin/Heidelberg, pp 430–436
185.
Xu J, Yan F, Li S (2011) Vehicle routing optimization with soft time windows in a fuzzy random environment. Transp Res E 47:1075–1091 CrossRef
186.
Yan F, Xu M, Yu H (2015) The vehicle routing optimization with uncertain demands and traveling time. In: Xu J et al (eds) Proceedings of the ninth international conference on management science and engineering Management. Advances in intelligent systems and computing, vol 362, pp 267–274
187.
Yang SY, Wang M, Jiao LC (2004) A quantum particle swarm optimization. In: Proceedings of the 2004 IEEE congress on evolutionary computation, vol 1, pp 320–324
188.
Yao B, Yu B, Hu P, Gao J (2016) An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot. Ann Oper Res 242: 303–320 MathSciNetCrossRef
189.
Yusoff M, Ariffin J, Mohamed A (2011) A multi-valued discrete particle swarm optimization for the evacuation vehicle routing problem. In: Tan Y et al (eds) ICSI 2011, Part I. LNCS, vol 6728. Springer, Berlin/Heidelberg, pp 182–193
190.
Yusoff M, Ariffin J, Mohamed A (2012) DPSO based on random particle priority value and decomposition procedure as a searching strategy for the evacuation vehicle routing problem. In: Huang T et al (eds) ICONIP 2012, Part III. LNCS, vol 7665. Springer, Berlin/Heidelberg, pp 678–685
191.
Yusoff M, Ariffin J, Mohamed A (2015) DPSO based on a min-max approach and clamping strategy for the evacuation vehicle assignment problem. Neurocomputing 148:30–38 CrossRef
192.
Zeimpekis VS, Tarantilis CD, Giaglis GM, Minis I (eds) (2007) Dynamic fleet management – concepts, systems, algorithms and case studies. Book series: operations research/computer science interfaces series, vol 38. Springer
193.
Zhan Z-H, Zhang J (2009) Discrete particle swarm optimization for multiple destination routing problems. In: Giacobini M et al (eds) EvoWorkshops 2009. LNCS, vol 5484. Springer, Berlin/Heidelberg, pp 117–122
194.
Zhang W, Ye J (2010) An improved particle swarm optimization for the multi-depot vehicle routing problem. In: Proceedings of 2010 international conference on E-business and E-government, Guangzhou, 7–9 May 2010, pp 3188–3191
195.
Zhang N-Z, Sun G-H, Wu Y-H, Geng, F-H (2009) A modified particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. In: Proceedings of the 7th Asian control conference, Hong Kong, 27–29 Aug 2009, pp 1679–1684
196.
Zhang T, Chaovalitwongse WA, Zhang Y (2012) Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Comput Oper Res 39:2277–2290 MathSciNetCrossRef
197.
Zhang L, Li Y, Fei T, Chen X, Ting G (2014) Research of emergency logistics routing optimization based on particle swarm optimization. In: Patnaik S, Li X (eds) Proceedings of international conference on computer science and information technology. Advances in intelligent systems and computing, vol 255, Springer, pp 415–421. https://​doi.​org/​10.​1007/​978-81-322-1759-6_​48
198.
Zhao Y, Li C, Zhang J-L, Ren X, Ren W (2011) Research on vehicle routing problem with stochastic demand based on multi-objective method. In: Huang D-S et al (eds) ICIC 2011. LNCS, vol 6838. Springer, Berlin/Heidelberg, pp 153–161
199.
Zhen T, Zhu Y, Zhang Q (2009) A particle swarm optimization algorithm for the open vehicle routing problem. In: Proceedings of 2009 international conference on environmental science and information application technology, Wuhan, 4–5 July 2009, pp 560–563
200.
Zhu Q, Qian L, Li Y, Zhu S (2006) An improved particle swarm optimization algorithm for vehicle routing problem with time windows. In: Proceedings of 2006 IEEE congress on evolutionary computation, Vancouver, 16–21 July 2006, pp 1386–1390
201.
Zong X, Xiong S, Fang Z (2014) A conflict-congestion model for Pedestrian-vehicle mixed evacuation based on discrete particle swarm optimization algorithm. Comput Oper Res 44: 1–12 CrossRef
Metadata
Title
Particle Swarm Optimization for the Vehicle Routing Problem: A Survey and a Comparative Analysis
Authors
Yannis Marinakis
Magdalene Marinaki
Athanasios Migdalas
Copyright Year
2018
Book
Handbook of Heuristics

Print ISBN: 978-3-319-07123-7

Electronic ISBN: 978-3-319-07124-4

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-07124-4_42

Premium Partner

    Image Credits