Lecture IX - Safety Planning for the Islamic Pilgrimage
Applied Optimization with Julia
Please take a moment at the start of the lecture to fill out the lecture evaluation survey. Thanks!
Introduction
Islamic Pilgrimage
Question: Have you ever heard of the Hajj?
The Hajj
- The great Islamic pilgrimage towards Mecca
- The holy city is the religious center of the Islamic religion
- Located in the Kingdom of Saudi Arabia
- Each physically able Muslim should perform Hajj once
- Confined spaces around the holy sites
- Only few million people are annually allowed
Mina Tent City
Mina Tent City
The scope of the Hajj
- Pilgrimage is actually a multi-day journey
- Involves a number of different rituals at several ritual sites
- Our efforts focused on the Rhamy-Al-Jamarat ritual
. . .
Pilgrims throw pebbles against three pillars, which symbolize the temptations of the devil. They repeat this ritual with small variations on four consecutive days.
Mina Tent City
- 1.5–2 million people reside in the tent city
- Pilgrims repeatedly access the holy site
- Perform the Rhamy-Al-Jamarat ritual
- Walk through a network of streets and pathways
- Later proceed to the Kaaba or return to the camp
Time Preferences
- When to perform the ritual on each of the four days?
- Pilgrims have different time preferences
- Constrained by arrival and departure shuttle times
- Extremely hot at midday quickly leading to exhaustion
- Traditions play an important role in time preferences
. . .
Question: What could become a problem?
Risk: Overcrowding at Mina
- In aggregation, the time preferences are clustered
- Popular peak times dating back to the Prophet Mohammad
- Equates to a city-scale crowd of millions of people
- Accessing one central place within only a few hours
. . .
Uncoordinated access within confined area can escalate into crowd disasters!
Crowd Accidents
- Historical incidents of crowd disasters
- Resulted in casualties and injuries
- High-density bottlenecks on the way to the rituals
- Several critical points of congestion
- Waiting times can lead to hazardous conditions
. . .
Question: What could we do to prevent this?
Pedestrian Traffic
Pedestrian Traffic
- Individuals and groups
- Multitude of destinations
- Mixing and formation
- Distractions
- Homogeneous groups
- Shared destination
- Higher densities
- Predictable
Types of Pedestrian Flow
. . .
Question: What is the most dangerous type here?
. . .
Multi-directional and intersecting flows are the most dangerous type!
Pilgrim Flows
Adhere to one-way flow systems and define path options for each camp under consideration of a unidirectional flow system.
Problem Structure
Objective?
Question: What could be the objective?
- Minimize risk of overcrowding and accidents
- Enable ritual participation of all pilgrims
- Satisfy time preferences of pilgrims
- Easy plans to execute under pressure
. . .
Question: How can we try to model this?
Objective
- Satisfy time preferences as much as possible
- Consideration of infrastructure bottleneck flow capacities
- Maximize safety for all pilgrims
- Simple plans to make the execution as simple as possible
- This can prevent critical errors later on!
. . .
Question: Where is the goal conflict?
Goal Conflict
Basic Structure
- We follow the structure of a simple scheduling problem
- The aim is to “assign” something to different time periods
- We assign time slots to groups using different paths
- Plans are kept simpler by assigning paths to camps
- Assignments are fixed over the entire time horizon
Pilgrim Routes
Each camp has a set of feasible one-way paths that include the stoning ritual.
Pilgrim Routes
Path may contain one or more bottlenecks, regarded as resources subject to a capacity.
Pilgrim Routes
Pilgrims departure from a camp at a time \(x\) and pass through the bottleneck later.
Pilgrim Routes
Our model should assign one of the feasible paths to a camp on all four ritual days.
Pilgrim Routes
These bottlenecks should not be overcrowded at any time during the Hajj.
Time Preferences
Time preference satisfaction
- Assign one departure time slot
- Assigned per ritual day to each pilgrim group
- Minimize difference between assigned and preferred time
- Different penalty functions are possible
. . .
May be computed, i.e., down-sampled given a distribution of pilgrims over time.
Penalty Functions
Fluctuations
Question: What could become a problem?
. . .
- If allowed demand between periods varies strongly, accidents are more likely to happen!
- We need keep the changes between periods within bounds
. . .
Question: Any idea how we can do that later?
. . .
- Restrict the change of the utilization between periods
Goals Summarized
- Satisfy time preferences of the pilgrims as much as possible under the consideration of infrastructure bottleneck flow capacities by assigning “something” to a time slot.
- For the sake of simplicity and safety, pilgrims coming from one camp will always have to be assigned the same path.
- We need to keep track of the relative utilization of each resource to restrict the fluctuations between periods to ensure a safer event.
Model Formulation
Sets?
Question: What could be the sets here?
Sets
- \(\mathcal{T}\) - Stoning periods in ascending order, indexed by \(t\)
- \(\mathcal{R}\) - Infrastructure resources, indexed by \(r\)
- \(\mathcal{C}\) - Pilgrim camps, indexed by \(c\)
- \(\mathcal{P}\) - Paths that include the stoning, indexed by \(p\)
- \(\mathcal{S}\) - Scheduling groups, indexed by \(s\)
. . .
But we further need subsets!
Subsets
- \(\mathcal{S}_c\) - Scheduling groups in camp \(c\)
- \(\mathcal{S}_p\) - Scheduling groups that can use path \(p\)
- \(\mathcal{P}_c\) - Feasible paths for camp \(c\)
- \(\mathcal{P}_s\) - Feasible paths for group \(s\)
- \(\mathcal{P}_r\) - Paths that contain the resource \(r\)
- \(\mathcal{T}_s\) - Available stoning periods for scheduling group \(s\)
On Subsets
Question: Why use subsets?
. . .
- It may seem like a lot
- But it also really helps a lot!
- We reduce the problem size
. . .
A smaller problem size reduces the solution space and helps the solver in finding the optimal solution faster!
Parameters?
Question: What could be possible parameters?
. . .
- \(n_s\) - Number of pilgrims in scheduling group \(s\)
- \(f_{s,t}\) - Penalty value of assigning period \(t\) to group \(s\)
- \(a_{p,r}\) - Offset between stoning and utilization period of \(r\) on \(p\)
- \(b_{r,t}\) - Capacity of resource \(r\) in period \(t\)
- \(\sigma_r\) - max. relative utilization deviation between \(t\) for \(r\)
First Decision Variable?
Satisfy time preferences of the pilgrims as much as possible under the consideration of infrastructure bottleneck flow capacities by assigning “something” to a time slot.
. . .
- Scheduling groups, \(s \in \mathcal{S}\)
- Stoning periods in ascending order, \(t \in \mathcal{T}\)
- Paths that include the stoning of the devil, \(p \in \mathcal{P}\)
First Decision Variable
Question: What could be our decision variable?
. . .
- \(X_{s,t,p}\) - 1, if scheduling group \(s\) is scheduled to perform stoning in period \(t\) and to use path \(p\), 0 otherwise.
. . .
Question: Do you get the idea here?
. . .
It’s a binary assignment of a group to a time slot and a path.
Second Decision Variable?
For the sake of simplicity and safety, pilgrims coming from one camp will always have to be assigned the same path.
. . .
- Pilgrim camps from which groups can depart, \(c \in \mathcal{C}\)
- Paths that include the stoning of the devil, \(p \in \mathcal{P}\)
. . .
Question: What could be our second variable?
Second Decision Variable
- \(Y_{c,p}\) - 1, if camp \(c\) is assigned to use path \(p\), 0 otherwise
. . .
Question: Does anyone remember the third part?
Third Decision Variable?
We need to keep track of the relative utilization of each resource to restrict the fluctuations between periods to ensure a safer event.
. . .
- Infrastructure resources, \(r \in \mathcal{R}\)
- Stoning periods in ascending order, \(t \in \mathcal{T}\)
. . .
Question: What could be our third variable?
Third Decision Variable
- \(U_{r,t}\) - Relative utilization of \(r\) in \(t\) with \(0 \leq U_{rt} \leq 1\)
. . .
Question: What does relative utilization mean?
. . .
- It’s a percentage of the capacity usage of the resource
- Normalizes the capacities between different resources
Objective Function?
Satisfy time preferences of the pilgrims as much as possible under the consideration of infrastructure bottleneck flow capacities by assigning “something” to a time slot. Hint: We thus could aim to minimize the total dissatisfaction with the timetable.
. . .
Question: How could we minimize the total dissatisfaction?
- Penalize difference between assigned and preferred time
- Different penalty functions, e.g., linear, quadratic, etc.
Objective Function
- \(f_{s,t}\) - Penalty value of assigning period \(t\) to group \(s\)
- \(X_{s,t,p}\) - 1 if group \(s\) is scheduled to perform stoning in \(t\) and to use \(p\), 0 otherwise
. . .
Question: What could be our objective function?
. . .
\[ \text{minimize} \quad \sum_{s \in \mathcal{S}}\sum_{t \in \mathcal{T}}\sum_{p \in \mathcal{P}} f_{s,t} \times X_{s,t,p} \]
Objective Function Characteristics
Question: Is our objective function linear?
. . .
- We can use non-linear penalty functions
- But still, it will always be linear
. . .
Question: Anybody an idea why?
. . .
- We can compute the penalties in advance
- Do not depend on the decision variables
Constraints
Constraints needed?
Key Constraints
Question: Which constraints do we need?
- Each group must have one path assigned
- Each camp must have one path assigned
- Each group must have one time slot assigned
- Each resource must have a capacity limit
- Constraint the relative utilization between periods
Assign Paths to Camps
Assign one path to each camp over the entire time horizon.
. . .
- \(Y_{c,p}\) - 1 if camp \(c\) is assigned to use path \(p\), 0 otherwise
. . .
Question: What could be the constraint?
\[ \sum_{p \in \mathcal{P}_c} Y_{c,p} = 1 \quad \forall c \in \mathcal{C} \]
Assign Time Slots to Groups?
Assign one time slot to each group over the entire time horizon using the same path we have assigned to the camp in the previous constraint.
. . .
- \(X_{s,t,p}\) - 1 if group \(s\) is scheduled to perform stoning in \(t\) and to use \(p\), 0 otherwise
- \(Y_{c,p}\) - 1 if camp \(c\) is assigned to use path \(p\), 0 otherwise
. . .
Question: What could be the constraint?
Assign Time Slots to Groups
\[ \sum_{t \in \mathcal{T}_s} X_{s,t,p} = Y_{c,p} \quad \forall c \in \mathcal{C}, p \in \mathcal{P}_c, s \in \mathcal{S}_c \]
. . .
- \(\mathcal{C}\) - Pilgrim camps
- \(\mathcal{S}_c\) - Scheduling groups in camp \(c\)
- \(\mathcal{T}_s\) - Available stoning periods for scheduling group \(s\)
- \(\mathcal{P}_c\) - Feasible paths for camp \(c\)
Relative Utilization and Capacities
Compute the relative utilization of each resource while also ensuring that the utilization does not exceed the capacity limit. This one is very tricky!
. . .
Difficulties:
- Includes the time-shift between stoning and utilization
- Used as parameter to shift periods in variable \(X_{s,t,p}\)
Compute Relative Utilization?
- \(n_s\) - Number of pilgrims in scheduling group \(s\)
- \(a_{p,r}\) - Period offset between stoning period and utilization period of \(r\) on \(p\)
- \(b_{r,t}\) - Capacity of resource \(r\) in period \(t\) in number of pilgrims
- \(X_{s,t,p}\) - 1, if \(s\) is scheduled to perform stoning in \(t\) and to use \(p\), 0 else
- \(U_{r,t}\) - Relative utilization of resource \(r\) in period \(t\) with \(0 \leq U_{r,t} \leq 1\)
. . .
Question: What could be the constraint?
Compute Relative Utilization
\[ \sum_{p \in \mathcal{P}_r}\sum_{s \in S_p} n_s \times X_{s,t-a_{p,r},p} = b_{r,t}\times U_{r,t} \quad \forall r \in \mathcal{R}, t \in \mathcal{T} \]
. . .
- \(n_s\) - Number of pilgrims in scheduling group \(s\)
- \(a_{p,r}\) - Period offset between stoning period and utilization period of \(r\) on \(p\)
- \(b_{r,t}\) - Capacity of resource \(r\) in period \(t\) in number of pilgrims
- \(X_{s,t,p}\) - 1, if \(s\) is scheduled to perform stoning in \(t\) and to use \(p\), 0 else
- \(U_{r,t}\) - Relative utilization of resource \(r\) in period \(t\) with \(0 \leq U_{r,t} \leq 1\)
How does the shift work?
Keep Fluctuations within Bounds?
Keep the relative utilization of each resource within bounds to ensure a safer event.
. . .
- \(\sigma_r\) - max. relative utilization deviation between \(t\) for \(r\)
- \(U_{r,t}\) - Relative utilization of resource \(r\) in period \(t\) with \(0 \leq U_{rt} \leq 1\)
. . .
Question: What could be the constraint?
Keep Fluctuations within Bounds
\[ U_{r,t} - U_{r,t-1} \leq \sigma_r \quad \forall (r,t) \in \left| \mathcal{R}\times \mathcal{T}\right| \]
\[ U_{r,t-1} - U_{r,t} \leq \sigma_r \quad \forall (r,t) \in \left| \mathcal{R}\times \mathcal{T}\right| \]
. . .
Question: Can somebody explain why this works?
- Each constraint limits the change
- The first one limits the increase
- The second one limits the decrease
Scheduling Problem I
\[\begin{align*} \text{min} \quad \sum_{s\in \mathcal{S}}\sum_{t \in \mathcal{T}_s}\sum_{p \in P_s} f_{s,t} \times X_{s,t,p} \end{align*}\]
subject to:
\[\begin{align*} & \sum_{p \in \mathcal{P}_c} Y_{c,p} = 1 && \forall c \in \mathcal{C} \\ & \sum_{t \in \mathcal{T}_s} X_{s,t,p} = Y_{c,p} && \forall c \in \mathcal{C}, p \in \mathcal{P}_c, s \in \mathcal{S}_c \end{align*}\]
Scheduling Problem II
\[\begin{align*} & \sum_{p \in \mathcal{P}_r}\sum_{s \in S_p} n_s \cdot X_{s,t-a_{p,r},p} = b_{r,t}\cdot U_{r,t} && \forall r \in \mathcal{R}, t \in \mathcal{T} \\ & U_{r,t} - U_{r,t-1} \leq \sigma_r && \forall (r,t) \in \left| \mathcal{R}\times \mathcal{T}\right| \\ & U_{r,t-1} - U_{r,t} \leq \sigma_r && \forall (r,t) \in \left| \mathcal{R}\times \mathcal{T}\right| \end{align*}\]
Restricting the relative utilization of each resource to a certain bound.
Scheduling Problem III
\[\begin{align*} & X_{s,t,p} \in \{0,1\} && \forall s \in \mathcal{S}, \forall t \in \mathcal{T}_s, \forall p \in \mathcal{P}_s \\ & Y_{c,p} \in \{0,1\} && \forall c \in \mathcal{C}, p \in \mathcal{P}_c \\ & U_{r,t} \in [0,1] && \forall r \in \mathcal{R}, t \in \mathcal{T} \end{align*}\]
All variables, except for \(U_{r,t}\), are binary.
Model Characteristics
Characteristics
Questions: On model characteristics
- Is the model formulation linear/ non-linear?
- What kind of variable domains do we have?
- Have we specified the length of a period?
Model Assumptions
Questions: On model assumptions
- What assumptions have we made?
- What are likely issues that can arise if applied?
- How can we measure flow capacities?
- Are all pilgrims equally fast?
Capacity Buffers
Implementation and Impact
Implementation
- Optimization part of a bigger picture
- Many projects with several disciplines involved
- E.g. Simulations, infrastructure projects, real-time monitoring, contingency plans, awareness campaigns, …
. . .
Optimization was part of a project by Knut Haase and his team (Haase et al. 2016).
Wrap Up
We now have covered a scheduling problem based on a real-world application and are ready to start solving some new tasks in the upcoming tutorial.
Literature
Literature I
For more interesting literature to learn more about Julia, take a look at the literature list of this course.