Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows

HU Da-wei; CHEN Cheng; WANG Lai-jun

Volume 7 Issue 5

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2007 > 7(5): 112-117

Next Previous

HU Da-wei, CHEN Cheng, WANG Lai-jun. Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 112-117.

Citation:

HU Da-wei, CHEN Cheng, WANG Lai-jun. Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 112-117.

HU Da-wei, CHEN Cheng, WANG Lai-jun. Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 112-117.

Citation:

HU Da-wei, CHEN Cheng, WANG Lai-jun. Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 112-117.

PDF( 301 KB)

Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows

1.
School of Automobile, Chang'an University, Xi'an 710064, Shaanxi, China
2.
School of Transportation, Fujian Agriculture and Forestry University, Fuzhou 350002, Fujian, China

More Information

Author Bio:
Hu Da-wei(1963-), male, professor, +86-29-82334426。dwhu2008cn@yahoo.com.cn
Received Date: 2007-04-07
Publish Date: 2007-10-25

Abstract

Abstract

In order to improve the efficiency of logistics distribution, a mathematic model of vehicle routing problem with pickups, deliveries and hard time-windows was set up, and a hybrid-genetic-heuristic algorithm is designed to solve the model.In the algorithm, improved C-W method and random producing method were used to produce the initial group of solutions to increase its varieties, and the tabu search was used for some better chromosomes of genetic algorithm to avoid local optimization and increase search beginning speed.Simulation result shows that the algorithm has better adaptability, the solution's precision is improved by 11.0% when improved cross operator is used, and the solution's precision is improved by 11.6% when reversed variation tactic is used under big time-windows condition.
- traffic planning,
- vehicle routing problem,
- pickups and deliveries,
- time-windows,
- hybrid-genetic-heuristic algorithm

FullText(HTML)

References(14)

References

[1]	Nagy G, Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research, 2005, 16(1): 126-141.
[2]	Clarke G, Wright J W. Scheduling of vehicle from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581. doi: 10.1287/opre.12.4.568
[3]	Min H. The multiple vehicle routing problem with simultane ous delivery and pick-up points[J]. Transportation Research: Part A, 1989, 23(4): 377-386.
[4]	Halse K. Modeling and solving complex vehicle routing problems[D]. Lyngby: Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, 1992.
[5]	Gendreau M, Laporte G, Hertz A. An approximation algorithm for the traveling salesman problem with backhauls[J]. Operations Research, 1997, 45(4): 639-641. doi: 10.1287/opre.45.4.639
[6]	郎茂祥. 物流配送车辆调度问题的模型和算法研究[D]. 北京: 北方交通大学, 2002.
[7]	Ye Zhi-jian, Du Wen, Zhou He-fang. Model for vehicle routing plan with mixed-demand and its lasso solution[J]. Journal of Southwest Jiaotong University, 2003, 38(3): 341-344. (in Chinese) doi: 10.3969/j.issn.0258-2724.2003.03.023
[8]	Osman I H. Meta-strategy simulated annealing and tabusearch algorithm for the vehicle routing problem[J]. Annalsof Operational Research, 1993, 41(4): 421-451. doi: 10.1007/BF02023004
[9]	邢文训, 谢金星. 现代优化计算方法[M]. 北京: 清华大学出版社, 1999.
[10]	英群. 应用禁忌搜索法于混合送收货之车辆途程问题[D]. 台湾: 逢甲大学, 2003.
[11]	Tan K C, Lee L H, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constraints[J]. Engineering Applications of Artificial Intelligence, 2001, 14(1): 825-837.
[12]	Hu Da-wei, Hu Yong, Zhu Zhi-qiang. Solving location-routing problem based on space filling curve and dynamic programming[J]. Journal of Chang'an University: Natural Science Edition, 2006, 26(3): 80-83. (in Chinese) doi: 10.3321/j.issn:1671-8879.2006.03.020
[13]	Niu Yong-liang, Wang Jin-mei. Vehicle route algorithm of logistics distribution[J]. Journal of Traffic and Transportation Engineering, 2006, 6(2): 83-87. (in Chinese) doi: 10.3321/j.issn:1671-1637.2006.02.019
[14]	Hu Da-wei, Zhu Zhi-qiang, Hu Yong. Simulated annealing algorithm for vehicle routing problem[J]. China Journal of Highway and Transport, 2006, 19(4): 123-126. (in Chinese) doi: 10.3321/j.issn:1001-7372.2006.04.023