Improved Bat Algorithm for Vehicle Routing Problem

doi:10.23940/ijpe.19.01.p32.317325

Int J Performability Eng ›› 2019, Vol. 15 ›› Issue (1): 317-325.doi: 10.23940/ijpe.19.01.p32.317325

Previous Articles Next Articles

Improved Bat Algorithm for Vehicle Routing Problem

Yu Li^a^b, Qian Guo^b, and Jingsen Liu^c*()

a Institute of Management Science and Engineering, Henan University, Kaifeng, 475004, China
b Business School, Henan University, Kaifeng, 475004, China;c Institute of Intelligent Network system, Henan University, Kaifeng, 475004, China

Revised on ; Accepted on
Contact: Liu Jingsen E-mail:ljs@henu.edu.cn
About author:Yu Li received her PhD from University of Shanghai for Science and Technology. She is a professor of Institute of Management Science and Engineering, and Business School, Henan University. Her research interests include intelligence algorithms, electronic commerce, etc.|Qian Guo is a master degree candidate of Business School, Henan University. Her research interest is intelligence algorithm.|Jingsen Liu received his PhD from Northwestern Poly-technical University. He is a professor of Institute of Intelligent Network system, and College of Software, Henan University. His research interests include intelligence algorithm and network information security, etc.

Abstract

Abstract:

Vehicle routing problem (VRP) is the key issue of logistics system optimization. As a classical combinatorial optimization problem, it belonged to the typical NP-hard problem and remained unsolved. In this paper, the novel bat algorithm is proposed to solve VRP. The improvement is based on the combination of dynamic inertia weight and time factor. It can take full advantages of dynamic search by the random velocity and random step-size. Furthermore, with the real-number encoding approach, the discrete VRP can be converted into a quasi-continuous one. The procedure of the optimal searching in multidimensional continuous space can be implemented directly. Experimental results indicate that improved bat algorithm performs well for vehicle routing problem.

Key words: vehicle routing problem, bat algorithm, inertia weight, time factor, real-number encoding

Yu Li, Qian Guo, and Jingsen Liu. Improved Bat Algorithm for Vehicle Routing Problem [J]. Int J Performability Eng, 2019, 15(1): 317-325.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

Figures/Tables 8

Bat algorithm

Figure 1

Table 1

Table 2

Figure 2

Table 3

Table 4

Table 5

References 18

[1]	G.B. Dantzig and J. H. Ramser , “The Truck Dispatching Problem,” Management Science,Vol. 6, No. 1, pp. 80-91, 1959
[2]	N. Christofides, A. Mingozzi, P. Toth , “Exact Algorithms for the Vehicle Routing Problem based on Spanning Tree and Shortest Path Relaxations,” Mathematical Programming, Vol. 20, No. 1, pp. 255-282, 1981
[3]	F. Glover and M. Laguna , “Tabu Search,” General Information, Vol. 106, No. 2, pp. 221-25, 2006
[4]	D. E. Goldberg , “Genetic Algorithm in Search Optimization and Machine Learning,” Addison Wesley xiii, Vol. 7, pp. 2104-2116, 1989
[5]	L. M. Gambardella, E. D. Taillard, G. Agazzi , “A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, ” 1999
[6]	J. Brandão , “A Tabu Search Algorithm for the Open Vehicle Routing Problem,” European Journal of Operational Research, Vol. 157, No. 3, pp. 552-564, 2004
[7]	E. Choi and D. W. Tcha , “A Column Generation Approach to the Heterogeneous Fleet Vehicle Routing Problem,” Computers & Operations Research, Vol. 34, No. 7, pp. 2080-2095, 2007
[8]	G. Nagy and S. Salhi , “Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries,” European Journal of Operational Research, Vol. 162, No. 1, pp. 126-141, 2005
[9]	X. S. Yang , “A New Metaheuristic Bat-Inspired Algorithm,”Computer Knowledge & Technology, Vol. 284, pp. 65-74, 2010
[10]	X. S. Yang , “Bat Algorithm for Multi-Objective Optimization,” International Journal of Bio-Inspired Computation, Vol. 3, No. 5, pp. 267-274, 2012
[11]	C. Karri and U. Jena , “Fast Vector Quantization using a Bat algorithm for Image Compression,” Engineering Science & Technology an International Journal, Vol. 19, No. 2, pp. 769-781, 2016
[12]	A. Chakri, R. Khelif, M. Benouaret, X. S. Yang , “New Directional Bat Algorithm for Continuous Optimization Problems,”Expert Systems with Applications, Vol. 69, pp. 159-175, 2017
[13]	P. Musikapun and P. Pongcharoen , “Solving Multi-Stage Multi-Machine Multi-Product Scheduling Problem using Bat Algorithm,”International Proceedings of Economics Development & Research, Vol. 35, 2012
[14]	G. G. Wang, H. C. E. Chu, and S. Mirjalili , “Three-Dimensional Path Planning for UCAV using an Improved Bat Algorithm,” Aerospace Science & Technology, Vol. 49, pp. 231-238, 2016
[15]	P. Augerat, J. M. Belenguer, E. Benaventb, A. Corberan, D. Naddef , “Separating Capacity Constraints in the CVRP using Tabu Search,”European Journal of Operational Research,Vol. 106, No.2-3, pp. 546-557, 1998
[16]	R. C. Eberhart, Y. Shi , “Tracking and Optimizing Dynamic Systems with Particle Swarms, ” Evolutionary Computation,in Proceedings of the 2001 Congress on IEEE, Vol. 1, pp. 94-100, 2001 doi: 10.1109/CEC.2001.934376
[17]	Y. Shi and R. Eberhart , “A Modified Particle Swarm Optimizer,” Advances in Natural Computation, pp. 439-439, Springer Berlin Heidelberg, 1998
[18]	J. Li , “Genetic Algorithm for Vehicle Scheduling Problem with Non-Full Load,” SYSTEMS ENGINE-THEORY METHODOLOGY APPLICATION, 2000

Algorithm	Times
Algorithm	1	2	3	4	5	6	7	8	9	10
Improved BA	67.50	69.00	67.50	69.00	67.50	69.00	67.50	70.00	69.00	69.00
	11	12	13	14	15	16	17	18	19	20
Improved BA	67.50	70.00	67.50	69.00	69.50	70.00	69.00	67.50	67.50	69.00

Algorithm	Times
Algorithm	1	2	3	4	5	6	7	8	9	10
standard GA	74.00	75.00	71.50	72.00	73.50	75.00	73.00	72.50	75.50	73.50
double-population GA	70.00	69.50	67.50	71.00	69.00	70.50	72.00	67.50	71.50	69.00
	11	12	13	14	15	16	17	18	19	20
standard GA	72.00	69.00	73.00	75.50	72.00	73.00	75.00	73.50	71.50	75.00
double-population GA	67.50	69.00	71.00	70.00	67.50	70.50	69.00	69.50	71.00	69.00

	Coordinate	Demand		Coordinate	Demand
0	(30,40)	0	10	(42,57)	8
1	(37,52)	19	11	(27,68)	7
2	(49,43)	30	12	(43,67)	14
3	(52,64)	16	13	(58,27)	19
4	(31,62)	23	14	(37,69)	11
5	(52,33)	11	15	(61,33)	26
6	(42,41)	31	16	(62,63)	17
7	(52,41)	15	17	(63,69)	6
8	(57,58)	28	18	(45,35)	15
9	(62,42)	14

Improved Bat Algorithm for Vehicle Routing Problem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 18

Related Articles 3

Recommended 0

	0	1	2	3	4	5	6	7	8
0	0	4	6	7.5	9	20	10	16	8
1	4	0	6.5	4	10	5	7.5	11	10
2	6	6.5	0	7.5	10	10	7.5	7.5	7.5
3	7.5	4	7.5	0	10	5	9	9	15
4	9	10	10	10	0	10	7.5	7.5	10
5	20	5	10	5	10	0	7	9	7.5
6	10	7.5	7.5	9	7.5	7	0	7	10
7	16	11	7.5	9	7.5	9	7	0	10
8	8	10	7.5	15	10	7.5	10	10	0
d		1	2	1	2	1	4	2	2

[1]	Anita Agárdi, László Kovács, and Tamás Bányai. Neutrality of Vehicle Routing Problem [J]. Int J Performability Eng, 2021, 17(10): 848-857.
[2]	Anita Agárdi, László Kovács, and Tamás Bányai. Using Time Series and Classification in Vehicle Routing Problem [J]. Int J Performability Eng, 2021, 17(1): 14-25.
[3]	Yuxia Li. Cloud Computing Resource Load Forecasting based on Bat Algorithm Optimized SVM [J]. Int J Performability Eng, 2019, 15(7): 1955-1964.

Input: Initialize the bat population ${{x}_{i}}$, ${{f}_{i}}$, and ${{v}_{i}}$,$(i=1,2,\cdots ,n)$
1. While$(t<{{T}_{\max }})$;
2. Update velocities and locations;
3. If$(rand>{{r}_{i}})$;
Select a current best solution randomly among the best solutions and generate a local solution around the selected best solution;
5. End if;
6. Generate a new solution randomly;
7. If ($rand<{{A}_{i}}$and $f({{x}_{i}})<f({{x}_{*}})$);
8. $f({{x}_{*}})=f({{x}_{i}})$;
9. Increase ${{r}_{i}}$and reduce ${{A}_{i}}$;
10. End if;
11. Rank the bats and find the current best ${{x}_{*}}$;
12. End while.

	0	1	2	3	4	5	6	7	8
0	0	4	6	7.5	9	20	10	16	8
1	4	0	6.5	4	10	5	7.5	11	10
2	6	6.5	0	7.5	10	10	7.5	7.5	7.5
3	7.5	4	7.5	0	10	5	9	9	15
4	9	10	10	10	0	10	7.5	7.5	10
5	20	5	10	5	10	0	7	9	7.5
6	10	7.5	7.5	9	7.5	7	0	7	10
7	16	11	7.5	9	7.5	9	7	0	10
8	8	10	7.5	15	10	7.5	10	10	0
d		1	2	1	2	1	4	2	2

	0	1	2	3	4	5	6	7	8
0	0	4	6	7.5	9	20	10	16	8
1	4	0	6.5	4	10	5	7.5	11	10
2	6	6.5	0	7.5	10	10	7.5	7.5	7.5
3	7.5	4	7.5	0	10	5	9	9	15
4	9	10	10	10	0	10	7.5	7.5	10
5	20	5	10	5	10	0	7	9	7.5
6	10	7.5	7.5	9	7.5	7	0	7	10
7	16	11	7.5	9	7.5	9	7	0	10
8	8	10	7.5	15	10	7.5	10	10	0
d		1	2	1	2	1	4	2	2