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

0 引言

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

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

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

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

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

1 差分進(jìn)化算法

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

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

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

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

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

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

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

圖1 差分進(jìn)化算法流程圖

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

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

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

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

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

2 多式聯(lián)運車輛路徑問題建模與優(yōu)化

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

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

根據(jù)以上定義，多式聯(lián)運車輛路徑問題的數(shù)學(xué)模型描述如下：

其中：該數(shù)學(xué)模型的約束條件可以被總結(jié)為如下公式：

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

多式聯(lián)運車輛路徑問題優(yōu)化過程如下：

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

步驟2：當(dāng)?shù)鷺?biāo)志g＜200時，開始執(zhí)行循環(huán)；否則，跳過優(yōu)化算法，執(zhí)行步驟13。

步驟3：當(dāng)個體索引i＜NP時，將個體i設(shè)置目標(biāo)個體。

步驟4：根據(jù)公式（4）計算原始種群所有個體的適應(yīng)度值。

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

步驟6：根據(jù)得到的變異個體，將其與目標(biāo)個體通過公式（2）進(jìn)行交叉操作，得到實驗個體。

步驟7：比較實驗個體和目標(biāo)個體的適應(yīng)度值，選取最優(yōu)個體置于種群中，即進(jìn)行選擇操作。

步驟8：比較新的目標(biāo)個體與原本的目標(biāo)個體的適應(yīng)值，選取最優(yōu)個體置于種群中，即再進(jìn)行一個選擇操作。

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

步驟10：返回步驟3。

步驟11：返回步驟2。

步驟12：輸出結(jié)果，結(jié)束程序。

3 仿真測試和結(jié)果

為了評估本文使用的差分進(jìn)化算法的有效性，本文研究了一種路由優(yōu)化案例，用于搜索不同運輸方式的最優(yōu)路徑規(guī)劃。此外，遺傳算法將用于比較，并且表1給出了差分進(jìn)化算法和遺傳算法的相應(yīng)參數(shù)設(shè)置情況。在本案例研究中，從A市到K市有一個10噸的運輸任務(wù)，其中網(wǎng)絡(luò)拓?fù)涔舶?1個城市。除了啟動城市A和目的地城市K之外，該網(wǎng)絡(luò)中有9個中轉(zhuǎn)城市和數(shù)百個可選路線，該網(wǎng)絡(luò)拓?fù)淙鐖D2所示。為了方便優(yōu)化算法計算種群個體和染色體的適應(yīng)度值，每個城市的運輸成本和轉(zhuǎn)移成本列于表2中，其中符號“-”表示列出的運輸方式不可使用。

表1 差分進(jìn)化算法和遺傳算法的參數(shù)設(shè)置

圖2 運輸網(wǎng)絡(luò)拓?fù)?/p>

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

4 總 結(jié)

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

表2 多式聯(lián)運模式運輸開銷

圖3 實驗迭代結(jié)果