Using real-world patterns to improve matching in theory and practice

This post introduces an Incremental Kuhn-Munkres (IKM) algorithm that significantly improves the performance of the ride-hailing dispatch system. The core innovation is to reduce the computational cost of the assignment problem by optimizing the computation of the cost matrix. By observing the 'spatial locality of matching' in real-world scenarios, the IKM algorithm computes travel times only when necessary, using a priority queue-based lower-bounding technique. This optimistic, incremental approach avoids computing exact costs for distant driver-passenger pairs, leading to an order of magnitude reduction in running time and a substantial increase in supported throughput compared to traditional KM algorithms. The post also details experimental investigations comparing IKM variants (IKM-DIJK and IKM-GAC) against standard KM algorithms on real-world Singapore road network data, demonstrating the practical effectiveness of the proposed techniques.