A Parallel Simulated Annealing Enhancement of the Optimal-Matching Heuristic for Ridesharing

In this paper, we develop an efficient parallelheuristic method for solving the global optimization problemassociated with the ridesharing system. Based on the carefullyformalized problem and objective function, we fully utilize theheuristic characteristics of the algorithm for handling the real-lifeconstraints in ridesharing. Following the principles of simulatedannealing, our method is adaptive in handling the matchingand route optimization tasks. We develop an efficient parallelscheme with simulated annealing, named PCSA, for solving theglobal optimization problem for ridesharing. Our algorithm iscapable to efficiently address the potential of ridesharing byexploiting the mobility information of the ride requests. Basedon extensive experiments on large real-world data, we validatethe performance of our parallel heuristic algorithm. Our resultsconfirm the effectiveness and efficiency of the proposed methodand its superiority over all other benchmarks.