Air Ambulance Reassignment Problem

Summary: The objective of the Air Ambulance Reassignment Problem is to determine a minimum cost assignment of helicopters to sites to satisfy the projected demand for the next time period.

Case Study Contents

pırpır

Problem Statement

An air ambulance (helicopter) service provider has a set of locations with a number of helicopters assigned to each site. Within each site's defined service area, requests are satisfied by the helicopters assigned to that site. At the end of each time period, the service provider updates the projected demand for each site and determines whether any of the helicopters need to be reassigned. There is a transportation cost associated with reassigning a helicopter to a different site. Therefore, the service provider wants to determine a minimum cost assignment of helicopters to sites to satisfy the next period's projected demand at each site.

As an example, consider an air ambulance service provider with 5 locations in the Midwest. The company evaluates the need to relocate helicopters based on the monthly projected demand for each location. The cost of reassigning a helicopter from site \(i\) to site \(j\) is $100 per kilometer of distance from site \(i\) to site \(j\). For each of the company's locations, the table below lists the \(x\) and \(y\) coordinates of the site, the number of helicopters currently assigned, and the projected demand for the next period.

  X - Coord Y-Coord # Assigned Projected Demand
Location #1 36 20 6 7
Location #2 23 30 2 3
Location #3 23 56 3 2
Location #4 10 15 3 4
Location #5 5 5 4 2

Mathematical Formulation

Given the set of locations, the pairwise distances between locations, the number of helicopters currently assigned to each location, the projected demand for each location, and the cost per kilometer, the objective of the Air Ambulance Reassignment Problem is to determine a minimum cost set of reassignments to satisfy projected demand. The problem can be formulated as a linear programming problem because the objective function and the constraints are all linear functions. The pairwise distances are computed as the Euclidean distance.

Set
\(L\) = the set of locations

Parameters
\(x_i\) = the x-coordinate for location \(i\), \(\forall i \in L\)
\(y_i\) = the y-coordinate for the location \(i\), \(\forall i \in L\)
\(d_i\) = projected demand for the next period for location \(i\), \(\forall i \in L\)
\(s_i\) = number of helicopters currently assigned to location \(i\), \(\forall i \in L\)
\(c\) = transportation cost per kilometer
\(dist_{ij}\) = Euclidean distance between location \(i\) and location \(j\), \(\forall i \in L\), \(\forall j \in L\)
\(dist_{ij}\) = \(\sqrt( (x_j - x_i)^2 + (y_j - y_i)^2 )\)

Variables
\(z_{ij}\) = number of helicopters to be moved from location \(i\) to \(j\), \(\forall i \in L\), \(\forall j \in L\)

Objective Function
Minimize \( \sum_{(i,j) \in L \times L} dist_{ij}*c*z_{ij}\)

Constraints
Flow balance constraint for each location \(i\) in set \(L\)

\(\sum_{j \in L} z_{ji} + s_i = d_i + \sum_{j \in L} z_{ij}, \forall i \in L\)

To solve this linear programming problem, we can use one of the NEOS Server solvers in the Linear Programming (LP) category. Each LP solver has one or more input formats that it accepts.

GAMS Model

Here is a GAMS model for the small example provided above in the problem statement section.

set L  /1*5/;

alias(L,nL);

Parameters
   x(L) x-coordinates
   / 1 36
     2 23
     3 23
     4 10
     5 5   /

   y(L) y-coordinates
   / 1 20
     2 30
     3 56
     4 15
     5 5  /

   d(L) projected demand
   / 1 7
     2 3
     3 2
     4 4
     5 2 /

   s(L) units currently assigned
   /  1 6
      2 2
      3 3
      4 3
      5 4 /;

Parameter dist(L,nL) distance;
dist(L,nL) = sqrt( (x(nL) - x(L))*(x(nL) - x(L)) + (y(nL) - y(L))*(y(nL) - y(L)));

Scalar c cost per kilometer /100/;

Variable 
  obj;

Positive Variable 
  z(L,nL);

Equations
   objective 
   balance(L)  ;

objective.. sum((L,nL), dist(L,nL)*c*z(L,nL)) =e= obj;

balance(L) .. sum(nL, z(nL,L)) + s(L) =e= d(L) + sum(nL, z(L,nL)) ;

Model AirAmbulance /all/ ;
Solve AirAmbulance using lp minimizing obj;
Display z.l;

If we submit this LP model to XpressMP, we obtain the following solution: \(z_{3,2}\) = 1, \(z_{5,1}\) = 1, and \(z_{5,4}\) = 1 with an objective function value of 7161.87. The pairwise distances are as follows: \(dist_{3,2}\) = 26, \(dist_{5,1}\) = 34.438, and \(dist_{5,4}\) = 11.180.

Optimization Category (Linear Programing, Integer, MIP and etc.):