sroutex.gms : Shortest Route Algorithm

Description

The problem is to find the shortest route or lowest transport
cost from each city to all others. This example is the same as
sroute except a shortest path algorithm is written using loops.


Reference

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

Small Model of Type : GAMS


Category : GAMS Model library


Main file : sroutex.gms

$Title Shortest Route Algorithm (SROUTEX,SEQ=93)

$Ontext

   The problem is to find the shortest route or lowest transport
   cost from each city to all others. This example is the same as
   sroute except a shortest path algorithm is written using loops.


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

$Offtext

 Set  i  cities  / boston, chicago, dallas, kansas-cty, losangeles
                   memphis, portland, salt-lake, wash-dc           /

 Alias(i,j,k)

 Parameter a(i,j) arcs and cost  /

    boston  .chicago      58,     kansas-cty .memphis       27
    boston  .wash-dc      25,     kansas-cty .salt-lake     66
    chicago .kansas-cty   29,     kansas-cty .wash-dc       62
    chicago .memphis      32,     losangeles .portland      58
    chicago .portland    130,     losangeles .salt-lake     43
    chicago .salt-lake    85,     memphis    .wash-dc       53
    dallas  .kansas-cty   29,     portland   .salt-lake     48
    dallas  .losangeles   85
    dallas  .memphis      28
    dallas  .salt-lake    75    /

 Parameters f(i,j)     shortest route between two cities;
 Option a:0, f:0;

 Scalars    old   old total distance
            new   new total distance ;


a(i,j) = max(a(i,j),a(j,i));

Display a;

f(i,j) = inf; f(i,i) = 0; f(i,j) $= a(i,j);

Loop(i,
   new = na;
   repeat(
      f(i,j)$(not sameas(i,j)) = smin(k$a(k,j), f(i,k)+ a(k,j));
      old=new;
      new = sum(j$(f(i,j) < inf), f(i,j));
      until old = new ) );

Display f ;