不确定环境下的危险品运输车辆路径优化

doi:10.3778/j.issn.1002-8331.2201-0137

摘要/Abstract

摘要： 针对非满载危险品运输车辆路径优化问题，通过模糊变量刻画运输过程中的人口密度、行驶速度与运输时间以及客户需求量等方面的不确定因素，考虑载货量变化对风险评估的影响，建立基于动态载货量的风险评估模型，以运输总风险、车辆总行程、车辆使用数最小为优化目标，同时兼顾时间窗、事故概率、载货量等约束构建了不确定环境下的危险品运输车辆路径多目标优化模型。将NSGA-II算法与LNS算法相结合，设计混合NSGA-II算法求解模型。结果表明，混合NSGA-II算法可以获得空间分布均匀且收敛性较好的Pareto解集，不同运输参与者可根据自身偏好在解集中选择相应的配送方案；该算法得到的最优总风险、总行程及车辆使用数目分别比NSGA-II算法优化了11.5%、1.0%和14.3%，算法搜索性能和求解精度明显提高。

关键词: 危险品运输, 不确定环境, 动态载货量, 混合NSGA-II算法, 路径优化

Abstract: Aiming at the route optimization problem of non-fully loaded hazardous material transportation vehicles in uncertain environment, the uncertain factors in the transportation process are described by fuzzy variables, and considering the impact of cargo volume change on risk assessment, a risk assessment model based on dynamic cargo volume is established. The optimization objectives are to minimize the total risk of transportation, the total travel of vehicles and the number of vehicles used, taking into account the time window based on the constraints of accident probability and load capacity, a multi-objective optimization model of hazardous material transportation vehicle route in uncertain environment is constructed. Combining NSGA-II algorithm with LNS algorithm, a hybrid NSGA-II algorithm solution model is designed. The results show that the hybrid NSGA-II algorithm can obtain the Pareto solution set with uniform spatial distribution and good convergence, and different transportation participants can choose the corresponding distribution scheme in the solution set according to their own preferences. The optimal total risk, total journey and number of vehicles obtained by the algorithm are 11.5%, 1.0% and 14.3% better than NSGA-II algorithm respectively. The search performance and solution accuracy of the algorithm are significantly improved.

Key words: transportation of dangerous goods, uncertain environment, dynamic load capacity, hybrid NSGA-II algorithm, path optimization

王琴, 杨信丰, 李楠, 李平, 方晟浩. 不确定环境下的危险品运输车辆路径优化[J]. 计算机工程与应用, 2022, 58(15): 309-316.

WANG Qin, YANG Xinfeng, LI Nan, LI Ping, FANG Shenghao. Route Optimization of Hazardous Materials Transportation Vehicles in Uncertain Environment[J]. Computer Engineering and Applications, 2022, 58(15): 309-316.

参考文献

[1] 柴获，何瑞春，马昌喜，等.危险品运输车辆路径问题的多目标优化[J].中国安全科学学报，2015，25（10）：84-90.
CHAI H，HE R C，MA C X，et al.Multi-objective optimization of hazardous materials transportation vehicle route problem[J].China Safety Science Journal，2015，25（10）：84-90.
[2] 代存杰，李引珍，马昌喜，等.随机时间依赖路网中危险品运输路径多准则优化[J].哈尔滨工业大学学报，2018，50（3）：156-164.
DAI C J，LI Y Z，MA C X，et al.Multi-criterion path optimization for hazardous materials transportation in stochastic time dependent road networks[J].Journal of Harbin Institute of Technology，2018，50（3）：156-164.
[3] LIU L，YANG X.Travel time reliability-based rescue resource scheduling for accidents concerning transport of dangerous goods by rail[J].Algorithms，2021，14（11）：325.
[4] BULA G A，AFSAR H M，GONZáLEZ F A，et al.Bi-objective vehicle routing problem for hazardous material transportation[J].Journal of Cleaner Production，2019，206：976-986.
[5] 李立，邓雨桐，牟玲玲.基于改进NSGA-II算法的危险品运输路径优化研究[J].安全与环境工程，2021，28（1）：111-117.
LI L，DENG Y T，MOU L L.Path optimization of danger-ous goods transportation based on improved NSGA-II algorithm[J].Safety and Environmental Engineering，2021，28（1）：111-117.
[6] 薛翔，朱小林.不确定需求下危险品运输路径问题的多目标优化[J].中国安全科学学报，2016，26（11）：93-98.
XUE X，ZHU X L.Multi-objective optimization of hazardous materials transportation route under uncertain demand condition[J].China Safety Science Journal，2016，26（11）：93-98.
[7] GHANNADPOUR S F，NOORI S，TAVAKKOLI-MOGHADDAM R，et al.A multi-objective dynamic vehicle routing problem with fuzzy time windows：model，solution and application[J].Applied Soft Computing，2014，14：504-527.
[8] KANG Y，BATTA R，KWON C.Generalized route planning model for hazardous material transportation with VaR and equity considerations[J].Computers & Operations Research，2014，43：237-247.
[9] MEN J，JIANG P，XU H.A chance constrained programming approach for HazMat capacitated vehicle routing problem in Type-2 fuzzy environment[J].Journal of Cleaner Production，2019，237.
[10] 魏福禄，刘攀，李志斌，等.基于风险价值的危险品运输路径优化方法[J].交通信息与安全，2020，38（3）：17-23.
WEI F L，LIU P，LI Z B，et al.A optimal routing method of hazardous materials transportation based on VaR[J].Journal of Transport Information and Safety，2020，38（3）：17-23.
[11] ZHANG H，YUAN M，LIANG Y，et al.A risk assessment based optimization method for route selection of hazardous liquid railway network[J].Safety Science，2018，110：217-229.
[12] 葛显龙，薛桂琴.不确定环境下多品类共同配送路径优化[J].计算机工程与应用，2019，55（9）：264-270.
GE X L，XUE G Q.Multi-products joint distribution vehicle routing optimization with uncertain circumstance[J].Computer Engineering and Applications，2019，55（9）：264-270.
[13] 张翔，王永刚，李赵钰.城市道路危险品运输路线风险评价方法[J].综合运输，2021，43（10）：34-38.
ZHANG X，WANG Y G，LI Z Y.Risk assessment method of urban road dangerous goods transportation route[J].China Transportation Review，2021，43（10）：34-38.
[14] HOLECZEK N.Analysis of different risk models for the hazardous materials vehicle routing problem in urban areas[J].Cleaner Environmental Systems，2021，2：100022.
[15] SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research，1987，35（2）：254-265.
[16] LIU L，LI J，ZHOU L，et al.Research on route optimization of hazardous materials transportation considering risk equity[J].Sustainability，2021，13（16）：9427.
[17] 张圣忠，陈婷婷，孙荣庭，等.考虑载货量的危险品运输车辆路径优化[J].武汉理工大学学报（信息与管理工程版），2020，42（4）：290-297.
ZHANG S Z，CHEN T T，SUN R T，et al.Research on optimization of hazardous materials transportation vehicle route considering load capacity[J].Journal of Wuhan University of Technology（Information and Management Engineering），2020，42（4）：290-297.
[18] IWAMURA K，LIU B.A genetic algorithm for chance constrained programming[J].Journal of Information and Optimization Sciences，1996，17（2）：409-422.
[19] SHAW P.A new local search algorithm providing high quality solutions to vehicle routing problems[D].Glasgow，Scotland，UK：University of Strathclyde.Dept of Computer Science.APES Group，1997.
[20] 南丽君，陈彦如，张宗成.改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题[J].计算机应用研究，2021，38（10）：2926-2934.
NAN L J，CHEN Y R，ZHANG Z C.Improved adaptive large neighborhood search algorithm for mixed fleet routing problem of dynamic demands[J].Application Research of Computers，2021，38（10）：2926-2934.
[21] 何东东，李引珍.多车型绿色车辆路径问题优化模型[J].计算机应用，2018，38（12）：3618-3624.
HE D D，LI Y Z.Optimization model of green multi-type vehicles routing problem[J].Journal of Computer Applications，2018，38（12）：3618-3624.