A Pilgrim Scheduling Approach to Increase Safety During the Hajj

The Hajj--the great pilgrimage to Mecca, Saudi Arabia--is one of the five pillars of Islam. Up to four million pilgrims perform the Hajj rituals every year. This makes it one of the largest pedestrian problems in the world. Ramy al-Jamarat--the symbolic stoning of the devil--is known to be a particularly crowded ritual. Up until 2006, it was repeatedly overshadowed by severe crowd disasters. To avoid such disasters, Saudi authorities initiated a comprehensive crowd management program. A novel contribution to these efforts was the development of an optimized schedule for the pilgrims performing the stoning ritual. A pilgrim schedule prescribes specific routes and time slots for all registered pilgrim groups. Together, the assigned routes strictly enforce one-way flows toward and from the ritual site. In this paper, we introduce a model and a solution approach to the Pilgrim Scheduling Problem. Our multistage procedure first spatially smooths the utilization of infrastructure capacity to avoid dangerous pedestrian densities in the network. In the next optimization step, it minimizes overall dissatisfaction with the scheduled time slots. We solve the Pilgrim Scheduling Problem by a fix-and-optimize heuristic, and subsequently simulate the results to identify necessary modifications of the scheduling constraints. Our numerical study shows that the approach solves instances with more than 2.3 million variables in less than 10 minutes on average. At the same time, the gap between optimal solution and upper bound never exceeds 0.28%. The scheduling approach was an integral part of the Hajj planning process in 2007-2014 and 2016-2017. No crowd disaster occurred in these years. Our approach was not applied in 2015, when a severe crowd crush happened close to the ritual site. We briefly discuss possible causes and consequences of this accident. Open Access Statement: This work is licensed under a Creative Commons Attribution 4.0 International License. You are free to copy, distribute, transmit and adapt this work, but you must attribute this work as 'Operations Research. Copyright [c] 2019 The Author(s). https://doi.org/10.1287/opre.2018.1798, used under a Creative Commons Attribution License: https://creativecommons.Org/licenses/by/4.0/.' Funding: This work was partially supported by the Ministry of Municipal and Rural Affairs of the Kingdom of Saudi Arabia. Keywords: Hajj * crowd management * scheduling * timetabling * pedestrian simulation * crowd disaster * crowd dynamics * pilgrimage
1. Introduction The number and severity of deadly crowd disasters at public events has risen significantly over the past decades (Helbing et al. 2015). A frequent cause of such disasters [...]