楊 璐，唐勇軍

（河海大學(xué) 商學(xué)院，江蘇 南京211100）

基于多聯(lián)式遺傳算法的運(yùn)輸網(wǎng)絡(luò)成本研究

楊 璐，唐勇軍

（河海大學(xué) 商學(xué)院，江蘇 南京211100）

針對目前多聯(lián)式運(yùn)輸網(wǎng)絡(luò)成本問題，本研究通過使用虛擬網(wǎng)絡(luò)建模綜合考慮了公路、鐵路和內(nèi)河航運(yùn)的網(wǎng)絡(luò)子節(jié)點(diǎn)連接，并構(gòu)建了4種運(yùn)輸鏈接模式來計算廣義成本。利用全有或全無的算法（AON）用于路徑流量的分配，在Michalewicz開發(fā)的編程邏輯基礎(chǔ)上使用GISDK中的二次開發(fā)環(huán)境創(chuàng)建了自腳本，提出了針對運(yùn)輸網(wǎng)絡(luò)成本的多聯(lián)式遺傳算法。該算法在上層求解運(yùn)輸網(wǎng)絡(luò)模型的最優(yōu)解。通過實(shí)驗(yàn)仿真，結(jié)果顯示：在處理運(yùn)輸網(wǎng)絡(luò)成本過程中，多聯(lián)式遺傳算法誤差率有效的控制在8%以內(nèi)；相比傳統(tǒng)遺傳算法，多聯(lián)式遺傳算法經(jīng)過AON路徑優(yōu)化后的貨物流量分配加速了算法的收斂效率，可以產(chǎn)生一個相對良好的運(yùn)輸路徑網(wǎng)絡(luò)，且性能穩(wěn)定。

遺傳算法；網(wǎng)絡(luò)子節(jié)點(diǎn)；運(yùn)輸網(wǎng)絡(luò)；運(yùn)輸成本

目前港口發(fā)展越來越依賴于腹地內(nèi)接入的公路、鐵路和水路系統(tǒng)，解決不斷增加的運(yùn)輸需求量是貨運(yùn)業(yè)的主要任務(wù)[1]。根據(jù)運(yùn)輸路徑和貨運(yùn)量模式的變化，終端網(wǎng)絡(luò)必須適應(yīng)地理信息和商品類型，在處理設(shè)備和信息技術(shù)不斷創(chuàng)新的環(huán)境下，新的網(wǎng)絡(luò)服務(wù)逐漸轉(zhuǎn)化為多聯(lián)式運(yùn)輸服務(wù)產(chǎn)業(yè)[2]?，F(xiàn)有關(guān)于運(yùn)輸網(wǎng)絡(luò)成本的研究方法主要集中在蟻群算法[3]、啟發(fā)式算法[4]和退火算法[5]。在考慮綜合調(diào)度和運(yùn)輸安排的終端網(wǎng)絡(luò)設(shè)計中，遺傳算法在求解運(yùn)輸成本時更具有靈活性[6]。本研究利用運(yùn)輸網(wǎng)絡(luò)子節(jié)點(diǎn)連接構(gòu)建虛擬網(wǎng)絡(luò)設(shè)計的新模式，模式之間的差異可以意味著終端的不同用途，這取決于運(yùn)輸網(wǎng)絡(luò)的的位置。通過建立不同的運(yùn)輸鏈接廣義成本，提出了基于多式聯(lián)遺傳算法求解運(yùn)輸網(wǎng)絡(luò)模型的最優(yōu)解，兼顧了終端的規(guī)模、多種貨物和多種模式的經(jīng)濟(jì)成本。

1 運(yùn)輸成本模型

1.1 系統(tǒng)建模

為了滿足運(yùn)輸?shù)男枨?，主要通過構(gòu)建多模式的識別網(wǎng)絡(luò)來最大限度地降低網(wǎng)絡(luò)成本[7]。通常假設(shè)整個網(wǎng)絡(luò)的需求是固定的，多模式識別網(wǎng)絡(luò)的成本一般包括外包運(yùn)輸成本、庫存成本和外部成本等[8]。一般與交通政策有關(guān)的地方政府投資與發(fā)展財政手段可能會對終端網(wǎng)絡(luò)結(jié)構(gòu)產(chǎn)生進(jìn)一步影響，例如對投資進(jìn)行補(bǔ)貼或運(yùn)輸價格[9]。探試算法的解決方案通常會限制商品和服務(wù)網(wǎng)絡(luò)最優(yōu)化模型的靈活性，同時也不能同時解決運(yùn)輸貨物數(shù)量和目的地定位的問題，故因此本文將采用多聯(lián)式遺傳算法（Mt-GA）來解決運(yùn)輸成本的問題。

基于Mt-GA算法的運(yùn)輸成本模型由4個模塊組成：1）始發(fā)地和目的地（OD）的需求模塊矩陣嵌入；2）區(qū)域地理信息和網(wǎng)絡(luò)的供給模塊共享數(shù)據(jù)庫；3）優(yōu)化最優(yōu)化模塊關(guān)于目的地的貨運(yùn)容量和地理位置的最優(yōu)解以使廣義成本最小化；4）相關(guān)政策策略包，主要將外部政策的變化納入模型考慮之中。其具體表示如圖1所示。

圖1 模型的總體框架

基于地理信息系統(tǒng)（GIS）的多式聯(lián)運(yùn)貨物運(yùn)輸網(wǎng)絡(luò)在CAD環(huán)境中通過使用“虛擬網(wǎng)絡(luò)”建模實(shí)現(xiàn)[10]。3種運(yùn)輸方式（公路，鐵路，內(nèi)河航運(yùn)）的基礎(chǔ)設(shè)施網(wǎng)絡(luò)通過子節(jié)點(diǎn)連接，每個終端的聯(lián)運(yùn)由終端提供的轉(zhuǎn)運(yùn)服務(wù)指定。

1.2 廣義成本

所謂的廣義成本是基于每種運(yùn)輸模式和轉(zhuǎn)運(yùn)模式的成本框架來計算每單位商品的運(yùn)輸成本。4個不同的成本函數(shù)被應(yīng)用于計算4種類型鏈路的廣義成本，即路線運(yùn)輸?shù)膹V義成本、轉(zhuǎn)運(yùn)環(huán)節(jié)的廣義成本、進(jìn)/出鏈路的廣義成本、始發(fā)地/目的地運(yùn)輸鏈接的廣義成本。通常在虛擬網(wǎng)絡(luò)中對應(yīng)相應(yīng)的運(yùn)輸鏈接模式來計算廣義成本。

1）路線運(yùn)輸?shù)膹V義成本：在地理路線x上運(yùn)輸一單元商品p的廣義成本計算公式表達(dá)如下：

其中，κα表示單位運(yùn)輸成本，τp是與運(yùn)輸?shù)臅r間成本相關(guān)的商品p的單位運(yùn)輸成本，sx是路線x的長度，va是運(yùn)輸?shù)钠骄俣取?/p>

2）轉(zhuǎn)運(yùn)環(huán)節(jié)的廣義成本：在轉(zhuǎn)運(yùn)環(huán)節(jié)h運(yùn)輸一單元商品p的廣義成本計算公式表達(dá)如下：

其中，ωh表示轉(zhuǎn)運(yùn)環(huán)節(jié)的單位管理成本，vh表示超過轉(zhuǎn)運(yùn)環(huán)節(jié)h成本的損耗，表示經(jīng)由轉(zhuǎn)運(yùn)鏈路的終端t和特定的傳輸模式之間由轉(zhuǎn)運(yùn)環(huán)節(jié)所產(chǎn)生的各種成本的參數(shù)。由于終端操作和管理效率在每個終端存在差異，即使它們具有相同的規(guī)模，并具有相同的運(yùn)輸量，不同的終端其轉(zhuǎn)運(yùn)費(fèi)用也可能存在差異。

3）進(jìn)/出鏈路的廣義成本：在發(fā)貨/進(jìn)貨鏈路環(huán)節(jié)e運(yùn)輸一單元商品p的廣義成本計算公式表達(dá)如下：

其中，κγ表示與模式相關(guān)的進(jìn)/出鏈路單位運(yùn)輸成本，se表示進(jìn)/出鏈路e之間的距離，υγ表示進(jìn)/出鏈路的平均速度，εo表示特定區(qū)域o和線路網(wǎng)絡(luò)之間由進(jìn)/出鏈路環(huán)節(jié)所產(chǎn)生的各種成本的參數(shù)。

4）始發(fā)地/目的地運(yùn)輸鏈接廣義成本：在始發(fā)地/目的地運(yùn)輸鏈路環(huán)節(jié)g運(yùn)輸一單元商品p的廣義成本計算公式表達(dá)如下：

其中，κβ表示與模式相關(guān)的始發(fā)地/目的地運(yùn)輸鏈路的單位運(yùn)輸成本，sg表示始發(fā)地/目的地運(yùn)輸鏈路g之間的距離，υβ表示始發(fā)地/目的地運(yùn)輸鏈路的平均速度，εot表示特定區(qū)域o和t之間的之間由始發(fā)地/目的地運(yùn)輸鏈路環(huán)節(jié)所產(chǎn)生的各種成本的參數(shù)。

2 多聯(lián)式遺傳算法

2.1 路徑流量分配

為了計算運(yùn)輸鏈接建立的廣義成本模型，利用全有或全無的算法（AON）用于路徑流量的分配[11]，其中廣義成本分為兩部分：1）與距離相關(guān)的部分，包括原點(diǎn)和目的地距離之間的維護(hù)、車輛的修理和燃料的成本；2）與時間相關(guān)的部分，它主要根據(jù)不同的運(yùn)輸方式，由運(yùn)輸經(jīng)營者承擔(dān)折舊、利息、稅收、執(zhí)照和許可證的辦理等。原則上，AON算法用于滿足每組目的地配對分配線路的需求，每組目的地配對線路滿足其目的地配對擁有最低廣義路線成本。上述的AON算法存在兩個限制：1）待選路徑的貨運(yùn)量被假定為無約束；2）沒有將路線選擇者的異質(zhì)性考慮在內(nèi)。存在隨機(jī)性和非隨機(jī)性的獲能分配算法和平衡算法通常應(yīng)用于貨物運(yùn)輸?shù)木W(wǎng)絡(luò)規(guī)劃當(dāng)中[12]。

出于以下3點(diǎn)原因，本文將選擇AON算法進(jìn)行鏈路分配：1）在貨運(yùn)量充足的既定假設(shè)之下，由AON算法獲得的結(jié)果同用戶平衡算法獲得的結(jié)果極有可能是相同的，同時由于AON算法不需要迭代來達(dá)到平衡[13]，使用AON算法大大節(jié)約了計算的時間；2）隨機(jī)參數(shù)是針對每種類型的鏈路來定義。無需在分配過程中引入額外的隨機(jī)參數(shù)[14]，因此隨機(jī)算法并不適用；3）考慮到終端的規(guī)模經(jīng)濟(jì)，成本函數(shù)可以是凹的，分配方案可能無法保持平衡狀態(tài)。

2.2 多聯(lián)式遺傳算法優(yōu)化

出于上述的考慮，文中選擇在Dijkstra方法的基礎(chǔ)上衍生出的AON算法用于路徑選擇和流量分配[15]。AON算法在TransCAD軟件平臺上運(yùn)行。由于待選鏈路數(shù)量眾多并且終端由于規(guī)模經(jīng)濟(jì)而造成成本函數(shù)的非凸性，因此選取遺傳算法（GA）在上層求解最優(yōu)解問題。模型中使用的遺傳算法是在Michalewicz開發(fā)的編程邏輯基礎(chǔ)上使用GISDK的二次開發(fā)環(huán)境中的自腳本[16]，其具體的迭代過程描述如下：

1）內(nèi)循環(huán)：流量分配

步驟1：根據(jù)具體線路情況啟動網(wǎng)絡(luò)功能；

步驟2：加載解決方案j，生成運(yùn)載網(wǎng)絡(luò)的代，同時根據(jù)之前定義的流量相關(guān)成本函數(shù)來計算各終端的轉(zhuǎn)運(yùn)成本；

步驟3：運(yùn)行多種貨物種類的AON流量分配；

步驟4：更新每個終端基于此步驟分配給終端的流量轉(zhuǎn)運(yùn)成本以及終端成本流量運(yùn)算公式；

步驟5：迭代步驟3和步驟4，直到兩個相鄰的運(yùn)行轉(zhuǎn)運(yùn)成本之差小于在每一個終端的預(yù)定義的公差；

步驟6：如果j+1=這一代解決方案的數(shù)量，然后轉(zhuǎn)至外循環(huán)的步驟2；

步驟7：加載第i代的解決方案j+1到網(wǎng)絡(luò)上，然后進(jìn)入步驟3。

2）外循環(huán)：優(yōu)化

步驟1：生成第一代的解決方案，轉(zhuǎn)到內(nèi)循環(huán)第一代的解決方案1；

步驟2：篩選出這一代的最優(yōu)解決方案；

步驟3：如果i+1的數(shù)量=迭代的數(shù)量，則直接運(yùn)行步驟6；

步驟4：應(yīng)用遺傳算法進(jìn)行“均勻變異”和“精英”并生成下一代；

步驟5：迭代步驟2至步驟5；

步驟6：輸出所有迭代中最優(yōu)的解決方案，算法結(jié)束。

3 算例模擬

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

本研究中，針對運(yùn)輸網(wǎng)絡(luò)計算運(yùn)輸成本均在Windows XP操作系統(tǒng)下進(jìn)行，數(shù)值仿真計算運(yùn)用Matlab 7.0運(yùn)行GISDK的二次開發(fā)環(huán)境中的自腳本，借助地理信息系統(tǒng)（GIS）在TransCAD軟件上使用AON算法模擬港口集裝箱貨物吞吐量運(yùn)輸路線位置信息數(shù)據(jù)。

設(shè)該港口承擔(dān)的集裝箱運(yùn)輸任務(wù)包含以上4個廣義成本，每個廣義成本的主要參數(shù)如表1所示。運(yùn)輸公司為單個集裝箱運(yùn)輸成本提供總額的上限為1萬元，運(yùn)輸總時間要求在5天內(nèi)完成。同時，運(yùn)輸公司對運(yùn)輸成本提出的要求為：①集裝箱在運(yùn)輸過程中必須在規(guī)定的時間內(nèi)完成，否則在最遲結(jié)束時段內(nèi)將剩余運(yùn)輸工作外包；②盡量降低運(yùn)輸公司為集裝箱運(yùn)輸支出的成本。

表1 項(xiàng)目的主要參數(shù)

3.2 計算結(jié)果

利用多聯(lián)式遺傳算法對運(yùn)輸成本進(jìn)行求解，將運(yùn)輸總時間根據(jù)成本類型劃分為4個時段，每個段均通過運(yùn)輸鏈路環(huán)節(jié)進(jìn)行連接，建立運(yùn)輸成本的最優(yōu)化廣義成本模型。為了反映多聯(lián)式遺傳算法對運(yùn)輸成本的優(yōu)化特點(diǎn)，運(yùn)用Matlab分別計算4種關(guān)于運(yùn)輸網(wǎng)絡(luò)的廣義成本，結(jié)果如圖2所示。

由圖2可得，運(yùn)輸過程中，路線廣義成本在第一天內(nèi)出現(xiàn)最高值，而轉(zhuǎn)運(yùn)廣義成本則隨著時間的推移逐漸變小，這是由于集裝箱在運(yùn)輸?shù)那捌谥饕蕾嚦杀酒叩钠囘\(yùn)輸，但相同的集裝箱在經(jīng)歷長途運(yùn)輸間接到短途運(yùn)輸過程中，裝運(yùn)單位商品會隨著時間的推移運(yùn)輸成本進(jìn)行分?jǐn)?；鏈路廣義成本在運(yùn)輸?shù)闹衅诔霈F(xiàn)最高值，而鏈接廣義成本則在前期和末期出現(xiàn)最高值，這是因?yàn)榘l(fā)貨/進(jìn)貨鏈路環(huán)節(jié)對貨物進(jìn)行整體的集中和分配，提高了商品的綜合調(diào)度效率，降低了線路網(wǎng)絡(luò)之間的各種成本，但在始發(fā)地和目的地對集裝箱的運(yùn)輸成本則表現(xiàn)出相反的效果。

圖2 各廣義運(yùn)輸成本的蒙特卡羅模擬最優(yōu)化結(jié)果

3.3 性能分析

為了比較多聯(lián)式遺傳算法和遺傳算法在處理運(yùn)輸成本計算上的差異，多聯(lián)式遺傳算法在AON算法的基礎(chǔ)上結(jié)合了運(yùn)輸路線信息對運(yùn)輸成本進(jìn)行了處理，通過多種貨物種類的AON流量分配構(gòu)建了商品最優(yōu)運(yùn)輸路徑。在規(guī)定的運(yùn)輸時間內(nèi)的商品發(fā)貨與接收利用運(yùn)輸網(wǎng)絡(luò)終端成本流量進(jìn)行數(shù)據(jù)運(yùn)算，具體的廣義成本誤差對比如表2所示。

由表2可得，不同的運(yùn)輸成本類型的模擬值誤差率呈現(xiàn)明顯差異，多聯(lián)式遺傳算法的誤差率有效的控制在8%內(nèi)，而遺傳算法的誤差率均較高。同時，對多聯(lián)式遺傳算法和遺傳算法進(jìn)行60次循環(huán)迭代，比較其魯棒穩(wěn)定性和收斂速度，如圖3所示。

表2 廣義成本誤差對比

圖3 魯棒穩(wěn)定和收斂速度對比

由圖3可得，（a）中，多聯(lián)式遺傳算法和遺傳算法的魯棒穩(wěn)定性差異并不大，而（b）中，收斂曲線可以看到，多聯(lián)式遺傳算法收斂速度非?？欤沂諗空`差均表現(xiàn)為正向，即經(jīng)過AON路徑優(yōu)化后的貨物流量分配加速了算法的收斂效率。因此可以得出結(jié)論：基于多聯(lián)式遺傳算法的運(yùn)輸成本可以產(chǎn)生一個相對良好的運(yùn)輸路徑網(wǎng)絡(luò)，且性能穩(wěn)定。

4 結(jié) 論

本研究利用運(yùn)輸網(wǎng)絡(luò)子節(jié)點(diǎn)構(gòu)建了4種運(yùn)輸鏈接模式的廣義成本，通過AON算法構(gòu)造了多聯(lián)式運(yùn)輸網(wǎng)絡(luò)貨物路徑流量的分配的內(nèi)循環(huán)模擬，結(jié)合遺傳算法對運(yùn)輸網(wǎng)絡(luò)廣義成本進(jìn)行計算的外循環(huán)優(yōu)化，提出了針對運(yùn)輸網(wǎng)絡(luò)成本計算的多聯(lián)式遺傳算法。該算法兼顧了空間距離成本和不同的運(yùn)輸方式時間相關(guān)成本，通過遺傳算法粒子群尋優(yōu)的方式篩選出待選鏈路，通過鏈接運(yùn)輸網(wǎng)絡(luò)終端節(jié)點(diǎn)的方式計算轉(zhuǎn)運(yùn)成本。借助地理信息系統(tǒng)（GIS）在TransCAD軟件上使用AON算法模擬港口集裝箱貨物吞吐量運(yùn)輸路線位置信息數(shù)據(jù)。算例結(jié)果分析可得，通過多種貨物種類的AON流量分配構(gòu)建商品最優(yōu)運(yùn)輸路徑可以有效的控制計算誤差率，而多聯(lián)式遺傳算法相比傳統(tǒng)的遺傳算法收斂速度更快。

[1]高軍，劉曉蕾，冀松婭.軍事物流系統(tǒng)中定位-運(yùn)輸路線安排模型及算法 [J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2012，42（19）:152-159.

[2]賴志柱.和聲搜索算法優(yōu)化多時間窗多式聯(lián)運(yùn)運(yùn)輸方案[J].計算機(jī)應(yīng)用，2013，33（9）:2640-2642.

[3]李英俊，陳志祥.基于改進(jìn)蟻群算法的一類運(yùn)輸能力約束的生產(chǎn)-運(yùn)輸批量問題求解 [J].工業(yè)工程，2012，15（6）:119-125.

[4]李莉英，王勇.一般運(yùn)輸成本結(jié)構(gòu)下渠道協(xié)調(diào)的成本效應(yīng)分析[J].計算機(jī)集成制造系統(tǒng)，2013，19（8）: 2090-2096.

[5]程博，楊育，劉愛軍，等.基于遺傳模擬退火算法的大件公路運(yùn)輸路徑選擇優(yōu)化[J].計算機(jī)集成制造系統(tǒng)，2013，19（4）:879-887.

[6]楊娟，郭海湘，楊文霞，等.基于MATLAB的GUI設(shè)計車輛路徑問題的仿真優(yōu)化平臺[J].系統(tǒng)仿真學(xué)報，2012，24（3）:722-727.

[7]倪玲霖，史峰.多分配快遞軸輻網(wǎng)絡(luò)的樞紐選址與分配優(yōu)化方法[J].系統(tǒng)工程理論與實(shí)踐，2012，32（2）:441-448.

[8]張秀玲，趙文保，張少宇，等.基于改進(jìn)TS云推理網(wǎng)絡(luò)的板形模式識別方法 [J].中南大學(xué)學(xué)報：自然科學(xué)版，2013，44（2）:580-586.

[9]吳小珍，李表奎，董紫嫣，等.基于SPFA的整車物流運(yùn)輸線路及運(yùn)輸方式的優(yōu)化及求解[J].物流工程與管理，2014（5）:176-178.

[10]江曉鵬，方源敏，黃貝瑩.ArcGIS環(huán)境下CAD數(shù)據(jù)轉(zhuǎn)換模型構(gòu)建[J].昆明理工大學(xué)學(xué)報：自然科學(xué)版，2014（4）:37-42.

[11]李雙琳，馬祖軍.震后交通管制下基于用戶均衡條件的救災(zāi)路徑選擇[J].管理工程學(xué)報，2014，28（3）: 148-155.

[12]諶永榮，黃崇超.非平衡交通分配的離散網(wǎng)絡(luò)平衡設(shè)計的遺傳算法[J].華中師范大學(xué)學(xué)報：自然科學(xué)版，2011，45（2）:189-192.

[13]劉燦燦，張衛(wèi)民，駱志剛.基于路徑平衡的工作流費(fèi)用優(yōu)化方法[J].軟件學(xué)報，2013（6）:1207-1221.

[14]譚文安，路廣振，孫勇.基于并行分層的工作流調(diào)度優(yōu)化算法 [J].計算機(jī)集成制造系統(tǒng)，2014，20（5）:1070-1077.

[15]司維超，齊玉東，韓維.基于融合Dijkstra的凸殼算法的艦載機(jī)機(jī)庫調(diào)運(yùn)規(guī)劃[J].系統(tǒng)工程與電子技術(shù)，2015，37（3）:583-588.

[16]郭婉青，葉東毅.基于帝國分裂的帝國競爭算法優(yōu)化[J].計算機(jī)應(yīng)用，2013，33（S2）:86-90.

Research on cost of transport network based on multi-type genetic algorithm

YANG Lu，TANG Yong-jun
（Business School，Hohai University，Nanjing 211100，China）

Aiming at the multi-modal transportation network costs，this study by using a virtual network modeling considering the road，rail and inland shipping child node network connection，transport links and builds four models to calculate the generalized cost.Use all or nothing algorithm （AON）for dispensing flow path using GISDK the secondary development environment programming logic developed on the basis of Michalewicz created from a script，a multi-connected transportation network costs for genetic algorithm.The algorithm for solving the optimal solution in the upper transport network model. The simulation results show that:Processing costs during transportation network，multi-type genetic algorithm error rate effectively controlled within 8%；compared to traditional genetic algorithm，multitype genetic algorithm through distribution of goods traffic AON path optimized to accelerate the convergence efficiency of the algorithm，It can produce a relatively good transportation route network，and stable performance.

GA；child node network；transportation network；transportation costs

TN02

A

1674-6236（2017）09-0153-04

2016-08-04稿件編號：201608035

國家自然科學(xué)基金資助項(xiàng)目（71102072）；國家社會科學(xué)基金資助項(xiàng)目（15BGL054）

楊 璐（1992—），女，山東日照人，碩士研究生。研究方向：環(huán)境會計。