基于差分進(jìn)化算法的多式聯(lián)運(yùn)物流運(yùn)輸問(wèn)題研究

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟9：個(gè)體索引更新i=i+1。

步驟10：返回步驟3。

步驟11：返回步驟2。

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

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

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

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

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

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

4 總 結(jié)

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

表2 多式聯(lián)運(yùn)模式運(yùn)輸開(kāi)銷

圖3 實(shí)驗(yàn)迭代結(jié)果