Lecture IX - Safety Planning for the Islamic Pilgrimage

Applied Optimization with Julia

Dr. Tobias Vlćek

University of Hamburg - Fall 2024

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

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

Caution

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

How is Hajj pedestrian

traffic different from the

regular urban pedestrian

traffic in cities?

Pedestrian Traffic

  • Individuals and groups
  • Multitude of destinations
  • Mixing and formation
  • Distractions

  • Homogeneous groups
  • Shared destination
  • Higher densities
  • Predictable

Types of Pedestrian Flow

1. 2. 3.

Question: What is the most dangerous type here?

Caution

Multi-directional and intersecting flows are the most dangerous type!

Pilgrim Flows

General idea

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.

How can we model

time preferences?

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

Group time preferences

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

  1. 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.
  2. For the sake of simplicity and safety, pilgrims coming from one camp will always have to be assigned the same path.
  3. 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\)

That looks

complicated…

On Subsets

Question: Why use subsets?

  • It may seem like a lot
  • But it also really helps a lot!
  • We reduce the problem size

Tip

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?

Our first goal is to:

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.

We need the following sets:

  • 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?

Our second goal (more a constraint):

For the sake of simplicity and safety, pilgrims coming from one camp will always have to be assigned the same path.

We need the following sets:

  • 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?

Our third goal (again, more a constraint):

We need to keep track of the relative utilization of each resource to restrict the fluctuations between periods to ensure a safer event.

We need the following sets:

  • 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

Let’s start with our

objective function!

Objective Function?

Our main objective is to:

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

We need the following parameters and variables:

  • \(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?

  1. Each group must have one path assigned
  2. Each camp must have one path assigned
  3. Each group must have one time slot assigned
  4. Each resource must have a capacity limit
  5. Constraint the relative utilization between periods

Assign Paths to Camps

The goal of this constraint is to:

Assign one path to each camp over the entire time horizon.

We need the following variables:

  • \(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?

The goal of this constraint is to:

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.

We need the following variables:

  • \(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 \]

We use the following sets:

  • \(\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

The goal of this constraint is to:

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?

We need the following:

  • \(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} \]

We use the following:

  • \(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\)

Let’s pause!

Have you understood

this part?

How does the shift work?

Keep Fluctuations within Bounds?

The goal of this constraint is to:

Keep the relative utilization of each resource within bounds to ensure a safer event.

We need the following:

  • \(\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*}\]

Note

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*}\]

Note

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

Can this be

applied?

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, …

Note

Optimization was part of a project by Knut Haase and his team (Haase et al. 2016).

Wrap Up

And that’s it for todays lecture!

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.

Questions?

Literature

Literature I

For more interesting literature to learn more about Julia, take a look at the literature list of this course.

Literature II

Haase, Knut, Habib Zain Al Abideen, Salim Al-Bosta, Mathias Kasper, Matthes Koch, Sven Müller, and Dirk Helbing. 2016. “Improving Pilgrim Safety During the Hajj: An Analytical and Operational Research Approach.” Interfaces 46 (1): 74–90.