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.