針對多中心場站下兩級選址路徑問題的雙智能集成算法

唐 震 霆， 胡 志 華

(上海海事大學 物流研究中心，上海 201306)

0 引 言

兩級選址路徑問題(two-echelon location routing problem，2E-LRP)是近年來物流領域的熱點問題，選址路徑問題從結構上來說首先要完成選址，而后進行路徑規劃.在一個多級運輸配送系統中，一條完整的運輸配送鏈也被分成多級，貨物從倉庫運輸至樞紐點整合并移交至最終客戶，高效利用各樞紐點與車輛容量是降本提效的關鍵，而將客戶點合理分配至每一個客戶是樞紐點高效運作的條件之一[1].

截至目前，許多優秀的學者提出了多級車輛運輸的相關選址路徑規劃方案以及方法論.有關2E-LRP的文獻開始涉及城市物流中兩級配送結構的運營和資源管理的短期綜合調度問題[2-7]，在確定樞紐點之后問題轉變為兩級車輛路徑問題(two-echelon vehicle routing problem，2E-VRP)；傳統的車輛路徑問題一般為單級物流系統，即車輛從中心場站直接向需求點提供服務.一般地，物流運輸車輛體積較大、質量較重，加重了城市道路交通擁堵、噪聲、污染等情況，地方政府對此也提出了限行條例：運輸物資先通過大型運輸車輛調配至企業位于郊區的中轉設施中，而后通過污染較小、較為靈活的小型運輸車輛進行配送，這也就是兩級車輛路徑問題的起源.Grangier等介紹了一個具有衛星同步的兩級多行程車輛路徑問題，并提出了一種自適應大鄰域搜索(adaptive large neighborhood search，ALNS)算法[8].Boccia 等考慮了多中心場站的場景，針對不同類型的車隊和兩級物流網絡路徑之間的聯系等要素采用了禁忌搜索算法對算例進行實驗，實驗結果證明了該算法的有效性[9].Yang等研究城市物流系統中帶時間約束的兩級選址路徑問題，基于概率選擇原則提出了一種綜合考慮時間和空間可達性的元啟發式算法來求解該類問題，并通過隨機生成的實例來驗證算法有效性[10].Pichka等認為多級分銷系統普遍存在于人們的日常生活中，其提出3種基于流通路徑的混合整數線性規劃以及1種混合啟發式算法來求解開放式選址與路徑優化問題[11].

對于上述研究，兩級設施選址與車輛路徑規劃問題的雙層結構特征是其復雜性的核心，兩級物流網絡的搭建與布局一直是許多物流企業的痛點，如何從備選節點中選擇有利于降低整體系統成本的節點來作為樞紐點、確定車輛經過節點的先后次序即車輛路徑以及客戶點、樞紐點與中心場站的對應關系是該問題的幾個重大難點，也是物流企業進行多級物流網絡建設所避不開的問題.在一些研究中將問題分割為兩個階段來進行求解[12-13]，這在一定程度上導致了求解問題的獨立性，對于兩級選址路徑問題，雙智能集成算法的表現優于其他傳統啟發式算法.本研究中進行節點資源配置的算法為ALNS的改進算法，擁有一組破壞與修復算子是其與常規ALNS算法[14]最明顯的不同，而模擬退火算法則用于路徑尋優.

1 多中心場站下兩級選址路徑問題的建模

基本的兩級選址路徑問題表述如下：從備選節點中選出若干個合適的節點作為樞紐點優化配送體系，降低系統成本；一組運輸車輛從中心場站出發，將貨物運輸碼放至樞紐點，而后由樞紐點委派運輸車輛將貨物交付給客戶，所有運輸車輛在完成配送后回到始發節點；每個客戶點的坐標位置已知；配送車輛有荷載限制；要求合理配置資源、優化行車路徑，以實現目標的優化.

多中心場站下兩級設施選址與車輛路徑規劃問題的圖論表述如下：D代表中心場站集合，通過τ∈D索引；N代表客戶點集合，一般通過i∈N索引每個客戶點，通過υ∈N索引樞紐點；候選樞紐點集合S?N；定義J=D∪N.Cij≥0為車輛從i∈J到j∈J的行駛成本；F1≥0與F2≥0分別為兩級運輸中單輛運輸車的固定成本；F3≥0為設置一個樞紐點的固定成本；由客戶需求Ri得出每一個樞紐點所需要的貨物量.第一級和第二級配送車輛的容量上限為K1和K2.C1和C2表示第一級和第二級車輛配送的單位里程成本.Ud表示中心場站數量，Us表示樞紐點數量.

變量qijτ表示從中心場站τ∈D出發的車輛經過i∈N到達j∈N路段中車輛的載貨量；變量pijυ表示從樞紐點υ∈N出發的車輛經過i∈N到達j∈N路段中車輛的載貨量.

決策變量βijτ=1，表示客戶點i分配給樞紐點j，并且j分配給中心場站τ；否則，βijτ=0.其中，i≠j.若節點i被選作樞紐點，則βiiτ=1.

決策變量xijτ=1，表示第一級配送車輛從中心場站τ出發，服務i∈N后下一個緊接的服務節點是j∈N；否則，xijτ=0.

決策變量yijυ=1，表示第二級配送車輛從樞紐點υ出發，服務i∈N后下一個緊接的服務節點是j∈N；否則，yijτ=0.

對2E-LRP問題中的變量與約束條件設置特點進行總結，完善數學模型的構建，所求得的解必須滿足以下約束：

(1)每個被選作樞紐點的節點至少服務一個客戶點；

(2)每次配送任務中任意車輛只運行一次；

(3)每條路徑從設施出發，最后要回到出發的設施；

(4)每個客戶點由且僅由一輛貨車進行服務；

(5)車輛服務的顧客的需求總和不能超過車輛的容量約束；

(6)每個客戶的需求Ri均為常量且已知；

(7)每個中心場站都至少輻射一個樞紐點.

首先，目標函數主要由兩部分組成，分別是兩級運輸中的路徑成本總和以及車輛、樞紐設施的固定使用成本，如下式所示：

minz=z1+z2

(1)

其中

針對樞紐點的選擇以及客戶點的分配這兩個子問題，考慮兩個層級下樞紐點集合與客戶點集合的分配邏輯構造約束，以便于路徑問題的求解，控制選址以及樞紐點分配的模型如下：

(2)

(3)

(4)

(5)

βikτ≤βkkτ；?i，k∈N，τ∈D

(6)

其中，約束(2)表示任意節點i∈N都會被分配一個樞紐點，且歸屬于一個中心場站；約束(3)表示樞紐點個數等于Us；約束(4)表示任意樞紐點僅被分配給一個中心場站；約束(5)表示若節點i∈N不是樞紐點必會被分配給一個樞紐點；約束(6)表示僅當k∈N為樞紐點時才會將客戶點分配至樞紐點k.

(7)

(8)

(9)

(10)

(11)

(12)

約束(7)～(9)去除了車輛從中心場站出發的無效路徑，約束(10)～(12)表示第一級運輸中的路徑約束與流平衡限制，且第一級運輸車輛經過的節點是被選作樞紐的節點.

(13)

(14)

qijτ≥xijτ；?i∈J，j∈N，τ∈D

(15)

qijτ≤K1xijτ；?i，j∈J，τ∈D

(16)

xijτ≤βjjτ；?i∈J，j∈N，τ∈D

(17)

xjiτ≤βjjτ；?i∈J，j∈N，τ∈D

(18)

(19)

約束(13)～(14)將車輛裝載量、路徑、分配問題相聯立，保證了車輛運輸過程中，經過樞紐點的順序與車輛裝載量同步變化，即當車輛經過任意樞紐點時裝載量減少相應節點所需的貨物量.約束(15)～(16)將變量qijτ與第一級運輸路徑xijτ建立聯系；約束(17)～(18)將第一級運輸路徑限制在樞紐點與中心場站間；約束(19)表示車輛回到中心場站時的裝載量為零.

(20)

(21)

約束(20)～(21)表示了第二級運輸中車輛裝載量與運輸路徑的聯系，以確立運輸順序與車輛裝載量的變化關系.

(22)

(23)

(24)

pijυ≤K2yijυ；?i，j，υ∈N

(25)

pijυ≥yijυ；?i，j，υ∈N，j≠υ

(26)

約束(22)～(24)對第二級運輸路徑進行約束，建立流平衡約束；約束(25)～(26)將變量pijυ與路徑yijυ聯立，確保車輛裝載量不超過車輛容量.

(27)

(28)

(29)

(30)

(31)

約束(27)～(30)將第二級運輸路徑與節點分配邏輯保持統一，若客戶點j由樞紐點υ服務且歸屬于中心場站τ，則允許在客戶點j處存在入度與出度；約束(31)表示第二級運輸車輛回到樞紐點時的裝載量為零.該模型綜合樞紐點選擇、兩級節點分配、車輛路徑規劃3個問題同時求解，保證了解決系統問題的連貫性、完整性.

2 雙智能集成算法

2.1 算法設計依據與邏輯

黃凱明等通過對多層級設施選址路徑規劃問題的研究，提出一種雙智能集成算法：量子進化算法負責設施選址和資源分配，而遺傳算法負責子路徑尋優[15].雙智能集成算法在求解選址路徑問題過程中體現出較大的優勢，在應對不同問題時都可以選擇針對問題具有較好求解性能的啟發式算法來進行處理，通過信息交互、共同迭代來求解復雜問題是一種較為優秀的求解思路.由此，本文在算法設計時采用了改進的自適應大鄰域搜索算法與模擬退火算法集成的雙智能算法，該混合啟發式算法通過兩種不同類型算法的交互，將求解任務分解，從而有效求解問題.

算法設計依據：兩級選址路徑問題的復雜性主要是因為該問題不僅需要確定節點分配方案，確定運輸工具遍歷樞紐點以及客戶點的次序，還需要留意運輸工具容量限制及樞紐點必須有子節點等條件，本混合啟發式算法能有效求解子問題并在算法內部交互迭代，因此該混合啟發式算法適合解決兩級選址路徑問題.自適應大鄰域搜索算法在多鄰域迭代過程中有著較優秀的表現，因此選擇自適應大鄰域搜索算法作為算法主體框架，使用模擬退火算法求解子路徑的最優排序，這也加快了問題整體的求解效率，算法邏輯如圖1所示.

算法設計邏輯：兩級自適應大鄰域搜索(two-echelon adaptive large neighborhood search，2E-ALNS)算法控制兩級節點分配方案，分別改變樞紐點被分配至中心場站的方案以及客戶點被分配至樞紐點的方案，根據分配方案確定每個旅行商問題(TSP)的構成節點，但此時的分配方案中節點是無序的，經過模擬退火算法進行求解后，節點分配方案中的排序與TSP解的節點排序一致，因此兩個算法分工明確且相輔相成.

2.2 模擬退火算法

采用模擬退火算法以解決車輛經過節點的次序問題，算法的輸入集是主節點編號、子節點編號以及節點坐標位置.算法采用隨機交換節點次序來進行路徑排序問題的尋優，模擬退火算法初始溫度設為50；冷卻速率為0.98；算法以一定概率接受改造解，概率公式如下：

式中：ρ為接受改造解的概率；Sc為當前迭代中的局部最優解，Sn為算法產生的新解；E(S)代表解S的能量，在本例中即為路徑成本；T為當前溫度；?為溫度與能量差值的轉換系數，本例中取?=0.8.當改造解的運輸成本小于局部最優解的運輸成本以，將改造解替代局部最優解；當改造解的運輸成本大于局部最優解的運輸成本時，以一定概率接受改造解，將接受概率和當前溫度相關聯，使得該算法在運行初期搜索區域變大，加快收斂速度，而在后期削減其搜索區域進行精細搜索.

2.3 改進的自適應大鄰域搜索算法

兩級自適應大鄰域搜索算法是在自適應大鄰域搜索算法的機理上再加一組破壞與修復算子使其能解決兩級問題，其中，通過第一級算子改變樞紐點至中心場站的分配方案，從而使得第一級的解改變，相似地，通過第二級算子改變非樞紐點的客戶點至樞紐點的分配方案.為了保證每個樞紐點承擔的中轉工作盡量相當，在算子設計上，使每一級運輸過程中每個主節點被分配的子節點數量盡量相當，這樣才能確保每個樞紐點工作量差距不會太大，不會有廢棄樞紐點的情況出現.

第一級算子設計邏輯有以下幾種：

第二級算子設計如下：

本算法的時間復雜度與自適應大鄰域搜索算法的運行過程極度相關，自適應大鄰域搜索算法在迭代過程中會根據算子權重自主地選擇算子，由于在該算法中包括破壞算子和修復算子，且每個算子都有不同的時間復雜度，故本算法的自身時間復雜度并不確定且處于一個區間中，因此本算法的時間復雜度并不穩定，且最壞情況為O(1952(3Ud+2Us)).

2.4 參與對比的啟發式算法

2.4.1 基于聚類算法的貪婪程式 聚類算法常用于分類問題，一般地，同一簇中的任意個體與同簇個體具有較高的相似度，而不同簇中的個體往往有較大差異.本啟發式的聚類算法以若干數據點為中心，將點集分為若干類，再根據中心點位置匹配距離較近的中心場站以提供配送服務.在貪婪程式中，將簇中距離中心場站以及簇中心位置最短的若干節點作為樞紐點并以此確定第一級運輸中的節點分配方案，而第二級運輸中的節點分配方案主要由K-means聚類的方法來控制，整個貪婪程式中蘊含了兩層貪心法則，在節點簇地理位置分隔較為明顯的案例下，該算法較為高效.

2.4.2 變鄰域搜索算法 變鄰域搜索算法是求解車輛路徑問題的最有利算法之一，通過復現并設計對應本問題的算子以方便將雙智能集成算法與之進行對比分析.

變鄰域搜索算法的擾動算子設計如下：

(1)x′←ExchangeOneHub(x)：選擇一個樞紐點將其與備選樞紐點中的剩余節點進行交換.

(2)x′←ChangeSequence1(x)：選擇任意兩個樞紐點進行次序變更.

(3)x′←ChangeSequence2(x)：變更任意車輛路徑中服務的客戶點先后次序.

(4)x′←AddOrDelete(x)：增加或刪除從某個樞紐點出發的無人機路徑.

變鄰域搜索算法的鄰域動作算子設計如下：

(1)x″←ChangeNodesSequence(x′)：選擇一條第二級路徑，將路徑中相近的兩個節點進行次序調換.

(2)x″←Remove&Insert(x′)：若子節點個數不少于1，去除任意子節點并將其插入其他路徑中.

(3)x″←ExchangeNodes(x′)：選定兩條不同路徑，并選擇兩者中的任意節點進行交換.

(4)x″←WorstNodesRemove(x′)：選擇任意第二級路徑中相近的客戶，去除其中任意一個并將其插入其他路徑中.

(5)x″←WorstExchange(x′)：選擇任意兩條第二級路徑，將各自距離樞紐點最遠的節點進行交換.

3 實例驗證

本研究求解的問題不同于常規的車輛路徑規劃問題，需要綜合考慮樞紐點選址問題、客戶點分配方案以及兩級車輛的路徑規劃問題.選擇車輛路徑問題的經典數據集作為實驗案例，對同一案例進行多次實驗，主要進行了模型與算法求解的對比.通過將本文提出的算法與基于聚類算法的貪婪程式以及在路徑優化問題領域較為成熟的變鄰域搜索算法進行對比實驗，證明算法的有效性.

3.1 實驗環境和算法參數確定

實驗環境如下：Intel i7-4720HQ 2.60 GHz CPU，8 GB內存，操作系統為Windows 7，編程環境為Python 3.7.

選擇CVRPLIB中的P-n101-k4數據集進行第一組實驗，增加中心場站位置數據，其余數據保持不變，數據集主要包含了3個中心場站、100個客戶點的位置數據以及客戶點的需求量數據，記錄運行結果的最優值，考慮收斂速度和平均最優值.參數設置：初始溫度50；溫度冷卻速率0.98；權重控制因子0.5.第二組實驗的算例為P-n50-k4，其中包含3個中心場站和50個客戶點，記錄不同運行時間下的啟發式算法運算結果與CPLEX求解數學模型的結果，并求出兩者間的差距，證明算法應對中等及大規模算例的有效性.在第三組實驗中，將本文提出的雙智能集成算法與貪婪程式以及變鄰域搜索算法進行對比實驗.

3.2 實驗結果與分析

將數據集P-n101-k4中各節點以及新增的中心場站進行編碼，取不同樞紐點數量進行實驗.在3組實驗中取10個樞紐點的平均路程成本最小.在此情景下，第一級車輛使用數量與中心場站數量相同(本例中為3).最后，樞紐點數量的確定需要考量車輛成本、樞紐點設立費用等累加再比較總成本大小，使用本文算法求解算例所花費的時間較為穩定，在相同樞紐點數量下，5個樣本在求解時間上的方差很小.同一算例下，樞紐點數量對成本的影響見表1.

表1 樞紐點數量對成本的影響

在完成樞紐點數量對整個兩級物流系統的成本影響實驗后，選取中等規模樣本進行反復實驗，將雙智能集成算法與數學模型求解的結果進行對比.實驗數據表明，雙智能集成算法在有限時間內能普遍求得優于數學模型求解的結果，其在兩級自適應算法外層還嵌套了模擬退火思想以控制整體迭代次數，外層框架中模擬退火初始溫度的不同對最終結果產生影響，實驗數據見表2.

表2 數學模型與雙智能集成算法求解結果對比

在本實驗中，將雙智能集成算法中的算子在不同算例下的得分與權重記錄下來，并分析修復與破壞算子的優劣，固定初始溫度為50，且取樞紐點數量為6，算子順序與前文介紹算子順序一致.算子總得分結果表明，雙智能集成算法中的算子得分均勻，并未出現使用次數極少或極多的算子.

而后，將前文提到的貪婪程式和變鄰域搜索算法與本文的雙智能集成算法進行對比分析，在該實驗中，分別選取樞紐點數量為6、8、10進行實驗，求解結果的對比見表3，實驗編號為中心場站數量-客戶點數量.

表3 貪婪程式、變鄰域搜索算法與雙智能集成算法求解結果對比

本實驗表明，在P-n50-k4這個案例中取8個樞紐點較優.雙智能集成算法與貪婪程式的平均差異為3.7%.此外雙智能集成算法中的算子設計依附了實際的運用情景，例如在城市物流中每一個驛站的選址路徑問題不僅涉及整體成本的多少，還應考慮單個樞紐點輻射客戶點的數量、上級節點對其配送的難易等，因此在算子設計過程中需要盡量保持每一個樞紐點服務的下屬節點均有一定量，也就是使得每個樞紐點的工作量差距不要太大.由此，雙智能集成算法在實際場景具有一定的泛用性，對于不同規模的算例皆可直接進行計算并獲取其解決方案.在與車輛路徑問題中主流方法的對比中，雙智能集成算法在多案例的求解結果中都略優于變鄰域搜索算法，且在該次實驗中，雙智能集成算法的平均求解時間(24.92 s)略小于變鄰域搜索算法的平均求解時間(26.54 s)，體現出該算法的高效性.此外，對于確定算例下樞紐點數量問題，也可通過改變選址數量的參數，運用雙智能集成算法對比不同樞紐點數量的系統成本高低，給予決策者較大的便利，解決整體系統中樞紐點選擇、節點分配及節點數量與系統最優性關系等問題.

在算例P-n50-k4中，實驗表明選取8個樞紐點相較于選取6個或10個樞紐點都更優，貪婪程式也呈現出相類似的趨勢，這也強有力地支持了本文算法的有效性以及對選址數量確定問題的求解效能.在算例p-n101-k4中，系統成本隨樞紐點數量的增加而減少，清晰地呈現了選取樞紐點數量與系統成本的變化趨勢.根據先前的實驗經驗，如果繼續增加樞紐點，在某個閾值點，系統成本會不降反升.本研究中提到的算法不僅可以提供不同規模問題集的較優解決方案，還可以幫助決策者確定固定案例下樞紐點數量的較優選取數量與位置，功能集成化與泛用性是該算法的重要優勢.

4 結 論

(1)本研究針對兩級車輛路徑與節點分配問題，提出了一種雙智能集成算法，該算法能完整地求解節點分配與車輛路徑這一系統問題，保證了問題求解的完整性.

(2)通過對自適應大鄰域搜索算法中破壞、修復算子的設計，使得每一級運輸下每一個主節點的工作量都相當，不會出現廢棄樞紐點的情況，這樣也比較符合該問題在現實中的應用.隨著中國現代化進程的不斷推進，人們對不同物資的需求越來越多，需求量的敏感性也越來越強，這勢必帶來物流網絡的復雜化和多級物流網絡的廣泛應用，網絡中不同層級的節點分配問題以及路徑問題是該情景下的主要問題.

(3)運用雙智能集成算法，決策者可以在較短時間內得到某個案例下選擇不同樞紐點數量對整個物流系統的影響并提供決策方案.從實驗結果來看，雙智能集成算法在不同算例下都優于本研究中給出的貪婪程式、變鄰域搜索算法，通過改變樞紐點數量生成多組實驗數據得出樞紐點數量與總成本之間存在一定的效益悖反.