$Title Fahrplanerstellung
$Ontext

Vorlesung: Service Operations Management
Abschnitt: 3.4 Timetabling
Problemstellung: Optimierung von Fahrplaenen des oeffentlichen Personenverkehrs als Periodic Event Scheduling
Quelle: Linienplan mit zwei Linien und sieben Stationen aus Foliensatz zur Vorlesung

 - Data -

Author: Christoph Schwindt
Date: 27/12/2019

$Offtext

sets
   i       Knoten des Constraint-Graphen (Kombinationen aus Haltestellen und Abfahrts- bzw. Ankunftsereignis)
           / A1-south-d, A2-south-a, A2-south-d, A3-south-a, A3-south-d, A4-south-a, A4-south-d, A5-south-a,
             A5-north-d, A4-north-a, A4-north-d, A3-north-a, A3-north-d, A2-north-a, A2-north-d, A1-north-a,
             B1-east-d, B2-east-a, B2-east-d, B3-east-a, B3-west-d, B2-west-a, B2-west-d, B1-west-a /
   end(i)  Ankunftsknoten von Endhaltestellen
           / A5-south-a, A1-north-a, B3-east-a, B1-west-a / ;

alias (i,j) ;

sets
   a(i,j)        Pfeile im Constraint-Graphen (Haltezeiten und Fahrzeiten sowie Umsteigezeiten)
   halt(i,j)     Haltepfeile
                 / A2-south-a.A2-south-d, A3-south-a.A3-south-d, A4-south-a.A4-south-d, A5-south-a.A5-north-d
                   A4-north-a.A4-north-d, A3-north-a.A3-north-d, A2-north-a.A2-north-d, A1-north-a.A1-south-d,
                   B2-east-a.B2-east-d, B3-east-a.B3-west-d, B2-west-a.B2-west-d, B1-west-a.B1-east-d /
   fahrt(i,j)    Fahrtpfeile
                 / A1-south-d.A2-south-a, A2-south-d.A3-south-a, A3-south-d.A4-south-a, A4-south-d.A5-south-a,
                   A5-north-d.A4-north-a, A4-north-d.A3-north-a, A3-north-d.A2-north-a, A2-north-d.A1-north-a,
                   B1-east-d.B2-east-a, B2-east-d.B3-east-a, B3-west-d.B2-west-a, B2-west-d.B1-west-a /
   umstieg(i,j)  Umsteigepfeile
                 / A3-south-a.(B2-east-d,B2-west-d), A3-north-a.(B2-east-d,B2-west-d),
                   B2-east-a.(A3-south-d,A3-north-d), B2-west-a.(A3-south-d,A3-north-d) / ;

   a(i,j) = halt(i,j)+fahrt(i,j)+umstieg(i,j) ;

parameters
   l(i,j)  Zeitlicher Mindestabstand zwischen Ereignissen i und j
*            Haltepfeile: Mindesthaltezeit
           / A2-south-a.A2-south-d 1, A3-south-a.A3-south-d 2, A4-south-a.A4-south-d 1, A5-south-a.A5-north-d 1
             A4-north-a.A4-north-d 1, A3-north-a.A3-north-d 2, A2-north-a.A2-north-d 1, A1-north-a.A1-south-d 1,
             B2-east-a.B2-east-d 2, B3-east-a.B3-west-d 1, B2-west-a.B2-west-d 2, B1-west-a.B1-east-d 1,
*            Fahrtpfeile: Fahrtzeit
             A1-south-d.A2-south-a 5, A2-south-d.A3-south-a 3, A3-south-d.A4-south-a 4, A4-south-d.A5-south-a 6,
             A5-north-d.A4-north-a 6, A4-north-d.A3-north-a 4, A3-north-d.A2-north-a 3, A2-north-d.A1-north-a 5,
             B1-east-d.B2-east-a 5, B2-east-d.B3-east-a 7, B3-west-d.B2-west-a 7, B2-west-d.B1-west-a 5,
*            Umsteigepfeile: Mindestumsteigezeit
             A3-south-a.B2-east-d 8, A3-south-a.B2-west-d 3, A3-north-a.B2-east-d 8, A3-north-a.B2-west-d 8,
             B2-east-a.A3-south-d 8, B2-east-a.A3-north-d 3, B2-west-a.A3-south-d 8, B2-west-a.A3-north-d 8 /
   u(i,j)  Zeitlicher Hoechstabstand zwischen Ereignissen i und j
   r(i,j)  Anzahl an Knoten i auf Weiterfahrt nach j wartender Fahrgaeste (fuer Haltepfeile)
           / A2-south-a.A2-south-d 23, A3-south-a.A3-south-d 43, A4-south-a.A4-south-d 29, A5-south-a.A5-north-d 2
             A4-north-a.A4-north-d 17, A3-north-a.A3-north-d 52, A2-north-a.A2-north-d 33, A1-north-a.A1-south-d 3,
             B2-east-a.B2-east-d 63, B3-east-a.B3-west-d 5, B2-west-a.B2-west-d 49, B1-west-a.B1-east-d 7 /
   s(i,j)  Anzahl an Knoten i zu Knoten j umsteigender Fahrgaeste (fuer Umsteigepfeile)
           / A3-south-a.B2-east-d 13, A3-south-a.B2-west-d 17, A3-north-a.B2-east-d 21, A3-north-a.B2-west-d 9,
             B2-east-a.A3-south-d 16, B2-east-a.A3-north-d 22, B2-west-a.A3-south-d 26, B2-west-a.A3-north-d 14 /
   w(i,j)  Gewicht des Pfeils i-j im Constraint-Graphen ;

   u(i,j)$(halt(i,j) and (not end(i))) = l(i,j) + 1 ;
   u(i,j)$(halt(i,j) and end(i)) = 15 ;
   u(i,j)$fahrt(i,j) = l(i,j) ;
   u(i,j)$umstieg(i,j) = l(i,j) + 10 ;

scalar bigM  Hinreichend grosse Konstante ;
   bigM = sum((i,j)$halt(i,j), r(i,j)) + sum((i,j)$umstieg(i,j), s(i,j)) + 1 ;

   w(i,j)$halt(i,j) = bigM + r(i,j) ;
   w(i,j)$fahrt(i,j) = 0 ;
   w(i,j)$umstieg(i,j) = s(i,j) ;

scalar bigT  Zykluslaenge des Fahrplans in Anzahl Perioden / 10 / ;

***** Transformation in aequivalente Instanz mit l(i,j) < bigT und u(i,j)-l(i,j) < bigT *****

   l(i,j)$a(i,j) = mod(l(i,j), bigT) ;
   u(i,j)$a(i,j) = l(i,j) + min(u(i,j)-l(i,j), bigT-1) ;