重大事故规避的危险品运输车辆路径优化研究

Research on Vehicle Routing for Hazardous Materials Transportation Based on Catastrophe Avoidance

基于重大事故规避的思想,建立以最大事故后果最小及运输成本最小为双目标,且事故后果基于实时装载量的危险品运输车辆路径优化模型。基于ε-约束法,设计可求得帕累托最优解的精确算法,该算法包含通过性质求ε下界、规避被支配解的预处理及不可行路径禁止约束3处改进。进一步设计处理大规模问题的多项式时间近似算法,并分析了算法的近似比。最后通过算例对模型和算法进行测试,并通过出灵敏度分析给出管理启示。

Based on the principles of catastrophe avoidance, a bi-objective vehicle routing model for hazardous materials transportation with actual loading dependent incident consequence is developed, minimizing the maximum incident consequence and transportation cost simultaneously. The exact algorithm to obtain the Pareto optimal solutions is developed based on ε-constraint method. Three improvements are developed for this exact algorithm, including a simple method to obtain the lower bound of ε by a property, a post-processing to avoid dominated points, and forbidding constraints on infeasible paths. A polynomial time approximation algorithm is developed to deal with large scale problems, and the approximation ratio is analyzed. Finally, the model and algorithms are tested by instances, and the managerial insights are derived from the sensitivity analysis.