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;