# 1-depot Lagrange relaxation of minimum cost vehicle scheduling problem.
#
# Lecture on Integer Programming and Public Transport
# WS 2006/07
# Technische Universitaet Berlin, Fakultaet 2, Institut fuer Mathematik
# Assignment 6, exercise 3
# Ralf Borndoerfer
# 01/2007
#
# ------------------------------------------------------------------------------
#
# The data are:
#
# - A arcs: set of all arcs, defined by tail, head, and depot
# - E deadheads: set of all deadhead trips corresponding to the arcs
# - V nodes: set of all nodes, corresponding to timetabled trips plus an
# artificial depot node 0
# - W trips: set of all timetabled trips
# - D depots: set of depots
# - c costs: array of arc costs
# - F flows: set of relaxed individual flow constraints
# - lambda duals: multipliers for relaxed individual flow constraints
# - s source/sink: artificial depot node to start and end rotations
#
# The variables are:
#
# - x flow
# - y fleet: depot fleet size
# - z fleet: total fleet size
# - r residuals: residuals of relaxed individual flow constraints
#
# ------------------------------------------------------------------------------
param s := 0;
set A := { read "arcs.dat" as "<2n,3n,4n>" comment "#" };
set E := proj(A,<1,2>);
set V := proj(A,<1>) union proj(A,<2>);
set W := V without { s };
set D := proj(A,<3>);
set F := V cross D;
param c[A] := read "arcs.dat" as "<2n,3n,4n> 5n" comment "#";
param lambda[F] := read "flowduals.dat" as "<1n,2n> 3n" comment "#" default 0;
var x[A] integer >= 0 <= 1;
var y[D] integer >= 0;
var z integer >= 0;
var r[F] >= -infinity <= infinity;
minimize obj:
sum __ in A: c[u,v,d]*x[u,v,d] - sum in F: lambda[v,d]*r[v,d];
subto flow1:
forall in V:
sum ____ in A: x[u,v,d] - sum in A: x[v,u,d] == 0;
subto flow:
forall in V:
forall in D:
sum ____ in A: x[u,v,d] - sum in A: x[v,u,d] == r[v,d];
subto trip:
forall in W:
sum ____ in A: x[u,v,d] == 1;
subto count:
forall in D:
sum __~~ in A: x[s,v,d] == y[d];
subto fleet:
sum in D: y[d] == z;
~~