relief.gms : Relief Mission

**Description**

Huts or villages are located at 20 location on a 10 x 10 grid. The problem is to find the two best drop locations for relief packages such that the total distance traveled by villagers is minimized. We look at this problem as a plant location problem and trace the efficiency frontier of multiple drops. The optimal solution for two drops is D.8 and E.2. Another interesting question may be: how many other drop locations are there that have a total distance traveled with, say, 3 percent of the best location.

**Reference**

- Toczek, J, Relief Mission. ORMS Today 37, 4 (2010), 14.

**Large Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** relief.gms

```
$Title Relief Mission (RELIEF,SEQ=353)
$ontext
Huts or villages are located at 20 location on a 10 x 10 grid. The problem
is to find the two best drop locations for relief packages such that the total
distance traveled by villagers is minimized.
We look at this problem as a plant location problem and trace the efficiency
frontier of multiple drops. The optimal solution for two drops is D.8 and E.2.
Another interesting question may be: how many other drop locations are there that
have a total distance traveled with, say, 3 percent of the best location.
Toczek J, Relief Mission, ORMS Today 37, 4 (2010), page 14
$offtext
$eolcom !
sets r rows / A*J /
c columns / 1*10 /
d drops / d1*d20 /
table dem(r,c) relief demands
1 2 3 4 5 6 7 8 9 10
A 1
B 1 1 1
C 1 1 1 1 1
D 1 1 1
E 1 1
F 1
G 1
H 1 1
I
J 1 1
alias(r,rr),(c,cc)
set huts(r,c) hut locations
parameter dis(r,c,r,c) Eucledian distances
numdrops number of drops
maxdem maximum drop demand;
huts(r,c) = dem(r,c);
maxdem = sum(huts, dem(huts));
dis(huts(r,c),rr,cc) = edist(r.pos-rr.pos,c.pos-cc.pos);
variables drop(r,c) drop locations
walk(r,c,r,c) distances walked from huts to nearest drop zone
total total distance walked
Binary variable drop; positive variable walk;
equations demand, supply, deftotal, defnumdrop;
demand(huts).. sum((r,c), walk(huts,r,c)) =e= 1;
supply(r,c).. sum(huts, walk(huts,r,c)) =l= drop(r,c)*maxdem;
deftotal.. total =e= sum((huts,r,c), dis(huts,r,c)*walk(huts,r,c));
defnumdrop.. sum((r,c), drop(r,c)) =e= numdrops;
model m / all /;
* --------------------------
* get best two drop solution
* --------------------------
numdrops = 2;
option limrow=0,limcol=0, optcr=0, solvelink=2, reslim=10;
m.solprint=0;
solve m min total using mip;
display drop.l;
* ------------------------
* trace efficient frontier
* ------------------------
parameter QDrep Quick and Dirty Report;
loop(d,
numdrops = d.pos;
solve m min total using mip;
m.solprint=2;
! we use round() because a MIP code (CPLEX) may return fractional values
QDrep(r,c,d)$round(drop.l(r,c)) = sum ( huts, dis(huts,r,c)*walk.l(huts,r,c)) + EPS*huts(r,c)*drop.l(r,c);
QDrep('max','dist',d) = smax((huts,r,c), dis(huts,r,c)*walk.l(huts,r,c));
QDrep('tot','dist',d) = sum ((huts,r,c), dis(huts,r,c)*walk.l(huts,r,c));
QDrep('CPU','used',d) = m.resusd );
display QDrep;
* ----------------------------------------------------------------
* find all drop points within x percent of best for two drop points
*
* To exclude the n'th integer solution we can write:
* cut(n).. sum(i, abs(x(i)-xsol(i,n)) =g= 1;
* simulating abs() will give
* cut(n).. sum((r,c), cutval(n,r,c)*drop(r,c)) =l= 1 ;
* where cutval() contains solutions to be excluded
* ----------------------------------------------------------------
set nn max number of close solutions / n1*n50 /
n(nn) dynamic set ;
parameters limit total distance for drop points
objval(nn) total miles traveled
cutval(nn,r,c) all possible solutions for cut generation;
numdrops = 2; solve m min total using MIP; limit = 1.03*total.l;
Equation cut(nn) known solutions to be eliminated;
cut(n).. sum((r,c), cutval(n,r,c)*drop(r,c)) =l= 1 ;
model mm / m, cut /;
n(nn) = no; ! clear set of cuts
mm.solvestat = %solvestat.NormalCompletion%;
mm.modelstat = %modelstat.Optimal%;
mm.solprint=0;
Loop(nn$(mm.solvestat=%solvestat.NormalCompletion% and
mm.modelstat=%modelstat.Optimal% and
total.l < limit),
n(nn) = yes; ! add element to set
cutval(nn,r,c) = round(drop.l(r,c));
solve mm min total using mip;
mm.solprint=0;
objval(nn) = total.l );
option cutval:0:1:1; display objval,cutval;
parameter hits; hits(r,c) = sum(nn, cutval(nn,r,c)); display hits;
```