基于不确定性的网约车在线派单算法

摘要

为快速而精准完成网约车与乘客之间的匹配,最大程度满足乘客需求,提高乘客满意度,引入了在并行机器调度中已应用成熟的在线算法来进行网约车派单问题的研究,利用在线竞争策略来解决不确定情形下的网约车派单问题.首先,由于乘客的下单时间与司机的在线时间都是不确定的,且车辆服务半径对派单也会有影响,故分析当乘客发出订单时,网约车在不同载客情况下的在线派单方案;其次,利用在线算法计算出其竞争比为(2m-1)/(m+1)(其中,m为处于载客状态的车辆数),说明竞争算法适用于网约车的大规模派单计算问题;最后,以20名乘客与20名司机之间的匹配为例验证该算法的可行性.