Javier MARENCO - University Torcuato Di Tella, Argentina
Wednesday, October 1
Titre : Dynamic parking in unstructured parking lots
Abstract : We consider the following dynamic car parking problem. We have a parking lot, which we assume is divided into a grid of n × m positions. A single car can be placed in each position. We assume that each position corresponds to a rectangle with its longest side parallel to the horizontal axis, so that each car faces either the left or right side of the grid. In the classic scheme, the grid is divided into vertical "lanes," on which a car cannot be placed, such that the remaining positions allow a path to/from the parking lot entrance/exit. In this work, we consider a more general version of the problem, in which a car can park in any position of the grid, as long as there are paths from the entrance/exit to that position when the car enters and exits the parking lot. Once parked, a car cannot move from its position. A priori, this strategy allows for the allocation of a larger number of cars than the classic scheme, making better use of available resources.
We assume we have a list of reservations, each consisting of a day and time of the reservation, a day and time of the car's arrival at the parking lot, and a day and time of the car's departure from the parking lot. Given this reservation list, the offline problem consists in determining the largest number of cars (or, alternatively, the largest revenue) that can be allocated to the parking lot. The online version consists of determining, for each car in the reservation list in order of reservation date, whether the car can be accepted and, if so, in which position it should be allocated. In this work, we propose an integer linear programming model for the offline problem and several integer linear programming-based strategies for the online problem. Using historical reservation data for a parking lot in Santiago, Chile, we show that online schemes are feasible and allow for a better use of the available space.