Ridesourcing Systems - Simulated Annealing Algorithm for Solving the Matching and Dispatching Problem in Dynamic Large-Scale Settings

Ridesourcing services are gaining gradual hypes with the advancements in mobile internet and technology. The objective of these services is to mainly match and dispatch operating vehicles to waiting requests within a very short duration. The expectations that service users have today are becoming more and more exigent. Potential passengers input their destinations into an application and expect to be matched shortly after. This paves a way for a dynamic denition of the problem with expanding complexity. From an operational point of view, nding an optimal solution for the entire system is nearly impossible because of the continuous arrival of requests. In fact, vehicles in a network usually roam around until being directed towards a pickup location. These purposeless movements however may have signicant impacts on the trac, particularly in urban spaces. Furthermore, empty vehicle kilometers have a considerable environmental cost without serving a particular purpose. In this report, we suggest a simulated annealing for solving the dynamic matching assignment problem all while accounting for the previously stated issues. Our objective is to maximize eet utilization and service level, and minimizing the waiting time of requests. Constant reoptimization runs are performed to accommodate requests that arrive over time. Compared to the more standard nearest available vehicle assignments, the method provided showed an increase in eet utilization and a decrease in the abandonment rate. i