# Multi-depot 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 # - 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 # # ------------------------------------------------------------------------------ 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>); param c[A] := read "arcs.dat" as "<2n,3n,4n> 5n" comment "#"; var x[A] integer >= 0 <= 1; var y[D] integer >= 0; var z integer >= 0; minimize obj: sum in A: c[u,v,d]*x[u,v,d]; subto flow: forall in V: forall in D: sum in A: x[u,v,d] - sum in A: x[v,u,d] == 0; subto count: forall in D: sum in A: x[s,v,d] == y[d]; subto fleet: sum in D: y[d] == z;