|
|
|
An improved fireworks algorithm for the capacitated vehicle routing problem |
Weibo YANG, Liangjun KE( ) |
| State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an 710049, China |
|
|
|
|
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
|
|
Corresponding Author(s):
Liangjun KE
|
|
Just Accepted Date: 18 July 2017
Online First Date: 06 July 2018
Issue Date: 24 April 2019
|
|
| 1 |
G BDantzig, J HRamser. The truck dispatching problem. Management Science, 1959, 6(1): 80–91
https://doi.org/10.1287/mnsc.6.1.80
|
| 2 |
RFukasawa, HLongo, JLysgaard, M P de Aragão, MReis, EUchoa, R F Werneck. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 2006, 106(3): 491–511
https://doi.org/10.1007/s10107-005-0644-x
|
| 3 |
RBaldacci, N Christofides, AMingozzi. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 2008, 115(2): 351–385
https://doi.org/10.1007/s10107-007-0178-5
|
| 4 |
GClarke, J WWright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12(4): 568–581
https://doi.org/10.1287/opre.12.4.568
|
| 5 |
B LGolden, T L Magnanti, H QNguyen. Implementing vehicle routing algorithms. Networks, 1977, 7(2): 113–148
https://doi.org/10.1002/net.3230070203
|
| 6 |
KAltinkemer, BGavish. Parallel savings based heuristics for the delivery problem. Operations Research, 1991, 39(3): 456–469
https://doi.org/10.1287/opre.39.3.456
|
| 7 |
B EGillett, L RMiller. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 1974, 22(2): 340–349
https://doi.org/10.1287/opre.22.2.340
|
| 8 |
J EBeasley. Route first-cluster second methods for vehicle routing. Omega, 1983, 11(4): 403–408
https://doi.org/10.1016/0305-0483(83)90033-6
|
| 9 |
SLin. Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 1965, 44(10): 2245–2269
https://doi.org/10.1002/j.1538-7305.1965.tb04146.x
|
| 10 |
G AKindervater, M W Savelsbergh. Vehicle routing: handling edge exchanges. In: Aarts E, Lenstra J, eds. Local Search in Combinatorial Optimization. Chichester: Wiley, 1997, 337–360
|
| 11 |
PToth, DVigo. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002
https://doi.org/10.1137/1.9780898718515
|
| 12 |
EAlba, B Dorronsoro. Computing nine new best-so-far solutions for capacitated VRP with a cellular genetic algorithm. Information Processing Letters, 2006, 98(6): 225–230
https://doi.org/10.1016/j.ipl.2006.02.006
|
| 13 |
DMester, O Bräysy. Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers & Operations Research, 2007, 34(10): 2964–2975
https://doi.org/10.1016/j.cor.2005.11.006
|
| 14 |
YNagata, O Bräysy. Edge assembly-based memetic algorithm for the capacitated vehicle routing problem. Networks, 2009, 54(4): 205–215
https://doi.org/10.1002/net.20333
|
| 15 |
BBullnheimer, R FHartl, CStrauss. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 1999, 89: 319–328
https://doi.org/10.1023/A:1018940026670
|
| 16 |
J EBell, P R McMullen. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 2004, 18(1): 41–48
https://doi.org/10.1016/j.aei.2004.07.001
|
| 17 |
MReimann, K Doerner, R FHartl. D-ants: savings based ants divide and conquer the vehicle routing problem. Computers & Operations Research, 2004, 31(4): 563–591
https://doi.org/10.1016/S0305-0548(03)00014-5
|
| 18 |
BYu, Z ZYang, BYao. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009, 196(1): 171–176
https://doi.org/10.1016/j.ejor.2008.02.028
|
| 19 |
CPrins. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 2004, 31(12): 1985–2002
https://doi.org/10.1016/S0305-0548(03)00158-8
|
| 20 |
B MBaker, M Ayechew. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 2003, 30(5): 787–800
https://doi.org/10.1016/S0305-0548(02)00051-5
|
| 21 |
S RThangiah, I HOsman, TSun. 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 |
TVidal, T G Crainic, MGendreau, NLahrichi, WRei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 2012, 60(3): 611–624
https://doi.org/10.1287/opre.1120.1048
|
| 23 |
YMarinakis, M Marinaki, GDounias. A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence, 2010, 23(4): 463–472
https://doi.org/10.1016/j.engappai.2010.02.002
|
| 24 |
T JAi, V Kachitvichyanukul. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering, 2009, 56(1): 380–387
https://doi.org/10.1016/j.cie.2008.06.012
|
| 25 |
WSzeto, YWu, S CHo. An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 2011, 215(1): 126–135
https://doi.org/10.1016/j.ejor.2011.06.006
|
| 26 |
A SAlfa, S SHeragu, MChen. A 3-opt based simulated annealing algorithm for vehicle routing problems. Computers & Industrial Engineering, 1991, 21(1–4): 635–639
https://doi.org/10.1016/0360-8352(91)90165-3
|
| 27 |
I HOsman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 1993, 41(4): 421–451
https://doi.org/10.1007/BF02023004
|
| 28 |
RTavakkoli-Moghaddam, N Safaei, YGholipour. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 2006, 176(2): 445–454
https://doi.org/10.1016/j.amc.2005.09.040
|
| 29 |
ÉTaillard. Parallel iterative search methods for vehicle routing problems. Networks, 1993, 23(8): 661–673
https://doi.org/10.1002/net.3230230804
|
| 30 |
MGendreau, AHertz, GLaporte. A tabu search heuristic for the vehicle routing problem. Management Science, 1994, 40(10): 1276–1290
https://doi.org/10.1287/mnsc.40.10.1276
|
| 31 |
PToth, DVigo. The granular tabu search and its application to the vehicle-routing problem. INFORMS Journal on Computing, 2003, 15(4): 333–346
https://doi.org/10.1287/ijoc.15.4.333.24890
|
| 32 |
D SLai, O C Demirag, J MLeung. 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
https://doi.org/10.1016/j.tre.2015.12.001
|
| 33 |
CPrins. 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
https://doi.org/10.1007/978-3-540-85152-3_2
|
| 34 |
P H VPenna, A Subramanian, L SOchi. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 2013, 19(2): 201–232
https://doi.org/10.1007/s10732-011-9186-y
|
| 35 |
OBräysy. A reactive variable neighborhood search for the vehiclerouting problem with time windows. INFORMS Journal on Computing, 2003, 15(4): 347–368
https://doi.org/10.1287/ijoc.15.4.347.24896
|
| 36 |
JKytöjoki, T Nuortio, OBräysy, MGendreau. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Computers & Operations Research, 2007, 34(9): 2743–2757
https://doi.org/10.1016/j.cor.2005.10.010
|
| 37 |
SRopke, D Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 2006, 40(4): 455–472
https://doi.org/10.1287/trsc.1050.0135
|
| 38 |
YTan, YZhu. Fireworks algorithm for optimization. In: Proceedings of International Conference on Swarm Intelligence. 2010, 355–364
https://doi.org/10.1007/978-3-642-13495-1_44
|
| 39 |
YPei, SZheng, YTan, H Takagi. 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
https://doi.org/10.1109/ICSMC.2012.6377916
|
| 40 |
SZheng, A Janecek, YTan. Enhanced fireworks algorithm. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 2069–2077
https://doi.org/10.1109/CEC.2013.6557813
|
| 41 |
SZheng, A Janecek, JLi , YTan. Dynamic search in fireworks algorithm. In: Proceedings of IEEE Congress on Evolutionary Computation. 2014, 3222–3229
https://doi.org/10.1109/CEC.2014.6900485
|
| 42 |
Y JZheng, X LXu, H FLing, S Y Chen. A hybrid fireworks optimization method with differential evolution operators. Neurocomputing, 2015, 148: 75–82
https://doi.org/10.1016/j.neucom.2012.08.075
|
| 43 |
AJanecek, YTan. Swarm intelligence for non-negative matrix factorization. International Journal of Swarm Intelligence Research, 2011, 2(4): 12–34
https://doi.org/10.4018/jsir.2011100102
|
| 44 |
WHe, GMi, YTan. Parameter optimization of local-concentration model for spam detection by using fireworks algorithm. In: Proceedings of International Conference on Swarm Intelligence. 2013, 439–450
https://doi.org/10.1007/978-3-642-38703-6_52
|
| 45 |
Y JZheng, QSong, S YChen. Multiobjective fireworks optimization for variable-rate fertilization in oil crop production. Applied Soft Computing, 2013, 13(11): 4253–4263
https://doi.org/10.1016/j.asoc.2013.07.004
|
| 46 |
NPholdee, S Bureerat. Comparative performance of meta-heuristic algorithms for mass minimisation of trusses with dynamic constraints. Advances in Engineering Software, 2014, 75: 1–13
https://doi.org/10.1016/j.advengsoft.2014.04.005
|
| 47 |
K SReddy, L KPanwar, RKumar, B K Panigrahi. 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
https://doi.org/10.1007/s40565-016-0195-6
|
| 48 |
BSaravanan, CKumar, DKothari. A solution to unit commitment problem using fire works algorithm. International Journal of Electrical Power & Energy Systems, 2016, 77: 221–227
https://doi.org/10.1016/j.ijepes.2015.11.030
|
| 49 |
ZLiu, ZFeng, LKe. Fireworks algorithm for the multi-satellite control resource scheduling problem. In: Proceedings of IEEE Congress on Evolutionary Computation. 2015, 1280–1286
https://doi.org/10.1109/CEC.2015.7257036
|
| 50 |
N HAbdulmajeed, MAyob. A firework algorithm for solving capacitated vehicle routing problem. International Journal of Advancements in Computing Technology, 2014, 6(1): 79–86
|
| 51 |
YTan. Discrete firework algorithm for combinatorial optimization problem. In: Tang Y, eds. Fireworks Algorithm. Berlin: Springer- Verlag, 2015, 209–226
https://doi.org/10.1007/978-3-662-46353-6_13
|
| 52 |
TStützle, H HHoos. Max–min ant system. Future Generation Computer Systems, 2000, 16(8): 889–914
https://doi.org/10.1016/S0167-739X(00)00043-1
|
| 53 |
OBräysy, M Gendreau. Vehicle routing problem with time windows, part I: route construction and local search algorithms. Transportation Science, 2005, 39(1): 104–118
https://doi.org/10.1287/trsc.1030.0056
|
| 54 |
NChristofides, A Mingozzi, PToth. The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, et al., eds. Combinatorial Optimization. Chichester: Wiley, 1979, 315–338
|
| 55 |
B LGolden, E AWasil, J PKelly, I M Chao. 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
https://doi.org/10.1007/978-1-4615-5755-5_2
|
| 56 |
CLee, ZLee, SLin, K Ying. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 2010, 32(1): 88–95
https://doi.org/10.1007/s10489-008-0136-9
|
| 57 |
JLysgaard, A N Letchford, R WEglese. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 2004, 100(2): 423–445
https://doi.org/10.1007/s10107-003-0481-8
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
