实时拼车系统中的贪婪式自动匹配算法

摘要

为解决一对多的实时拼车匹配问题,提出了一种新的贪婪式自动匹配算法.算法对每条车与乘客相连的边,利用桶排序算法根据其权值进行降序排序,然后根据车辆的空座数量,构造临时分配图.同时,为保证每位乘客只能搭乘一辆车,在临时分配图中删除与乘客相连的多余的边.算法通过反复构造临时分配图进行车辆与乘客的匹配,直到不能为乘客分配空座或者所有乘客分配了空座为止.仿真结果表明,该算法具有运行时间低、成功匹配率高等特点.