1 引言

2 業務背景

3 問題模型

4 算法選擇

5 遺傳算法介紹

5.1 遺傳算法原理

5.2 遺傳算法應用

5.3 收斂過程演示

6 總結

       6.1 業務收益

       6.2 技術選型

1.引言

假設有4位上門工程師和24個待派訂單，如何分配訂單，使得：

• 工程師同一時間段只能履約一個訂單，即訂單時間窗口不能重復。
• 工程師通行總通行時間最低。
• 工程師訂單盡量均衡。

如下圖，紅色點為工程師，藍色點為用戶訂單，藍色點上方數字為上門時間，例：14-16表示該訂單履約時間為14點到16點。

圖片

派單之后，每個工程師路線圖：

圖片

每位工程師的訂單數量分配比較均衡，且訂單地理位置集中在工程師服務半徑內，使得通行成本得到控制。

2.業務背景

奢侈品回收業務的初期，上門訂單的派發完全依賴人工。開放的十多個上門城市都是人工規劃路線。

人工派單需要綜合考量多種因素，主要包括：

• 準時履約確保工程師能在每個訂單開始時間前到達，并且訂單結束時，有足夠時間到達下一單。
• 路線最優盡量保證工程師整體的通行成本是最低的。
• 訂單均衡盡量保證工程師分配的訂單數量均衡。

基于上述因素，人工決策和主觀判斷需要反復嘗試、調整派單方案，不僅效率低下，而且容易陷入局部最優，難以實現全局最優的派單方案。

另外，奢侈品上門回收派單方式有兩種：

實時派單通過規則的方式實現，這里不再贅述。接下來，將重點對批量派單進行詳細介紹。

3.問題模型

要通過算法求解最優的派單方案，首先需要確定問題模型，自動派單可以被認為是VRPTW模型（帶時間窗口的車輛路徑問題，VRP變種問題）。

圖片

在VRPTW模型中，約束條件如下：

• 時間窗約束工程師必須在履約時間范圍內到達并完成服務。
• 訂單約束一個工程師可以分配多個訂單，一個訂單只屬于一個工程師。
• 起始約束工程師從起點出發，最終回到起點。
• 順序約束工程師按照訂單的開始時間順序履約。

基于以上約束條件，問題模型的目標是：

• 最低通行成本確保工程師的總體通行成本最小化。
• 訂單均衡均衡分配每位工程師的訂單數量。

解決這類問題的核心是在解空間搜索不同的組合方式，通過嘗試不同組合并打分，可以確定最優或近似最優的派單方案。

4.算法選擇

確定問題模型之后，下一步選擇合適的算法或方案。

圖片

我們分析一下不同算法模型的優劣。

精確算法

• 優勢暴力搜索全量解空間，枚舉所有組合，能得到理論最優解。
• 劣勢計算復雜度指數級增長（NP-Hard問題），m個工程師n個訂單， 時間復雜度為O(mⁿ)。
• 使用場景用于驗證其他算法的有效性。適合小規模訂單派發。

經過實驗，在5名工程師和30個訂單的場景下，即使CPU資源被完全占用，耗時10分鐘，最終也未能搜索到最優解。

近似算法

• 優勢計算速度快，實現簡單。
• 劣勢每次只關注下一單的最優分配，無法關注到整體最優，短視問題導致解的質量差，易陷入局部最優解。
• 使用場景配合其他算法做初始解生成。一般和派單規則結合，適合小規模流式訂單派發。

目前，我們的實時派單功能就是結合近似算法與派單規則的方式實現。

強化學習

• 優勢通過試錯自主學習，獎勵函數反饋不斷優化派單方案。適合高維復雜問題（多目標、多動態約束）。
• 劣勢初期缺乏數據支撐，有冷啟動問題。派單方案解釋性差，對業務來說是”黑盒“。依賴高算力，成本高。
• 使用場景擁有海量的歷史派單數據可用于訓練。適合訂單量級大、實時要求較高、能投入高成本的場景。

美團、Uber等公司實時調度系統采用強化學習。

元啟發式算法

• 優勢既能避免組合爆炸的問題，又能夠全面兼顧全局搜索能力。適合高維復雜問題（多目標、多動態約束）。耗時低，秒級結果輸出。無需高算力。
• 劣勢不一定能搜索到絕對最優解，但能搜索到近似最優解（最優解的95%~100%）。算法參數調優依賴實驗驗證。
• 使用場景不需要追求絕對最優解的組合優化。無需額外成本。

在綜合考慮業務體量與人效成本的情況下，就批量派單方式而言，元啟發式算法是最佳的選擇。

5.遺傳算法介紹

遺傳算法是一種模擬自然選擇和遺傳機制的優化算法。它通過模擬生物進化過程中的選擇、交叉和變異等操作產生子代，逐步淘汰劣勢個體，保留優勢個體。經過多輪迭代和優勝劣汰，最終存活的個體往往是較為優秀的，這些個體即可視為問題的最優解或近似最優解。

5.1 遺傳算法原理

前置

了解染色體中交叉、變異操作。

圖片

• 交叉交叉是指通過將兩個父代個體的部分基因進行交換，生成新的子代個體的過程。
• 變異變異是指通過隨機改變個體基因序列，為種群引入新的多樣性。

交叉和變異操作的核心在于，在保留父代優良基因的基礎上，進一步探索更優的個體。

舉例

為了更好的理解思想，這里舉個淺顯的例子，假設我們要組建一支『閃電小隊』。

圖片

這個簡單案例揭示了遺傳算法的基本原理：通過多代選擇適應度較高的個體，使這些優勢個體在遺傳過程中保留優良基因，并通過交叉、變異等操作產生更加優秀的后代，從而逐步逼近問題的最優解，最終收斂到最優解。

5.2 遺傳算法應用

遺傳算法思想平移到自動派單，該如何設計呢？接下來會重點講解核心步驟：

圖片

初始化種群

首先說明個體和種群的概念和關系。

• 個體一種派單方案被認為是一個個體，例如，有工程師A和B，有訂單1、2、3、4，那么一個個體可以表示為：

工程師A：訂單1、訂單3工程師B：訂單2、訂單4

也可以是：

工程師A：訂單1工程師B：訂單2、訂單3、訂單4

• 種群

若干個個體組成種群。

• 初始化

種群初始化是遺傳算法的首要步驟，核心是生成具有多樣性的初始解集合。

圖片

可以根據問題規模設置種群大小，比如種群大小設置100，即初始化100個個體。

適應度函數

適應度函數是遺傳算法中評估個體優劣的關鍵指標。在自動派單中，我們設計的適應度函數主要優化兩個目標：最短工程師通行時間和最均衡訂單分配。表現越好的個體（派單方案），其適應度評分越高。

歸一化之后的適應度函數：

圖片

• ：當前個體的工程師通行總時間
• ：種群中最大通行總時間
• ：訂單分配均衡性的標準差
• ：成功派單數
• ：訂單總數
• , , 為優化目標權重系數，通過業務訴求和實驗確定具體值。

選擇

在遺傳算法的選擇階段，系統會根據適應度函數評估結果，采用特定的選擇策略從當前種群中篩選出優質個體作為父代。這些被選中的父代個體將通過后續的交叉和變異操作產生新一代子代，從而推動種群向更優解進化。

列舉兩種最常用的選擇策略：

圖片

建議兩種方式組合使用，只選擇精英保留可能會導致“近親繁殖”問題，種群多樣性快速下降，陷入局部最優；只選擇輪盤賭，可能會存在適應度相近時選擇壓力不足。

交叉

交叉是遺傳算法中最關鍵的進化操作，它通過模擬生物染色體片段交換的方式，將父代個體的優良特征傳遞給子代。

常見交叉策略有：

圖片

這里以多點交叉舉例，假設從種群中選擇了兩個個體作為父代。(A:1 2 3 代表工程師A分配了訂單[1,2,3])

• 父代1A:1 2 3 4 5 6

• 父代2A:6 4 5 2 1 3

• 片段選擇從父代1中選定基因片段[3,4,5]。
• 基因重組移除父代2中與選定片段沖突的基因[3,4,5]。將父代1的片段[3,4,5]插入父代2的末端。
• 產生子代

• 子代A:6 2 1 3 4 5

示例僅展示基因重組原理，實際還需要考慮訂單時間窗口沖突問題。

變異

如果交叉理解為在解空間中大踏步尋找最優解，那么變異就是在解空間小踏步尋找最優解。

上述通過交叉操作產生的子代，采用保守的變異概率（推薦5%±2%），在保持種群多樣性和保護優良基因之間取得平衡。

變異操作最常用的是打亂重組的基因片段，例如，將[3,4,5]打亂得到[5,3,4],則經過交叉、變異后得到的子代是：

• 子代A:6 2 1 5 3 4

優勝劣汰

優勝劣汰模擬生物進化中的自然選擇過程，其核心原則是保留適應度較高的個體，同時淘汰掉適應度較低的個體，從而推動種群整體向更優解方向進化。

圖片

至此，種群完成一次進化（迭代），整體解的質量要高于上一代。

5.3 收斂過程演示

工程師嚴格按照預約開始時間履約，所以最終收斂的路線規劃結果不可避免地會出現折返情況。

圖片

6.總結

6.1 業務收益

算法代替人工后，單日人力耗時從6人時/日降至10分鐘/日，效率提升約97.22%，釋放2人力。

6.2 技術選型

最終采用遺傳算法實現自動派單系統，其優勢包括：

• 魯棒性即使問題規模擴大，計算量仍能保持合理增長，能規避組合爆炸風險。
• 秒級響應中、大規模批量派單場景下仍能實現秒級響應。
• 業務匹配精準適配當前業務體量與派單模式，以最優成本實現效率最大化。

關于作者

蔣韜，轉轉回收技術部的后端工程師