T812
|
|
Modellen voor real-time-optimalisatie van binnenscheepvaart
Promotor: Karl Meerbergen
Begeleider: Karl Meerbergen, Luc Knapen (FKS)
Probleemstelling
Het verkeer op een (vermaasd) netwerk van kanalen (stilstaand water met constant niveau) moet worden geoptimaliseerd.
Er zijn 2 soorten kostenfuncties
- functies op basis waterverbruik door het schutten
- functies op basis van de duur van de vaart
Kenmerken
- er zijn lokale snelheidsbeperkingen
- er zijn beweegbare bruggen die on demand bediend worden (autoverkeer)
- er zijn beweegbare bruggen die met opgelegde planning bediend worden (spoorweg)
- er zijn sluizen van verschillende types
- schepen hebben minimale en maximale snelheden
- schepen hebben minimale en maximale versnellingen
- de capaciteit van de vaarweg m.b.t. kruisende en inhalende schepen wordt in elk punt bepaald door het dwarsprofiel
Beschikbare Oplossing
Het gebruikte model bestaat uit
- het netwerk samengesteld uit
- vaarwegcomponenten met constante nautische karakteristieken
- kunstwerken (sluizen, bruggen) gemodelleerd als Finite State Machines
- de schedule van spoorwegbruggen
- de getijdentabellen voor eindknopen van het net (daar kunnen schepen enkel in bepaalde timeslots relatief
en uitvaren)
- de schepen
Op dit ogenblik is er een oplossing voor het gestelde probleem die werkt als volgt :
- eerst wordt voor elk schip de kortste route door het netwerk gezocht met een verkeersonafhankelijke kostenfunctie
- vervolgens wordt voor elk schip in het model het optimale vaarschema bepaald op basis van
- de status van het verkeer in het model (schepen en kunstwerken)
- de gegeven meldingen van doorgang voor individuele schepen in welbepaalde punten (worden gebruikt om het model op elk ogenblik aan te
passen aan de meest recente informatie)
- een na een worden de schepen in het model toegevoegd en worden de kunstwerkoperaties gepland
- de gebruiker kan bijkomende eisen opleggen door interactief schepen te groeperen voor kunstwerkoperaties en door
kunstwerkoperaties te fixeren in de tijd
Beperkingen van de bestaande oplossing
- schepen worden in een voorafbepaalde orde aan het model toegevoegd : dat moeten we doen om te kunnen aantonen dat de
+rekentijd van de gebruikte algoritmen eindig is
- elke wijziging van gegevens vergt het complete doorrekenen van het model : als we voor probleem P0 de oplossing
+kennen, kunnen we die informatie niet gebruiken om de oplossing voor P1 te bepalen (waarbij de randvoorwaarden van
+P0 en P1 weinig van elkaar verschillen. Wijzigende randvoorwaarden met kleine afwijking treden bijvoorbeeld op bij
+meldingen van doorgang (de passage van een vaartuig in een welbepaald punt wordt vastgesteld : dat levert bijkomende randvoorwaarden
+(positie, indicatie van snelheid) voor het model)
- we kunnen geen sluizencomplexen met alternatieve parallelle kolken verwerken (komen voor in Vlaanderen)
- de watersnelheid moet nul zijn
- de nautische karakteristieken moeten constant zijn in de tijd
In het bestaande model (8 bruggen, 2 sluizen) kost de berekening van een vaarschema (voor 1 vaartuig) 350 .. 450 [msec]. De berekening
van een realistisch model (40 schepen op Kanaal Brussel-Schelde) kost daardoor ongeveer 15[sec].
Verder onderzoek en ontwikkeling
Intussen hebben we een methode in ontwerp (maar nog niet in detail onderzocht, noch geïmplementeerd) waarbij we het probleem
modelleren als een verzameling van gecoördineerde HP-FSM (Hierarchical Parallel Finite State Machines).
De eigenschappen van de coördinatie zijn goed beschreven. Op basis van reeds uitgevoerd onderzoek vermoeden we
- dat we met deze methode wel de oplossing van hoger genoemd probleem P1 uit die van P0 kunnen afleiden
- dat we parallelle kolken kunnen behandelen
- dat we geen voorafbepaalde vaste orde van verwerking van schepen moeten opleggen
Het is de bedoeling om in het kader van een eindwerk te zoeken naar algemeen bruikbare algoritmen voor het minimaliseren van een
kostenfunctie gedefinieerd over een grote set van gecoördineerde HP-FSM’s wanneer een oplossing onder weinig afwijkende
randvoorwaarden gekend is.
Daarbij kan eventueel gestart worden van een nagenoeg-optimale situatie (die kan door de huidige software geleverd worden).
|
