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

doi:10.3934/mbe.2021009

Mathematical Biosciences and Engineering, 2021, 18(1): 166-181. doi: 10.3934/mbe.2021009. Research article

Export file:

Format

RIS(for EndNote,Reference Manager,ProCite)
BibTex
Text

Content

Citation Only
Citation and Abstract

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

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: , Accepted: , Published:

Abstract Full Text(HTML) Figure/Table

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.

Figure/Table

Supplementary

Article Metrics

Keywords: 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. Mathematical Biosciences and Engineering, 2021, 18(1): 166-181. doi: 10.3934/mbe.2021009

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.
2. O. A. Hjelkrem, E. O. Ryeng, Chosen risk level during car-following in adverse weather conditions, Accid. Anal. Prev., 95 (2016), 227-235.
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.
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.
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.
8. G. Poonthalir, R. Nadarajan, M. Senthil Kumar, Hierarchical optimization of green routing for mobile advertisement vehicle, J. Clean. Prod., 258 (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.
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.
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.
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.
13. S. Jayaswal, N. Vidyarthi, Facility location under service level constraints for heterogeneous customers, Ann. Oper. Res., 253 (2017), 275-305.
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.
15. N. Perrier, A. Langevin, J.F. Campbell, A survey of models and algorithms for winter road maintenance. Part IV: Vehicle routing and fleet sizing for plowing and snow disposal, Comput. Oper. Res., 34 (2007), 258-294.
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.
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.
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.
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.
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.
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.
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.
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.

show all references

Reader Comments

your name: * your email: *

Download full text in PDF

Associated material

Metrics