基于差分進化算法的多式聯運物流運輸問題研究

孫 哲，劉晨磊，孫知信 （南京郵電大學，江蘇 南京 210003）

0 引言

在貿易全球化的現在，各物流公司更加有效地優化和管理物流環節是很有必要的。其中，最重要的一種實現方法就是對貨物進行物流運輸時車輛路線進行合理的規劃，因為這不僅可以降低運輸成本，還對提升服務質量起到重要作用。經典的車輛路徑問題（Vehicle Route Problem，VRP）[1]是指在給定的運輸網絡上的對物流車輛的路線進行有效規劃，以便物流公司在一些特定的約束條件下高效地服務于客戶。其中，縮減所有車輛的總運輸距離、總運輸成本或者減少行程時間成本被視為VRP的典型目標。可持續的物流運輸問題需要充分考慮目標和相當多的約束條件，文獻[1] 提出了新的車輛路徑模型和應用場景，但是同樣引出了一種更復雜的組合優化問題。一般意義上，基本的車輛路徑問題是指確認一組有效的多個旅行商（TSP）路線問題，即車輛從起點到目的地的，以服務給定的一組客戶，并且每個客戶應該只被一輛車訪問一次。此外，由于單個路線可能超過允許的運輸距離或者運輸時間，因此物流車輛可能存在多種不同運輸路線。因此，VRP實際上被認為是更復雜、更高級別和更廣泛的一類路由問題。

VRP由于約束條件或者目標的不同存在著多種變體，例如容量VRP（CVRP）[2]，多倉庫VRP（MDVRP）[3]和帶時間窗的VRP（VRPTW）[4]。此外，隨著不同運輸方式的發展，傳統的道路運輸模式已不再是唯一的物流運輸解決方案，基于多式聯運的物流運輸方案已成為全球物流行業的重要工作模式，并且多式聯運的應用被政府視為推動運營高效化和環?；闹匾獎恿?。與經典的VRP類似，多式聯運VRP[5]也是一個NP難的優化問題，同時被認為是一個復雜的組合優化問題，研究人員需要在運輸成本和時間成本方面協調規劃車輛路線和運輸模式，因此在過去20年中已經成為一個具有挑戰性的研究課題。

精確算法被認為是解決這類物流運輸車輛路徑問題的最有效方法之一，在文獻[6] 中，作者提出了一種基于經典Dijkstra算法的路徑搜索算法及其決策機制，解決了大型應用系統中搜索算法的時空復雜度較大的問題。在文獻[7] 中，作者通過建立迭代矩陣和序列數矩陣提出了一種改進的Floyd算法，并成功地采用該算法來處理汽車導航系統中的路徑選擇問題。文獻[8] 中，作者為了獲得最佳路線，提出了基于概率變量鄰域搜索的三步局部搜索算法，并將其用于車輛路徑規劃問題的求解中。在文獻[9] 中，作者提出了一種分支切割算法來解決商人庫存路徑問題，并運用經濟目標函數分析了經濟環境變化對車輛路徑問題的運輸平均利潤造成的影響。還有研究[10]為VRP開發了一種有效穩健的分支切割和價格算法，在這個算法中路線通常與列相關聯，這些列是容量化基本路線的松弛，這使得定價問題在假多項式時間內能夠被解決。通常，這些精確算法適用于那些簡單的VRP和路由規劃，但是對于處理復雜的路由規劃問題，精確算法的性能可能就無法滿足計算要求了。

與精確算法相比，啟發式算法，如禁忌搜索算法[11]、模擬退火算法[12]、蟻群算法[13]、遺傳算法[14]、粒子群優化[15]和差分進化算法[16]由于強大的搜索能力，在大規模多重約束優化方面表現出優異的性能。例如，在文獻[17] 、[18] 中，Brando提出了禁忌搜索算法，并利用3個過程來得出初始解，還為鄰域定義了3個運算符：單個插入、雙插入和交換。該算法還在搜索期間利用了強化和多樣化的操作，故該方法能夠獲得更高質量的解決方案。在文獻[19] 中，作者提出了一種結合了幾種局部搜索技術的模擬退火算法（SA）來處理車輛路徑問題（VRP）的變體，其中時間窗口是與每個客戶服務相關聯。在文獻[20] 中，研究人員提出了一種粒子群優化方法，采用自學習方法處理配送中心的車輛路徑規劃問題，該配送中心具有多個交叉對接處理多種產品。針對算法早熟收斂問題與降低基本蟻群算法（ACA）的計算成本，文獻[13] 提出了一種基于信息熵和局部搜索的自適應蟻群算法求解車輛路徑問題和能力的VRP。在文獻[14] 中，研究人員采用混合的遺傳算法來解決具有時間窗的VRP（VRPTW），其中有一個特定的時間可服務任何客戶，然后他對他的結果和其他算法的結果進行了比較，如模擬退火算法。

作為一種高效且功能強大的全局優化算法——差分進化算法（Differential Evolution Algorithm，DE）[16]已成功應用于各種鄰域，因為其性能優于其他優化算法[13-15]。因此，搜索多式聯運VRP問題的差分進化算子被認為是優化最佳路徑的有效、可行的方案，這構成了本篇文章的基礎。本文的結構如下：第1章中我們描述了差分進化算法；多式聯運的VRP模型在第2章；模擬測試和結果討論在第3章；總結部分在最后一個章節中。

1 差分進化算法

1.1 算法原理。DE算法被認為是用于實際參數優化問題的有效且易于理解的一種優化方法。根據文獻[21] 的描述，DE算法啟動時隨機生成NP只個體，記為P ｝。第i個潛在解決方案由D維向量xi=表示。 通常，標準的DE算法由3個基本操作組成，即變異、交叉和選擇。

變異操作：在其變異階段，DE算法從當前群體中隨機選擇3個目標個體x1,x2和x3。需要注意的是，這些被挑選出的目標向量不能夠重合。其中，變異個體通過式（1）產生。

其中：Fm∈ [0,2 ] 是一個控制差分變量的縮放因子。通常情況下，Fm過小會導致算法過早收斂，但是Fm過大也會導致減弱算法的局部最優解搜索能力。

交叉操作：為了提高概率密度，變異操作之后通常采用交叉操作。新的個體向量] 將通過以下規則獲得。

其中：randj是第j次隨機進化，其范圍是是交叉概率約束，] 是選擇指數，用來保證元素vi,j能夠得到。

選擇操作：選擇操作的目的是決定將哪些個體保留到下一代以及將多少個體復制到下一代。貪婪選擇方案被應用在DE算法中，以確定新的個體ui和目標個體xi。如果ui優于xi，那么新個體將替換到下一代中的相應目標向量，否則目標個體保留在種群中。因此，種群要么變得更好，要么在健康狀態下保持不變，但永遠不會產生惡化。貪婪選擇方案被描述為以下的優化問題minf（x）：

1.2 差分進化算法流程?；谝陨咸峒暗牟僮?，差分進化算法的執行步驟進行如下總結，并且具體的差分進化算法執行流程圖如圖1所示。

圖1 差分進化算法流程圖

步驟2：更新種群迭數g=g+1，并設置個體索引i=1;

步驟3：從當前的種群中選擇3個不同的目標個體，通過對xi的變異操作計算出變異個體vi；

步驟4：在xi和vi間執行交叉操作，隨后執行選擇操作；

步驟5：更新個體索引i=i+1，返回步驟3直至i=NP；

步驟6：判斷當前一代的最佳值是否符合終止條件，如果符合，則停止算法的執行；否則返回步驟2。

2 多式聯運車輛路徑問題建模與優化

2.1 模型構建。結合客戶的需求本文對模型中涉及的參數進行如下定義：P是所有運輸站點的集合；S是運輸模式的集合；di,j表示站點i和站點j之間距離；表示站點i和站點j之間使用運輸方式k；表示在站點j上將運輸方式k調整為運輸方式l；

表示站點i和站點j之間在運輸方式k下的運輸時間；表 示在站點j上將運輸方式k調整為運輸方式l需要的時間；T是最長服務時間；表示站點i和站點j之間在運輸方式k下的運輸成本；表示在站點j上將運輸方式k調整為運輸方式l需要的成本；Q是運輸量；表示站點i和站點j之間在運輸方式k下的運輸量。

根據以上定義，多式聯運車輛路徑問題的數學模型描述如下：

其中：該數學模型的約束條件可以被總結為如下公式：

2.2 優化過程。為了利用差分進化算法來優化多式聯運VRP，VRP需要采用十進制代碼編碼。在該優化過程中本文采用兩個分段編碼的形式，DE個體的第一部分代表運輸路徑，其余部分是多模式運輸類型。例如，如果共有8個運輸點，在路徑編碼中，我們將 [0,1 ,…,7] 定義為傳輸點編號，并且0,7定義初始點和終點；在運輸型編碼中，[1,2,3,4] 分別代表公路運輸、鐵路運輸、船舶運輸和航空運輸。

多式聯運車輛路徑問題優化過程如下：

步驟1：初始化差分進化算法的種群的道路和運輸方式模型，并初始化算法相關參數（例如，1→2→4→3→5；公路→鐵路→空運→公路等）。

步驟2：當迭代標志g＜200時，開始執行循環；否則，跳過優化算法，執行步驟13。

步驟3：當個體索引i＜NP時，將個體i設置目標個體。

步驟4：根據公式（4）計算原始種群所有個體的適應度值。

步驟5：隨機選取3個個體利用公式（1）進行變異操作，得到變異個體。

步驟6：根據得到的變異個體，將其與目標個體通過公式（2）進行交叉操作，得到實驗個體。

步驟7：比較實驗個體和目標個體的適應度值，選取最優個體置于種群中，即進行選擇操作。

步驟8：比較新的目標個體與原本的目標個體的適應值，選取最優個體置于種群中，即再進行一個選擇操作。

步驟9：個體索引更新i=i+1。

步驟10：返回步驟3。

步驟11：返回步驟2。

步驟12：輸出結果，結束程序。

3 仿真測試和結果

為了評估本文使用的差分進化算法的有效性，本文研究了一種路由優化案例，用于搜索不同運輸方式的最優路徑規劃。此外，遺傳算法將用于比較，并且表1給出了差分進化算法和遺傳算法的相應參數設置情況。在本案例研究中，從A市到K市有一個10噸的運輸任務，其中網絡拓撲共包括11個城市。除了啟動城市A和目的地城市K之外，該網絡中有9個中轉城市和數百個可選路線，該網絡拓撲如圖2所示。為了方便優化算法計算種群個體和染色體的適應度值，每個城市的運輸成本和轉移成本列于表2中，其中符號“-”表示列出的運輸方式不可使用。

表1 差分進化算法和遺傳算法的參數設置

圖2 運輸網絡拓撲

通過分別使用差分進化算法和遺傳算法，可以容易地獲得具有運輸模式的最佳路線，即從A市到K市的最佳路線是A→B→F→J→K，相應的交通方式是從A市到B市到F市的鐵路運輸，從F市到J市到K市的船舶運輸。此外，為了確認差分進化算法的有效性與性能，本文在本案例實驗中選擇了標準遺傳算法和標準差分進化算法進行對比，其迭代趨勢的比較結果如圖3所示。從圖3可以看出，差分進化算法相比于遺傳算法收斂速度更快，并且能夠計算出更加優秀的物流運輸車輛路徑規劃方案。綜上，本文設計的差分進化算法在多式聯運車輛路徑問題上的應用方案是可行的、有效的。

4 總 結

物流運輸車輛路徑規劃問題被認為是一個復雜的組合優化問題，其在過去的20年中已成為一個具有挑戰性的研究課題。為了解決這類NP難問題，本文鄰域搜索操作，提出了一種將差分進化算法應用于物流多式聯運車輛路徑問題的方案。同時，為了證明所提出方法的有效性，本文設計并測試了基于多式聯運方式的物流運輸實例，并通過仿真實驗證明了差分進化算法應用在多式聯運車輛路徑問題上的可行性和有效性。

表2 多式聯運模式運輸開銷

圖3 實驗迭代結果