Heuristic algorithm for multi-vehicle ride matching problem

Multi-vehicle ride matching problem studies how to take passengers as much as possible through optimizing vehicles´ route and matching between vehicles and passengers. But at present, problems exist in the researches like that models divorced from reality and low efficiency of algorithms. For this problem, this paper presents a solution based on clustering of vehicles´ route order. Transferring the MRMP to RMP through clustering of vehicles´ route order, it forms the first matching result between vehicles and passengers. And looking for the best sort order through sorting the first matching result making use of priori clustering. At last, we optimize the solution one times more through optimized rules. Experimental result shows that, the method based on clustering of vehicles´ route order can solve the problem with high matching efficiency and low cost.