Hybrid genetic algorithm of vehicle routing with time windows
Article Text (Baidu Translation)
-
摘要: 基于标准遗传算法, 将每一个染色体与分组信息相结合, 使染色体结构包含有更多信息, 辅以λ-交换局部搜索技术, 构造了一种新的混合遗传算法, 对带时间窗约束的车辆路径问题进行了求解, 并与标准遗传算法的求解结果进行了对比研究, 发现使用混合遗传算法, 总行驶里程为162km, 而使用标准遗传算法, 总行驶里程为182 km。结果表明混合遗传算法的求解结果比标准遗传算法更加接近最优解, 所需的行驶里程缩短, 有效降低运输企业的车辆运行成本。Abstract: Based on standard genetic algorithm, each chromosome was associated with more informations, the λ-interchange local search method was applied to developed a new algorithm, named hybrid genetic algorithm, for solving vehicle routing. It is found that the total journey computed by hybrid algorithm is 162 km, and the journey by standard algorithm is 182 km. The results indicate that the hybrid algorithm can find better solution than standard genetic algorithm, the necessary journey is shorten greatly, the transportation cost can be reduced effectively.
-
Key words:
- ITS /
- time windows /
- vehicle routing problem /
- hybrid genetic algorithm /
- λ-inter-change local search
-
[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 10(6): 80-91. [2] 祝崇隽, 刘民, 吴澄. 供应链中车辆路径问题的研究进展及前景[J]. 计算机集成制造系统, 2001, 7(11): 1-6. doi: 10.3969/j.issn.1006-5911.2001.11.001ZHU Chong-jun, LIU Min, WU Cheng. Review of vehicle rou-ting problem in supply chain[J]. Computer Integrated Manu-facturing Systems, 2001, 7(11): 1-6. (in Chinese) doi: 10.3969/j.issn.1006-5911.2001.11.001 [3] Thangiah S R. A hybrid genetic algorithm, simulated annealing and tabu search heuristics for the vehicle routing problem with time windows[J]. Complex Coding Systems, 1999, 3 (1): 253-277. [4] 肖雁, 符卓, 李育安. 带软时间窗的车辆路径问题及其应用前景探讨[A]. 中国运筹学会第六届学术交流会论文集[C]. 长沙: Global-Link出版社, 2000. [5] 张丽萍, 柴跃廷, 曹瑞. 有时间窗车辆路径问题的改进遗传算法[J]. 计算机集成制造系统, 2002, 8(6): 452-454. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200206007.htmZHANG Li-ping, CHAI Yue-ting, CAO Rui. Improved genetic algorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2002, 8 (6); 452-454. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200206007.htm [6] 孙增圻. 智能控制理论与技术[M]. 北京: 清华大学出版社, 2000. [7] 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. [8] Osman I H, Christofides N. Capacitated clustering problem by hybrid simulated annealing and tabu search[J]. International Transaction in Operation Research, 1994, 1(3): 317-336. doi: 10.1016/0969-6016(94)90032-9 [9] 姜大立, 杨西龙, 杜文, 等. 车辆路径问题的遗传算法研究[J]. 系统工程理论与实践, 1999, 19(6): 40-45. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL906.006.htmJIANG Da-li, YANG Xi-long, DU Wen, et al. A study on the genetic algorithm for vehicle routing problem[J]. Systems En-gineering-Theory & Practice, 1999, 19(6): 40-45. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL906.006.htm -
下载: 
点击查看大图
表(1)
计量
- 文章访问数: 305
- HTML全文浏览量: 143
- PDF下载量: 447
- 被引次数: 0
