Optimal rental and configuration of reserved parking for carsharing by Integer Linear Programming and Ant Colony Optimization

Carsharing services allow customers to carry out short rents of vehicles, classically paying a per-minute fee, and have known a wide success in major cities all around the world in recent years. They represent an important case of shared mobility and are considered a crucial service in modern smart cities. In this work, we highlight the relevant role that parking slots reserved to carsharing vehicles may have in favouring the success and diffusion of such services, also referring to remarkable regulations of some major cities. Given such relevance, we address the problem of a Local Government that intends to select locations to deploy sets of parking slots reserved to carsharing, also selecting the configuration of the set (e.g., the number and orientation of the slots). In order to mathematically represent the problem, we propose an Integer Linear Programming model that includes whether to rent or not to rent a cluster of parking slots to carsharing companies as central decisions, while also comprising constraints that models lower and upper bounds on the number and type of reserved slots (e.g., modeling the tolerance of the local residents with respect to losing slots for parking their private vehicles). Since the problem is hard to solve from a theoretical point of view, we propose a metaheuristic solution algorithm that combines an improved ant colony optimization algorithm, exploiting suitable linear relaxations of the integer model, with an exact large neighborhood search. On the basis of realistic data instances referring to the city of Rome, we report results of computational tests, highlighting that our optimization method can grant good quality solutions associated with a fair distribution of the reserved parking slots.