Heuristic genetic algorithm of vehicle routing problem with time windows

ZHAO Jian-you; WU Li-qing; LIU Da-xue

Volume 8 Issue 1

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2008 > 8(1): 113-117

Next Previous

ZHAO Jian-you, WU Li-qing, LIU Da-xue. Heuristic genetic algorithm of vehicle routing problem with time windows[J]. Journal of Traffic and Transportation Engineering, 2008, 8(1): 113-117.

Citation:

ZHAO Jian-you, WU Li-qing, LIU Da-xue. Heuristic genetic algorithm of vehicle routing problem with time windows[J]. Journal of Traffic and Transportation Engineering, 2008, 8(1): 113-117.

ZHAO Jian-you, WU Li-qing, LIU Da-xue. Heuristic genetic algorithm of vehicle routing problem with time windows[J]. Journal of Traffic and Transportation Engineering, 2008, 8(1): 113-117.

Citation:

ZHAO Jian-you, WU Li-qing, LIU Da-xue. Heuristic genetic algorithm of vehicle routing problem with time windows[J]. Journal of Traffic and Transportation Engineering, 2008, 8(1): 113-117.

PDF( 594 KB)

Heuristic genetic algorithm of vehicle routing problem with time windows

1.
School of Automobile, Chang'an University, Xi'an 710064, Shaanxi, China
2.
School of Navigation, Jimei University, Xiamen 361021, Fujian, China
3.
Department of Automobile, Zhejiang Institute of Communications, Hangzhou 311112, Zhejiang, China

More Information

Author Bio:
Zhao Jian-you(1963-), male, professor, +86-29-82334069, jyzhao@chd.edu.cn
Received Date: 2007-08-15
Publish Date: 2008-02-25

Abstract

Abstract

In order to reasonably arrange vehicle routes according to time request in transportation production, a mathematical model for vehicle routing problem with time windows(VRPTW) was constructed, and a heuristic genetic algorithm was put forward to solve it. In the algorithm, chromosomes were constructed, initial groups were produced and optimized, their capability was estimated by the existent ability of individual, and the optimized value was computed. The number of evolving offspring is 100, operating time is 10, VRPTW with one center depot and eight branch depots was solved by correspond program. The result indicates that goods are distributed with three trucks in three routes, total distance is 483 km, total time is 15.55 h, there is no idle time for truck, and all warehouses are served on time. Obviously, the algorithm is effective and feasible.
- traffic transportation,
- vehicle routing problem,
- mathematical model,
- time windows,
- heuristic genetic algorithm

FullText(HTML)

References(11)

References

[1]	Tan K, Lee T. A messy genetic algorithm for the vehicle routing problem with time window constraints[C]//IEEE. Proceedings of the IEEE Congress on Evolutionary Computation. New York: IEEE, 2001: 679-686.
[2]	Ozdemir H, Mohan C. Evolving schedule graphs for the vehicle routing problem with time windows[C]//IEEE. Proceedings of the IEEE Congress on Evolutionary Computation. New York: IEEE, 2000: 888-895.
[3]	Hwang H. An improved model for vehicle routing problem with time constraint based on genetic algorithm[J]. Computers & Industrial Engineering, 2002, 42(2/4): 361-369.
[4]	Osman H, Christofides N. Capaqitated clustering problem by hybrid simulated annealing and tabusearch[J]. International Transactionin Operation Research, 1994, 1(3): 317-336. doi: 10.1016/0969-6016(94)90032-9
[5]	Bu Lei, Yin Chuan-zhong, Pu Yun. Genetic algorithm for optimal arrangement of general piece goods[J]. Journal of Traffic and Transportation Engineering, 2004, 4(4): 84-87. (in Chinese) doi: 10.3321/j.issn:1671-1637.2004.04.021
[6]	Fan Xiao-hong, Jing Bian-shun. Freeway automatic incident detection with genetic algorithm[J]. Journal of Chang'an University: Natural Science Edition, 2005, 25(4): 70-72. (in Chinese) doi: 10.3321/j.issn:1671-8879.2005.04.018
[7]	Wang Lai-jun, Hu Da-wei, Shi Zhong-ke. Model and genetic algorithms applying to a type of constrained facility location problem[J]. Journal of Chang'an University: Natural Science Edition, 2006, 26(6): 65-68. (in Chinese) doi: 10.3321/j.issn:1671-8879.2006.06.015
[8]	Jiang Da-li, Yang Xi-long, Du Wen, et al. A study on the genetic algorithm for vehicle routing problem[J]. Systems Engineering—Theory and Practice, 1999, 19(6): 40-45. (in Chinese) doi: 10.3321/j.issn:1000-6788.1999.06.007
[9]	Niu Yong-liang, Wang Jin-mei. The algorithm for vehicle routing problem of logistics[J]. Journal of Traffic and Transportation Engineering, 2006, 6(2): 83-87. (in Chinese) http://transport.chd.edu.cn/article/id/200602019
[10]	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) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200604022.htm
[11]	Fan Tao. Evaluation method of subgrade earthwork volumes based on genetic algorithm[J]. China Journal of Highway and Transport, 2006, 19(6): 45-48. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200606008.htm