Wartezeiten bei zyklischen Bedienungen an Kanten

Bei der Betrachtung von periodischen Kantenproblemen gibt es einen Planungshorizont H. In H sollen Kanten / Jobs erledigt werden. Bis zur nächsten Bedienung der Kante gibt es dann ein Zeitfenster als Abstand zu der letzten Bedienung: einen Minimalen Abstand minspan (u) und einen maximalen Abstand maxspan(u) einer Kante u. Daraus ergibt sich eine Kombination comb(u) der möglichen Bedientage.
Bei einem Planungshorizont H von einer Woche gibt es np = 7  Perioden : { 1,2,3,4,5,6,7=np}, um täglich Bedienung durch zuführen, oder bei einer 2xwöchentlichen Bedienung einer Kante kann z.B. comb(u)  = {1,4} oder {2,5} sein. Da aber an Samstagen und Sonntagen keine Bedientage sind reduzieren sich die Möglichkeiten:

• 1 mal pro Woche: {1},{2},{3},{4},{5} // Mo, ... Fr
• 2 Mal pro Woche: {1,4}, {2,5}
• 5 mal pro Woche: {1,2,3,4,5} // täglich

Periodizität an den Kanten

Periodische Kantenprobleme

An m Kanten (Straßenabschnitten) in einem gerichteten Graph G  gibt es einen bestimmten Planungshorizont H mit einer Anzahl von np Perioden.
Jeder Job oder Kante hat einen bestimmte Frquenz. Dabei ist bei den ungerichteten Kanten darauf zu achten, dass nicht nur die Kosten einmalig für beide Kanten u und v anfallen, sondern auch die Frequenz f(u) gleich ist (f(u)  = f(inv(u)). So muss eine Kante u 1<= f(u) <= np mal im Planungshorizont H bedient werden.
Die Summe aller Frequenzen ns im Planungshorituont H zerteilt das Problem in bestimmte Tagesrhytmen. Unglücklicherweise können die Bedientage nicht willkurlich gewählt werden, sondern sie sollen auch Abstandsregeln einhalten; somit sollen 2 Bedientage in der Persiode wöchentlich nicht z.B. Montag-Dienstag stattfinden, sondern dazwischen mindestens ein Bedienpausentag liegen (z.B. Montag- Donnerstag).