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

doi:10.13229/j.cnki.jdxbgxb20170894

Abstract

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

CLC Number:

U116.2

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.

Figures/Tables 8

Fig.1

Fig.2

Table 1

Calculation results of benchmark examples"

算例	$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

Table 1

Table 2

The first three optimal distribution routes of each criterion"

序号	$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

Table 2

Table 3

Optimal distribution routes of different optimization criteria"

序号	$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

Table 3

Table 4

Calculation results and running time with different ρ and 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

Table 4

Fig.3

Table 5

Calculation results and running time of different algorithms"

算法	( $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

Table 5

References 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

Comments

Recommended 10

[1]	LI Shoutao, LI Yuanchun. Autonomous Mobile Robot Control Algorithm Based on Hierarchical Fuzzy Behaviors in Unknown Environments[J]. 吉林大学学报(工学版), 2005, 35(04): 391 -397 .
[2]	Zhang Quan-fa，Li Ming-zhe，Sun Gang，Ge Xin . Comparison between flexible and rigid blank-holding in multi-point forming[J]. 吉林大学学报(工学版), 2007, 37(01): 25 -30 .
[3]	Nie Jian-jun，Du Fa-rong，Gao Feng . Finite time thermodynamics of real combined power cycle operating between internal combustion engine and Stirling engine with heat leak[J]. 吉林大学学报(工学版), 2007, 37(03): 518 -0523 .
[4]	Bao Tie，Liu Shu-fen . Network fault management formal description based on Communication Sequential Processes （CSP）[J]. 吉林大学学报(工学版), 2007, 37(01): 117 -120 .
[5]	Shao Bao-dong Sun Zhao-wei,Wang Li-feng . Optimization design of structural size of microchannel cooling heat sink[J]. 吉林大学学报(工学版), 2007, 37(02): 313 -0318 .
[6]	Dong Li-yan, Yuan Sen-miao,Liu Guang-yuan, Li Yong-li,Guan Wei-zhou . Constrained classifier learning algorithm based on genetic algorithm[J]. 吉林大学学报(工学版), 2007, 37(03): 595 -0599 .
[7]	Wang Gang，Liu Xiao-guang，Dong Sha-sha，Liu Jing . Research on optimal redundancy doubleerasurecorrecting data layout[J]. 吉林大学学报(工学版), 2007, 37(03): 611 -0615 .
[8]	Fan Yong-kai，Lin Jun，Sun Tian-ze，Sui Yang-yi . Requirementdriven virtual instrument software automatic generation framework[J]. 吉林大学学报(工学版), 2007, 37(03): 606 -0610 .
[9]	Hao Dong-lai，Ge Jian-hua . Precodingbased semi-blind channel estimation for MIMO systems[J]. 吉林大学学报(工学版), 2007, 37(03): 686 -0690 .
[10]	Zhang Da-qing;He Qing-hua;Hao Peng;Chen Qian-gen . Robust trajectory tracking control of hydraulic excavator bucket[J]. 吉林大学学报(工学版), 2006, 36(06): 934 -938 .

Multi-criteria optimization for hazardous materials distribution routes under uncertain conditions

RICH HTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 8

References 30

Related Articles 15

Metrics

Comments

Recommended 10

[1]	SUN Lu, XU Jian, CUI Xiang-min. Panel data models for analysis and prediction of crash count [J]. 吉林大学学报(工学版), 2015, 45(6): 1771-1778.
[2]	LI Hui-hui, HUA Li, YANG Ning, LIU Kun. Multi-target association algorithm for remote sensing images based on MSA features and simulated annealing optimization [J]. 吉林大学学报(工学版), 2015, 45(4): 1353-1359.
[3]	XU Jian, SUN Lu. Modeling of excess zeros issue in crash count andysis [J]. 吉林大学学报(工学版), 2015, 45(3): 769-775.
[4]	HAN Xiao,LIU Shu-fen,XU Tian-qi. Improved K-medoids algorithm based on genetic simulated annealing algorithm [J]. 吉林大学学报(工学版), 2015, 45(2): 619-623.
[5]	JIN Li-sheng, WANG Yan, LIU Jing-hua, WANG Ya-li, ZHENG Yi. Front vehicle detection based on Adaboost algorithm in daytime [J]. 吉林大学学报(工学版), 2014, 44(6): 1604-1608.
[6]	JIN Li-sheng,NIU Qing-ning,LIU Jing-hua,QIN Yan-guang,YU Huan-huan. Driver cognitive distraction detection in different road lines [J]. 吉林大学学报(工学版), 2014, 44(3): 642-647.
[7]	ZHAN Wei, LYU Qing, SHANG Yue-quan. Analysis of gray-Markov forecasting for traffic accidents in highway tunnel group region [J]. 吉林大学学报(工学版), 2014, 44(01): 62-67.
[8]	LIU Luo, GUO Li-hong, XIAO Hui, WANG Jian-jun, WANG Gai-ge. Software reliability growth model based on SAA-DFNN [J]. , 2012, 42(05): 1225-1230.
[9]	JIN Li-sheng\| FANG Wen-ping, HOU Hai-jing, SUN Yu-qin. Co-simulation of lane keeping control system based on BP neural network [J]. 吉林大学学报(工学版), 2010, 40(03): 650-0654.
[10]	JIN Li-sheng, BART van Arem,YANG Shuang-bin1, MASCHA van der Voort,MARTIJN Tideman . Safety lane change model of vehicle assistant driving on highway [J]. 吉林大学学报(工学版), 2009, 39(03): 582-0586.
[11]	LI Yu-qing, XU Min-qiang, WANG Ri-xin . Scheduling observations of spot object of threeaxis stabilized satellites [J]. 吉林大学学报(工学版), 2008, 38(06): 1447-1451.
[12]	Li Bao-lin; Li Zhi-shu;Jin Hu; Sun Ji-rong;Chen Yan-hong. Test case generation base on R_N(K) criterion annealing algorithm [J]. 吉林大学学报(工学版), 2008, 38(03): 680-0684.
[13]	Zhang Fei-jun,Wang Yun-peng,Shi Shu-ming,Li Shi-wu,Sun Fu-shen, Wang Bin-bin . Simulation of road alignment design safety evaluation [J]. 吉林大学学报(工学版), 2007, 37(03): 528-0532.
[14]	Tian Jian, Li Jiang, Li Yaqiao. Calibration technique of photogrammetry of traffic accident scene [J]. 吉林大学学报(工学版), 2006, 36(增刊1): 136-0139.
[15]	Wang Yunpeng， Yang Zhifa， Li Shiwu， Wang Junli. Quantitative Assessment of Influence of Traffic Environment on Road Safety [J]. 吉林大学学报(工学版), 2006, 36(01): 119-0122.