Routing relief teams by introducing new urban congestion parameter and solving using GACD-MDVRP clustering through genetic algorithm

Document Type : Research Article

Authors

1 Department of Industrial Engineering, Tarbiat Modares University (TMU), Jalal-Al-Ahmad St., Tehran, Iran

2 Faculty of Industrial and Systems, Industrial and Systems, Tarbiat Modares, Tehran, Iran

Abstract

Emergency disaster-relief activities could dramatically reduce injuries and casualties, while routing and scheduling of the relief teams is also considered an important factor in reducing the fatalities. For this reason, in this paper, a new model is proposed for routing rescue teams considering time windows, capacitated and multi-depot vehicles. In this model, additional factors such as availability of relief centers, congestion and service standard for the vehicles. A new parameter has been developed to denote the congestion of each path and id incorporated into the model using the concept of Social Network Analysis (SNA). Finally, the model is solved using a COREI5 8GB system. The model is also implemented using the data obtained from the Roads and Transport Organization and the Iranian Red Crescent Society. The average accuracy of this algorithm was 87% after solving 23 problem samples and improvement of the runtime was 74% in large problems. The model is then applied to the case study of the 2017 earthquake in Kermanshah, Iran. A rescue scenario is generated using the historical data of I.R. Iran Road Maintenance Transportation Organization and the I.R. Relief and Rescue Organization of Red Crescent Society of Iran. In this study, simulations are conducted based on a case study with actual locations.

Keywords

Main Subjects

References

[1]Z. Shen, F. Ordónez, and M. M. Dessouky, “The minimum unmet demand stochastic vehicle routing problem,” Working paper 2006-07, University of Southern California, 2006.
[2]T. J. Cova and J. P. Johnson, “A network flow model for lane-based evacuation routing,” Transp. Res. Part A Policy Pract., vol. 37, no. 7, pp. 579–604, 2003.
[3]L. Margulis, P. Charosky, J. Fernandez, and M. A. Centeno, “Hurricane evacuation decision-support model for bus dispatch,” Fourth LACCEI Int. Lat. Am. Caribb. Conf. Eng. Technol. (LACCET),Breaking Front. Barriers Eng. Educ. Res. Pract., pp. 21–23, 2006.
[4]S. Shahparvari, B. Abbasi, P. Chhetri, and A. Abareshi, “Vehicle routing and scheduling for bushfire emergency evacuation,” in IEEE International Conference on Industrial Engineering and Engineering Management, 2015, vol. 2016–Janua, pp. 696–700.
[5]E. Pourrahmani, M. R. Delavar, P. Pahlavani, and M. A. Mostafavi, “Dynamic evacuation routing plan after an earthquake,” Nat. Hazards Rev., vol. 16, no. 4, 2015.
[6]F. Sayyady, “Optimizing the Use of Public Transit System in No-notice Evacuations in Urban Areas,” Optim. Use Public Transit Syst. No-notice Evacuations Urban Areas, 2007.
[7]I.R. Iran Road Maintenance Transportation Organization, “traffic counter files,” 2019. [Online]. Available: www.141.ir/trafficcounterfiles.
[8]M. Junxu, L. Dun, and Z. Wanhua, “Assembly errors analysis of linear axis of CNC machine tool considering component deformation,” Int. J. Adv. Manuf. Technol., vol. 86, no. 1–4, pp. 281–289, 2016.
[9]W. B. Du, Y. Gao, C. Liu, Z. Zheng, and Z. Wang, “Adequate is better: Particle swarm optimization with limited-information,” Appl. Math. Comput., vol. 268, pp. 832–838, 2015.
[10]Y. Shen, G. Ren, and Y. Liu, “Finding the biased-shortest path with minimal congestion in networks via linear-prediction of queue length,” Phys. A Stat. Mech. its Appl., vol. 452, pp. 229–240, 2016.
[11]K. Beom, Y. Chang, H. Seung, and J. Hawoong, “Path finding strategies in scale-free networks,” Phys. Rev. E, vol. 65, no. 2, 2002.
[12]Z.-Y. Jiang, J.-F. Ma, and Y.-L. Shen, “Check-in based routing strategy in scale-free networks,” Physica A, vol. 486, pp. 205–211, 2017.
[13]M. Girvan and N. ME, “Community structure in social and biological networks,” Proc Natl Acad Sci USA, pp. 7821–7826, 2002.
[14]XingqinQi, HuiminSong, JianliangWu, EdgarFuller, RongLuo, and Cun-QuanZhang, “Eb&D: A new clustering approach for signed social networks based on both edge-betweenness centrality and density of subgraphs,” Phys. A Stat. Mech. its Appl., vol. 482, pp. 147–157, 2017.
[15]A. R. Güner, A. Murat, and R. B. Chinnam, “Dynamic routing under recurrent and non-recurrent congestion using real-time ITS information,” Comput. Oper. Res., vol. 39, no. 2, pp. 358–373, 2012.
[16]M. R. Jabbarpour et al., “Ant-based vehicle congestion avoidance system using vehicular networks,” Eng. Appl. Artif. Intell., vol. 36, pp. 303–319, 2014.
[17]K. He, Z. Xu, and P. Wang, “A hybrid routing model for mitigating congestion in networks,” Phys. A Stat. Mech. its Appl., vol. 431, pp. 1–17, 2015.
[18]L. Wen and R. Eglese, “Minimum cost VRP with time-dependent speed data and congestion charge,” Comput. Oper. Res., vol. 56, pp. 41–50, 2015.
[19]Y. Xiao and A. Konak, “The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion,” Transp. Res. Part E Logist. Transp. Rev., vol. 88, pp. 146–166, 2016.
[20]E. Angelelli, I. Arsik, V. Morandi, M. Savelsbergh, and M. G. Speranza, “Proactive route guidance to avoid congestion,” Transp. Res. Part B Methodol., vol. 94, pp. 1–21, 2016.
[21]H. Abou-Senna, “Congestion pricing strategies to investigate the potential of route diversion on toll facilities using en-route guidance,” J. Traffic Transp. Eng. (English Ed., vol. 3, no. 1, pp. 59–70, 2016.
[22]C. Rizet, C. Cruz, and M. Vromant, “The Constraints of Vehicle Range and Congestion for the Use of Electric Vehicles for Urban Freight in France,” Transp. Res. Procedia, vol. 12, pp. 500–507, 2016.
[23]I. Kaddoura and K. Nagel, “Agent-based Congestion Pricing and Transport Routing with Heterogeneous Values of Travel Time Savings,” Procedia Comput. Sci., vol. 83, pp. 908–913, 2016.
[24]S. Le Vine and J. Polak, “A novel peer-to-peer congestion pricing marketplace enabled by vehicle-automation,” Transp. Res. Part A Policy Pract., vol. 94, pp. 483–494, 2016.
[25]M. Marufuzzaman and S. D. Ekşioğlu, “Managing congestion in supply chains via dynamic freight routing: An application in the biomass supply chain,” Transp. Res. Part E Logist. Transp. Rev., vol. 99, pp. 54–76, 2017.
[26]E. Angelelli, V. Morandi, and M. G. Speranza, “Congestion avoiding heuristic path generation for the proactive route guidance,” Comput. Oper. Res., vol. 99, pp. 234–248, 2018.
[27]J. Echagüe, V. Cholvi, and D. R. Kowalski, “Effective use of congestion in complex networks,” Phys. A Stat. Mech. its Appl., vol. 494, pp. 574–580, 2018.
[28]M. Farda and C. Balijepalli, “Exploring the effectiveness of demand management policy in reducing traffic congestion and environmental pollution: Car-free day and odd-even plate measures for Bandung city in Indonesia,” Case Stud. Transp. Policy, 2018.
[29]N. R. Sabar, A. Bhaskar, E. Chung, A. Turky, and A. Song, “A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion,” Swarm Evol. Comput., 2018.
[30]J. Wang and H. Niu, “A distributed dynamic route guidance approach based on short-term forecasts in cooperative infrastructure-vehicle systems,” Transp. Res. Part D Transp. Environ., 2018.
[31]Y. Wang, K. Assogba, J. Fan, M. Xu, Y. Liu, and H. Wang, “Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost,” J. Clean. Prod., vol. 232, pp. 12–29, 2019.
[32]C. Liu, G. Kou, X. Zhou, Y. Peng, H. Sheng, and F. E. Alsaadi, “Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach,” Knowledge-Based Syst., p. 104813, 2019.
[33]G. Macrina, L. Di Puglia Pugliese, F. Guerriero, and G. Laporte, “The green mixed fleet vehicle routing problem with partial battery recharging and time windows,” Comput. Oper. Res., vol. 101, pp. 183–199, 2019.
[34]Y. Li, M. K. Lim, Y. Tan, S. Y. Lee, and M.-L. Tseng, “Sharing economy to improve routing for urban logistics distribution using electric vehicles,” Resour. Conserv. Recycl., vol. 153, pp. 1–13, 2020.
[35]Z. Mohtashami, A. Aghsami, and F. Jolai, “A green closed loop supply chain design using queuing system for reducing environmental impact and energy consumption,” J. Clean. Prod., vol. 242, p. 118452, 2020.
[36]J. R. Montoya-Torres, J. L. Franco, S. N. Isaza, H. F. Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Comput. Ind. Eng., vol. 79, pp. 115–129, 2015.
[37]L. V Wassenhove, “Delivering relief to tsunami victims,” Logist. Today, vol. 46, pp. 1–9, 2005.
[38]S. Shahparvari, P. Chhetri, B. Abbasi, and A. Abareshi, “Enhancing emergency evacuation response of late evacuees: Revisiting the case of Australian Black Saturday bushfire,” Transp. Res. Part E Logist. Transp. Rev., vol. 93, pp. 148–176, 2016.
[39]S. Salhi, A. Imran, and N. A. Wassan, “The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation,” Comput. Oper. Res., vol. 52, pp. 315–325, 2014.
[40]M. Pelikan and D. . Goldberg, “Genetic algorithms, clustering, and the breaking of symmetry,” Parallel Probl. Solving from Nat. PPSN VI., pp. 385–394, 2000.
[41]C. A. Murthy and N. Chowdhury, “In search of optimal clusters using genetic algorithms,” Pattern Recognit. Lett., vol. 17, pp. 825–832, 1996.
[42]M. Kargari and M. M. Sepehri, “Stores clustering using a data mining approach for distributing automotive spare-parts to reduce transportation costs,” Expert Syst. Appl., vol. 39, pp. 4740–4748, 2012.
[43]L. Novak, “Genetic algorithms for the Multi Depot Vehicle Routing Problem,” 2015. [Online]. Available: https://github.com/libornovax/mdvrp.
[44]P. Surekha and Sumathi, “Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms,” 2002.
AUT Journal of Modeling and Simulation
Volume 52, Issue 1
June 2020
Pages 77-88

Files

Share

How to cite

Statistics