Int J Performability Eng ›› 2019, Vol. 15 ›› Issue (1): 317-325.doi: 10.23940/ijpe.19.01.p32.317325
Previous Articles Next Articles
Yu Liab, Qian Guob, and Jingsen Liuc*(
)
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.
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
Bat algorithm
pseudo code"
| 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. |
Figure 1
Paths"
Table 1
Distance and demand"
| 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 | |
Table 2
Solution for 20 times"
| Algorithm | Times | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
Figure 2
Convergence curve At the same time, it can be seen more intuitively through the convergence curve in Figure 2. It is more efficient and faster to solve VRP with the improved BA, which can converge to the optimal solution within 100 generations."
Table 3
Solution by standard GA and double-population GA for 10 times"
| Algorithm | Times | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
Table 4
P-n19-k2 coordinate and demand"
| 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 |
Table 5
Solution of P-n19-k2 for 10 times and the average value, standard deviation"
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | AV | Std | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| P-n19-k2 | 288 | 265 | 266 | 258 | 282 | 265 | 272 | 275 | 274 | 284 | 272.9 | 2.83 |
| [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 |
| [1] | Yuxia Li. Cloud Computing Resource Load Forecasting based on Bat Algorithm Optimized SVM [J]. Int J Performability Eng, 2019, 15(7): 1955-1964. |
|
