Reaching available public parking spaces in urban environments using ad hoc networking

A fundamental application in vehicular ad-hoc networks (VANETs) is the discovery of available parking spaces as vehicles navigate through urban road networks. Vehicles are now capable of finding such parking spots using their on-board sensing and computational infrastructure and then they can disseminate this information for use by other members of the travelling community in the geographic vicinity. In this context, we examine the problem of locating an available parking space for a vehicle entering an urban network of roads. Upon its entry, a vehicle has to determine the best way to visit parking spots reported to be free. In deciding this, the vehicle has to consider the time required to reach each candidate position, its distance from the final destination should the driver walk, and of course, the probability that the spot(s) will be still-free once the vehicle shows up at location. We formulate the question at hand as a Time-Varying Travelling Salesman problem and we propose an approach for computing the route that a vehicle must traverse in order to visit all parking spaces known to be available. Our method takes into account the limited computational resources of vehicles and attempts to find the best feasible trip. This is done in conjunction with a cost function that estimates the probability to find a space filled. In order to ascertain the effectiveness of our proposal, we compare it with a best-first approach and examine computational overheads. We also investigate how close to optimal results our approach comes.