Abstract: 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.

Key words: operational research, hazardous materials transportation, catastrophe avoidance, actual loading, ε-constraint method

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

关键词: 运筹学, 危险品运输, 重大事故规避, 实时装载量, ε-约束法