A Primal-Dual Algorithm for Online Parking Allocation Problems

In this research, we present an efficient primal-dual algorithm for an online resource allocation problem occurring in parking allocation. We consider the situation where vehicles arrive over time and request a parking place in one of the available parking. Upon arrival, a driver declares her intended duration of stay, however, at the end of the declared duration, the driver may extend its stay for a stochastic number of periods. The algorithm is designed to maximize the total expected reward. Through numerical experiments, we show that the algorithm converges fast to the value of the offline LP relaxation of the model for large number of vehicles and available capacity.