Making the Hajj safer for millions of Muslim Pilgrims
An introduction to Operations Research used for social good.
In my list of “worst ways to die”, I have never even considered death by trampling during a stampede. A human stampede, at that. Unfortunately, hundreds of lives have been tragically lost this way at what is supposed to be a peaceful, religious tradition every single year in Makkah, Saudi Arabia. During the last month of the Islamic (lunar) calendar, anywhere from 1 to 4 million Muslims participate in a religious pilgrimage called Hajj. Unfortunately, crowd control during Hajj has been so dire that there were deadly stampedes and other accidents almost every year from the years 1990 to 2006. The Saudi government has since developed strategies to avoid such catastrophes, and one of the most successful has been a mathematical optimization model.
As part of Hajj, millions of Muslim worshippers follow a rather strict agenda of rituals over a span of 5 days in order to reverently and symbolically follow the journey of Muhammad. Their list of rituals includes circling around the Kaaba seven times counterclockwise, running between two hills seven times, and throwing stones at three Jamarah pillars that represent the devil, a practice sometimes called “stoning the devil”. Some rituals, including the stoning of the devil, are considered to be time-sensitive, so worshippers will only go at certain times of the day, which makes it hard to evenly distribute throughout the day. With everyone following the same series of rituals at nearly the same time, crowd control is a constant struggle during Hajj.
In order to host millions of pilgrims over several days, The Saudi government must provide large camps for sleeping and transportation between locations, which may be miles apart. Certain infrastructures are critical to the worshippers’ routes, including metro platforms, bridges, tunnels, and of course the religious sites, so these are natural bottlenecks for crowd movement. When crowds become too densely packed in small areas, this can trigger stampedes — or a phenomenon called a crush — which often lead to casualties. Bridges and tunnels, especially, have been the sites of many trampling-related deaths in the past.
These crowd control incidents have killed thousands of worshippers between the years of 1990 and 2006. The first major accident was in 1990 when a stampede in a pedestrian tunnel resulted in 1,426 people dying. In the following two decades: 266 died in 1994, 118 died in 1998, 251 died in 2004, and 363 died in 2006. Even recently, the Mina crush of 2015 led to the deaths of over 2,000 worshippers (the Saudi government still has not released an accurate number). Tragedies like these are what organizers are trying to prevent.
So with such a complex and life-threatening crowd control problem, what exactly is operations research and how was it helpful? Operations research is the science of mathematical optimization, or finding the best decision for a large and complex system. Furthermore, there are many constraints that require a solution to satisfy the realistic confines of the real world. For example, no budget is infinite; there is always some upper limit. Operations research algorithms use these constraints to identify not only feasible solutions, but the best possible solution, which can then be translated back into a strategy for the organizers.
The ideal strategy to better manage the large population of pilgrims during the Hajj would be to formulate a schedule for groups of worshippers to move between locations. These schedules must be thorough, including decisions about the mode of transportation, which platforms to use for the metro, the times to be at each religious site, and even in which tents to stay the night at the camp. The list of constraints on these decisions is rather extensive, including the avoidance of high-risk crowd movements (such as merging-, intersecting-, and counter-flows), and they are fully explored in the paper published by Haase, et. al.
Even still, there are likely millions of potential schedules. Of course one of the goals is to minimize the distance traveled by the pilgrims, so organizers would prefer only the optimal schedule out of those millions of potential schedules. Luckily, this type of problem is where operations research methods thrive! Rather than enumerating all of the potential solutions to find the best one, a fundamental algorithm in operations research, the Simplex algorithm, cleverly finds a series of improving solutions until it finds the best possible schedule.
The mathematics of operations research is founded on many ideas from multivariate calculus, linear algebra, and real analysis. However, operations research also has much of its own mathematical theory. For the mathematically curious, the decisions in problems like these are modeled as variables, and then we can represent the constraints as (in)equalities and the objectives as functions of these variables. All the important decisions in the scheduling problem — for example which path will group A take from start to finish — are encoded as variables (e.g., either x=1 if group A takes path P or x=0 if not). Not only does the problem have a very high dimensionality with hundreds of thousands of variables, but we also require some variables to be integer (e.g., 0 or 1), which makes the problem becomes much harder. However, decades of research into integer programming has resulted in efficient algorithms that allow solving even large problems.
The research team organizing the Hajj decomposed it into 3 independent problems and each was solved by mathematical optimization. The first scheduled groups of pilgrims according to paths and times for the stoning ritual. The second assigned groups to camps and metro stations. The third designed the camp’s layout to best suit the pilgrims. Some objectives that they took into consideration were satisfying the preferences of pilgrims’ stoning times and minimizing total walking distance.
By implementing this optimized scheduling algorithm, there were no crowd control accidents and no deaths during Hajj between the years of 2007 and 2014! It is important to note that this scheduling algorithm was one of many strategies used by the organization team, including improvement of infrastructures; computer simulations to analyze crowd movement through infrastructures; more efficient transportation between the religious sites; and surveillance methods for real-time monitoring of crowd flow. However, the scheduling algorithm was the fundamental tool for organizational planning, which not only avoided crowd flows that could have started a deadly stampede or crush, but it also resulted in more balanced use of the infrastructures and decreased environmental footprint.
Unfortunately, as mentioned previously, the 2015 Hajj had a crowd control incident that made it the deadliest Hajj in history; however, it seems that the same optimization and management tools were not used for that year. The cause of the incident was due to two intersecting crowds of pilgrims in a single, small street. This incident could have been avoided if the optimization tools were used to plan the groups’ movements. Or it is possible that the cause was on-the-ground misdirection of groups. It is unknown which is the case because the Saudi government has not yet released investigation reports about the accident — not even an accurate death toll. While these optimization tools may not be enough to prevent all future accidents, they have surely proven effective for 7 continuous years, and proper analysis of the 2015 tragedy could prove remarkably useful in improving such tools.
Altogether, a team of operations researchers were able to employ decades of optimization research technique to solving a very dire problem affecting thousands of people every year. During the seven years of safe Hajj, millions of Muslim pilgrims were able to complete their journey safely and make it home to their families having survived what should be one of the most memorable experiences in the Muslim faith — not a near-death experience.
