Improving parking garage efficiency using reservation optimization techniques (2011)

Parking in urban and suburban districts is becoming increasingly problematic due the information gap between the parking garages and the average commuter. This thesis describes and evaluates techniques that can be implemented by parking garages to augment parking garage efficiency. The issues studied in this thesis were i) Real-time tracking of car position ii) maximizing the number of reservations made for the parking garage by re-arrangement of existing reservations (Reservation Defragmentation) and iii) maximizing revenue for the parking garage through increased occupancy (Revenue Management). For the tracking problem, in order to be able to track the real-time position of the vehicle inside the parking garage, we have proposed two techniques. The first one involves a high accuracy algorithm that takes as input a higher number of sensor values (high accuracy) and the second one is a lower cost algorithm that takes as input fewer number of sensor values (low cost). We simulated various conditions of sensor failure rate and determined our metric to be number of tracked points as a percentage of the path to the destination. We determined limitations of these algorithms with respect to maximum speed of cars and inter-car distance. For the reservation defragmentation problem, we looked at increasing occupancy efficiency for i) Next day reservations and ii) Current day reservations. For this problem, we implemented three algorithms. For next day reservations, we established metrics to determine the efficiency of the algorithm including number of free parking spots created and reduction in lengths of free space in between the reservations. For current day reservations, our metric was the increase in maximum occupancy observed due to defragmentation. For increased revenue management, we suggested the application of two techniques: Booking limits and Overbooking. In booking limits, two-fare class of parking was suggested and the number of spots that need to be reserved for higher class (Capacity of garage - booking limit) was determined for probability distributions of customer arrival such as Poisson distribution. Since the practice of overbooking is done in order to compensate for the no-shows that occur despite reservations made, we have suggested an algorithm to determine the amount of overbooking based on a Gaussian distribution of customer ‘no-shows’. We obtained the following results for the algorithms implemented. In case of the tracking algorithm, as the sensor failure rate increased, the inaccuracy of the two proposed algorithms also increased. For 2% failure rate, we track 0.4% of the incoming cars inaccurately (given that a tracking is marked as correct if 75% or less of all sensors along the path of the car fail). In case of reservation defragmentation, we obtained best results for Recursive First-Fit algorithm. For next day reservation defragmentation, using a mean of 15% cancellation of reservations resulted in 14.6% decrease in occupied parking spots which can then lead to increased occupancy and 46.3% decrease in inter-reservation free space sizes for a 1000 arrival reservation system. The reservations were exponentially distributed with a mean of 20 reservations/hour. For current day reservations, we were able to increase maximum occupancy of the parking garage by 5.5% using Recursive First Fit algorithm. Among other conditions, we have evaluated Poisson arrival distribution with corporate arrival rate 100 cars/hour (Flintsch et al., 2006) [56] and corporate fare twice of leisure fare. For this condition, protection level (number of parking slots reserved for corporate class) is determined to be 20% of garage capacity. We also evaluated Binomial distribution with probability of incoming customer to be corporate customer as 0.5 and corporate fare twice of leisure fare. For this condition, protection level is determined to be 50% of garage capacity. We evaluated overbooking for several combinations of No-show rates, mean and standard deviation values and the highest amount of overbooking we obtained was 1.93 times maximum garage capacity and this implies that permitting this number of reservations for the parking garage would minimize the number of parking spots being under-utilized and increase the revenue of the parking garage operator due to effective use of parking spots. The algorithms have been simulated for different arrival distributions (for Revenue Management), different arrival rates (tracking) as well as variable durations of stay (reservation defragmentation). Besides the problems mentioned, there are certain other aspects, such as generalizing the tracking algorithms for parking garages of arbitrary layouts represents the work that needs to be done in the future.