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

Online Dispatch Algorithm for Online Car-hailing Based on Uncertainty

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

In order to quickly and accurately complete the matching between online car hailing and passengers,to meet the needs of passengers to the greatest extent and improve passenger satisfaction,the mature online model and algorithm will be applied in parallel machine scheduling to study the online car hailing dispatch problem,and the online competition strategy is used to solve the online car hailing dispatch problem under uncertainty.Firstly,considering that both the passenger's order time and the driver's online time are uncertain,and the vehicle's service radius will also have an impact on the order dispatch,this paper analyzes the online order dispatching scheme of online car hailing under different passenger carrying conditions when there are passengers placing orders.Secondly,the competition ratio is calculated by using the online algorithm to be(2m–1)/(m+1),m is the number of vehicles in passenger mode,which indicates that the competitive algorithm is suitable for large-scale dispatching of online car hailing.Finally,the matching between 20 passengers and 20 drivers is taken as an example to verify the feasibility of the algorithm.