A vulnerability-based vehicle routing approach for solving capacitated arc routing problem in urban snow plowing operations

Lei Jin; Sixiang Lin; Binglei Xie; Lin Liu; Lei Jin; Sixiang Lin; Binglei Xie; Lin Liu

doi:10.3934/mbe.2021009

Mathematical Biosciences and Engineering

2021, Volume 18, Issue 1: 166-181. doi: 10.3934/mbe.2021009

Previous Article Next Article

Research article

A vulnerability-based vehicle routing approach for solving capacitated arc routing problem in urban snow plowing operations

1.
School of Civil and Transportation Engineering, Guangdong University of Technology, Guangzhou 510006, China
2.
School of Architecture, Harbin Institute of Technology, Shenzhen 518055, China

Received: 24 September 2020 Accepted: 22 November 2020 Published: 25 November 2020

Vehicle drivers usually perceive a higher risk when driving on snow covered roads. The city cleaning efficiency would directly influence the risk and mitigation of wintertime events, especially for snow covered roads. Under the risk-informed approach background, more attention is paid to the capacitated arc routing problem (CARP) of urban snow plowing operations. Current algorithms mainly relies on the topology of road network without considering snow covered pavement's negative effect on road capacity and traffic flow. This paper proposes a vulnerability-based parallel heuristic algorithms applied for the CARP by implementing risk-informed approach. First, a method is proposed to set service priorities based on the vulnerability evaluation by considering the added cost of travel demands. Second, a sub-process path-scanning approach is developed to avoid redundant path scans. Then verification and comparison between this newly proposed constructive heuristic and existing algorithms of whole-process path-scanning and sequential processing are conducted. Results show that the sub-process path-scanning approach obviously costs less service completion time than the existing algorithms for solving the CARP. However, this improved algorithm would also cause an increase of deadhead time upon dispatch. The balance between service completion time and deadhead time for more routing problems would be discussed in the near future.
- capacitated arc routing problem,
- climate-resilient transport,
- risk-informed approach,
- snow and freezing event,
- urban snow plowing operations,
- vulnerability evaluation
Citation: Lei Jin, Sixiang Lin, Binglei Xie, Lin Liu. A vulnerability-based vehicle routing approach for solving capacitated arc routing problem in urban snow plowing operations[J]. Mathematical Biosciences and Engineering, 2021, 18(1): 166-181. doi: 10.3934/mbe.2021009

Related Papers:

Abstract

Vehicle drivers usually perceive a higher risk when driving on snow covered roads. The city cleaning efficiency would directly influence the risk and mitigation of wintertime events, especially for snow covered roads. Under the risk-informed approach background, more attention is paid to the capacitated arc routing problem (CARP) of urban snow plowing operations. Current algorithms mainly relies on the topology of road network without considering snow covered pavement's negative effect on road capacity and traffic flow. This paper proposes a vulnerability-based parallel heuristic algorithms applied for the CARP by implementing risk-informed approach. First, a method is proposed to set service priorities based on the vulnerability evaluation by considering the added cost of travel demands. Second, a sub-process path-scanning approach is developed to avoid redundant path scans. Then verification and comparison between this newly proposed constructive heuristic and existing algorithms of whole-process path-scanning and sequential processing are conducted. Results show that the sub-process path-scanning approach obviously costs less service completion time than the existing algorithms for solving the CARP. However, this improved algorithm would also cause an increase of deadhead time upon dispatch. The balance between service completion time and deadhead time for more routing problems would be discussed in the near future.

References

[1]	J. Gao, Analysis and assessment of the risk of snow and freezing disaster in China, Int. J. Disaster Risk Reduct., 19 (2016), 334-340. doi: 10.1016/j.ijdrr.2016.09.007
[2]	O. A. Hjelkrem, E. O. Ryeng, Chosen risk level during car-following in adverse weather conditions, Accid. Anal. Prev., 95 (2016), 227-235. doi: 10.1016/j.aap.2016.07.006
[3]	Y. Feng, L. Xiang-Yang, Improving emergency response to cascading disasters: Applying case-based reasoning towards urban critical infrastructure, Int. J. Disaster Risk Reduct., 30 (2018), 244-256. doi: 10.1016/j.ijdrr.2018.04.012
[4]	J. O. Ebinger, N.L. Vandycke, Moving toward climate-resilient transport: The World Bank's experience from building adaptation into programs. Washington, D. C.: World Bank Group, 2015. http://documents.worldbank.org/curated/en/177051467994683721/Moving-toward-climate-resilient-transport-the-World-Bank-s-experience-from-building-adaptation-into-programs.
[5]	N. Perrier, A. Langevin, C. A. Amaya, Vehicle routing for urban snow plowing operations, Transp. Sci., 42 (2008), 44-56. doi: 10.1287/trsc.1070.0195
[6]	K. Holmberg, The (Over) zealous snow remover problem, Transp. Sci., 53 (2019), 867-881.
[7]	S. Yang, F. Hu, R.G. Thompson, W. Wang, Y. Li, S. Li, W. Ni, Criticality ranking for components of a transportation network at risk from tropical cyclones, Int. J. Disaster Risk Reduct., 28 (2018), 43-55. doi: 10.1016/j.ijdrr.2018.02.017
[8]	G. Poonthalir, R. Nadarajan, M. Senthil Kumar, Hierarchical optimization of green routing for mobile advertisement vehicle, J. Clean. Prod., 258 (2020), 120661. doi: 10.1016/j.jclepro.2020.120661
[9]	L. Zhen, M. Li, G. Laporte, W. Wang, A vehicle routing problem arising in unmanned aerial monitoring, Comput. Oper. Res., 105 (2019), 1-11. doi: 10.1016/j.cor.2019.01.001
[10]	H. Asefi, S. Shahparvari, P. Chhetri, Integrated Municipal Solid Waste Management under uncertainty: A tri-echelon city logistics and transportation context, Sustain. Cities Soc., 50 (2019), 101606. doi: 10.1016/j.scs.2019.101606
[11]	X. Zuo, Y. Xiao, M. You, I. Kaku, Y. Xu, A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function, J. Clean. Prod., 236 (2019), 117687. doi: 10.1016/j.jclepro.2019.117687
[12]	R. Kendy Arakaki, F. Luiz Usberti, An efficiency-based path-scanning heuristic for the capacitated arc routing problem, Comput. Oper. Res., 103 (2019), 288-295. doi: 10.1016/j.cor.2018.11.015
[13]	S. Jayaswal, N. Vidyarthi, Facility location under service level constraints for heterogeneous customers, Ann. Oper. Res., 253 (2017), 275-305. doi: 10.1007/s10479-016-2353-7
[14]	L.S. Franca, G.M. Ribeiro, G. de L.D. Chaves, The planning of selective collection in a real-life vehicle routing problem: A case in Rio de Janeiro, Sustain. Cities Soc., 47 (2019), 101488. doi: 10.1016/j.scs.2019.101488
[15]	N. Perrier, A. Langevin, J.F. Campbell, A survey of models and algorithms for winter road maintenance. Part Ⅳ: Vehicle routing and fleet sizing for plowing and snow disposal, Comput. Oper. Res., 34 (2007), 258-294. doi: 10.1016/j.cor.2005.05.008
[16]	L. Santos, J. Coutinho-Rodrigues, J.R. Current, An improved heuristic for the capacitated arc routing problem, Comput. Oper. Res., 36 (2009), 2632-2637. doi: 10.1016/j.cor.2008.11.005
[17]	X. Zhu, A. Garcia-Diaz, M. Jin, Y. Zhang, Vehicle fuel consumption minimization in routing over-dimensioned and overweight trucks in capacitated transportation networks, J. Clean. Prod., 85 (2014), 331-336. doi: 10.1016/j.jclepro.2013.10.036
[18]	J. Li, D. Wang, J. Zhang, Heterogeneous fixed fleet vehicle routing problem based on fuel and carbon emissions, J. Clean. Prod., 201 (2018), 896-908. doi: 10.1016/j.jclepro.2018.08.075
[19]	L. Jin, H. Wang, B. Xie, L. Yu, L. Liu, A user exposure based approach for non-structural road network vulnerability analysis, PLoS One., 12 (2017), 0188790.
[20]	T. Kwon, L. Fu, C. Jiang, Effect of winter weather and road surface conditions on macroscopic traffic parameters, Transp. Res. Rec., 2329 (2013), 54-62. doi: 10.3141/2329-07
[21]	F. Ma, Y. Liang, K.F. Yuen, Q. Sun, Y. Zhu, Y. Wang, W. Shi, Assessing the vulnerability of urban rail transit network under heavy air pollution: A dynamic vehicle restriction perspective, Sustain. Cities Soc., 52 (2020), 101851. doi: 10.1016/j.scs.2019.101851
[22]	J. Cheng, G. Zeng, An agent-oriented approach to process partition and planning in migrating workflow systems, Eng. Appl. Artif. Intell., 25 (2012), 837-845. doi: 10.1016/j.engappai.2011.09.027
[23]	Y. Xiao, A. Konak, A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem, J. Clean. Prod., 167 (2017), 1450-1463. doi: 10.1016/j.jclepro.2016.11.115
[24]	A. Chen, C. Yang, S. Kongsomsaksakul, M. Lee, Network-based acessibility measures for vulnerability analysis of degradable transportation networks, Networks Spat. Econ., 7 (2007), 241-256. doi: 10.1007/s11067-006-9012-5

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)