Improved genetic algorithm for vehicle routing problem with hard time windows

被引：0
作者：
Wu, Tian-Yi [1 ]
Xu, Ji-Heng [1 ]
Liu, Jian-Yong [1 ]
Zan, Liang [1 ]
机构：
[1] College of Field Engineering, PLA University of Science and Technology
来源：
Xi Tong Gong Cheng Yu Dian Zi Ji Shu/Systems Engineering and Electronics | 2014年 / 36卷 / 04期
关键词：
Entrance matrix; Export matrix; Genetic algorithm; Hard time window; Logistics;
D O I：
10.3969/j.issn.1001-506X.2014.04.17
中图分类号：
学科分类号：
摘要：
In view of the vehicle routing problem with hard time windows in military transportation, an improved genetic algorithm which aims to minimize the vehicles' total delivery time with the combination of hybrid crossover operation, improved mutation operation and an elite reserve strategy is put forward. First, it improves the initial population superiority by the greedy thought. Second, the entrance matrix and export matrix of the convergence population are constructed and the improved crossover operator based on the matrices is proposed. At the same time, the hybrid crossover operation is designed, which speeds up the population optimization through introducing the push forward insertion heuristic algorithm. At last, the population diversity is increased with the introduction of an improved mutation operator. The experimental results show that the improved genetic algorithm has a faster convergence speed and a better convergence effect than the basic algorithm.
引用
收藏
页码：708 / 713
页数：5
相关论文
共 17 条
  • [1] Li J., Guo Y.H., Logistics Vehicle Scheduling Theory and Methods, pp. 1-20, (2001)
  • [2] Shi Y.F., Su S., Peng Q.Y., Optimization of military transportation routes based on genetic algorithm, Journal of Southwest Jiaotong University, 40, 2, pp. 241-244, (2005)
  • [3] Xie B.L., Li J., Guo Y.H., Genetic algorithm for vehicle scheduling problem of non-full loads with time windows, Journal of Systems Engineering, 15, 3, pp. 290-294, (2000)
  • [4] Tan K.C., Lee L.H., Zhu Q.L., Et al., Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering, 15, 3, pp. 281-295, (2001)
  • [5] Chang T.S., Wan Y.W., Ooi W.T., A stochastic dynamic traveling salesman problem with hard time windows, European Journal of Operation Research, 198, 3, pp. 748-759, (2009)
  • [6] Ziauddin U., Daryl E., David C., Et al., Localized genetic algorithm for vehicle routing problem with time windows, Applied Soft Computing, 11, 8, pp. 5375-5390, (2011)
  • [7] Zhang L.P., Chai Y.T., Cao R., Improved genetic algorithm for vehicle routing problem with time windows, Computer Integrated Manufacturing Systems, 8, 6, pp. 451-454, (2002)
  • [8] Song H.B., Cai Y.L., Hybrid genetic algorithm of vehicle routing with time windows, Journal of Traffic and Transportation Engineering, 3, 4, pp. 112-115, (2003)
  • [9] Huang L., Pang W., Wang K.P., Et al., New genetic algorithm for vehicle routing problem with time window, Journal of Chinese Computer System, 26, 2, pp. 214-217, (2005)
  • [10] Thibaut V., Teodor G.C., Michel G., Et al., A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research, 40, 1, pp. 475-489, (2013)
12