An improved fireworks algorithm for the capacitated vehicle routing problem

Abstract

The capacitated vehicle routing problem (CVRP), which aims at minimizing travel costs, is a wellknown NP-hard combinatorial optimization. Owing to its hardness, many heuristic search algorithms have been proposed to tackle this problem. This paper explores a recently proposed heuristic algorithm named the fireworks algorithm (FWA), which is a swarm intelligence algorithm. We adopt FWA for the combinatorial CVRP problem with severalmodifications of the original FWA: it employs a new method to generate “sparks” according to the selection rule, and it uses a new method to determine the explosion amplitude for each firework. The proposed algorithm is compared with several heuristic search methods on some classical benchmark CVRP instances. The experimental results show a promising performance of the proposed method.We also discuss the strengths and weaknesses of our algorithm in contrast to traditional algorithms.

Keywords

fireworks algorithm / vehicle routing problem / computational intelligence

References

[1] Dantzig G B, Ramser J H. The truck dispatching problem. Management Science, 1959, 6(1): 80–91

[2] Fukasawa R, Longo H, Lysgaard J, de Aragão M P, Reis M, Uchoa E, Werneck R F. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 2006, 106(3): 491–511

[3] Baldacci R, Christofides N, Mingozzi A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 2008, 115(2): 351–385

[4] Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12(4): 568–581

[5] Golden B L, Magnanti T L, Nguyen H Q. Implementing vehicle routing algorithms. Networks, 1977, 7(2): 113–148

[6] Altinkemer K, Gavish B. Parallel savings based heuristics for the delivery problem. Operations Research, 1991, 39(3): 456–469

[7] Gillett B E, Miller L R. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 1974, 22(2): 340–349

[8] Beasley J E. Route first-cluster second methods for vehicle routing. Omega, 1983, 11(4): 403–408

[9] Lin S. Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 1965, 44(10): 2245–2269

[10] Kindervater G A, Savelsbergh M W. Vehicle routing: handling edge exchanges. In: Aarts E, Lenstra J, eds. Local Search in Combinatorial Optimization. Chichester: Wiley, 1997, 337–360

[11] Toth P, Vigo D. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002

[12] Alba E, Dorronsoro B. Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm. Information Processing Letters, 2006, 98(6): 225–230

[13] Mester D, Bräysy O. Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers & Operations Research, 2007, 34(10): 2964–2975

[14] Nagata Y, Bräysy O. Edge assembly-based memetic algorithm for the capacitated vehicle routing problem. Networks, 2009, 54(4): 205–215

[15] Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 1999, 89: 319–328

[16] Bell J E, McMullen P R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 2004, 18(1): 41–48

[17] Reimann M, Doerner K, Hartl R F. D-ants: savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 2004, 31(4): 563–591

[18] Yu B, Yang Z Z, Yao B. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009, 196(1): 171–176

[19] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12): 1985–2002

[20] Baker B M, Ayechew M. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 2003, 30(5): 787–800

[21] Thangiah S R, Osman I H, Sun T. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Technical Report SRU CpSc-TR-94-27, 1994

[22] Vidal T, Crainic T G, Gendreau M, Lahrichi N, Rei W. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 2012, 60(3): 611–624

[23] Marinakis Y, Marinaki M, Dounias G. A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 2010, 23(4): 463–472

[24] Ai T J, Kachitvichyanukul V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 2009, 56(1): 380–387

[25] Szeto W, Wu Y, Ho S C. An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 2011, 215(1): 126–135

[26] Alfa A S, Heragu S S, Chen M. A 3-opt based simulated annealing algorithm for vehicle routing problems. Computers & Industrial Engineering, 1991, 21(1–4): 635–639

[27] Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 1993, 41(4): 421–451

[28] Tavakkoli-Moghaddam R, Safaei N, Gholipour Y. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 2006, 176(2): 445–454

[29] Taillard É. Parallel iterative search methods for vehicle routing problems. Networks, 1993, 23(8): 661–673

[30] Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem. Management Science, 1994, 40(10): 1276–1290

[31] Toth P, Vigo D. The granular tabu search and its application to the vehicle-routing problem. INFORMS Journal on Computing, 2003, 15(4): 333–346

[32] Lai D S, Demirag O C, Leung J M. A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 2016, 86: 32–52

[33] Prins C. A GRASP × evolutionary local search hybrid for the vehicle routing problem. In: Pereira F B, Tavares J, eds. Bio-inspired algorithms for the Vehicle Routing Problem. Berlin: Springer-Verlag, 2009, 35–53

[34] Penna P H V, Subramanian A, Ochi L S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 2013, 19(2): 201–232

[35] Bräysy O. A reactive variable neighborhood search for the vehiclerouting problem with time windows. INFORMS Journal on Computing, 2003, 15(4): 347–368

[36] Kytöjoki J, Nuortio T, Bräysy O, Gendreau M. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 2007, 34(9): 2743–2757

[37] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 2006, 40(4): 455–472

[38] Tan Y, Zhu Y. Fireworks algorithm for optimization. In: Proceedings of International Conference on Swarm Intelligence. 2010, 355–364

[39] Pei Y, Zheng S, Tan Y, Takagi H. An empirical study on influence of approximation approaches on enhancing fireworks algorithm. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. 2012, 1322–1327

[40] Zheng S, Janecek A, Tan Y. Enhanced fireworks algorithm. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 2069–2077

[41] Zheng S, Janecek A, Li J, Tan Y. Dynamic search in fireworks algorithm. In: Proceedings of IEEE Congress on Evolutionary Computation. 2014, 3222–3229

[42] Zheng Y J, Xu X L, Ling H F, Chen S Y. A hybrid fireworks optimization method with differential evolution operators. Neurocomputing, 2015, 148: 75–82

[43] Janecek A, Tan Y. Swarm intelligence for non-negative matrix factorization. International Journal of Swarm Intelligence Research, 2011, 2(4): 12–34

[44] He W, Mi G, Tan Y. Parameter optimization of local-concentration model for spam detection by using fireworks algorithm. In: Proceedings of International Conference on Swarm Intelligence. 2013, 439–450

[45] Zheng Y J, Song Q, Chen S Y. Multiobjective fireworks optimization for variable-rate fertilization in oil crop production. Applied Soft Computing, 2013, 13(11): 4253–4263

[46] Pholdee N, Bureerat S. Comparative performance of meta-heuristic algorithms for mass minimisation of trusses with dynamic constraints. Advances in Engineering Software, 2014, 75: 1–13

[47] Reddy K S, Panwar L K, Kumar R, Panigrahi B K. Distributed resource scheduling in smart grid with electric vehicle deployment using fireworks algorithm. Journal of Modern Power Systems and Clean Energy, 2016, 4(2): 188–199

[48] Saravanan B, Kumar C, Kothari D. A solution to unit commitment problem using fire works algorithm. International Journal of Electrical Power & Energy Systems, 2016, 77: 221–227

[49] Liu Z, Feng Z, Ke L. Fireworks algorithm for the multi-satellite control resource scheduling problem. In: Proceedings of IEEE Congress on Evolutionary Computation. 2015, 1280–1286

[50] Abdulmajeed N H, Ayob M. A firework algorithm for solving capacitated vehicle routing problem. International Journal of Advancements in Computing Technology, 2014, 6(1): 79–86

[51] Tan Y. Discrete firework algorithm for combinatorial optimization problem. In: Tang Y, eds. Fireworks Algorithm. Berlin: Springer- Verlag, 2015, 209–226

[52] Stützle T, Hoos H H. Max–min ant system. Future Generation Computer Systems, 2000, 16(8): 889–914

[53] Bräysy O, Gendreau M. Vehicle routing problem with time windows, part I: route construction and local search algorithms. Transportation Science, 2005, 39(1): 104–118

[54] Christofides N, Mingozzi A, Toth P. The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, et al., eds. Combinatorial Optimization. Chichester: Wiley, 1979, 315–338

[55] Golden B L, Wasil E A, Kelly J P, Chao I M. The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In: Crainic T G, Laporte G, eds. Fleet Management and Logistics. Springer US, 1998, 33–56

[56] Lee C, Lee Z, Lin S, Ying K. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 2010, 32(1): 88–95

[57] Lysgaard J, Letchford A N, Eglese R W. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 2004, 100(2): 423–445

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature