时变条件下有宵禁限制的有害物品运输最短路研究

An Approach for Hazardous Materials Transportation Path Problem in the Time-Varing Network Curfews

在有害物品运输过程中,往往需要获得从起点到终点之间的最短路。针对有害物品运输网络具有很强的时变特性,且运输过程中往往有宵禁的限制(curfews)的情况。建立了允许有多个出发时间的,时变条件下有软、硬宵禁限制的有害物品运输的最短路模型,利用动态规划设计了求解时变条件下有软、硬宵禁限制的多目标最短路的算法,通过此算法可以获得时变条件下有软、硬宵禁限制的有害物品运输最短路,并分析了算法的复杂性。然后,对网络中可行路径在不同限制条件下的目标值进行了排序,并进行了证明。最后,给出了一个应用算例,证实了算法和模型的有效性。

In hazardous materials transportation, the shortest path problem is almost wanted. Moreover, the transportation networks are always time-varying and there will be curfews in some nodes. The paper developed the models for tlme-varying shortest path in the hazardous materials transportation with soft and hard curfews. Based on the dynamic programming, the algorithms were proposed for them. Then, the computational complexity of the algorithm was discussed. By this algorithm, the non-dominated paths in the hazardous materials transportation were provided. The sequence of values for the feasible route in the network with the different conditions were proposed and proved for them. At last, a case was studied.