1 引言

2 業(yè)務(wù)背景

3 問題模型

4 算法選擇

5 遺傳算法介紹

5.1 遺傳算法原理

5.2 遺傳算法應(yīng)用

5.3 收斂過程演示

6 總結(jié)

       6.1 業(yè)務(wù)收益

       6.2 技術(shù)選型

1.引言

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

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

如下圖，紅色點(diǎn)為工程師，藍(lán)色點(diǎn)為用戶訂單，藍(lán)色點(diǎn)上方數(shù)字為上門時(shí)間，例：14-16表示該訂單履約時(shí)間為14點(diǎn)到16點(diǎn)。

圖片

派單之后，每個(gè)工程師路線圖：

圖片

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

2.業(yè)務(wù)背景

奢侈品回收業(yè)務(wù)的初期，上門訂單的派發(fā)完全依賴人工。開放的十多個(gè)上門城市都是人工規(guī)劃路線。

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

• 準(zhǔn)時(shí)履約確保工程師能在每個(gè)訂單開始時(shí)間前到達(dá)，并且訂單結(jié)束時(shí)，有足夠時(shí)間到達(dá)下一單。
• 路線最優(yōu)盡量保證工程師整體的通行成本是最低的。
• 訂單均衡盡量保證工程師分配的訂單數(shù)量均衡。

基于上述因素，人工決策和主觀判斷需要反復(fù)嘗試、調(diào)整派單方案，不僅效率低下，而且容易陷入局部最優(yōu)，難以實(shí)現(xiàn)全局最優(yōu)的派單方案。

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

實(shí)時(shí)派單通過規(guī)則的方式實(shí)現(xiàn)，這里不再贅述。接下來，將重點(diǎn)對(duì)批量派單進(jìn)行詳細(xì)介紹。

3.問題模型

要通過算法求解最優(yōu)的派單方案，首先需要確定問題模型，自動(dòng)派單可以被認(rèn)為是VRPTW模型（帶時(shí)間窗口的車輛路徑問題，VRP變種問題）。

圖片

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

• 時(shí)間窗約束工程師必須在履約時(shí)間范圍內(nèi)到達(dá)并完成服務(wù)。
• 訂單約束一個(gè)工程師可以分配多個(gè)訂單，一個(gè)訂單只屬于一個(gè)工程師。
• 起始約束工程師從起點(diǎn)出發(fā)，最終回到起點(diǎn)。
• 順序約束工程師按照訂單的開始時(shí)間順序履約。

基于以上約束條件，問題模型的目標(biāo)是：

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

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

4.算法選擇

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

圖片

我們分析一下不同算法模型的優(yōu)劣。

精確算法

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

經(jīng)過實(shí)驗(yàn)，在5名工程師和30個(gè)訂單的場景下，即使CPU資源被完全占用，耗時(shí)10分鐘，最終也未能搜索到最優(yōu)解。

近似算法

• 優(yōu)勢計(jì)算速度快，實(shí)現(xiàn)簡單。
• 劣勢每次只關(guān)注下一單的最優(yōu)分配，無法關(guān)注到整體最優(yōu)，短視問題導(dǎo)致解的質(zhì)量差，易陷入局部最優(yōu)解。
• 使用場景配合其他算法做初始解生成。一般和派單規(guī)則結(jié)合，適合小規(guī)模流式訂單派發(fā)。

目前，我們的實(shí)時(shí)派單功能就是結(jié)合近似算法與派單規(guī)則的方式實(shí)現(xiàn)。

強(qiáng)化學(xué)習(xí)

• 優(yōu)勢通過試錯(cuò)自主學(xué)習(xí)，獎(jiǎng)勵(lì)函數(shù)反饋不斷優(yōu)化派單方案。適合高維復(fù)雜問題（多目標(biāo)、多動(dòng)態(tài)約束）。
• 劣勢初期缺乏數(shù)據(jù)支撐，有冷啟動(dòng)問題。派單方案解釋性差，對(duì)業(yè)務(wù)來說是”黑盒“。依賴高算力，成本高。
• 使用場景擁有海量的歷史派單數(shù)據(jù)可用于訓(xùn)練。適合訂單量級(jí)大、實(shí)時(shí)要求較高、能投入高成本的場景。

美團(tuán)、Uber等公司實(shí)時(shí)調(diào)度系統(tǒng)采用強(qiáng)化學(xué)習(xí)。

元啟發(fā)式算法

• 優(yōu)勢既能避免組合爆炸的問題，又能夠全面兼顧全局搜索能力。適合高維復(fù)雜問題（多目標(biāo)、多動(dòng)態(tài)約束）。耗時(shí)低，秒級(jí)結(jié)果輸出。無需高算力。
• 劣勢不一定能搜索到絕對(duì)最優(yōu)解，但能搜索到近似最優(yōu)解（最優(yōu)解的95%~100%）。算法參數(shù)調(diào)優(yōu)依賴實(shí)驗(yàn)驗(yàn)證。
• 使用場景不需要追求絕對(duì)最優(yōu)解的組合優(yōu)化。無需額外成本。

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

5.遺傳算法介紹

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

5.1 遺傳算法原理

前置

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

圖片

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

交叉和變異操作的核心在于，在保留父代優(yōu)良基因的基礎(chǔ)上，進(jìn)一步探索更優(yōu)的個(gè)體。

舉例

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

圖片

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

5.2 遺傳算法應(yīng)用

遺傳算法思想平移到自動(dòng)派單，該如何設(shè)計(jì)呢？接下來會(huì)重點(diǎn)講解核心步驟：

圖片

初始化種群

首先說明個(gè)體和種群的概念和關(guān)系。

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

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

也可以是：

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

• 種群

若干個(gè)個(gè)體組成種群。

• 初始化

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

圖片

可以根據(jù)問題規(guī)模設(shè)置種群大小，比如種群大小設(shè)置100，即初始化100個(gè)個(gè)體。

適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是遺傳算法中評(píng)估個(gè)體優(yōu)劣的關(guān)鍵指標(biāo)。在自動(dòng)派單中，我們?cè)O(shè)計(jì)的適應(yīng)度函數(shù)主要優(yōu)化兩個(gè)目標(biāo)：最短工程師通行時(shí)間和最均衡訂單分配。表現(xiàn)越好的個(gè)體（派單方案），其適應(yīng)度評(píng)分越高。

歸一化之后的適應(yīng)度函數(shù)：

圖片

• ：當(dāng)前個(gè)體的工程師通行總時(shí)間
• ：種群中最大通行總時(shí)間
• ：訂單分配均衡性的標(biāo)準(zhǔn)差
• ：成功派單數(shù)
• ：訂單總數(shù)
• , , 為優(yōu)化目標(biāo)權(quán)重系數(shù)，通過業(yè)務(wù)訴求和實(shí)驗(yàn)確定具體值。

選擇

在遺傳算法的選擇階段，系統(tǒng)會(huì)根據(jù)適應(yīng)度函數(shù)評(píng)估結(jié)果，采用特定的選擇策略從當(dāng)前種群中篩選出優(yōu)質(zhì)個(gè)體作為父代。這些被選中的父代個(gè)體將通過后續(xù)的交叉和變異操作產(chǎn)生新一代子代，從而推動(dòng)種群向更優(yōu)解進(jìn)化。

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

圖片

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

交叉

交叉是遺傳算法中最關(guān)鍵的進(jìn)化操作，它通過模擬生物染色體片段交換的方式，將父代個(gè)體的優(yōu)良特征傳遞給子代。

常見交叉策略有：

圖片

這里以多點(diǎn)交叉舉例，假設(shè)從種群中選擇了兩個(gè)個(gè)體作為父代。(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的末端。
• 產(chǎn)生子代

• 子代A:6 2 1 3 4 5

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

變異

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

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

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

• 子代A:6 2 1 5 3 4

優(yōu)勝劣汰

優(yōu)勝劣汰模擬生物進(jìn)化中的自然選擇過程，其核心原則是保留適應(yīng)度較高的個(gè)體，同時(shí)淘汰掉適應(yīng)度較低的個(gè)體，從而推動(dòng)種群整體向更優(yōu)解方向進(jìn)化。

圖片

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

5.3 收斂過程演示

工程師嚴(yán)格按照預(yù)約開始時(shí)間履約，所以最終收斂的路線規(guī)劃結(jié)果不可避免地會(huì)出現(xiàn)折返情況。

圖片

6.總結(jié)

6.1 業(yè)務(wù)收益

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

6.2 技術(shù)選型

最終采用遺傳算法實(shí)現(xiàn)自動(dòng)派單系統(tǒng)，其優(yōu)勢包括：

• 魯棒性即使問題規(guī)模擴(kuò)大，計(jì)算量仍能保持合理增長，能規(guī)避組合爆炸風(fēng)險(xiǎn)。
• 秒級(jí)響應(yīng)中、大規(guī)模批量派單場景下仍能實(shí)現(xiàn)秒級(jí)響應(yīng)。
• 業(yè)務(wù)匹配精準(zhǔn)適配當(dāng)前業(yè)務(wù)體量與派單模式，以最優(yōu)成本實(shí)現(xiàn)效率最大化。

關(guān)于作者

蔣韜，轉(zhuǎn)轉(zhuǎn)回收技術(shù)部的后端工程師