An integrated ride-sharing and parking allocation system

This study introduces a new policy for managing parking scarcity called Parking Allocation and Ride-Sharing System (PARS). In PARS, a centralized algorithm allocates parking spacesto drivers who are willing to participate in a coordinated carpool. The algorithm is used to optimize the creation of carpools going to and returning from a particular venue and simultaneously reserve parking for these carpools at the venue. An efficient mixed integer linear programming (MIP) formulation is presented and two heuristics, namely Ride Decomposition (RD) and Quick Converge (QC), are proposed and compared via internally generated experiments. Experimental results show that a commercial solver is able to solve the MIP with thousands of individuals to optimality in minutes. For larger instances, the RD and QC heuristic algorithms can solve the problem, on average, 42.23% and 86.39% faster than the commercial solver and provide solutions that are 3.61% and 3.49% from optimal, respectively.