Zebra-reeks nr. 53, Epsilon, Amsterdam, 68 pp., ISBN 978-90-5041-172-1.

Het \(53^{\text{ste}}\) boekje in de Zebra-reeks heb ik in één teug leeggelezen. En daarna heb ik onmiddellijk een rekenblad geopend om na te rekenen of alles wel klopte. Je doet dit wellicht ook als je dit boekje in handen krijgt, tenminste indien je van onconventionele en onverwachte wiskunde houdt. Knap geschreven, goed opgebouwd.

Het thema van dit zebraboekje is het modelleren van een dienstregeling voor een willekeurig spoorwegnetwerk. De Nederlandse spoorwegen gebruiken voor hun dienstregeling een simulatieprogramma SIMONE en PETER, gebaseerd op de (max,+)-algebra. In de voorbeelden en oefeningen gaat het uiteraard om netwerken die flink wat kleiner zijn dan die van de Nederlandse spoorwegen.

Als kennismaking met dit model, val ik meteen halverwege het Zebraboekje binnen.

Een merkwaardig matrixproduct

Tegen alle verwachting in is het volgende matrixproduct correct berekend. Zie je wat hier achter zit?

\( \left(\begin{matrix}-\infty&-\infty&-\infty&4&7\\2&-\infty&-\infty&-\infty&-\infty\\5&-\infty&-\infty&-\infty&-\infty\\6&3&4&-\infty&-\infty\\-\infty&-\infty&6&4&-\infty\end{matrix}\right) \otimes \left(\begin{matrix}7\\2\\5\\6\\6\end{matrix}\right)=\left(\begin{matrix}13\\9\\12\\13\\11\end{matrix}\right)\)

Het teken \(\otimes\) doet waarschijnlijk een belletje rinkelen. Het gaat hier om een ongebruikelijke matrixvermenigvuldiging. Normaal vermenigvuldig je een rij van de eerste matrix met de kolom van de tweede matrix. In deze context is dit ook zo op voorwaarde dat je de vermenigvuldiging \(\otimes\) van twee reële getallen opvat als een (gewone) optelling en de optelling \(\oplus\) van twee reële getallen als de berekening van een maximum:

\(a \otimes b = a+b \textrm{ en } a \oplus b= \textrm{max}(a, b).\)

Zo is \(-\infty \otimes 7=7\) en \(7 \otimes 6=13\) en \(7 \oplus 13=13\). De vermenigvuldiging van de eerste rij met de eerste (en enige) kolom geeft dan

\(\textrm{max}(-\infty+7,-\infty+2,-\infty+5,4+6,7+6)\)

wat gelijk is aan 13. En de vermenigvuldiging van de tweede rij met de eerste kolom geeft

\(\textrm{max}(2+7,-\infty+2,-\infty+5,-\infty+6,-\infty+6)\)

wat gelijk is aan 9.

Kijk nu even na of je de volgende matrixbewerkingen vat.

\( \left(\begin{matrix}-\infty&-\infty&-\infty&4&7\\2&-\infty&-\infty&-\infty&-\infty\\5&-\infty&-\infty&-\infty&-\infty\\6&3&4&-\infty&-\infty\\-\infty&-\infty&6&4&-\infty\end{matrix}\right) \otimes \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right)=\left(\begin{matrix}25\\21\\24\\25\\24\end{matrix}\right)\)

\(6 \otimes \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right)=\left(\begin{matrix}25\\21\\24\\25\\24\end{matrix}\right)\)

Door gelijkstelling krijg je een uitdrukking die wat doet denken aan eigenwaarden en eigenvectoren.

\( \left(\begin{matrix}-\infty&-\infty&-\infty&4&7\\2&-\infty&-\infty&-\infty&-\infty\\5&-\infty&-\infty&-\infty&-\infty\\6&3&4&-\infty&-\infty\\-\infty&-\infty&6&4&-\infty\end{matrix}\right) \otimes \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right)=6 \otimes \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right)\)

Zulke uitdrukkingen blijken een cruciale rol te spelen in het organiseren van dienstregelingen van een willekeurig spoorwegnetwerk. Mysterieus? Absoluut!

Eigenschappen van \(\oplus\) en \(\otimes\)

Terug naar het begin van het Zebraboekje. De nieuwe optelling \(\oplus\) en de nieuwe vermenigvuldiging \(\otimes\) voldoen bijna aan dezelfde eigenschappen als de `normale’. Er zijn twee soorten van commutativiteit en twee soorten van associativiteit:

\(a \oplus b = b \oplus a\)

\(a \otimes b = b \otimes a\)

\(a \oplus (b \oplus c)=(a \oplus b) \oplus c\)

\(a \otimes (b \otimes c)=(a \otimes b) \otimes c.\)

Bovendien hebben de beide bewerkingen een neutraal element:

\(a \oplus -\infty= a\)

\(a \otimes 0=a.\)

Voor de nieuwe vermenigvuldiging (de klassieke optelling) heeft elk reëel getal een inverse. Maar voor de nieuwe optelling helaas niet (ga na!).

Tot slot is er distributiviteit van de nieuwe vermenigvuldiging ten opzichte van de nieuwe optelling:

\(a \otimes (b \oplus c)= a \otimes b \oplus a \otimes c.\)

De auteur legt ook uit hoe machten worden berekend. Er is zelfs een alternatief voor het klassieke sommatieteken. Hier gaan we niet verder op in.

Verband met een spoorwegnetwerk

Beeld je je een spoorwegnetwerk in als een gerichte graaf. De `knopen’ (punten) zijn de stations. De `bogen’ (lijnen) zijn de spoorwegen die de stations verbinden. De gewichten bij de bogen zijn de onderlinge reistijden (de overstaptijden zijn hierin verrekend). En de oriëntatie van de bogen geeft de rijrichting aan.

 

In figuur 1 zie je een spoorwegnetwerk met vijf stations. Niet elke twee stations zijn met elkaar verbonden. De verbindingstijden kunnen vastgelegd worden in een verbindingsmatrix \(A\) zo dat het element \(a_{ij}\) de tijd is van een ritje van station \(j\) naar station \(i\). We spreken af dat twee stations die niet verbonden zijn met een spoorlijn een verbindingstijd hebben gelijk aan \(-\infty\). Zo vinden we de verbindingsmatrix:

\(A=\left(\begin{matrix}-\infty&-\infty&-\infty&4&7\\2&-\infty&-\infty&-\infty&-\infty\\5&-\infty&-\infty&-\infty&-\infty\\6&3&4&-\infty&-\infty\\-\infty&-\infty&6&4&-\infty\end{matrix}\right).\)

Stel dat er uit elk van de vijf stationnetjes treinen vertrekken op afgesproken tijdstippen. Deze eerste vertrektijden zetten we per station in een kolommatrix \(V_1\):

\(V_1=\left(\begin{matrix}7\\2\\5\\6\\6\end{matrix}\right)\)

Uit deze eerste vertrektijden kunnen we de vertrektijden berekenen van een tweede lichting treinen. Hiervoor zijn wel regels opgelegd. Deze treinen mogen pas vertrekken op het moment dat alle treinen van de vorige lichting in het station zijn toegekomen. Geen enkele passagier mag immers een aansluiting missen.

Hoe berekenen we het tweede vertrektijdstip vanuit station 1? Wel, in station 1 komen twee treinen toe. De trein die vanuit station 4 komt, rijdt het station binnen op tijdstip 4+6 (6 was het vertrektijdstip en 4 is de verbindingstijd). De trein die vanuit station 5 komt, arriveert op tijdstip 7+6 (6 was het vertrektijdstip en 7 is de verbindingstijd). De tweede trein die station 1 verlaat mag dit pas doen op tijdstip max\((4+6,7+6)=13\), wanneer de laatste van de twee treinen toegekomen is. Er moet geen rekening gehouden worden met treinen die van een ander station komen.

Het getal 13 berekenden we eerder al op een gelijkaardige wijze via het matrixproduct

\( \left(\begin{matrix}-\infty&-\infty&-\infty&4&7\\2&-\infty&-\infty&-\infty&-\infty\\5&-\infty&-\infty&-\infty&-\infty\\6&3&4&-\infty&-\infty\\-\infty&-\infty&6&4&-\infty\end{matrix}\right) \otimes \left(\begin{matrix}7\\2\\5\\6\\6\end{matrix}\right)=\left(\begin{matrix}13\\9\\12\\13\\11\end{matrix}\right).\)

Ook voor de andere stations kun je zulke redenering herhalen. We besluiten hieruit dat de vertrektijden van de tweede lichting treinen die vanuit elk station vertrekken, gevat worden in de matrix

\(V_2=\left(\begin{matrix}13\\9\\12\\13\\11\end{matrix}\right).\)

Op deze manier kun je de volgende vertrektijden \(V_3, V_4, V_5 \dots\) berekenen in de hoop dat er een regelmaat in zit, die zorgt voor een periodieke herhaling van de reistijden. Zulke regelmaat is aangenaam, zowel voor reizigers als voor spoorwegpersoneel. De periodieke herhaling blijkt tot mijn grote verbazing altijd gevonden te kunnen worden bij sterk verbonden netwerken, d.w.z. bij netwerken waarbij je van elk station naar elk station kunt reizen.

Het poweralgoritme

Het poweralgoritme werkt, zoals de naam doet vermoeden, met machten van de verbindingsmatrix \(A\). We leggen dit algoritme hier even uit zonder te steunen op de machtsverheffing. Kies een willekeurige vertrekmatrix \(V_1\) en bereken hieruit \(V_2\), \(V_3\), \(V_4\) enz. Ga hiermee door tot één van deze vertrekmatrices \(r \otimes\) een andere vertrekmatrix is.

We rekenen dit hieronder uit voor het spoorwegnetwerk dat hierboven getekend is:

\(V_1=\left(\begin{matrix}0\\0\\0\\0\\0\end{matrix}\right) \textrm{ en } V_2=\left(\begin{matrix}7\\2\\5\\6\\6\end{matrix}\right) \textrm{ en } V_3=\left(\begin{matrix}13\\9\\12\\13\\11\end{matrix}\right)\)

\(\textrm{en } V_4=\left(\begin{matrix}18\\15\\18\\19\\18\end{matrix}\right) \textrm{ en } V_5=\left(\begin{matrix}25\\20\\23\\24\\24\end{matrix}\right) \textrm{ en } V_6=\left(\begin{matrix}31\\27\\30\\31\\29\end{matrix}\right).\)

Het rekenwerk kan makkelijk overgelaten worden aan een rekenblad. Als je goed kijkt, merk je dat \(V_5=18 \otimes V_2\). De vertrektijden van \(V_5\) zijn 18 eenheden groter dan de vertrektijden van \(V_2\).

De waarde \(r=18\) kan ook op zicht gevonden worden zonder rekenwerk met matrices, althans voor relatief kleine netwerkjes. Je zoekt een gesloten circuit waarbij de omloopstijd gedeeld door het aantal etappes (m.a.w. het circuitgemiddelde) maximaal is. Zo is er altijd eentje. Na even te puzzelen zie je dat het circuit met het grootste circuitgemiddelde \(1 \rightarrow 3 \rightarrow 5 \rightarrow 1\) is. Dit circuit heeft lengte 18 en circuitgemiddelde 6. We noemen dit circuit het kritieke circuit. Op dit circuit sluiten de treinen onmiddellijk op elkaar aan als je in een rondje rijdt. Als er een vertraging is op dit circuit, zal de hele dienstregeling hier door in de war geraken. Vandaar het adjectief kritiek.

Eigenwaarde en eigenvector

We berekenden op twee manieren dat het circuitgemiddelde van het kritieke circuit gelijk is aan 6, een keer door de opeenvolgende vertrekvectoren \(V_i\) te berekenen en een keer door het circuitgemiddelde van het kritieke circuit te zoeken. Deze waarde is een eigenwaarde van de verbindingsmatrix \(A\). De eigenwaarde geeft aan na hoeveel tijd de hele dienstregeling ten vroegste kan herhaald worden. In dit geval na 6 tijdseenheden.

De bijbehorende eigenvector berekenen is veel lastiger. Ik heb het geprobeerd door een stelsel op te stellen met vijf vergelijkingen en vijf onbekenden maar het liep niet van een leien dakje.

Ook voor de berekening van eigenvectoren wordt in de tekst een algoritme voorgeschoteld, jammer genoeg zonder bewijsvoering. Hier bleef ik wat op mijn honger zitten maar ik neem aan dat dit bewijs te moeilijk is voor het doelpubliek dat bestaat uit middelbareschoolleerlingen (en misschien ook voor mezelf).

We laten het algoritme even links liggen en plukken de eigenvector uit een eerdere berekening:

\( \left(\begin{matrix}-\infty&-\infty&-\infty&4&7\\2&-\infty&-\infty&-\infty&-\infty\\5&-\infty&-\infty&-\infty&-\infty\\6&3&4&-\infty&-\infty\\-\infty&-\infty&6&4&-\infty\end{matrix}\right) \otimes \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right)=6 \otimes \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right).\)

De eigenvector

\(E= \left(\begin{matrix}19\\15\\18\\19\\18\end{matrix}\right)\)

stelt nu de dienstregeling voor. Hiermee bedoelen we de mogelijke vertrektijdstippen van een eerste lichting treinen. Als we de klok 15 eenheden doordraaien, ongeveer zoals bij de zomer- en wintertijd, dan vinden we de dienstregeling

\(D= \left(\begin{matrix}4\\0\\3\\4\\3\end{matrix}\right).\)

die makkelijk te interpreteren is. De eerste lichting treinen vertrekt op de tijdstippen aangegeven in de matrix \(D\). De tweede lichting treinen vertrekt 6 minuten later. De derde lichting vertrekt 12 minuten later, enz. Ik vat de vertrektijdstippen samen in een tabel.

Controle van de dienstregeling

Met deze dienstregeling zou geen enkele reiziger zijn aansluiting moeten missen en zouden de wachttijden op de perrons binnen de perken moeten blijven. Even controleren of dit klopt.

In station 5 komen twee treinen toe, eentje uit station 3 die vertrekt op tijdstip 3 en die 6 minuten onderweg is en eentje die vertrekt uit station 4 die vertrekt op tijdstip 4 en die 4 minuten onderweg is. De ene trein komt op tijdstip 9 toe en de andere op tijdstip 8. De tweede trein uit station vertrekt op tijdstip 9: een naadloze aansluiting voor de reizigers vanuit station 3 en een wachttijd van 1 minuut voor de reizigers uit station 4. Dat is zeker in orde.

Als je het hele netwerk aftast zul je ergens een wachttijd vinden van 2 eenheden (op het perron van station 1) en een wachttijd van 3 eenheden (op het perron van station 4). Of deze verloren tijd binnen de aanvaardingsnormen ligt, weet ik niet.

Bijkomende problemen en opportuniteiten

Gerardo Soto y Koelemijer laat duidelijk zien hoe deze dienstregelingen opgewassen zijn tegen kleine vertragingen op bepaalde circuits. Na verloop van tijd zijn alle achterstanden spontaan ingehaald door het opofferen van wachttijd bij het overstappen. De dienstregelingen zijn echter machteloos tegen vertragingen op het kritieke circuit. Elk oponthoud op dit circuit zet zich door naar het hele netwerk. Hiervoor is ook een oplossing bedacht helemaal op het einde van het Zebraboekje.

Na het lezen bleef ik nog met een praktische vraag zitten, die voortkomt uit de vereenvoudiging in de modellering van de reisschema’s. Als er verschillende treinen uit hetzelfde station vertrekken, gaat dit model er van uit dat deze treinen simultaan vertrekken. In praktijk is het uiteraard niet zo dat treinen vanuit een bepaald station in kudde worden vrijgelaten op hetzelfde tijdstip. Misschien kunnen leerlingen zelf een oplossing zoeken voor dit bijkomende probleem.

Tot slot bedenk ik dat het interessant is voor leerlingen om een dienstregeling uit te rekenen van een sterk samenhangend netwerk met een twintigtal stations. Dit doen ze dan uiteraard met een rekenblad. Volgens de theorie moet er gerekend worden met \(-\infty\), een getal dat te klein is om door een rekenblad aanvaard te worden. Zelf heb ik \(-\infty\) (de reistijd voor ontbrekende verbindingen) vervangen door \(-1\). En dat lukte ook.