Username   Password       Forgot your password?  Forgot your username? 


Improved Bat Algorithm for Vehicle Routing Problem

Volume 15, Number 1, January 2019, pp. 317-325
DOI: 10.23940/ijpe.19.01.p32.317325

Yu Lia,b, Qian Guob, and Jingsen Liu

aInstitute of Management Science and Engineering, Henan University, Kaifeng, 475004, China
bBusiness School, Henan University, Kaifeng, 475004, China
cInstitute of Intelligent Network system, Henan University, Kaifeng, 475004, China

(Submitted on October 23, 2018; Revised on November 24, 2018; Accepted on December 27, 2018)


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.


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, and 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, and 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, and 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, and 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
      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


          Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

          This site uses encryption for transmitting your passwords.