真實場景，數據量大：歷史數據包含西南某省會城市一個月時間內幾百個 G 的數據記錄；線上亦基於若干天的真實數據來評測；
因素多：影響司機收益的因素很多，如接駕距離、天氣、路況信息、出行時間等，需要考慮複雜的環境因素；
實時性：在一天內，算法每 2 秒被調用一次，必須 2 秒內做出分配，且訂單和司機信息每次不同，不能預分配；
調參難：官方並未提供模擬器，且已有數據不足以在線下搭建出高質量的模擬器，需要開發的算法具有較強的魯棒性。
為了最大化平臺上所有司機日均收入，在計算每個訂單的收益時，採用基於強化學習的方法，不僅能考慮當前時刻的收入，還能兼顧未來可能的收益。同時，結合剪枝與 C++ 實現的高效二分圖匹配算法，能夠在 2 秒的時限內，及時找到合適的訂單分配方案，從而取得了更好的效果。代碼地址：https://github.com/maybeluo/KDDCup2020-RL-1st-solution本賽題的優化目標是最大化平臺上司機一天內的平均總收益，因此在派單時，不僅要考慮最大化當前時間窗的收益，還必須考慮未來的可能收益。同時，當前的訂單分配會影響車輛的位置和收益，對未來產生影響，是一個序列決策問題，因此考慮通過強化學習解決。此情景下，環境 (Environment) 包括訂單、司機車輛信息位置等，而參賽者需要定義智能體 (Agent)的學習和預測策略，以最大化司機的收益。本問題中司機和車輛一一對應，下文中如未特殊強調，車輛和司機含義一般可以互換。狀態 (State)、動作(Action) 和獎勵 (Reward) 設計如下：聯合團隊使用車輛的地理坐標經過離散化後對應的 ID，來表示車輛的狀態，而不考慮時間因素。具體的，團隊同時使用了多種離散化策略，使得每個地理坐標，對應多個不同粒度的狀態，如主辦方提供的六邊形格子劃分策略，還可以是多種不同大小的四邊形等。如下圖所示，對於圖中的坐標點（紅色圓點），離散化後，可以同時採用六邊形、不同大小的四邊形來標識該點對應的狀態。智能體執行派單程序後，會生成司機和訂單的匹配列表。在不考慮取消訂單的情況下，成功匹配的司機將會進入服務 (serving) 狀態: 司機會到達指定上車點，接到乘客，並運送到指定下車點，拿到相應的獎勵。而未能分配到訂單的司機，將會閒置(idle)，不能拿到任何收益。每次派單成功後，司機會拿到相應訂單的收益，作為本次動作的獎勵。本次比賽的目標，即是最大化所有司機的平均收益。每次智能體被調用時，將接收到當前所有的候選訂單信息，並在 2 秒內做出司機和乘客的匹配。候選信息列表是候選訂單的集合，每個候選訂單主要包含如下信息：oorder_id 和 driver_id: 訂單 ID 和司機 ID，用來唯一標識候選訂單和司機；
odriver_location: 司機在當前時刻所處的地理位置，本次比賽中地理位置信息均採用經緯度對來表示；該信息信息經過離散化後，得到訂單的起始狀態標識；
oorder_finish_location：訂單結束位置，即訂單的目的地；該信息經過離散化後，得到訂單的終點狀態標識；
oduration：訂單的預估時長；
oreward：訂單帶來的收益。
此外，還有當前時刻信息、訂單起始位置（order_start_location）、接駕距離（司機和乘客的距離 order_driver_distance）、預估接駕時長（pick_up_eta）等，可以根據此類信息推斷訂單取消概率。本方案整體策略為通過時序差分算法（Temporal Difference）學習狀態值，並通過二分圖匹配算法最大化收益。具體的，智能體接受到候選訂單列表後，將依次執行以下三個步驟：1) 構圖：通過候選訂單信息，將司機和乘客建模成二分圖；並根據起止點對應的狀態，計算邊權；
2) 匹配：通過二分圖匹配算法，將司機和乘客匹配，並派單；
3) 更新：根據匹配結果，通過時序差分算法的學習規則，更新涉及到的狀態對應的值。
下面詳細介紹每個步驟。
本文將訂單 ID 和司機 ID 作為圖的頂點，並根據候選訂單信息，連接相應的訂單和司機，得到對應的圖。因為訂單之間、司機之間均不存在連接關係，因此該圖是二分圖。另外，為了保證更快的得到匹配效果，加速後續匹配算法，將二分圖按如下策略剪枝：對於每個訂單，只保留接駕距離最小 K 個司機對應的邊；在比賽中，K 取 11。不妨將司機位置（driver_location）和訂單終點（order_finish_location）對應的狀態分別記為 S 和 S^'，其對應的狀態值分別為 V(S) 和 V(S^') ，則二分圖中的邊權 w 計算方式為：其中，R 為訂單對應的收益，t 為離散化後的訂單時長，為折扣因子， p 為訂單的取消概率。訂單取消概率和接駕距離、接駕時長等有關，可以通過對官方提供的歷史數據中訂單取消概率建模，得到對應的訂單取消概率預測模型，以便線上推斷每個訂單的取消概率。構圖完成後，得到剪枝後的二分圖以及每條邊的權重，可以直接利用匈牙利算法進行匹配。在實際使用時，團隊發現 Scipy 提供的對應算法接口 (https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html) 效率較低，導致超時（不能在 2 秒的時間窗內做出匹配）。如果直接使用貪心算法（完全貪心或- greedy）分配訂單，則效果不佳。另外，司機和乘客數量一般不等，導致圖中二分圖頂點數目不均衡。綜合以上因素，我們使用 C++ 實現了高效的匈牙利算法（hungarian algorithm），並編譯成對應的 so 文件，通過 Python 直接調用，以解決容易超時的問題。當訂單分配完成後，需要根據分配的結果更新對應的狀態值。因官方未提供比賽環境對應的模擬器，不能線下調參，因此選擇從簡單模型入手。我們選取了單步在線策略更新的 SARSA 算法（state–action–reward–state–action）。對於每個訂單的起點和終點，它們均會同時激活多個不同粒度的狀態表示，記每個坐標位置離散化後的狀態個數為 k。計算得到狀態值後，對起點所對應的各狀態，按照如下公式更新：其中，為學習率。聯合團隊也曾嘗試基於深度強化學習的狀態學習和更新方法，但效果不佳；嘗試基於動態規劃、時序差分等方法，通過歷史數據在線下學習對應狀態值，作為線上狀態的初值，未能取得收益。也嘗試了一系列方法，以降低時序差分單步更新時可能引入的噪音，仍未能取得更好的效果。因此，針對真實場景下的大規模訂單實時分配問題，將強化學習和二分圖匹配算法相結合，在最大化當前收益的同時，能夠有效兼顧未來可能的收益。相比基線模型或其他選手方案，本方案能夠取得更大的收益。Amazon SageMaker 是一項完全託管的服務，可以幫助開發人員和數據科學家快速構建、訓練和部署機器學習 模型。SageMaker完全消除了機器學習過程中每個步驟的繁重工作，讓開發高質量模型變得更加輕鬆。
現在，企業開發者可以免費領取1000元服務抵扣券，輕鬆上手Amazon SageMaker，快速體驗5個人工智慧應用實例。
© THE END
轉載請聯繫本公眾號獲得授權
投稿或尋求報導：content@jiqizhixin.com