Dynamic Programming for Multi-Crew Scheduling of the Emergency Repair of Network

Subject Areas : Business Strategy

Mehrdad Niyazi ¹ , Javad Behnamian ²

1 - Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran
2 - Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

Received: 2020-07-14 Accepted : 2021-02-11 Published : 2021-03-08

Keywords: Dynamic programming, Network Repair, Repair Crew Scheduling, Multi-Crew Planning,

Abstract :

One of the most necessary operations in humanitarian logistics is the distribution of relief goods to the population in disaster areas. When a disaster occurs, some parts of the distribution infrastructure may be damaged and consequently make it impossible to reach all the demand nodes and delivering the relief goods. In this study, we focus on the planning of infrastructure recovery efforts in post-disaster response. The problem is the scheduling of the emergency repair of a network that has been damaged by a disaster. The objective is to maximize network accessibility for all demand nodes in order to deliver relief goods to them. We adopt a dynamic programming algorithm to solve the problem when more than one crew group is available. Our numerical analysis of the solution shows the performance of the algorithm. We, also, compare our results with some similar studies to indicate the differences between one and multi-crew scheduling.

References:

Aksu, D. T., & Ozdamar, L. (2014). A mathematical model for post-disaster road restoration: Enabling accessibility and evacuation. Transportation research part E: logistics and transportation review, 61, 56-67.

Altay, N., & Green, W. (2006). OR/MS research in disaster operations management. European Journal of Operational Research, 175(1), 475–493.

Barbarosoğlu, G., Özdamar, L., & Cevik, A. (2002). An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations. European Journal of Operational Research, 140(1), 118-133.

Beamon, B., & Balcik, B. (2008). Performance measurement in humanitarian relief chains. International Journal of Public Sector Management, 21(1), 4–25.

Benson, C., Twigg, J., & Myers, M. (2001). NGO initiatives in risk reduction: An overview. Disasters, 25(3), 199–215.

Besiou, M., Stapleton, O., & Van Wassenhove, L. (2011). System dynamics for humanitarian operations. Journal of Humanitarian Logistics and Supply Chain Management, 1(1), 78–103.

Caunhye, A. M., Nie, X., & Pokharel, S. (2012). Optimization models in emergency logistics: A literature review. Socio-economic planning sciences, 46(1), 4-13.

Chang, M. S., Tseng, Y. L., & Chen, J. W. (2007). A scenario planning approach for the flood emergency logistics preparation problem under uncertainty. Transportation Research Part E: Logistics and Transportation Review, 43(6), 737-754.

Chen, Y. W., & Tzeng, G. H. (1999). A fuzzy multi-objective model for reconstructing the post-quake road-network by genetic algorithm. International Journal of Fuzzy Systems, 1(2), 85-95.

Chen, Y. W., & Tzeng, G. H. (2000). Determining the optimal reconstruction priority of a post-quake road network. In Computing in civil and building engineering (2000) (pp. 686-693).

Duran, S., Gutierrez, M. A., & Keskinocak, P. (2011). Pre-positioning of emergency items for CARE international. Interfaces, 41(3), 223-237.

Feng, C. M., & Wang, T. C. (2003). Highway emergency rehabilitation scheduling in post-earthquake 72 hours. Journal of the 5th Eastern Asia Society for Transportation Studies, 5(3281), 3276-85.

Fiedrich, F., Gehbauer, F., & Rickers, U. (2000). Optimized resource allocation for emergency response after earthquake disasters. Safety science, 35(1-3), 41-57.

Hoyos, M. C., Morales, R. S., & Akhavan-Tabatabaei, R. (2015). OR models with stochastic components in disaster operations management: A literature survey. Computers & Industrial Engineering, 82, 183-197.

IFRC, 2012. What is a disaster? URL www.ifrc.org/en/what-we-do/disaster-management/about-disasters/whatis-a-disaster/ (accessed 14 June 2018).

Jenelius, E., & Mattsson, L. G. (2012). Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study. Transportation research part A: policy and practice, 46(5), 746-760.

Jin, S., Jeong, S., Kim, J., & Kim, K. (2015). A logistics model for the transport of disaster victims with various injuries and survival probabilities. Annals of Operations Research, 230(1), 17-33.

Klingman, D., Napier, A., & Stutz, J. (1974). NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Management Science, 20(5), 814–821.

Kovács, G., & Spens, K. (2011). Trends and developments in humanitarian logistics–A gap analysis. International Journal of Physical Distribution & Logistics Management, 41(1), 32–45.

Kunz, N., & Reiner, G. (2012). A meta-analysis of humanitarian logistics research. Journal of Humanitarian Logistics and Supply Chain Management, 2(2),
116–147.

Matisziw, T. C., & Murray, A. T. (2009). Modeling s–t path availability to support disaster vulnerability assessment of network infrastructure. Computers & Operations Research, 36(1), 16-26.

Maya Duque, P., & Sörensen, K. (2011). A GRASP metaheuristic to improve accessibility after a disaster. OR spectrum, 33(3), 525-542.

Maya Duque, P., Dolinskaya, I. S., & Sörensen, K. (2016). Network repair crew scheduling and routing for emergency relief distribution problem. European Journal of Operational Research, 248(1), 272-285.

Mete, H. O., & Zabinsky, Z. B. (2010). Stochastic optimization of medical supply location and distribution in disaster management. International Journal of Production Economics, 126(1), 76-84.

Molaei, S., Seyed Esfahani, M., Esfahanipour, A. (2016). Using Genetic Algorithm to Robust Multi Objective Optimization of Maintenance Scheduling Considering Engineering Insurance. Journal of System Management, 2(1),
1-19.

Murray, A. T., Matisziw, T. C., & Grubesic, T. H. (2007). Critical network infrastructure analysis: interdiction and system flow. Journal of Geographical Systems, 9(2), 103-117.

Özdamar, L., Ekinci, E., & Küçükyazici, B. (2004). Emergency logistics planning in natural disasters. Annals of operations research, 129(1-4), 217-245.

Rawls, C. G., & Turnquist, M. A. (2010). Pre-positioning of emergency supplies for disaster response. Transportation research part B: Methodological, 44(4),
521-534.

Sheu, J. B. (2007). An emergency logistics distribution approach for quick response to urgent relief demand in disasters. Transportation Research Part E: Logistics and Transportation Review, 43(6), 687-709.

Sohn, J. (2006). Evaluating the significance of highway network links under the flood damage: An accessibility approach. Transportation research part A: policy and practice, 40(6), 491-506.

Tahanian, A., Khaleghi, M. (2015). Staff scheduling by a genetic algorithm. Journal of System Management, 1(4), 73-86.

Tamura, T., Sugimoto, H., & Kamimae, T. (1994). Application of genetic algorithms to determining priority of urban road improvement. Doboku Gakkai Ronbunshu, 1994(482), 37-46.

United Nations Office for Disaster Risk Reduction, 2012. Infographic: The economic and human impact of disasters in the last 12 years. URL http://infographiclist.com/2013/05/08/the-economic-and-human-impactof disasters-in-the-last-12-years-infographic/ (accessed 14 June 2018).

Yan, S., & Shih, Y. L. (2009). Optimal scheduling of emergency roadway repair and subsequent relief distribution. Computers & Operations Research, 36(6), 2049-2065.

Yi, W., & Özdamar, L. (2007). A dynamic logistics coordination model for evacuation and support in disaster response activities. European Journal of Operational Research, 179(3), 1177-1193.