同時取送貨配送路徑優化的兩階段混合策略搜索算法

徐 寧，胡義秋，姚 康（南京審計大學 商學院，江蘇 南京 210029）

0 引言

車輛同時取送貨是物流企業在配送環節提高運作效率所需要采用的重要模式，通過將集貨與配貨結合起來可以合理利用配送途中車輛剩余載荷。配送中實現同時取貨與送貨作業可以有效結合再制造與資源的回收利用，降低企業的配送成本。該模式下的路徑優化問題具有高復雜度和難以求解的特點，同時求解過程需要面臨時間效率、運作成本的兼顧。

同時取送貨問題是傳統車輛路徑問題的延伸，擴展了車輛路徑問題的使用場景，近些年越來越多的學者對其展開研究。Hu 等考慮了動態且取貨與送貨不相容的VRPSPD 問題[1]，為管理者解決貨物不相容的取送貨問題提供了定量的依據；Wang 等考慮了時間窗[2]，構建了多目標優化模型，并以實際業務數據證明了所設計的多目標鄰域搜索算法的有效性；馬艷芳等考慮了運行環境的不確定性構建了不確定VRPSPD 數學模型[3]，引入模糊隨機理論描述決策環境中的不確定性；Hornstra 等研究了考慮貨物裝卸后進先出原則的同時取送貨車輛路徑問題[4]；Zhang 等研究了新加坡快時尚商品的多種類商品需求的同時取送貨問題[5]，并通過自適應內存優化策略求解超過10 000 個節點的大規模實際問題；Büsta 等以最小化燃油消耗為目標[6]，建立了綠色取送貨車輛路徑問題的整數線性規劃模型，并設計了超啟發式算法對其進行求解；Golsefidi 等針對生產-庫存的同時取送貨問題提出了一種魯棒的混合整數線性規劃模型[7]，并設計了兩種啟發式算法用于求解該線性模型；Foroutan 等研究了同時考慮多車型與碳排放的同時取送貨路徑規劃問題[8]，建立了以最小化成本和碳排放的多目標整數線性規劃模型。

對于求解同時取送貨問題，根據問題的業務場景與客戶規模的不同，學者提出了諸多的策略。Soylu 在研究多旅行商問題時設計了變鄰域搜索算法[9]，并通過仿真試驗驗證了算法具有良好的收斂效果；Mu 等設計了并行模擬退火算法用于求解同時取送貨車輛路徑問題[10]，并通過不同規模算例驗證了算法的有效性；Belgin 等設計了變鄰域下降與鄰域搜索算法求解帶同時取送貨的兩級車輛路徑問題[11]，并構建中大規模算例驗證算法有效性，通過實例表明文中算法能夠有效應用于現實配送場景；裴頌文等采用了一種融合拓展性K-Means++算法和遺傳算法的路徑動態規劃模型（KMG）[12]，實現包含逆向物流的無人機調度策略；Majidi 等設計了自適應大鄰域搜索算法用于求解帶同時取送貨的污染路徑問題[13]；Lagos 等設計了改進的粒子群算法對帶同時取送貨和時間窗的車輛路徑問題進行了求解[14]；Chentli 等設計了自適應大鄰域算法用于求解同時取送貨的車輛路徑問題[15]，并通過多個算例證明了算法的有效性；Qiu 等采用了分支定界的方法求解考慮逆向物流的路徑問題[16]，算法在取貨量相對較大時更加高效；Zhao 等設計了一種超啟發式算法框架用于求解帶同時取送貨的選址-路徑問題[17]，該算法框架在求解質量和速度上均優于傳統的算法框架；Ma 等采用基于模糊邏輯控制器和模糊隨機仿真的混合優先級嵌套遺傳算法求解逆向物流環境下帶時間窗和同時取送貨的車輛路徑問題[18]，并用多個規模算例對算法有效性進行驗證；Afra 等在求解取送貨問題時考慮了啟動成本和環保因素[19]，設計了拉格朗日松弛算法（LR）對其進行求解。客戶規模是路徑優化問題的重要影響因素之一，隨著客戶節點的規模增大，精確求解法和傳統啟發式算法的計算時間呈指數級增長，難以求得較優解。

本文研究較大規模帶同時取送貨的車輛路徑問題，針對規模較大的同時取送貨物流配送問題提出了基于“先分解，再求解”思想的兩階段策略，通過聚類方法將規模較大的問題分解為多個小規模的問題，并將每個子問題的規模約束在一輛運輸車能滿足規模內所有客戶需求的范圍內，即將子問題轉化為求解旅行商問題，再設計混合變鄰域搜索算法提高對子問題搜索能力的適應，提高對該類較大規模配送路徑問題的求解能力。本文通過不同規模的算例計算，并與同類算法進行對比，驗證兩階段的算法能夠有效求解同時取送貨物流配送問題，為企業在整合取貨與送貨時合理調配車輛提供方法理論支持。

1 同時取送貨物流配送問題描述與數學模型的構建

1.1 同時取送貨物流配送問題描述

帶同時取送貨物流配送規劃問題是傳統VRP 問題的延展，指配送車輛在對客戶執行送貨任務時，同時可能有取貨需求，這要求車輛需要有效利用配送任務中產生的剩余載荷，在滿足容量約束的條件下，規劃配送路線，最小化配送成本。同時取送貨物流配送問題可以被描述為在歐式平面內的一個全連通圖G=｛V,A ｝，頂點集V=｛0,1 ,…,N ｝，其中：0 為配送中心，i（i≠ 0）為客戶節點。弧集為A，車輛沿弧（i,j）∈A 的行駛距離為dij。配送中心負責滿足N 個客戶的送貨需求di和取貨需求pi，設所有客戶的送貨與取貨需求由配送中心的M 輛運輸車負責，運輸車完全相同，其固定啟動成本為c1，單位距離的運輸成本為c2，載荷量為Q，車輛從配送中心出發，負責服務一批客戶后回到配送中心，每個客戶僅被訪問一次，且每個客戶的需求都被滿足。所有距離都用平面上的歐式距離表示，假設所有車輛的速度為勻速，且嚴禁超載。同時取送貨物流配送問題就是為每輛車找到滿足約束且成本最小的路徑。同時取送貨物流配送網絡如圖1 所示。

圖1 同時取送貨物流配送問題示意圖

構建模型需滿足以下約束：載荷約束，在任何時刻，車輛的載重量不超過車輛的最大載荷；行駛路線，約束車輛從配送中心出發，完成配送任務后返回配送中心；服務次數約束，一個客戶節點只能被一輛車服務，一輛車可服務多個客戶節點；節點約束，車輛從某個客戶節點進入則必須從該節點離開。

1.2 建立同時取送貨物流配送問題的數學模型

基于上述問題描述，構建以成本最小化為目標函數的同時取送貨物流配送模型：

目標函數式（1）表示最小化配送總成本，第一項為車輛固定啟動成本，第二項為車輛的旅行成本；式（2）表示每個客戶僅被訪問一次，式（3）表示車輛駛入某節點后一定從該點駛出；式（4）表示每輛車最多只被使用一次；式（5）表示每條弧上的取貨和送貨載荷不超過車輛的額定載荷；式（6）和式（7）表示取貨與送貨的流量守恒；式（8）表示每條弧上的載荷都大于等于0；式（9）表示若車輛k 經過弧（i,j） ∈A，則為1，否則為0。模型所有的符號定義如表1 所示。

表1 模型中的符號說明

2 求解同時取送貨物流配送問題的兩階段策略設計

2.1 區域劃分聚類算法

客戶節點都為離散的點，本文基于k 均值聚類算法設計區域劃分算法（RPC）將配送范圍劃分為多個區域。聚類屬于無監督學習，聚類過程不受限制，由于車輛有載荷約束，因此需對聚類算法增加約束使得每個類中配送需求或取貨需求總量都不超過一輛車的載荷能力。算法將客戶節點劃分為M 個區域，每個區域內的客戶滿足一輛運輸車即可負責服務，從而在每個區域內的路徑規劃可轉化為求解旅行商路徑問題。

計算客戶的送貨總量D 與取貨總量P，通過單輛運輸車的容量Q，估算滿足全部客戶需求所需的車輛總數M。式（10）為需要的車輛數即劃分的區域數量。

隨機選取配送范圍內M 個坐標點作為M 個區域的中心點，對于每個客戶，計算其與各個中心點的距離，選擇與其距離最近的中心點且該區域內的配送總量滿足車輛容量約束時加入該區域內，若不滿足則將其加入到距離次近的區域內，直至所有客戶節點都加入到某個區域中。

計算每個區域的重心μj，并將重心作為新的區域中心重新劃分客戶，重復迭代上述劃分的過程，算法的終止條件為達到區域內平方和最小化：

2.2 混合變鄰域搜索算法

通過第一階段的區域劃分聚類算法將配送范圍劃分成M 個區域，從而將求解大規模問題轉化為求解多個小規模的子問題，分別對每個區域的物流配送服務使用混合變鄰域搜索算法（HVNS）求解。HVNS 可以被描述為，設s 為一個可行解，Nk（s） 是關于s 的一個鄰域結構的解集，其中：k=1,…,kmax。HVNS 算法通過變鄰域下降法（VND）拓展局部搜索，并混合模擬退火接受準則判斷是否接受新解。混合變鄰域算法的組成包括初始化參數、一組鄰域結構、模擬退火接受準則和算法終止條件。

初始化參數包括初始可行解、初始溫度、退火速率和最終溫度，本文使用貪婪算法生成初始解。

鄰域Nk-1（s）的局部最優s 優于Nk（s）的局部最優s'時以概率）接受新解，使得變鄰域算法以一定概率進入下一個鄰域，避免只在前幾個鄰域中搜索，擴大算法的搜索范圍。

HVNS 的關鍵步驟是使用合適的鄰域搜索方案，鄰域結構的選擇與鄰域搜索方案的順序都影響著HVNS 性能。本文采用了五種（lmax=5）鄰域結構方案，包括插入法，2-opt，3-opt，cross-exchange 和大鄰域搜索。插入法從路徑中刪除一個節點，并將其插入到路徑的其他位置上得到一條新的路徑，選擇使得目標函數最小的插入方案；two-opt 將路徑中的一段進行反轉操作得到一條新的路徑，若目標函數減小即進行反轉，否則不反轉；three-opt 首先刪除路徑中3 條邊，生成3 條子路徑，從而產生了7 種不同的重連方式，并找出其中最優的重連方法；cross-exchange 隨機選取路徑中兩條子路徑，且兩條子路徑沒有重復的節點，交換兩條子路徑的訪問順序，生成新的路徑；大鄰域搜索包括destroy 和repair 兩個算子。本文采用貪婪的思想設計摧毀和修復算子，計算摧毀節點后的節約值，將路徑中對目標函數影響最大的節點摧毀。修復算子將被摧毀的節點插入到路徑中對目標函數影響最小的位置。

變鄰域下降（VND）是HVNS 最關鍵的部分，VND 的原理基于一個事實：一個鄰域結構的局部最小值對于另一個鄰域結構未必如此。VND 拓展了局部搜索，當在一個鄰域結構內陷入局部最優時跳出該鄰域結構重新尋找另一鄰域結構內的局部最優，全局最優是關于所有可能的鄰域結構的局部最優。

在遍歷一個鄰域后，通過退火速率更新當前溫度，算法終止條件為溫度達到設定的最終溫度。

表2 給出了兩階段算法RPCHVNS 的偽代碼。

表2 兩階段算法的偽代碼

3 算法實驗與結果分析

針對提出的兩階段策略，本文通過隨機生成的方法生成數據進行數值實驗。通過多組實驗對比，得出本文算法在求解較大規模的同時取送貨問題時優于其他同類算法。

3.1 算例構建與有效性驗證

本文采用隨機生成的方法構建算例，構建一個大小為30km×30km 的歐氏平面，配送中心的坐標為（15,15），客戶規模為200個，客戶的配送需求滿足均值為5，標準差為2 的高斯分布，設定25%的節點有取貨要求，5%既有送貨也有取貨需求的客戶節點，詳細的客戶信息見表3。設定運輸車的載荷為150kg，車輛的固定啟動成本c1為600 元，車輛平均行駛速度為50km/h，單位距離的行駛成本c2為5 元，運輸車從配送中心出發，完成規劃的配送任務后返回配送中心。算法使用Python3.8 編程，在主頻2.1GHz，8GB 內存的PC 上運行。

表3 配送信息

算法第一階段RPC 算法是將問題按規模劃分為多個子問題，使得每個子問題的規模為一輛運輸車即可完成全部服務，計算總送貨量為755kg，總取貨量為290kg，通過式（10）計算得出M 值為6。通過區域劃分聚類算法對所有點進行劃分，聚類的結果如圖2 所示。

圖2 客戶節點聚類結果圖

通過第一階段的分解后，使用HVNS 分別求解子問題，設置初始溫度為50 000，退火速率為0.98，最終溫度為15，返回迭代過程中出現的最優解。算法求得6 條配送子路徑。使用兩階段算法生成的配送方案路線圖如圖3 所示，每一個閉環代表一輛運輸車的配送路徑。

圖3 配送方案路徑

生成的配送子路徑中，路徑中服務的客戶數量有的區別較大，但配送的里程接近，如路徑6 的客戶服務數量為21，配送里程為62.3，路徑3 的客戶服務數量為40，配送里程為68.1，與路徑6 的里程接近，在平均速度近似的情況下，每輛運輸車的配送時間也接近。由于RPC 算法僅有地理坐標與車輛載荷維度的約束，因此若考慮到配送中的裝卸貨的需求，會有任務分配不均勻的情況發生。

3.2 算法對比與分析

針對3.1 構建的算例，本文對比了文獻[9]中提出的變鄰域搜索算法（GVNS）和文獻[20]中提出的的改進遺傳算法（GA）。分別使用各算法求解10 次，得到計算結果的平均值與標準差，算法對比結果如表4 所示。結果顯示，本文所提出的兩階段策略在處理較大規模的算例上具有優勢，對比文獻[9]的GVNS，車輛行駛距離減少了17.8%，成本節約了8.6%，時間節省了77.9%；對比文獻[20]的GA，車輛行駛距離減少了82.8%，成本節約了66.6%，時間節省了73.8%。兩階段算法在規模較大時解的質量與求解時間均優于傳統啟發式算法，這是由于當算例規模增大時，解空間呈指數級增長，傳統啟發式算法每次迭代都需要花較長時間，難以收斂，兩階段的策略將大規模問題劃分為多個小規模的子問題，減少了計算時間，同時提高了算法的尋優效果。

表4 與算法結果對比

3.3 構建多個規模算例

本文將RPCHVNS 算法應用于幾個不同規模的算例，并與GVNS 和GA 的計算結果進行對比分析。構建客戶規模分別為20、50、100 和200 的隨機算例，算例的構建方法與3.1 中采取的方法相同。分別對每個規模求解10 次，獲得其配送成本的最優解、平均值與標準差。不同算法在不同規模算例下的數值結果如表5 所示。

表5 不同算法在不同規模算例下的數值結果

計算結果顯示本文提出的RPCHVNS 算法在求解不同規模問題上都有良好的性能表現。在客戶規模為20 的算例中，RPCHVNS 與GA 和GVNS 的效果區別并不明顯，從標準差上看，GA 與GVNS 能夠得出比本文算法更加穩定的結果；當規模達到50 時，由于GA 的局部搜索性能較差，求解質量較差，GVNS 和RPCHVNS 的表現良好；當規模超過100 時，可以看出RPCHVNS 能夠得出的解更加優秀，且穩定性表現良好。因此，本文提出的RPCHVNS 更加適合規模較大的問題，解的質量和穩定性都表現良好。

4 結論與展望

本文考慮了實際物流配送中常見的同時取送貨的情景，構建了帶同時取送貨的物流配送數學模型，采用了兩階段算法RPCHVNS 求解該類問題，首先通過區域劃分聚類算法將問題分解為多個小規模的子問題，對于每個子問題，設計了混合變鄰域搜索算法求解配送路徑。通過數值實驗證明了RPCHVNS 在求解不同規模同時取送貨物流配送問題的有效性，對比傳統啟發式算法，RPCHVNS 在客戶規模較小時優越性并不明顯，當規模增大到數百個時，本文算法在求解時間和數值結果上都有良好的表現，這為企業在開展同時取送貨業務時提供了參考意義。

本文在第一階段的聚類過程中，僅考慮了地理位置與車輛載荷約束，而實際配送過程中可能會有裝卸貨與時間窗約束，而當約束增多時，不可行解的數量也增多，算法的尋優能力難以保證。因此下一步的工作將對考慮時間窗和裝卸貨的同時取送貨問題展開研究，并不斷改進RPCHVNS 的尋優性能。