sroute.gms : The Shortest Route Problem

Description

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


Reference

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

Large Model of Type : LP


Category : GAMS Model library


Main file : sroute.gms

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