Abstract

Currently no dynamic route planners are present that take different transport modes into account. Although the highway network in the Netherlands is flooded with cars and is subject to heavy congestion in both rush hours and about 22% of the trains is delayed no planner is available that finds the fastest route using all kinds of transportation and considering all occuring delays.

In this thesis state of the art applications in this field are reviewed and the research that has been carried out into such a route planner is described, culminating in the design of such a planner and the implementation of a prototype, called KRIS (Knowledge based Routing Information System). It is shown that such a planner is feasible, although its quality will depend on the availability of public transport delay data and sophisticated travel time predictors for the roads in the highway network.

When research was carried out to the performance of traditional shortest path algorithms, like Dijkstra’s algorithm, in such a route planner, it showed that the computation time increases significantly when dynamic data are incorporated. Consequently, other possibilities were explored and since humans are quite well capable of finding alternative routes in the case of congestion it was decided to study the feasibility of an expert system approach. In the prototype that has been build two implementations have been made, one using an expert system approach, the other using a Dijkstra-like shortest path algorithm, to be able to compare both methods.

It is concluded that the expert system approach shows great potential. Not only requires the expert system significantly less computation time, it is also possible to perform incremental searching: alternative routes are computed one by one and the best one found so far is available at every moment. The incremental searching property of the algorithm may prove to be very useful in a real time application, for example when a user is approaching a junction and needs to know quickly which route to take.