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 on two-way driving lanes, 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 requiring 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 then 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 from 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 op