# Solution to sheet 4, exercise 1.
# Lecture: Integer Programming in Public Transport (TU Berlin, winter term 2006/07).
# Ralf Borndoerfer, Christian Liebchen, and Marc Pfetsch
#
# Direct travelers model for line planning.
#
# Marc Pfetsch
# 11/2006
# ------------------------------------------------------------------------------
#
# The data are:
# - edges edges of the graph. They are directed and the data should contain
# forward and backward directions if necessary.
# - load passenger load on each edge
# - odnodes contains a list of all OD-nodes, which are a subset of the nodes of
# the graph. We need this for reading and accessing the OD-matrix.
# - od OD-matrix
# - lines edges on lines. The lines are taken as undirected, i.e., the file
# only contains one direction and the model has to take care to check
# both directions.
# ------------------------------------------------------------------------------
# sets:
# OD-Nodes
# The OD-nodes could be inferred from the edges "E", but
# for reading the OD-matrix we need the correct order.
set O := { read "odnodes.dat" as "<1s>" comment "#" };
# edges (directed!)
set E := { read "edges.dat" as "<1s,2s>" comment "#" };
# line set
set line := { read "lines.dat" as "<1s,2s,3s>" comment "#" };
# line names
set L := proj(line,<1>);
# nodes on lines
set N := proj(line, <1,2>) union proj(line, <1,3>);
do print "Number of OD-nodes:";
do print card(O);
do print "Number of edges:";
do print card(E);
do print "Number of lines:";
do print card(L);
# ------------------------------------------------------------------------------
# parameters:
# load on each edge
param load[E] := read "load.dat" as "<1s,2s> 3n" comment "#";
# OD-matrix
param d[O*O] := read "od.dat" as "n+" comment "#";
# Parameters for computing the capacity
param carcap := 467;
param maxcars := 5;
param traincap := maxcars * carcap;
param maxfreq := 10;
# compute lower bound on frequency
param lbf[__ in E] := ceil(load[u,v]/traincap);
# ------------------------------------------------------------------------------
# sets once again:
# demand pairs
set D := { __~~ in O * O with d[s,t] > 0 };
# possible combinations for traveling:
# direct connection between all nodes s and t that lie on line l:
set R := { in L*D with in N and in N };
# ------------------------------------------------------------------------------
# checks
do forall in line do check ~~__ in E and in E;
# ------------------------------------------------------------------------------
# variables:
# y[l,s,t] direct travelers on line l from s to t
var y[R] integer >= 0;
# f[l] frequency of line l
var f[L] integer >= 0;
# ------------------------------------------------------------------------------
# objective
maximize obj: sum in R do y[l,s,t];
# ------------------------------------------------------------------------------
# constraints
# note that the graph is directed - hence we have to include
# the back direction as well
subto lb:
forall ____ in E:
sum in L with in line or in line: f[l] >= lbf[u,v];
subto ub:
forall ____ in E:
sum in L with in line or in line: f[l] <= maxfreq;
subto demand:
forall __~~ in D:
sum in L with in R: y[l,s,t] <= d[s,t];
subto capacity:
forall in L:
sum ~~~~ in D with in R: y[l,s,t] - traincap * f[l] <= 0;
~~