I. Introduction
FINDING a parking space in a densely populated area is a nontrivial challenge. Furthermore, the unavailability of instantaneous parking causes significant damages, both economically and environmentally. People cruising for parking waste not only their own time, which they could spend working or for leisure but also consume road capacity, burn fuel, and produce toxic emissions, thus contributing significantly to congestion, greenhouse gas emissions, and pollution. It was recently reported that, over one year in a small Los Angeles business district, cars cruising for parking burned 47 000 gal of gasoline and produced 730 ton of carbon dioxide [13]. Further, the consulting firm McKinsey recently claimed that the average car owner in Paris spends four years of his life searching for parking spaces [4].