不确定条件下危险品配送路线多准则优化

doi:10.13229/j.cnki.jdxbgxb20170894

摘要/Abstract

摘要：

针对非满载的危险品配送车辆路线优化问题,考虑危险品数量对运输风险的影响,利用分段线性逼近方法对配送过程中的潜在风险动态评估。根据运输企业的不同优化准则以及配送路线的不确定性属性,基于可信性理论和期望值方法,建立了有容量约束的危险品配送路线多准则优化模型。设计了改进的模拟退火算法对模型求解,并利用快速非支配排序方法和动态拥挤距离计算方法提高求解效率,改善Pareto解在解空间内分布的均匀性,结合解的编码方式设计变邻域搜索策略提高算法的局部和全局搜索能力。采用不同算例验证了模型的合理性和算法的有效性,研究结果可为危险品运输企业在多种不确定条件下的配送路线选择提供决策支持。

关键词: 交通运输安全工程, 配送路线优化, 动态风险评价, 模拟退火算法, 变邻域搜索

Abstract:

To solve the distribution route optimization problem for not-fully loaded vehicles of Hazardous Materials (HM), a piece-wise linear approximation method was used to evaluate the potential transport risk dynamically with consideration of the impact of HM quantity. According to different optimization criteria of the transportation enterprises and the uncertainties of route attributes, a multi-criteria optimization model for distribution routes of HM with capacity constraints was formulated based on the credibility theory and expected value method. An improved simulated annealing algorithm was designed to solve this model. The fast non-dominated sorting method and the dynamic crowding distance calculation method were used to increase the solving efficiency and to improve the distribution uniformity of Pareto optimal solutions in solution-space. The variable neighborhood search strategies were designed based on the coding structure of the solution to enhance the local and global search ability of this algorithm. Different examples were used to illustrate the rationality of the model and the effectiveness of the algorithm. The research results can provide decision support for the distribution route selection of HM transport enterprises under multiple uncertain conditions.

Key words: transportation safety engineering, distribution routes optimization, dynamic risk evaluation, simulated annealing algorithm, variable neighborhood search

中图分类号:

U116.2

代存杰,李引珍,马昌喜,柴获,牟海波. 不确定条件下危险品配送路线多准则优化[J]. 吉林大学学报(工学版), 2018, 48(6): 1694-1702.

DAI Cun-jie,LI Yin-zhen,MA Chang-xi,CHAI Huo,MU Hai-bo. Multi-criteria optimization for hazardous materials distribution routes under uncertain conditions[J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1694-1702.

图/表 8

图1

图2

表1

Benchmark算例的计算结果"

算例	$MD$	$MC$	$BD$	DGap/%
X-n101-k25	27602	70028	27591	0.04
X-n125-k30	55539	187535	55539	0.00
X-n153-k22	21267	69513	21220	0.22
X-n181-k23	25584	70479	25569	0.06
X-n195-k51	44237	122924	44225	0.03
X-n204-k19	19565	58373	19565	0.00
X-n214-k11	10902	30317	10856	0.42
X-n233-k16	19256	54280	19230	0.13
X-n251-k28	38716	109114	38684	0.01
X-n298-k31	34247	90203	34231	0.05

表1

表2

各优化准则对应的前3组最优配送路线"

序号	$f R (x)$ /人	$f C (x)$	$f T (x)$ /h	$VN$ /辆	$Routes$
R-1	34.73	0.03	34.22	10	0-5-7-0-15-18-0-16-8-0-4-1-0-20-14-2-13-0-17-10-19-0-6-0-12-3-0-11-0-9-0
R-2	35.59	0.11	35.18	10	0-5-7-0-19-18-0-16-8-0-4-1-0-17-13-2-14-0-10-11-0-9-0-15-0-6-0-12-3-0
R-3	35.38	0.92	35.45	9	0-6-7-0-15-18-0-3-8-0-12-1-0-16-14-2-13-0-20-19-10-0-4-5-0-17-9-0-11-0
C-1	54.85	1.00	34.58	9	0-6-7-0-15-18-0-3-8-0-4-1-0-17-14-2-13-0-20-19-10-0-12-5-0-16-9-0-11-0
C-2	55.35	1.00	33.60	9	0-4-20-0-6-10-13-0-17-5-2-0-11-0-12-19-0-8-16-14-0-15-18-0-3-1-0-7-9-0
C-3	68.14	1.00	30.10	9	0-15-20-0-6-10-13-0-5-17-2-0-11-0-12-19-0-4-16-14-0-9-18-0-3-8-0-7-1-0
T-1	410.04	0.08	27.14	9	0-9-7-0-15-18-0-19-8-0-4-1-0-16-14-13-10-0-17-2-5-0-6-0-12-3-0-11-0
T-2	395.19	0.94	27.29	9	0-6-7-0-15-18-0-19-8-0-4-1-0-16-14-13-10-0-17-2-5-0-12-3-0-11-0-9-0
T-3	398.45	0.99	27.64	9	0-7-6-0-15-18-0-19-8-0-4-1-0-16-14-2-10-0-17-13-5-0-12-3-0-9-0-11-0

表2

表3

不同优化准则对应的最优配送路线"

序号	$f R (x)$ /人	$f C (x)$	$f T (x)$ /h	$VN$ /辆	$Routes$
1	14.73	0.95	32.26	10	0-9-7-0-4-18-0-3-8-0-12-1-0-16-14-2-13-0-20-19-10-0-6-0-17-5-0-11-0-15-0
2	16.64	1.0	34.68	9	0-6-7-0-15-18-0-3-8-0-4-1-0-17-14-2-13-0-19-20-10-0-9-16-0-12-5-0-11-0
3	31.43	0.11	27.19	9	0-6-7-0-15-18-0-19-8-0-4-1-0-10-13-2-14-0-17-5-16-0-12-3-0-11-0-9-0

表3

表4

不同ρ及S下的计算结果及计算时间"

$ρ$	$S$	( $f R (x), av e R$ )/人	( $f C (x), av e C$ )	( $f T (x), av e T$ )/h	计算时间/s
0.2 0.2 0.2	100 200 400	(113.04,282.71) (113.04,245.47) (92.18,211.52)	(0.95,0.46) (0.98,0.62) (0.98,0.63)	(36.67,39.76) (32.14,35.44) (32.08,35.91)	14.73 38.26 61.88
0.5 0.5 0.5	100 200 400	(36.52,226.33) (34.73,189.95) (32.84,192.18)	(1.00,0.78) (1.00,0.84) (1.00,0.86)	(28.79,31.28) (27.14,30.01) (27.08,31.47)	68.35 142.71 247.26
0.8 0.8 0.8	100 200 400	(36.38,201.29) (33.15,162.77) (32.84,153.29)	(1.00,0.82) (1.00,0.90) (1.00,0.89)	(27.21,31.17) (26.68,28.06) (26.68,28.43)	153.62 286.74 527.96

表4

图3

表5

不同算法的计算结果及计算时间"

算法	( $f R (x), av e R$ )/人	( $f C (x), av e C$ )	( $f T (x), av e T$ )/h	计算时间/s
NSSA	(34.73,189.95)	(1.00,0.84)	(27.14,30.01)	68.35
NSGA-II	(34.73,214.27)	(1.00,0.79)	(28.49,30.42)	46.18
AMOSA	(36.38,238.52)	(1.00,0.78)	(27.29,29.92)	92.36

表5

参考文献 30

[1]	Pradhananga R, Taniguchi E, Yamada T , et al. Environmental analysis of Pareto optimal routes in hazardous material transportation[J]. Procedia-Social and Behavioral Sciences, 2014,125(1):506-517. doi: 10.1016/j.sbspro.2014.01.1492
[2]	Bula G A, Prodhon C, Gonzalez F A , et al. Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation[J]. Journal of Hazardous Materials, 2017,324(PtB):472-480. doi: 10.1016/j.jhazmat.2016.11.015
[3]	Tarantilis C, Kiranoudis C T . Using the vehicle routing problem for the transportation of hazardous materials[J]. Operational Research, 2001,1(1):67-78. doi: 10.1007/BF02936400
[4]	Androutsopoulos K N, Zografos K G . Solving the bicriterion routing and scheduling problem for hazardous materials distribution[J]. Transportation Research Part C: Emerging Technologies, 2010,18(5):713-726. doi: 10.1016/j.trc.2009.12.002
[5]	Androutsopoulos K N, Zografos K G . A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution[J]. Euro Journal on Transportation & Logistics, 2012,1(1/2):157-183. doi: 10.1007/s13676-012-0004-y
[6]	Zografos K G, Androutsopoulos K N . A heuristic algorithm for solving hazardous materials distribution problems[J]. European Journal of Operational Research, 2004,152(2):507-519. doi: 10.1016/S0377-2217(03)00041-9
[7]	Zografos K G, Androutsopoulos K N . A decision support system for integrated hazardous materials routing and emergency response decisions[J]. Transportation Research Part C: Emerging Technologies, 2008,16(6):684-703. doi: 10.1016/j.trc.2008.01.004
[8]	Pradhananga R, Taniguchi E, Yamada T . Ant colony system based routing and scheduling for hazardous material transportation[J]. Procedia-Social and Behavioral Sciences, 2010,2(3):6097-6108. doi: 10.1016/j.sbspro.2010.04.022
[9]	Pradhananga R, Taniguchi E, Yamada T , et al. Bi-objective decision support system for routing and scheduling of hazardous materials[J]. Socio-Economic Planning Sciences, 2014,48(2):135-148. doi: 10.1016/j.seps.2014.02.003
[10]	吕品 . 基于改进VRP模型的危险品配送路径优化及其求解研究[J]. 中国安全生产科学技术, 2011,7(11):87-91.
	Lyu Pin . Research on route optimization and algorithm of hazardous materials distribution based on improved VRP model[J]. Journal of Safety Science and Technology, 2011,7(11):87-91.
[11]	于晓桦, 刘凯峥, 刘浩学 , 等. 基于遗传算法的固定起讫点危险品配送路线优化[J]. 数学的实践与认识, 2013,43(12):44-50.
	Yu Xiao-hua, Liu Kai-zheng, Liu Hao-xue , et al. Route optimization for dangerous material distribution with fixed origin and destination site based on improved genetic algorithm[J]. Mathematics in Practice and Theory, 2013,43(12):44-50.
[12]	李双琳, 马祖军, 邹坤 . 危险品物流中的多目标定位-路径问题[J]. 运筹与管理, 2014,23(3):8-15. doi: 10.3969/j.issn.1007-3221.2014.03.002
	Li Shuang-lin, Ma Zu-jun, Zou Kun . Multi-objective location-routing problem for hazardous materials logistics[J]. Operations Research and Management Science, 2014,23(3):8-15. doi: 10.3969/j.issn.1007-3221.2014.03.002
[13]	Bula G A, Gonzalez F A, Prodhon C , et al. Mixed integer linear programming model for vehicle routing problem for hazardous materials transportation[J]. IFAC Papersonline, 2016,49(12):538-543. doi: 10.1016/j.ifacol.2016.07.691
[14]	袁文燕, 徐腾飞, 杨丰梅 , 等. 基于新风险度量方式的危险品车辆路径双目标优化模型[J]. 数学的实践与认识, 2016,46(14):275-284.
	Yuan Wen-yan, Xu Teng-fei, Yang Feng-mei , et al. Bi-objective decision model for vehicle routing of hazardous material based on new risk measure[J]. Mathematics in Practice and Theory, 2016,46(14):275-284.
[15]	Button N P, Reilly P M . Uncertainty in incident rates for trucks carrying dangerous goods[J]. Accident Analysis & Prevention, 2000,32(6):797-804. doi: 10.1016/S0001-4575(00)00003-8 pmid: 10994607
[16]	Chang T S, Nozick L K, Turnquist M A . Multiobjective path finding in stochastic dynamic networks, with application to routing hazardous materials shipments[J]. Transportation Science, 2005,39(3):383-399. doi: 10.1287/trsc.1040.0094
[17]	Jia H, Zhang L, Lou X , et al. A fuzzy-stochastic constraint programming model for hazmat road transportation considering terrorism attacking[J]. Systems Engineering Procedia, 2011,1:130-136. doi: 10.1016/j.sepro.2011.08.022
[18]	Du J, Li X, Yu L , et al. Multi-depot vehicle routing problem for hazardous materials transportation[J]. Information Sciences, 2017,399(C):201-218. doi: 10.1016/j.ins.2017.02.011
[19]	秦军昌, 张金梁, 王刊良 . 危险品运输线路问题的鲁棒优化模型[J]. 统计与决策, 2009(20):25-26.
	Qin Jun-chang, Zhang Jin-liang, Wang Kan-liang . Robust optimization model of hazardous materials transportation route[J]. Statistics and Decision, 2009,24(20):25-26.
[20]	Erkut E, Ingolfsson A . Transport risk models for hazardous materials: revisited[J]. Operations Research Letters, 2013,33(1):81-89. doi: 10.1016/j.orl.2004.02.006
[21]	Abkowitz M, Cheng P D . Developing a risk/cost framework for routing truck movements of Hazardous materials[J]. Accident Analysis and Prevention, 1988,20(1):39-51. doi: 10.1016/0001-4575(88)90013-9 pmid: 3337764
[22]	Guo X, Verma M . Choosing vehicle capacity to minimize risk for transporting flammable materials[J]. Journal of Loss Prevention in the Process Industries, 2010,23(2):220-225. doi: 10.1016/j.jlp.2009.07.007
[23]	Liu B . Theory and Practice of Uncertain Programming[M]. Heidelberg:Physica-Verlag, 2002: 41-43.
[24]	Li X . Credibilistic Programming: An Introduction to Models and Applications[M]. Heidelberg:Springer-Verlag, 2013: 31-43.
[25]	Hassanzadeh R, Mahdavi I, Mahdavi-Amiri N , et al. A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths[J]. Mathematical & Computer Modelling, 2013,57(1/2):84-99. doi: 10.1016/j.mcm.2011.03.040
[26]	王占中, 赵利英, 曹宁博 . 基于多层编码遗传算法的危险品运输调度模型[J]. 吉林大学学报:工学版, 2017,47(3):751-755. doi: 10.13229/j.cnki.jdxbgxb201703009
	Wang Zhan-zhong, Zhao Li-ying, Cao Ning-bo . Hazardous material transportation scheduling model based on mutilayer coding genetic algorithm[J]. Journal of Jilin University (Engineering and Technology Edition), 2017,47(3):751-755. doi: 10.13229/j.cnki.jdxbgxb201703009
[27]	Eglese R W . Simulated annealing: A tool for operational research[J]. European Journal of Operational Research, 1990,46(3):271-281. doi: 10.1016/0377-2217(90)90001-R
[28]	Deb K, Pratap A, Agarwal S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197. doi: 10.1109/4235.996017
[29]	Uchoa E, Pecin D, Pessoa A , et al. New benchmark instances for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2016,257(3):845-858. doi: 10.1016/j.ejor.2016.08.012
[30]	Han D H, Kim Y D, Lee J Y . Multiple-criterion shortest path algorithms for global path planning of unmanned combat vehicles[J]. Computers & Industrial Engineering, 2014,71(1):57-69. doi: 10.1016/j.cie.2014.02.013

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed