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

Vasilis Verroios, Vasilis Efstathiou, Alex Delis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 12th IEEE International Conference on Mobile Data Management, MDM 2011
Pages141-151
Number of pages11
DOIs
StatePublished - 2011
Event2011 12th IEEE International Conference on Mobile Data Management, MDM 2011 - Lulea, Sweden
Duration: Jun 6 2011Jun 9 2011

Publication series

NameProceedings - IEEE International Conference on Mobile Data Management
Volume1
ISSN (Print)1551-6245

Conference

Conference2011 12th IEEE International Conference on Mobile Data Management, MDM 2011
CountrySweden
CityLulea
Period6/6/116/9/11

Keywords

  • ad-hoc networking
  • incremental computing
  • parking space problem
  • Time-Varying Travelling Salesman Problem
  • TSP
  • VANETs

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Reaching available public parking spaces in urban environments using ad hoc networking'. Together they form a unique fingerprint.

Cite this