$title The Shortest Route Problem (SROUTE,SEQ=6)

$onText
The problem is to find the shortest route or lowest transport
cost from each city to all others.

Dantzig, G B, Chapter 17.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

Keywords: linear programming, shortest route, network optimization
$offText

Set
   i      'cities' / boston, chicago, dallas, kansas-cty, losangeles,
                     memphis, portland, salt-lake, wash-dc            /
   r(i,i) 'routes';

Alias (i,ip,ipp);

Parameter
   darc(i,ip) 'directed arcs'
   uarc(i,ip) 'undirected arcs'
              / boston  .chicago      58, boston  .wash-dc      25
                chicago .kansas-cty   29, chicago .memphis      32
                chicago .portland    130, chicago .salt-lake    85
                dallas  .kansas-cty   29, dallas  .losangeles   85
                dallas  .memphis      28, dallas  .salt-lake    75
                kansas-cty .memphis   27, kansas-cty .salt-lake 66
                kansas-cty .wash-dc   62, losangeles .portland  58
                losangeles .salt-lake 43, memphis    .wash-dc   53
                portland   .salt-lake 48                           /;

darc(i,ip) = max(uarc(i,ip),uarc(ip,i));
r(i,ip)    = yes$darc(i,ip);

display darc;

Variable
   x(i,ip,ipp) 'arcs taken'
   cost        'total cost or length';

Positive Variable x;

Equation
   nb(i,ip) 'node balance'
   cd       'cost definition';

nb(i,ip)$(not sameas(i,ip))..
   sum(ipp$darc(ipp,ip), x(i,ipp,ip)) =g= sum(ipp$darc(ip,ipp), x(i,ip,ipp)) + 1;

cd.. cost =e= sum((i,ip,ipp), darc(ip,ipp)*x(i,ip,ipp));

Model route 'shortest route' / all /;

solve route minimizing cost using lp;

Parameter sroute(i,ip);

sroute(i,ip) = -nb.m(i,ip);

display sroute;