Optimal Vehicle Assignment for a Dynamic Ride-Sharing Service and Spatiotemporal Taxi Demand Forecasting

During the recent years, the transportation of persons and items is changing drastically. Shared mobility systems are providing flexible public travel modes comparable to private transportation systems at accessible prices. Companies like Uber, Lyft, Postmates are developing algorithms for managing their fleets of vehicles to accommodate ever-growing demands. In 2014 Uber announced UberPool, a ride-sharing service that nowadays accounts for 20% of the total Uber rides. Ride-sharing was born to fit the requests of more customers in one single vehicle ride, so that to decrease the service costs both for the providers and the customers. The complexity of the problem derives from the number of constraints influencing the system. The goal is to efficiently manage the fleet, by reducing transportation costs and increasing the occupancy ratio of vehicles, while at the same time satisfying the most customers. In this thesis, a dynamic ride-sharing algorithm for the assignment of vehicles to customers has been developed together with a demand forecasting algorithm to predict the number of pickup requests that will happen in the different areas of a map. Our ride-sharing algorithm is dynamic because it can add requests to vehicles when vehicles are already serving other requests, while meeting all the time requirements of the customers on the arrival times. Dynamic systems must be able to manage and process data that change over time, and to compute assignments under strict temporal constraints. The algorithm works by matching requests using network theory by building a so called shareability graph, that describes which requests can be shared and which vehicles can serve them, depending on the time windows of the different tasks and on the capacities of the vehicles. Then, on top of this graph, a set of feasible trips is generated. An integer linear programming problem (ILP) will assign vehicles to trips by choosing them from the set of feasible trips. Great emphasis has been given to the execution time of the algorithm, since the future scope is to have it running on a real application for dynamic vehicle assignment, which will need to manage real-time data from incoming requests of customers. In our case, since it is not needed to assign all requests, imbalance between the distributions of the demand and of the vehicles can leave some customers unserved. To try to serve previously unassigned customers a rebalancing phase is designed where idle vehicles, if present, are matched with requests that are still pending via the solution of a linear programming problem. It is imperative for transportation companies to prevent imbalances in the distribution of the fleet in the areas covered by the service by predicting what will be the demand for taxis in the different regions. To this aim, we want to build a model to predict the hourly number of pickups in different areas of the map. For this thesis, we have used the dataset of the yellow taxi trips record data of New York City from three months of year 2016. The data have been preprocessed so that to generate a dataset that can give spatiotemporal information of the pickups distribution. Weather conditions have been added as an additional feature to the dataset. Then, we have made a comparison between naïve prediction approaches and more advanced techniques like gradient boosting and LSTM recurrent neural networks, investigating what could be the advantages of more complex algorithms.