Optimization on tractor-and-trailer transportation scheduling with uncertain empty-trailer tasks
-
摘要: 在实际路网下建立了空挂任务不确定情形下的甩挂运输调度优化模型, 设计两阶段启发式算法进行求解, 第1阶段分别按照空挂调运距离最小和重挂任务起终(OD)点总顺差最低2种策略确定空挂调运方案, 第2阶段结合任务节点顺差和贪婪思想确定所有任务的执行序列, 采用算例分析算法的性能。分析结果表明: 空挂运输成本与总成本分别为325.5、1 010.5元, 比原有方案分别节约10.44%、3.62%, 且使用的牵引车更少; 基于辽宁省内城市间甩挂运输算例所得空挂调运距离最小和重挂任务OD点总顺差最低2种策略的最优值分别为2 561.3、2 464.6元, 平均求解时间分别为21.5、27.3s, 第2种策略各结果的稳定性较好; 模拟退火算法所得总成本均在3 100元以上, 求解时间均在80s以上。可见, 本文算法的精度和效率较高, 重挂任务OD点总顺差最低策略在求解空挂任务不确定情形下的甩挂运输调度问题方面有着明显的优势。Abstract: In actual road network, the optimization model on tractor-and-trailer transportation scheduling with uncertain empty-trailer tasks was built.A two-stage heuristic algorithm was designed to solve the model.At the first stage, the transportation scheme of empty-trailer task was decided by two strategies, minimizing the transportation distance of empty-trailer and minimizing the total surplus of origin destination(OD)points for heavy-trailer tasks respectively.At the second stage, the task node surplus and the greed thought were combined to determine the execution sequence of all tasks.Numerical examples were used to analyze the performance of the algorithm.Analysis result shows that empty-trailer transportation cost and total cost are 325.5 and 1 010.5 yuan respectively, which respectively save by 10.44% and 3.62% compared to the original scheme, and less tractors are used.Based on the numerical example of tractor-and-trailer transportation among cities in Liaoning Province, the optimal values under two strategies, minimizing the transportation distance of empty-trailer and minimizing the total surplus of ODpoints for heavy-trailer tasks are 2 561.3 and 2 464.6 yuan respectively, average solving times are21.5 and 27.3 srespectively, and the results under the second strategy have good stability.The total costs computed by using simulated annealing algorithm are all above 3 100 yuan, and the solving times are all above 80 s.So, the algorithm in this paper has higher precision and efficiency, and the strategy of minimizing total surplus of OD points for heavy-trailer tasks has obvious advantages on tractor-and-trailer transportation scheduling problem with uncertain empty-trailer tasks.
-
图 3 第1阶段的编码方式及对应的调运方案
Figure 3. Coding mode and corresponding dispatching scheme at the first stage
图 7 重挂任务不平衡度变化的求解结果
Figure 7. Solving results with different unbalance degrees of heavy-trailer tasks
图 8 空重挂任务比例变化的求解结果
Figure 8. Solving results with different ratios of empty-trailer tasks to heavy-trailer tasks
表 1 本文算法结果与原有结果的对比
Table 1. Comparison of result computed by algorithm in this paper and original result
下载: 导出CSV
-
[1] CHAO I M. A tabu search method for the truck and trailer routing problem[J]. Computers and Operations Research, 2002, 29(1): 33-51. doi: 10.1016/S0305-0548(00)00056-3 [2] LIN S W, YU V F, CHOU S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers and Operations Research, 2009, 36(5): 1683-1692. doi: 10.1016/j.cor.2008.04.005 [3] LIN S W, YU V F, CHOU S Y. A note on the truck and trailer routing problem[J]. Expert Systems with Applications, 2010, 37(1): 899-903. doi: 10.1016/j.eswa.2009.06.077 [4] LIN S W, YU V F, LU C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows[J]. Expert Systems with Applications, 2011, 38(12): 15244-15252. doi: 10.1016/j.eswa.2011.05.075 [5] VILLEGAS J G, PRINS C, PRODHON C, et al. GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots[J]. Engineering Applications of Artificial Intelligence, 2010, 23(5): 780-794. doi: 10.1016/j.engappai.2010.01.013 [6] VILLEGAS J G, PRINS C, PRODHON C, et al. A GRASPwith evolutionary path relinking for the truck and trailer routing problem[J]. Computers and Operations Research, 2011, 38(9): 1319-1334. doi: 10.1016/j.cor.2010.11.011 [7] VILLEGAS J G, PRINS C, PRODHON C, et al. Amatheuristic for the truck and trailer routing problem[J]. European Journal of Operational Research, 2013, 230(2): 231-244. doi: 10.1016/j.ejor.2013.04.026 [8] DERIGS U, PULLMANN M, VOGEL U. Truck and trailer routing-problems, heuristics and computational experience[J]. Computers and Operations Research, 2013, 40(2): 536-546. doi: 10.1016/j.cor.2012.08.007 [9] ZHANG Rui-you, LU J C, WANG Ding-wei. Container drayage problem with flexible orders and its near real-time solution strategies[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 61: 235-251. doi: 10.1016/j.tre.2013.11.009 [10] SCHEUERER S. A tabu search heuristic for the truck and trailer routing problem[J]. Computers and Operations Research, 2006, 33(4): 894-909. doi: 10.1016/j.cor.2004.08.002 [11] MIRMOHAMMADSADEGHI S, AHMED S. Metaheuristic approaches for solving truck and trailer routing problems with stochastic demands: a case study in dairy industry[J]. Mathematical Problems in Engineering, 2015, 2015: 1-14. [12] 胡志华, 陶莎. 基于混合进化算法的甩挂配送问题[J]. 公路交通科技, 2013, 30(5): 147-152. https://www.cnki.com.cn/Article/CJFDTOTAL-GLJK201305025.htmHU Zhi-hua, TAO Sha. Distribution by trailer pick-up transport based on hybrid evolutionary algorithm[J]. Journal of Highway and Transportation Research and Development, 2013, 30(5): 147-152. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-GLJK201305025.htm [13] TAN K C, CHEW Y H, LEE L H. A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems[J]. European Journal of Operational Research, 2006, 172(3): 855-885. doi: 10.1016/j.ejor.2004.11.019 [14] LEE L H, TAN K C, OU K, et al. Vehicle capacity planning system: a case study on vehicle routing problem with time windows[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2003, 33(2): 169-178. doi: 10.1109/TSMCA.2002.806498 [15] XUE Zhao-jie, ZHANG Can-rong, LIN Wei-hua, et al. A tabu search heuristic for the local container drayage problem under a new operation mode[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 62: 136-150. doi: 10.1016/j.tre.2013.12.007 [16] XUE Zhao-jie, LIN Wei-hua, MIAO Li-xin, et al. Local container drayage problem with tractor and trailer operating in separable mode[J]. Flexible Services and Manufacturing Journal, 2015, 27(2): 431-450. [17] XUE Zhao-jie, ZHANG Can-rong, YANG Peng, et al. Acombinatorial benders'cuts algorithm for the local container drayage problem[J]. Mathematical Problems in Engineering, 2015, 2015: 1-7. [18] FRANCIS P, ZHANG Guang-ming, SMILOWITZ K. Improved modeling and solution methods for the multi-resource routing problem[J]. European Journal of Operational Research, 2007, 180(3): 1045-1059. doi: 10.1016/j.ejor.2006.03.054 [19] CHENG Yao-rong, LIANG Bo, ZHOU Mei-hua. Optimization for vehicle scheduling in iron and steel works based on semitrailer swap transport[J]. Journal of Central South University of Technology, 2010, 17(4): 873-879. doi: 10.1007/s11771-010-0570-9 [20] LI Hong-qi, LU Yue, ZHANG Jun, et al. Solving the tractor and semi-trailer routing problem based on a heuristic approach[J]. Mathematical Problems in Engineering, 2012, 2012: 1-12. [21] 余莉, 林桦, 陈伯如. 网络型甩挂运输模式下的车辆调度问题[J]. 交通运输工程与信息学报, 2014, 12(2): 58-64. https://www.cnki.com.cn/Article/CJFDTOTAL-JTGC201402009.htmYU Li, LIN Hua, CHEN Bo-ru. Research of vehicle scheduling problem of the network drop and pull transport[J]. Journal of Transportation Engineering and Information, 2014, 12(2): 58-64. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JTGC201402009.htm [22] 薛亮, 马健霄, 余伟. 甩挂运输具体应用分析[J]. 交通运输系统工程与信息, 2011, 11(5): 200-205. doi: 10.3969/j.issn.1009-6744.2011.05.030XUE Liang, MA Jian-xiao, YU Wei. Application analysis of drop and pull transport[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(5): 200-205. (in Chinese). doi: 10.3969/j.issn.1009-6744.2011.05.030 [23] 钟慧玲, 吴聪, 张冠湘, 等. 内河港口甩挂运输组织中场站选址问题研究[J]. 交通运输系统工程与信息, 2013, 13(3): 126-131, 137. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201303022.htmZHONG Hui-ling, WU Cong, ZHANG Guan-xiang, et al. Freight station location of inland port semi-trailer swap transport organization[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(3): 126-131, 137. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201303022.htm [24] 胡志华, 曹杨, 王云霞. 集装箱集散的空重箱循环甩挂调度方法[J]. 武汉理工大学学报, 2012, 34(10): 68-73. https://www.cnki.com.cn/Article/CJFDTOTAL-WHGY201210016.htmHU Zhi-hua, CAO Yang, WANG Yun-xia. Cyclic tractorand-trailer scheduling for consolidation and distribution of loaded and empty containers[J]. Journal of Wuhan University of Technology, 2012, 34(10): 68-73. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-WHGY201210016.htm [25] 胡志华. 集装箱码头间互拖的集卡甩挂运输调度问题[J]. 重庆交通大学学报: 自然科学版, 2013, 32(2): 313-317. https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201302031.htmHU Zhi-hua. Scheduling of container truck-and-trailer transport between two ports[J]. Journal of Chongqing Jiaotong University: Natural Science, 2013, 32(2): 313-317. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CQJT201302031.htm -
点击查看大图
图(8) / 表(7)
计量
- 文章访问数: 1940
- HTML全文浏览量: 104
- PDF下载量: 1691
- 被引次数: 0
