City-Based Parking and Routing System
A Master Thesis Project
Abstract
People driving by car from point A to point B try to reach their destination as soon as possible. Along the route, however they can experience all sorts of delays. Unforeseen traffic jams, road maintenance and lack of route knowledge on the side of the driver are some of the most common problems that cause delays. Modern day navigational systems like TomTom are able to help the driver reach his destination as soon as possible by calculating a route that in theory represents the shortest route in time from point A to point B. However, the service offered by these devices is limited. The shortest routes in time presented by these devices are only theoretical since most devices are unable to take traffic jams, accidents and road maintenance into account relying solely on static routing algorithms. Furthermore, once the destination is reached the driver himself is required to search for suitable parking place, which can cause considerable delays and hampers the flow of other traffic within the city.
In this thesis, we propose to solve these two hiatuses in the level of service of navigational systems by introducing a City‐Based Parking and Routing System (CBPRS). The CBPRS is a distributed system that provides its participants with the comfort of a guaranteed parking place at their point of destination in combination with a time optimal route towards their destination from the outskirts of a city environment monitored by the CBPRS. The CBPRS consists out of a large set of intelligent lampposts placed near intersections and parking places that allow the CBPRS to communicate with CBPRS participants and monitor the status of parking places. Participating drivers reserve parking places monitored by the system via wireless communication with one of the intelligent lampposts placed at each intersection in the city. The system then guides the driver using a constant stream of directional information via the most time optimal path towards the reserved parking place. On the route towards the parking place, the driver provides the CBPRS with route delay information so that the system can calculate the most optimal route towards the destination.
The ant colony meta‐heuristic – originally deducted from the behavior of Argentinean ants – is adapted for hierarchical distributed routing in a city environment. The algorithm implements a hierarchy that separates normal roads from main roads and high ways. The normal roads are classified into colonies between which vehicles can travel via the main road network that resides on a higher hierarchical level. The ant‐based algorithm is fully distributed with routing tables residing at intelligent lampposts located at intersections. Route delay information communicated to the CBPRS is exchanged between lampposts by use of intelligent agents called ants. The ant‐based algorithm is thereby able to route vehicles using current and up‐to‐date information concerning the actual state of the traffic network, resulting in routes that are optimal in practice.
Via a series of experiments in ever larger and complex city environments, we tested the behavior of the CBPRS. During these experiments, we found that once environments reached the size of cities the CBPRS performed significantly better than static routing solutions offered by navigational systems. Vehicular distributions created by the ant‐based algorithm of the CBPRS proved to decrease overall travel times, increase traffic flows and lower the amount and duration of traffic jams within the environment.