带时间窗车辆路径问题的启发式遗传算法

赵建有; 吴利清; 刘大学

带时间窗车辆路径问题的启发式遗传算法

1.
长安大学汽车学院，陕西西安 710064
2.
集美大学航海学院，福建厦门 361021
3.
浙江交通职业技术学院汽车系，浙江杭州 311112

基金项目:

江苏省交通科学研究计划项目 06R22

详细信息

作者简介:
赵建有(1963-), 男, 河南西峡人, 长安大学教授, 从事交通运输规划与管理研究

中图分类号: U492.22
计量
- 文章访问数: 267
- HTML全文浏览量: 97
- PDF下载量: 770
- 被引次数: 0
出版历程
- 收稿日期: 2007-08-15
- 刊出日期: 2008-02-25

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

摘要

摘要: 为了在运输生产中按时间要求合理安排车辆路径, 建立了带时间窗车辆路径问题数学模型, 用启发式遗传算法进行求解。先构造染色体, 产生初始群, 再对其进行优化, 根据个体生存能力的体现进行性能估计, 并计算优化值。运用VisualBasic编写相应计算程序, 设定迭代代数为100, 运算次数为10次, 对有时间窗限制的有1个中心仓库与8个分仓库的实际问题进行求解。模拟结果显示需要3辆车按照3条运输线路进行物流配送服务, 总运行距离为483km, 总运行时间为15.55h, 车辆未出现闲置时间, 且全部仓库得到及时服务。可见启发式遗传算法有效、可行。
- 交通运输 /
- 车辆路径问题 /
- 数学模型 /
- 时间窗 /
- 启发式遗传算法
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

HTML全文

图 1 局部最优法

Figure 1. Partial optimal method

下载: 全尺寸图片幻灯片

图 2 全局最优法

Figure 2. Overall optimal method

下载: 全尺寸图片幻灯片

图 3 计算流程

Figure 3. Computation process

下载: 全尺寸图片幻灯片

表 1 仓库参数

Table 1. Parameters of warehouses

仓库	0	1	2	3	4	5	6	7	8
0	0	54	36	96	24	120	48	45	60
1		0	60	45	60	60	60	60	45
2			0	45	39	60	45	45	45
3				0	66	54	66	54	42
4					0	30	60	24	45
5						0	45	30	42
6							0	90	60
7								0	54
8									0
需求量d_i/t		2.0	1.0	2.0	1.5	1.0	2.0	3.5	3.0
卸货时间T_i/h		1.5	1.0	1.5	0.5	1.0	0.5	0.5	1.0
服务时间窗		[2.0, 4.5]	[2.5, 5.0]	[2.5, 4.0]	[0.5, 2.0]	[1.5, 2.5]	[0.5, 2.0]	[0.5, 1.0]	[1.0, 2.5]

下载: 导出CSV

参考文献(11)

[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]	卜雷, 尹传忠, 蒲云. 优化普零货物拼箱装配的遗传算法[J]. 交通运输工程学报, 2004, 4(4): 84-87. doi: 10.3321/j.issn:1671-1637.2004.04.021 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]	樊小红, 荆便顺. 基于遗传算法的交通事件控制[J]. 长安大学学报: 自然科学版, 2005, 25(4): 70-72. doi: 10.3321/j.issn:1671-8879.2005.04.018 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]	王来军, 胡大伟, 史忠科. 容量受限型设施定位模型及遗传算法[J]. 长安大学学报: 自然科学版, 2006, 26(6): 65-68. doi: 10.3321/j.issn:1671-8879.2006.06.015 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]	姜大立, 杨西龙, 杜文, 等. 车辆路径问题的遗传算法研究[J]. 系统工程理论与实践, 1999, 19(6): 40-45. doi: 10.3321/j.issn:1000-6788.1999.06.007 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]	牛永亮, 王金妹. 物流配送车辆路线求解算法[J]. 交通运输工程学报, 2006, 6(2): 83-87. http://transport.chd.edu.cn/article/id/200602019 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]	胡大伟, 朱志强, 胡勇. 车辆路径问题的模拟退火算法[J]. 中国公路学报: 2006, 19(4): 123-126. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200604022.htm 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]	樊涛. 基于遗传算法的路基土石方数量估算方法[J]. 中国公路学报, 2006, 19(6): 45-48. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200606008.htm 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