---
title: Efficient Vaccine Distribution
tags: Templates, Talk
description: View the slide with "Slide Mode".
---

# Efficient Vaccine Distribution

##### Johanna Järvsoo, Pasin Marupanthorn, Andrés Miniguano-Trujillo, Conor Osborne, Xinyi Xu
##### Supervisor: Poul Hjorth

<!-- Put the link to this slide here so people can follow
slide: https://hackmd.io/p/template-Talk-slide -->

---
## Problem :world_map:

<img align="center" src="https://i.imgur.com/ut4Tlt0.png">

---

We want to distribute vaccines :syringe: on the sococo island. :desert_island:

The vaccines are kept at the depo $0$ :office: and need to be distributed to the cities $1,\dots,n$. :cityscape:

The lorry :truck: cannot carry all the vaccines, so a refill lorry :articulated_lorry: is required. At point $i^*$ the initial lorry :truck: runs out of vaccine, the refill lorry :articulated_lorry: meets up with it and the drivers swap vehicles. The refill lorry :articulated_lorry: continues.

---

## Strategies

Fuel :fuelpump: is costly and must be spent wisely :dollar:. The fuel consumption of the lorrys :truck::articulated_lorry: depends on the weight of the lorry and the vaccines :syringe: and the distance it travels. :motorway:

We look at two strategies:
* begin delivering at city $1$ :city_sunrise: and continue forward,
* begin delivering at city $n$ :city_sunset: and continue back towards the depot. :office:

Which strategy results in a smaller fuel cost?



---

#### Notation

* $V_I$: initial weight of vaccines in the lorry (Kg) :package:
* $V_A$: weight of the kits to be added at node $i_p^*$ (Kg), $p\in\{1,2\}$ :package:
* $c_k$: cost of fuel per kilometre for empty lorry $k$, for $k\in \{1,2\}$ (Dollar/Km) :dollar:
* $\gamma$: increased fuel cost per additional loaded weight (in kilograms), (Dollar/Kg/Km) 🪙
* $\ell_k$: weight of the lorry $k$ in kilograms for $k\in \{1,2\}$ (Kg) :truck:
* $V_j$: weight of vaccine after unloading at node $j-1$ and before unloading the vaccine at node $j$ (Kg) :syringe:
* $s_j$: weight of the vaccine demanded at node $j$ (Kg) :package:
* $d_j$: distance between nodes $j-1$ and $j$ (Km)
* $\alpha_{i_p^*}$: distance of shortcut from node $0$ to node $i_p^*$ (Km), $p\in\{1,2\}$
* $\beta_{i_p^*}$: distance of shortcut from node $i_p^*$ to node $0$ (Km), $p\in\{1,2\}$

---

#### Strategy :one:

Define a directed graph $G=(V,B)$ with $V := \{0,1,\ldots,n\}$ and
\begin{align}
B := \{ (i,i+1): \, i \in V\setminus\{n\} \} \cup \{ (n,0) \} \cup \{ (0,i_1^*), (i_1^*,0) \}.
\end{align}
Here node $i_1^*$ is computed as the first node that satisfies the equation
\begin{align}
V_I - \sum_{j \leq i_1^*} s_j = 0,
\end{align}
this is the node where the lorry :truck: runs out of vaccine kits and meets the second driver. :articulated_lorry:


---

The weight of the vaccines :syringe: in the lorry :truck::
\begin{align}
V_j =
\begin{cases}
V_I - \sum_{1 \leq k < j} s_k & \text{if } j \leq i_1^*,
\\
V_A & \text{if } j = i_1^* + 1,
\\
V_A - \sum_{i_1^* < k < j} s_k & \text{if } j > i_1^* + 1.
\end{cases}
\end{align}


---

Total fuel cost :moneybag::
\begin{align}
\mathrm{Cost}_1 = \sum_{j\leq i_1^*} d_j (c_1 + \gamma V_j) + \alpha_{i_1^*} (c_2 + \gamma V_A) + \beta_{i_1^*} c_1 + \sum_{j > i_1^*} d_j (c_2 + \gamma V_j) + \beta_nc_2
\end{align}

Dimensionless version:
\begin{equation}
\mathrm{Cost}_1' =\sum_{j\leq i_1^*} d_j' (c_1' + \hat{\gamma} V_j') + \alpha_{i_1^*}' (c_2' + \hat{\gamma}V_A') + \beta_{i_1^*}' c_1' + \sum_{j > i_1^*} d_j' (c_2' + \gamma' V_j') + \beta_n'c_2'
\end{equation}

where $\gamma' = \gamma v_0 d_0/c_0$.

---

#### Strategy :two:

Another directed graph $G=(V,B)$ with
\begin{align}
B := \{ (i,i-1): \, i \in V\setminus\{0\} \} \cup \{ (0,n) \} \cup \{ (0,i_1^*), (i_1^*,0) \}.
\end{align}

Here node $i_2^*$ is computed as the furthest node that satisfies the equation
\begin{align}
V_I - \sum_{j > i_2^*} s_j = 0,
\end{align}
this is the node where the lorry :truck: runs out of vaccine kits (on its way back) and meets the second driver. :articulated_lorry:


---

We compute the weight of vaccines :syringe: as follows:
\begin{align}
V_j =
\begin{cases}
V_I - \sum_{n \geq k > j} s_k & \text{if } j \geq i_2^*,
\\
V_A & \text{if } j = i_2^* - 1,
\\
V_A - \sum_{i_2^* > k \geq j} s_k & \text{if } j < i_2^* - 1.
\end{cases}
\end{align}

The total fuel cost :moneybag: for strategy 2 is:

\begin{align}
\mathrm{Cost}_2 = \alpha_n (c_1+\gamma V_I) +\sum_{j\geq i_2^*} d_j (c_1 + \gamma V_j) + \alpha_{i_2^*} (c_2 + \gamma V_A) + \beta_{i_2^*} c_1 + \sum_{j < i_2^*} d_j (c_2 + \gamma V_j)
\end{align}

And the dimensionless version:

\begin{align}
\mathrm{Cost}_2' = \alpha_n' (c_1' +\gamma' V_I')+ \sum_{j\geq i_2^*} d_j' (c_1' + \gamma' V_j') + \alpha_{i_2^*} (c_2' + \gamma' V_A') + \beta_{i_2^*} c_1' + \sum_{j < i_2^*} d_j' (c_2' + \gamma' V_j').
\end{align}

where $\gamma' = \gamma v_0 d_0/c_0$.

---

## Numerical results :computer:

:pencil2: :open_book: :triangular_ruler:

To do the calculations we need to know what effect the weight of the vaccines :syringe: has on fuel consumption.


[US department of transport research](https://imise.co.uk/wp-content/uploads/2017/09/RR5-Effects-of-Payload-on-the-Fuel-Consumption-of-Trucks.pdf)

* Empty lorry :truck: uses approximately $0.2$ litres of fuel per kilometer.
* For every extra tonne of vaccine the lorry uses extra $0.003$ litres per kilometer.
* The capacity of the lorry is approximately $23$ tonnes.

Let us also assume that fuel price is $1$ dollar :dollar: per litre.

This gives us approximate values to use in calculations.

---

## General Solution

def cost1_j(Cities, Demands, j, c_1, c_2, γ, asymmetry, α_Euclidean)
    return Cost1
    
def cost2_j(Cities, Demands, j, c_1, c_2, γ, asymmetry, α_Euclidean)
    return Cost2

* Time Complexity $O(N)\;$ $(N$: $\#$ Cities$)$

i1,k1 <- [first and last city that lorry 2 arrival satisfies both capacity]
i2,k2 <- [first and last city that lorry 2 arrival satisfies both capacity]
sol <- list

for i in range(i1,k1):
    cost1 = cost1_i(...)
    sol.append((cost1,i,1))
    
for j in range(i2,k2):
    cost2 = cost2_j(...)
    sol.append((cost2,j,2))

return min(sol)

* Time Complexity $O(N^2)\;$
* Space complexity $O(N)$

---
## Assuming varying capacity limit...

We examine the cost :moneybag: of each strategy under the same assumption, but varying capacity limits (so the second lorry can choose any city to resume). With different assumptions on the forward and backward routes (i.e., they are the same or one is longer), we obtain the following results.

Assumptions:
* Maximum demand: 100 boxes each city.
* Box weight: 30.4 Kilograms.

 

---

## Simplified version
Suppose we simplify our model such that

* There are no shortcuts,
* Both lorrys are identical :truck::truck: so that $c:=c_1=c_2$,
* Distances :motorway: between cities are constant $d:=d_1=...=d_n$,
* Weight of vaccines to be distributed at each site is constant $s = s_1=...=s_n$. :package:

Set of arcs is now
\begin{align}
B := \{ (i,i+1): \, i \in V\setminus\{n\} \} \cup \{ (i,i-1): \, i \in V\setminus\{0\} \}.
\end{align}

Reduced problem total fuel cost :moneybag: related to strategy 1 and 2
\begin{align}
\mathrm{Cost}_1 &= d{i_1^*} (2c + \gamma V_A) + d(2cn + \gamma V_T),\\
\mathrm{Cost}_2 &= d{i_2^*} (2c+ \gamma V_A) + d(2cn + \gamma V_I +\gamma V_T).
\end{align}

To compare the cost :moneybag: of the strategies 1 and 2, we consider
\begin{equation}
\Delta = \mathrm{Cost}_1 - \mathrm{Cost}_2 = d({i_1^*} - {i_2^*})(2c + \gamma V_A) - d\gamma V_I.
\end{equation}

If $i_1^* \leq i_2^*$, then strategy 1 is more efficient than strategy 2 since
$$
d({i_1^*} - {i_2^*})(2c + \gamma V_A) - d\gamma V_I\leq- d\gamma V_I<0.
$$.

Furthermore, if $\gamma V_T$ and $\gamma V_A$ are significantly small, the cost difference becomes

$$\Delta = 2cd({i_1^*} - {i_2^*})$$.

---

---

## Future work :muscle: :tada: :heavy_check_mark:

- Solve as a linear programming problem
- Look at multiple routes being optimised in tandem
- Multiple refill lorrys :tada:


- Create a web application to deliver our stakeholders

---