哈啰兩輪車調度算法介紹

調度是將稀缺資源分配到一定時間內的不同任務上的決策過程，目的是優化一個或多個目標。兩輪車調度場景是指通過預測未來用戶的騎行需求，決定各站點車輛的調配任務，并將這些任務分配給合適的運維人員來執行，從而滿足用戶的騎行需求。在這個調度場景里會涉及三個對象，一是車輛，目標是用戶需求滿足率高，移車成本低，車輛翻臺高。二是運維，目標是運維效率高，運維人員體驗好。三是用戶，目標是用戶體驗好。

我們將兩輪車調度和外賣/網約車調度做對比，調度涉及到任務生成、任務派發和履約管控三個環節。在任務生成環節，兩輪車調度的復雜度比外賣/網約車調度高，原因在于調度涉及到三個要素，調度算法觸發的時機需要依托算法來決策，同時需要兼顧線下各種復雜的情況，如天氣季節因素，競對或城管干預等。在任務派發環節，兩輪車調度的復雜度比外賣/網約車調度低，原因在于需要匹配的對象少，實時性要求低。在履約管控環節，兩輪車調度的復雜度比外賣/網約車調度高，原因在于司機運維執行結果難以監管，而外賣/網約車有用戶評價體系，監管便捷。

兩輪車調度的難度是多維且立體的，一是定位不準，不同車輛型號定位的精準度是有差異的；二是車輛分散，司機需要去收集散落在各地的車輛；三是需求波動，如季節性的波動、早晚高峰的波動；四是供需失衡，實際投放的車輛數量與用戶日益增長的需求匹配不上；五是城市差異，由于城市發展階段和管控政策不同，會導致車輛投放與用戶需求的差異；六是算法黑盒，會導致算法效果評估比較模糊；七是信息孤島，如司機的載具在某個時刻可能會發生變化，但這些信息并不能及時同步到上層用于算法決策；八是計算復雜，一系列復雜的場景會導致算法的計算復雜度大增。

兩輪車調度算法的目標總結下來是多快好省。一是多，我們希望算法調度占比高，覆蓋的場景多，支持個性化。二是快，能夠實時生成、實時派發、實時執行、實時反饋。三是好，我們希望讓業務叫好，讓司機叫好。四是省，既能省人工成本，又能省機器成本。

為了達成目標，我們制定了解決方案，左側是我們解決方案的架構分層圖。我們根據多快好省四個分類，推出了對應的解決措施。一是多，我們提供了站點組的調度策略，千城千策，調度場景覆蓋廣。二是快，我們將需求預測、任務派發與任務決策實時化，并通過路徑規劃找出最優路線。三是好，我們通過全局匹配來實現最優化，任務聚合來實現效果好，收益預估來提高收益，精益管理來提高管理效率。四是省，我們利用彈性計算、MR調度框架和調度波動預警，提高機器整體的資源利用率。

調度算法在效果評測上的挑戰

調度算法效果評測上有五個挑戰，一是效率低，一個迭代平均效果評估回收時間需要兩周左右。二是不受控，我們無法控制線下運維的執行情況。三是干擾多，線下執行受到的干擾因素多，效果回收準確度低，導致收益和算法歸因模糊。四是質量差，模型上線試驗后，效果回收正向率低。五是公信力弱，由于線上效果差，合作方對模型效果信任度低。

調度算法仿真系統介紹

為了解決這個挑戰，我們提出了仿真系統，通過對物理世界的仿真，達成調度算法離線驗證和預測推演的能力。仿真邏輯如圖所示，我們可以通過感知建模，對物理世界里的場景屬性及行為，轉換成特征和模型，其中特征是用來表達物理世界場景屬性的數字化信息，而行為、規則用模型來表達。有了特征和模型后，我們可以使用工程技術手段把它演化成仿真世界里的場景、屬性、行為和規則。如何做到仿真世界的實現，我們提出了三個層面，分別是特征數據、仿真模型和工程支撐。 特征數據

在物理世界中會存在各種各樣的信息，如站點信息、車輛信息、用戶騎行事件、調度事件、日期天氣特征，訂單、收益等。我們將其歸納成五個維度，站點數據、車輛數據、運力數據、外部數據和評估指標。 一是站點數據特征，包括站點基礎信息、站點間流轉訂單、站點實時停駐車輛數、站點歷史需求量和站點間騎行時間。二是車輛數據，包括車輛基礎信息、車輛實時標簽狀態、車輛實時電量、車輛健康度和用戶騎行收益。三是運力數據，包括司機畫像、載具畫像、載具實時數據、司機實時排班和運力成本。四是外部數據特征，包括節假日數據、天氣特征、競對實時數據、地圖數據和城管干預。五是評估指標，如缺車數據、訂單數據、調度量、翻臺數據和車輛收益。

仿真模型

仿真模型是對物理世界行為或規則的模擬，主要會涉及到兩部分。一是自然流轉，指車輛在物理世界自然流動的情況，我們需要把它模擬出來。二是模型輸入，指仿真世界里的一些實時數據，我們需要提供給調度算法去作為輸入數據，如供需上需要預測的數據或運力的模擬數據。

接下來介紹車輛自然流轉的仿真實現，車輛自然流轉指在某一時刻某一有限空間下，車輛在不同站點之間流動的情況。如圖是某一時刻，車輛在不同站點之間流動的軌跡。我們進行公式提煉，假設某個站點Sa在某一時刻流出的車輛總數是O，流向各個站點的概率為（Si，Pi）。我們就可以知道站點Sa流向站點Sb的車輛情況，或者是站點Sa流向站點Sc的車輛情況，通過這個計算公式就可以得出來。

第一步我們要計算某一時刻站點流出的車輛數，會用到三個維度的特征數據，一是站點數據，包括站點基礎信息、站點實時車輛數、站點歷史需求和站點間車輛騎行時長。二是車輛數據，包括車輛實時電量和車輛實時標簽。三是外部數據，包括節假日數據和天氣特征。我們的篩選條件有兩個，一是可用日期的篩選，我們取歷史一個月內相同日期特征的數據，如是否節假日、天氣因素相似。二是站點內可用車輛的數據，這里需要剔除異常車輛，如故障車和低電車。舉個例子，我們要計算2月28日0點10分的站點車輛流出數據，會獲取歷史一個月內同樣是0點10分的所有站點數據，根據可用日期作為篩選條件，把相同日期特征的站點數據篩選出來，匯總取平均值。有了平均站點車輛數后，我們還要去看站點內的可用車的情況。如果可用車輛數大于計算出來站點的出站數，就取出站數；如果可用車輛數小于出站數，就取站內可用車輛數。

第二步我們要計算某一時刻站點間轉移概率，會用到兩個維度的特征數據。一是站點數據，包括站點間流轉訂單、站點間車輛騎行時長。二是外部數據，包括節假日數據和天氣特征。它是一個統計問題，又因為物理世界中會存在某種意外概率的事件，為了能夠模擬這些意外概率的事件，我們加入輪盤賭選擇法，來使我們仿真的結果更貼近于物理世界。統計方式有些類似，都是取一個月內相同日期特征，計算不同站點之間流轉概率的平均匯總。

第三步是結合流出車輛數據和站點間流轉概率，模擬特定時刻站點間車輛流轉情況。如圖所示，0點10分站點A流出10輛車，結合流轉概率，我們可以得出站點A會往B流出5輛車，站點A會往C流出3輛車，站點A會往D流出2輛車，同樣其他站點用類似的計算方式會得出流轉方式。 仿真會帶來一些優勢：

能夠修正錯誤，特定日期可能會有異常，如某個站點當日流出5輛車，并不代表它的真實需求是5輛車，可能是因為這個站點內只有5輛車，所以只能最多流出5輛車。我們有歷史數據作為依據，可以修正異常值。

降低偶然性，如某些站點某一時刻會由于熱點事件，如臺風天氣或演唱會舉辦等事件帶來需求的波動，并不代表普遍的效果。

介紹完車輛自然流轉模擬，這里有個問題，什么結果是好的仿真結果？于是就有了逼真度的概念。逼真度是用來量化仿真系統的一種途徑，在一定程度上能夠體現出仿真系統的正確性和可信度。而只有保證仿真系統的正確性和可信度，仿真結果才具有實際應用價值。

第一個維度是數據源和建模，我們假設數據源選取某城市、某日期，計算每個站點在每個時刻的真實流出，計算每個站點在每個時刻的仿真流出。我們會做兩個維度的建模，站點維度和時間維度。站點維度建模是指我們按照真實流出和仿真流出兩個指標，匯總出每一個站點在所有時刻的總流出并排序，會得到站點維度的真實排序和站點維度的仿真排序。時間維度建模是匯總每個小時在這個城市所有站點的總流出并按時間排序，得出時間維度的真實排序和時間維度的仿真排序。

這里我們評估逼真度，借鑒了偽時間排序分數POS算法，設計仿真流轉排序相似性算法。舉個例子，如圖是時間維度的排序，我們看到按照相似性算法，真實流出在0-1時是遞減的，所以我們用“-”，0-2時是遞增的，所以我們用“+”。仿真流出數據也按照這個邏輯。我們會發現0-2時真實流出和仿真流出不一致，因此我們得出排序相似性是83%。

依據這樣的計算方式，我們對某個城市某一時刻的數據做逼真度的分析，會得出兩個結果。時間維度上站點每小時的真實流出與仿真流出，在24小時的排序相似度達到93%；站點維度上排序相似度達到85%。因此我們得出，真實流出跟仿真流出的數據具有高度的相似性。 工程支撐

工程支撐主要借助工程的能力，融合特征和模型去實現仿真世界的演化。這里會用到很多的技術能力，如地圖引擎、服務調度、報表分析、過程回放和數倉數據計算。我們將其歸納成三個維度，包括數據計算、調度中臺和前端效果。

仿真數據具有三大特點：

數據量大，哈啰單車和助力車覆蓋近千個城市，近百萬站點，近千萬輛車，有上億的訂單和IOT數據上報。

數據結構復雜，數據來源多樣性，導致結構化數據、非結構化數據、半結構化數據都混合在一起。

計算粒度細、周期長，如果在仿真的時候去臨時計算，成本會非常高，因此我們借助了數倉的離線計算能力，提高效率。

如圖是實驗創建執行流程，以此介紹調度中臺的工作過程。首先是用戶在前端創建實驗，調度中臺通過實驗創建環節，會把用戶創建實驗的配置信息、城市、模型信息存儲到在線存儲里去。如果用戶在前端進行實驗執行的操作，調度中臺通過實驗調度的環節，根據之前配置的信息，整合相關的特征數據的集合，包括實驗周期的約束條件，傳遞給仿真算法，這是異步的過程。數據傳遞過去后，仿真算法會根據粒度和周期去調用在線和離線數據作為模型入參，執行算法決策。 在周期執行過程中，算法會把過程記錄通過消息的方式實時反饋給調度中臺，調度中臺會把這些數據進行過程指標的計算，并把過程結果和指標結果落庫到在線存儲里去。前端就可以實時查看實驗的過程，對實驗的過程進行操作干預。仿真算法執行完成后，調度中臺會對整個實驗數據做存儲和規格化的處理，能夠給前端提供過程回放和實驗數據的展現，這是整個的實驗流程。

仿真系統是我們算法測試平臺的一個子服務，平臺還涵蓋數據質量監控、服務可用性監測、模型性能評測、模型效果評測、語音識別評測、文本識別評測和圖像識別評測。 算法測試平臺采用微服務的設計思路，最外層有web服務層，對接所有的上游前端業務，底層可分為四大中心：

調度中心（負責所有管理行為，如數據調度，任務管理，策略管理，告警管理，計算調度等）

數據計算中心（負責所有計算行為，如實時&離線數據計算，數據轉換，數據訂正等）

數據分析統計中心（負責指標統計類行為，因為指標計算規則變化頻繁且靈活多樣，因此在該中心下連接多個腳本環境容器，如python，groovy等，通過平臺在線編輯能力，允許用戶靈活調整，隨時變更指標分析與統計腳本）

數據中心（負責所有內外部數據訪問收口及三方服務訪問收口，并通過提高該服務的應用等級，保障整個系統的穩定性）。

它們各司其職，保證協作的穩定性和迭代開發的效率。

前端效果總覽包括實驗的管理、仿真過程回放和各項指標評測結果：

仿真實驗室，作為仿真系統的入口，提供了實驗創建、篩選和實驗過程管控。

實驗配置，可以去設置實驗相關的參數，如仿真區域、時間區間、時間粒度等。

仿真回放，我們嵌入了地圖的渲染引擎，提供觀測不同模型的車輛流轉效果和數據變化過程的能力。

實驗報告，提供各項評估指標數據、報表化展示、交叉對比驗證的能力。

收益和展望

仿真系統的收益歸納起來有六點：

城市覆蓋，原先城市覆蓋的數量有限且成本高，仿真系統可以支持全國400多個城市的任意選擇。

評估效率，原先評估效率是周級別，仿真系統評估效率是小時級別。

線上質量，原先線上回收正向率低，仿真系統線上回收正向率預計提高兩倍。

評估指標，原先評估指標比較簡單，回收也相對麻煩，仿真系統可以定制多維度的指標。

干擾因素，原先有很多不可控因素，仿真系統干擾項都是可感知可控制的。

過程分析，原先過程變化是看不到的，仿真系統過程可回放、可分析。

當前我們是在平臺化階段，依托仿真平臺化建設，實現車輛調度類算法評測賦能，帶來六大收益。后面我們希望能夠實現場景化，借助場景化建模，實現業務場景無感接入，靈活擴展。第三個階段是智能化仿真世界，我們希望能夠實現智能感知特征數據、自主學習規則模型、智能分析評測效果。最后是業務賦能，我們希望能夠賦能更多的業務場景，去實現線下的推演和可行性的驗證，助力業務的高速增長。

編輯：黃飛