A Branch-and-Cut Algorithm for the Optimal Design of Parking Lots with One-way and Two-way Lanes

We address the problem of maximizing the number of stalls in parking lots where vehicles park perpendicular to the driveways. Building on recent research, we first formulate a mixed integer program to maximize the number of parking stalls using a flow-based approach. Parking lots are rasterized into a grid, and the proposed MIP model optimizes them in a generic manner, adapting to the grid resolution and stall size without the need for custom formulations. The constraints ensure the connectivity of parking stalls and driveways to the entrance/exit. This formulation is then extended to the case of one-way driving lanes. We also propose valid inequalities and a branch-and-cut algorithm for the one-way and two-way lane configurations. This approach eliminates flow variables, big-M type constraints, and improves solution times for medium-sized instances. The effectiveness of the suggested models is showcased on 325 parking lots in New York City. For instances in which the flow version could be solved in 15 minutes, the branch-and-cut algorithm improved the median runtimes by 87.43% for the one-way case and by 79.36% for the two-way case and resulted in better optimality gaps for the other instances, compared to the baseline flow-based formulation. Similar advantages were observed when run with a time budget of two hours. One-way configurations accommodated up to 18.63% more vehicles on average than their two-way counterparts across all the instances. Modifications to the proposed formulations that consider the turning characteristics of vehicles and the presence of multiple entrances and exits are also examined.