## Modeling and Simulating Political Violence and Optimizing Aid Distribution in Uganda

### Optimizing humanitarian aid delivery

#### The traveling salesman problem

One question of particular interest is how to route emergency aid to locations where it is needed. For concreteness, let’s postulate a Red Cross medical or food supply caravan that originates from the organization’s in-country headquarters. This caravan wishes to visit all $n$ emergent locations in order to deliver needed supplies. They wish to do so in the most efficient manner possible.

This is the traveling salesman problem (TSP), an optimization problem that is quite well known. It was first described in 1932 by Karl Menger and has been studied extensively ever since. Here is the traditional convex optimization specification of the problem:

\begin{aligned} \min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} && \\ \mathrm{s.t.} & \\ & x_{ij} \in \{0, 1\} && i,j=0, \cdots, n \\ & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\ & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\ &u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n\end{aligned}

As is clear from the constraints, this is an integer linear program (ILP) where:

• $x_{ij}$ is a binary decision variable indicating whether we go from location $i$ to location $j$.
• $c_{ij}$ is the distance between location $i$ and location $j$. (Note: in our application, we deal with geospatial data on a large enough scale that the Euclidean distance is actually very imprecise. In order to model distances over the planet’s surface, we use the Haversine formula.)
• The objective function is the sum of the distances for routes that we decide to take.
• The final constraint ensures that all locations are visited once and only once.

Figure 11

Figure 12

Figure 13

#### Finding the optimal site for the resupply location

Our initial assumption was that the HQ was located in the capital city of Kampala. However, we should ask whether our HQ could be more conveniently located. We can answer this question by treating the reload location as another parameter and continuing to sample HQ locations using SA. Figure 14 shows the TSP/Knapsack optimized once again, this time using a the optimal HQ location, while figure 15 compares the loss function as each method converges to its best possible configuration.

Figure 14

Figure 15