哈啰兩輪車調(diào)度算法介紹

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

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

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

兩輪車調(diào)度算法的目標(biāo)總結(jié)下來是多快好省。一是多，我們希望算法調(diào)度占比高，覆蓋的場景多，支持個性化。二是快，能夠?qū)崟r生成、實時派發(fā)、實時執(zhí)行、實時反饋。三是好，我們希望讓業(yè)務(wù)叫好，讓司機叫好。四是省，既能省人工成本，又能省機器成本。

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

調(diào)度算法在效果評測上的挑戰(zhàn)

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

調(diào)度算法仿真系統(tǒng)介紹

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

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

仿真模型

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

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

第一步我們要計算某一時刻站點流出的車輛數(shù)，會用到三個維度的特征數(shù)據(jù)，一是站點數(shù)據(jù)，包括站點基礎(chǔ)信息、站點實時車輛數(shù)、站點歷史需求和站點間車輛騎行時長。二是車輛數(shù)據(jù)，包括車輛實時電量和車輛實時標(biāo)簽。三是外部數(shù)據(jù)，包括節(jié)假日數(shù)據(jù)和天氣特征。我們的篩選條件有兩個，一是可用日期的篩選，我們?nèi)v史一個月內(nèi)相同日期特征的數(shù)據(jù)，如是否節(jié)假日、天氣因素相似。二是站點內(nèi)可用車輛的數(shù)據(jù)，這里需要剔除異常車輛，如故障車和低電車。舉個例子，我們要計算2月28日0點10分的站點車輛流出數(shù)據(jù)，會獲取歷史一個月內(nèi)同樣是0點10分的所有站點數(shù)據(jù)，根據(jù)可用日期作為篩選條件，把相同日期特征的站點數(shù)據(jù)篩選出來，匯總?cè)∑骄怠Ｓ辛似骄军c車輛數(shù)后，我們還要去看站點內(nèi)的可用車的情況。如果可用車輛數(shù)大于計算出來站點的出站數(shù)，就取出站數(shù)；如果可用車輛數(shù)小于出站數(shù)，就取站內(nèi)可用車輛數(shù)。

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

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

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

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

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

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

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

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

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

仿真數(shù)據(jù)具有三大特點：

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

數(shù)據(jù)結(jié)構(gòu)復(fù)雜，數(shù)據(jù)來源多樣性，導(dǎo)致結(jié)構(gòu)化數(shù)據(jù)、非結(jié)構(gòu)化數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)都混合在一起。

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

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

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

調(diào)度中心（負責(zé)所有管理行為，如數(shù)據(jù)調(diào)度，任務(wù)管理，策略管理，告警管理，計算調(diào)度等）

數(shù)據(jù)計算中心（負責(zé)所有計算行為，如實時&離線數(shù)據(jù)計算，數(shù)據(jù)轉(zhuǎn)換，數(shù)據(jù)訂正等）

數(shù)據(jù)分析統(tǒng)計中心（負責(zé)指標(biāo)統(tǒng)計類行為，因為指標(biāo)計算規(guī)則變化頻繁且靈活多樣，因此在該中心下連接多個腳本環(huán)境容器，如python，groovy等，通過平臺在線編輯能力，允許用戶靈活調(diào)整，隨時變更指標(biāo)分析與統(tǒng)計腳本）

數(shù)據(jù)中心（負責(zé)所有內(nèi)外部數(shù)據(jù)訪問收口及三方服務(wù)訪問收口，并通過提高該服務(wù)的應(yīng)用等級，保障整個系統(tǒng)的穩(wěn)定性）。

它們各司其職，保證協(xié)作的穩(wěn)定性和迭代開發(fā)的效率。

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

仿真實驗室，作為仿真系統(tǒng)的入口，提供了實驗創(chuàng)建、篩選和實驗過程管控。

實驗配置，可以去設(shè)置實驗相關(guān)的參數(shù)，如仿真區(qū)域、時間區(qū)間、時間粒度等。

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

實驗報告，提供各項評估指標(biāo)數(shù)據(jù)、報表化展示、交叉對比驗證的能力。

收益和展望

仿真系統(tǒng)的收益歸納起來有六點：

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

評估效率，原先評估效率是周級別，仿真系統(tǒng)評估效率是小時級別。

線上質(zhì)量，原先線上回收正向率低，仿真系統(tǒng)線上回收正向率預(yù)計提高兩倍。

評估指標(biāo)，原先評估指標(biāo)比較簡單，回收也相對麻煩，仿真系統(tǒng)可以定制多維度的指標(biāo)。

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

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

當(dāng)前我們是在平臺化階段，依托仿真平臺化建設(shè)，實現(xiàn)車輛調(diào)度類算法評測賦能，帶來六大收益。后面我們希望能夠?qū)崿F(xiàn)場景化，借助場景化建模，實現(xiàn)業(yè)務(wù)場景無感接入，靈活擴展。第三個階段是智能化仿真世界，我們希望能夠?qū)崿F(xiàn)智能感知特征數(shù)據(jù)、自主學(xué)習(xí)規(guī)則模型、智能分析評測效果。最后是業(yè)務(wù)賦能，我們希望能夠賦能更多的業(yè)務(wù)場景，去實現(xiàn)線下的推演和可行性的驗證，助力業(yè)務(wù)的高速增長。

編輯：黃飛