空挂任务不确定情形下的甩挂运输调度优化
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.3 s,第2种策略各结果的稳定性较好; 模拟退火算法所得总成本均在3 100元以上,求解时间均在80 s以上。可见,本文算法的精度和效率较高,重挂任务OD点总顺差最低策略在求解空挂任务不确定情形下的甩挂运输调度问题方面有着明显的优势。
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 OD points for heavy-trailer tasks are 2 561.3 and 2 464.6 yuan respectively, average solving times are 21.5 and 27.3 s respectively, 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. 7 tabs, 8 figs, 25 refs