出租車線上打車平臺調度算法分析研究

姜安華 胡加德

摘 要：本文參考市面上主流的線上打車平臺，結合貴州省實際的業務模式和市場需求，針對線上打車平臺的調度算法進行分析研究。在整個分析過程中，主要從業務的類型劃分、對象的狀態轉換、調度總體流程和具體的推送規則幾個方面依次進行展開，對每一個環節進行了簡單的梳理與分析。

關鍵詞：出租車 調度算法 平臺

隨著城市的發展，人們的出行需求越來越旺盛，生活節奏越來越快，傳統的道路運輸模式已經不能完全滿足市場對用戶的出行需求，因此，市面上出現了許多的線上打車平臺，在提升用戶出行效率的同時，為傳統運輸企業提供高效的信息管理手段。

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）.

貴州省交通運輸廳科技項目