...SDPA流媒体调度算法分析研究.pdf
姜安华 胡加德
摘 要：本文参考市面上主流的线上打车平台，结合贵州省实际的业务模式和市场需求，针对线上打车平台的调度算法进行分析研究。在整个分析过程中，主要从业务的类型划分、对象的状态转换、调度总体流程和具体的推送规则几个方面依次进行展开，对每一个环节进行了简单的梳理与分析。
关键词：出租车 调度算法 平台
随着城市的发展，人们的出行需求越来越旺盛，生活节奏越来越快，传统的道路运输模式已经不能完全满足市场对用户的出行需求，因此，市面上出现了许多的线上打车平台，在提升用户出行效率的同时，为传统运输企业提供高效的信息管理手段。
1.业务类型划分
线上打车业务一般分为三类，实时打车、预约打车和实时拼车业务。实时打车业务就是乘客通过打车平台发起实时订单，平台驾驶员接到该订单后，立即前往乘客位置接送乘客，在整个过程中只为该乘客提供出行服务；实时拼车业务是根据实际的市场需求，为了最大化的提高车辆的利用率和解决乘客出行难的问题而产生的，拼客的组数一般由平台根据地区的实际情况进行设置；预约打车业务就是乘客提前做好出行规划，设置好出行的时间，并在平台上提交预约订单，驾驶员接单后按照乘客实际出行时间准时到达指定位置对乘客进行服务[1]。
2.驾驶员状态划分
在平台运行的整个程中，将驾驶员的状态划分为离线、空闲和忙碌三种状态。其中离线状态表示当前驾驶员未在平台上线或者上线了但是未处于听单状态，平台在调度乘客订单的时候将不给这类驾驶员进行推送；忙碌状态表示驾驶员当前处于听单状态，但是有未处理完成的任务，平台在调度新订单的时候也不给这类驾驶员进行推送；空闲状态表示驾驶员当前处于听单状态，并且当前没有未处理完成的相关任务，平台在对新订单进行调度的时候就调度该类驾驶员。
3.订单调度状态及调度权值
对于在平台中产生的订单，将订单调度状态划分为待调度、已推送、调度超时、用户取消、调度完成五个状态。当乘客发起一个订单请求时，系统将该订单置为待调度状态，等待调度系统进行调度；当调度系统将该订单推送出去以后，将其状态置为已推送状态；如果被驾驶员接单，该订单的调度状态置为调度完成；如果该订单在调度过程中被乘客取消，将该订单的调度状态置为用户取消；系统推送之后，如果在规定的时间内没有任何驾驶员接收该订单并且乘客也未取消，超过时间后将该订单调度状态置为调度超时，调度超时给乘客进行反馈，乘客可以根据系统提示进行相关操作。
为了体现出订单的调度优先级，为每个订单设置一个权值，初始订单权值为零。当订单被调度系统推送出去1次后，将该订单的调度权值进行加1，权值越高的订单推送的优先级越高，通过权值也能监控调度系统的调度效率。
驾驶员及订单的状态转换如图1所示。
4.订单调度流程
乘客提交一个新的订单请求，首先将该订单放入到新订单队列中，按照订单的提交时间进行排列，调度系统从新订单队列中依次取出订单进行调度。为了保障系统的稳定，需要对同时调度的订单数量进行控制，如最大限制100，當调度中的订单数量小于100的时候，就从队列中取出订单进行调度；当调度订单数量大于或等于100的时候，就待有订单调度完成后再取出队列中的订单进行调度。为了避免同一个订单在调度系统中进行无限循环调度，调度系统设置一个调度临界值，当某个订单调度失败后，判定该订单的权值是否超过平台设置的调度临界值。如果平台设置的调度临界值为3，当权值小于3时，该订单权值加1，同时将该订单放入历史待调度订单列表中；当权值大于或等于3时，给用户进行反馈，由用户选择继续等待或者取消；当用户选择继续等待后，将该订单的权值进行初始化，重新放入历史待调度订单列表；如果用户选择的次数大于两次，就将该订单结束，乘客选择后系统为其重新创建一个新的订单，再按照订单调度流程进行调度，具体的调度流程如图2所示。
5.调度系统推送规则
当用户发起一个订单后，订单通过调度流程进入到调度系统中，调度系统根据订单的具体信息以及周边驾驶员的情况和平台规则进行具体调度。
调度系统要准确的对订单进行推送，首先需要获取到调度订单的乘客起点坐标以及订单的类型，如实时普通订单、实时拼车订单或预约订单。对于实时拼车订单，还需要获取到订单的出行人数。
订单的信息获取到了，需要将该订单推送给符合规则的驾驶员。首先通过该订单的起点坐标和推送距离获取到附近所有有效的驾驶员（状态为空闲、未进入黑名单、已通过审核等）列表，并将该批驾驶员的状态置为忙碌状态。然后分别计算订单起点与每个驾驶员之间的距离（这里采用直线距离），并与驾驶员的偏好设置进行比对，当计算出的直线距离大于驾驶员设置的接单范围时，将该驾驶员置为空闲状态，并移除当前列表，待其他订单进行调度；当计算出的直线距离小于或等于驾驶员设置的接单范围时，将该驾驶员保留，等待下一步处理。距离过滤完成之后，将只听收车订单且不顺路（通过计算路径的重合度来进行判断[2]）的驾驶员移除掉，最后提按照距离从小到大的顺序进行排列，取出前十个驾驶员进行推送，其他驾驶员置为空闲状态，待其他订单调度。
驾驶员收到推送订单后，可以选择接受与拒绝。当驾驶员选择拒绝后，将该驾驶员状态置为空闲状态，待其他订单调度；当驾驶员选择接受之后，调度系统给其他被该订单锁定的驾驶员推送订单被接单消息，同时将这些驾驶员状态置为空闲状态，待其他订单调度；在订单被推送出去后，如果乘客发起了取消请求，调度系统给该被该订单锁定的驾驶员推送订单取消消息，同时将这些驾驶员状态置为空闲状态， 待其他订单调度。接单成功的驾驶员当任务完成后，该驾驶员状态转为空闲状态，可以被其他订单调度。
对于实时拼车订单的调度，在实时普通订单调度的算法之上，需要增加判断每个驾驶员目前的拼单数量以及目前的空位数与订单的人数，另外对于拼单，还需要计算拼单之间的顺路程度。
对于预约订单的调度，因为不需要司机立即去接送，因此推送的的范围可以按城市或行政区域来划分[3]。
6.结论
调度算法作为线上打车平台的核心内容，调度流程及推送规则的制定直接关系到整个平台的调度效率，也是衡量一个平台优劣的指标。本文通过对平台的业务类型、业务对象的分析，梳理出了打车平台调度总体流程以及具体推送规则的制定方式，可通过该思路完成相应的调度算法的实现。
参考文献：
[1] 翟思宇，刘洋，郭煜杰. “互联网+”时代的出租车资源配置[J]. 南京：中国人民解放军理工大学，2017（03）.
[2] 林基艳，张雅琼，张慧. 基于出租车GPS 轨迹数据挖掘的居民出行特征研究[J]. 陕西： 榆林学院信息工程学院，2017（5）.
[3] 金通，朱晓艳，郑凌浩. “互联网+”下的出租车： 市场演化与嵌入式监管[J]. 浙江： 浙江财经大学经济学院，2017（10）.
贵州省交通运输厅科技项目
