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.

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

Keywords: mixed integer linear programming, plant location problem, coordinating relief
$offText

$eolCom //

Set
   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);

Variable
   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;

Equation 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 = 60;
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';

Parameter
   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;