Research article

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

  • 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.

    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:

  • 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.


    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3150) PDF downloads(118) Cited by(0)

Article outline

Figures and Tables

Figures(3)  /  Tables(4)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog