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.

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, 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;
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170