A Heuristic Approach to Optimal Meeting Points in Multi-modal Ride-Sharing Networks
摘要
This paper addresses the challenge of determining an equitable meeting point for carpooling participants, ensuring that both walkers and drivers have equivalent travel times. The proposed solution automatically generates a fair meeting point in real time. The paper first reviews the current state of the art in this domain, then provides a formal problem definition. We present both an exact solution and a heuristic algorithm, which includes an efficient technique for pruning a multi-modal road network. The two methods are then compared in terms of execution time and solution quality. Additionally, we explore the impact of various algorithmic parameters on performance. Finally, both algorithms were tested under extreme conditions on the entire road network of Belgium to assess their scalability and robustness. The paper concludes by outlining potential directions for future research.