Hybrid-genetic-heuristic algorithm of vehicle routing problem with hard time-windows
-
摘要: 为了提高物流配送效率, 建立了集货和配送一体化的带硬时间窗的车辆路线问题的数学模型, 提出了混合遗传启发式算法, 并对模型进行了求解。采用改进节约法与随机法相结合的手段构造了初始解群体以增加解的多样性, 对遗传算法中较优的一部分染色体进行了禁忌搜索以使搜索更容易跳出局部最优, 同时加快搜索初期的搜索速度。仿真计算结果表明: 混合遗传启发式算法具有更好的适应性, 采用改进交叉算子使解的精度提高11.0%;在宽时间窗情形下采用倒位变异可使解的精度提高11.6%。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.
-
表 1 客户点的数据
Table 1. Data of customers
客户编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 横坐标 3.8 15.2 18.6 11.9 10.2 5.3 0.6 6.1 7.6 16.0 15.3 1.6 9.0 5.4 7.8 18.6 14.5 15.0 9.8 1.4 纵坐标 5.5 10.9 12.9 8.2 9.5 9.6 9.9 15.0 19.2 15.7 15.2 14.7 9.2 13.3 10.0 7.8 5.3 18.7 5.0 6.9 需求量 0.8 0.6 0.4 1.6 0.8 0.6 1.9 1.3 1.8 1.8 0.4 1.6 1.1 1.6 1.0 0.8 1.4 1.2 0.4 1.4 供应量 0.5 1.6 0.7 0.3 0.6 1.4 1.7 1.0 0.9 1.9 1.0 1.8 1.4 0.4 1.8 1.8 0.8 0.2 0.5 1.0 需求时间窗开始时间 8.8 2.4 0.1 9.8 9.6 0.3 5.9 1.7 0.6 9.8 4.7 7.0 0.1 0.1 9.0 7.4 0.5 8.3 5.7 3.0 需求时间窗结束时间 14.6 8.1 4.9 14.1 13.8 6.0 11.6 7.5 5.2 13.9 10.3 12.4 5.0 4.7 14.7 12.5 5.6 13.0 10.9 7.5 供应时间窗开始时间 6.0 8.0 6.8 0.6 1.7 5.6 8.0 4.5 4.9 6.1 7.1 4.0 2.9 5.1 8.1 6.7 3.6 0.0 1.1 2.9 供应时间窗结束时间 14.6 13.8 12.3 5.0 6.3 10.4 12.6 8.5 10.3 12.0 11.8 9.8 7.1 9.8 13.9 11.6 9.4 5.8 6.1 7.0 
下载: 导出CSV
表 2 模拟结果比较
Table 2. Comparison of simulation results
下载: 导出CSV
表 3 交叉算子试验结果
Table 3. Test results of cross operators
交叉算子 混合时间窗路线数/总行驶距离 紧时间窗路线数/总行驶距离 宽时间窗路线数/总行驶距离 HX1HX2 66/176 940.075 7 111/251 362.548 8 47/126 274.646 0 HX1MX2 66/193 535.022 0 108/263 366.992 2 48/166 841.772 5 MX1MX2 66/216 610.693 4 107/289 610.864 3 46/195 677.844 2 HX2MX1 70/176 957.214 4 107/286 066.259 8 43/198 448.999 0 IHMX 66/170 081.359 9 111/244 100.268 6 44/116 302.868 7
下载: 导出CSV
表 4 变异概率试验结果
Table 4. Test results of variation probabilities
变异概率 混合时间窗路线数/总行驶距离 紧时间窗路线数/总行驶距离 宽时间窗路线数/总行驶距离 0.06 68/171 408.374 0 110/250 938.183 6 46/123 548.486 3 0.08 65/174 855.969 2 108/254 082.104 5 45/126 925.695 8 0.10 67/171 397.619 6 111/252 154.370 1 47/122 479.370 1 0.12 65/172 942.968 8 111/245 038.916 0 43/125 140.105 3 适应性变异概率 66/170 081.359 9 111/244 100.268 6 44/116 302.868 7
下载: 导出CSV
表 5 变异算子试验结果
Table 5. Test results of variation operators
变异算子 混合时间窗路线数/总行驶距离 紧时间窗路线数/总行驶距离 宽时间窗路线数/总行驶距离 三次对换变异 66/185 320.520 0 110/247 271.362 3 47/131 613.531 6 倒位变异 66/170 081.359 9 111/244 100.268 6 44/116 302.868 7
下载: 导出CSV
-
[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] 叶志坚, 杜文, 周荷芳. 混合运输需求的车队车辆路线规划模型及算法[J]. 西南交通大学学报, 2003, 38(3): 341-344. doi: 10.3969/j.issn.0258-2724.2003.03.023Ye 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] 胡大伟, 胡勇, 朱志强. 基于空间填充曲线和动态规划解的定位路线问题[J]. 长安大学学报: 自然科学版, 2006, 26(3): 80-83. doi: 10.3321/j.issn:1671-8879.2006.03.020Hu 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] 牛永亮, 王金妹. 物流配送车辆路线求解算法[J]. 交通运输工程学报, 2006, 6(2): 83-87. doi: 10.3321/j.issn:1671-1637.2006.02.019Niu 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] 胡大伟, 朱志强, 胡勇. 车辆路径问题的模拟退火算法[J]. 中国公路学报, 2006, 19(4): 123-126. doi: 10.3321/j.issn:1001-7372.2006.04.023Hu 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 -
点击查看大图
图(3) / 表(5)
计量
- 文章访问数: 302
- HTML全文浏览量: 82
- PDF下载量: 368
- 被引次数: 0
