|
In this game, you have to deal with the following items: Sets of trains, railway stations, tracks between the stations,
passengers who want to travel, and a plan for the trains. If you call the stations nodes, and the tracks edges,
nodes and edges form a graph. The edges of the graph have a FIFO-property, which means that you can have several trains
on the same edge at the same time, but the train which enters an edge as first, will also leave it as the first.
Usually, the edges are directed, but some of them may have the property that their direction can be reversed at certain points
of time. A plan tells us, which trains leave and enter which stations at what time.
Moreover, there are passengers, who would like to travel from some origins to destinations. They use a
fixed, pre-determined path. At a certain point of time,
i.e. their desired starting time, they travel to their start station and take the next train that follows their desired path.
The pitty with this game is that the travel times of the trains from one station to another one is not deterministic. The travel times
are only known in form of probability distributions. Thus, trains may arrive later than planned.
On the one hand, if a train T arrives late at a certain station,
it might be useful to make another train S wait for T, because a lot of passengers desire to change the train from T to S.
On the other hand, it might be more profitable not too wait for T, because lots of passengers would then be delayed.
A controller has to decide case by case, when a train has to wait for another one, and when not. Additionally, we might also
provide another plan in advance, a plan which is more robust against disruptions.
The task is to find a good plan and/or control strategy, such that all passengers reach their destinations, and
such that the weighted sum of all travel times of all passengers
is minimized.
We have developed a framework for testing such waiting policies. A server is running the schedule and sending out
queries, and another program, called the Engine, is supposed to answer these queries. Both are connected via a
game client that also provides a graphical user interface and a visualization. Below you find more details about
the model that is running on the server and about how to implement your own waiting policy as an Engine.
Three simple Engines for testing and presenting are available below. An Engine using Monte Carlo tree search is work in progress.
|
|