裴驍，蘆有鵬，劉斌，羅海燕，許乃萱

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院,甘肅 蘭州 730070)

多式聯(lián)運(yùn)作為一種高效的集約型運(yùn)輸方式，能夠?qū)崿F(xiàn)各種運(yùn)輸方式和資源的互補(bǔ)，從而達(dá)到提升運(yùn)輸效率的目的[1].就目前的研究狀況而言，多式聯(lián)運(yùn)問題研究的核心是如何在約束環(huán)境下選擇最優(yōu)的路徑與運(yùn)輸方式的組合.Hao等[2]建立了貨物的運(yùn)輸時(shí)間、成本和質(zhì)量的均衡模型，并應(yīng)用動(dòng)態(tài)規(guī)劃的方法，獲得了路徑和運(yùn)輸方式的最優(yōu)組合策略.Li等[3]考慮了每個(gè)節(jié)點(diǎn)發(fā)生擴(kuò)建的可能，以總費(fèi)用最少為目標(biāo)建立了模型，并設(shè)計(jì)遺傳算法(genetic algorithm，GA)進(jìn)行求解.She等[4]建立了綜合約束條件下的模型，并設(shè)計(jì)了蟻群算法(ant colony optimization，ACO)進(jìn)行求解.Teng等[5]分析了碳成本對(duì)路線選擇的影響，建立了考慮碳成本的路徑選擇模型，并對(duì)運(yùn)力限制等約束進(jìn)行了分析和探討.Chang等[6]考慮了路徑及節(jié)點(diǎn)上的風(fēng)險(xiǎn)成本，建立了危險(xiǎn)品多式聯(lián)運(yùn)的多目標(biāo)優(yōu)化模型，并設(shè)計(jì)了相應(yīng)算法，Lei等[7]將粒子群算法和蟻群算法算法結(jié)合，求解基于運(yùn)輸成本、時(shí)間和風(fēng)險(xiǎn)的決策優(yōu)化模型，Zhang等[8]將遺傳算法與模擬退火算法結(jié)合起來，求解了以可靠性最大、總成本最小的雙目標(biāo)優(yōu)化模型.何方國等[9]針對(duì)各類網(wǎng)絡(luò)最短路問題，設(shè)計(jì)在遺傳算法中加入退火罰函數(shù)算子，通過溫度動(dòng)態(tài)調(diào)節(jié)對(duì)不可行解的懲罰力度.王德東[10]、趙祎[11]等則針對(duì)隨機(jī)環(huán)境下的路徑選擇問題，設(shè)計(jì)了多層前向神經(jīng)網(wǎng)絡(luò)和遺傳算法的混合算法.

本文考慮了運(yùn)輸過程中的規(guī)模效應(yīng)，采用連續(xù)分段線性函數(shù)的形式表示運(yùn)輸成本，在此基礎(chǔ)上建立了相應(yīng)的優(yōu)化模型，通過懲罰函數(shù)的形式將目標(biāo)函數(shù)進(jìn)行簡(jiǎn)化，在此基礎(chǔ)上設(shè)計(jì)了GA-ACO混合算法進(jìn)行求解，并將混合算法與GA、ACO算法分別單獨(dú)進(jìn)行比較，驗(yàn)證了算法的可行性和有效性，并進(jìn)一步通過混合算法探討了不同約束環(huán)境下的路徑選擇模式.

1 問題描述與建模

1.1 模型假設(shè)

文中以內(nèi)陸城市為研究對(duì)象，只考慮公路、鐵路2種運(yùn)輸模式，且任意兩節(jié)點(diǎn)之間只能采用2種運(yùn)輸方式中的一種；運(yùn)輸方式的轉(zhuǎn)換只能發(fā)生在節(jié)點(diǎn)處，除了O、D點(diǎn)，每個(gè)節(jié)點(diǎn)均可以進(jìn)行運(yùn)輸方式的轉(zhuǎn)換，但每個(gè)節(jié)點(diǎn)最多只能進(jìn)行一次中轉(zhuǎn)；承運(yùn)人每次只承擔(dān)一個(gè)物流任務(wù)，且運(yùn)輸任務(wù)在中途不能分割；在途時(shí)間均與路線長度相關(guān)，鐵路運(yùn)輸受到時(shí)刻表的限制，有規(guī)定的到發(fā)時(shí)間，公路運(yùn)輸則無此項(xiàng)約束；轉(zhuǎn)運(yùn)成本及轉(zhuǎn)運(yùn)時(shí)間均與運(yùn)量成線性關(guān)系，且所有節(jié)點(diǎn)設(shè)施均滿足轉(zhuǎn)運(yùn)過程的要求.

1.2 模型描述

假設(shè)存在無向圖G=(V,E,K),其中V是運(yùn)輸網(wǎng)絡(luò)的節(jié)點(diǎn)集合，E為運(yùn)輸路段的集合，K則為運(yùn)輸方式集合，存在運(yùn)量為q的貨物需從起點(diǎn)O運(yùn)送到終點(diǎn)D.

?(i,j)∈E,i∈V,k∈K

(5)

1.3 模型轉(zhuǎn)化

上述模型為存在非線性約束的單目標(biāo)優(yōu)化模型，為了進(jìn)一步簡(jiǎn)化模型，可以將約束(4)轉(zhuǎn)化為懲罰因子，將其添加到目標(biāo)函數(shù)中，從而減少一個(gè)約束，如式(10)所示：

約束條件為(2)～(3)以及(5)～(9)，由于約束(5)仍為非線性約束，采用普通的商業(yè)軟件求解時(shí)求解過程會(huì)變得異常復(fù)雜，從而考慮設(shè)計(jì)智能算法對(duì)目標(biāo)進(jìn)行求解[12].

2 混合算法設(shè)計(jì)

多式聯(lián)運(yùn)路徑規(guī)劃問題的實(shí)質(zhì)是路徑與運(yùn)輸方式的組合優(yōu)化問題[13].多數(shù)文獻(xiàn)通過染色體將路徑與運(yùn)輸方式編碼后計(jì)算適應(yīng)度值，但在擇優(yōu)過程中沒有任何引導(dǎo)，整個(gè)計(jì)算過程實(shí)際是路徑與運(yùn)輸方式的隨機(jī)匹配，容易陷入局部最優(yōu).針對(duì)上述問題，為確保求解精度與效率，本文設(shè)計(jì)了GA-ACO混合算法，結(jié)合單蟻群算法在路徑尋優(yōu)問題的優(yōu)勢(shì)和其在初始階段由于信息素積累較少而導(dǎo)致收斂速度慢的特點(diǎn)，混合算法首先使用遺傳算法循環(huán)多次后生成若干較優(yōu)個(gè)體，以此作為蟻群算法中先驗(yàn)矩陣的初始參數(shù)，然后人工螞蟻依據(jù)各節(jié)點(diǎn)路徑先驗(yàn)矩陣和路徑信息素矩陣生成選擇概率，采用輪盤賭的方法選取所要到達(dá)的下個(gè)節(jié)點(diǎn).同時(shí)根據(jù)多式聯(lián)運(yùn)網(wǎng)絡(luò)的特點(diǎn)，設(shè)置相應(yīng)的運(yùn)輸方式先驗(yàn)矩陣和信息素矩陣，為路徑匹配合適的運(yùn)輸方式，同時(shí)不斷更新兩類信息素矩陣，為下一代人工螞蟻的優(yōu)選提供依據(jù)直至終點(diǎn).混合算法流程圖如圖1所示.

圖1 混合算法流程Figure 1 Schematic diagram of hybrid algorithm flow

2.1 遺傳算法描述

染色體編碼：為了方便編碼解碼操作，整個(gè)網(wǎng)絡(luò)采用元胞數(shù)組的形式存儲(chǔ)，假設(shè)網(wǎng)絡(luò)中有n個(gè)城市節(jié)點(diǎn)，除了終點(diǎn)，其他節(jié)點(diǎn)均有后向節(jié)點(diǎn)，后向節(jié)點(diǎn)最多為m，設(shè)計(jì)元胞數(shù)組的大小為n*m，元胞數(shù)組第n行表示了第n個(gè)節(jié)點(diǎn)與其后向節(jié)點(diǎn)之間的關(guān)系，如第二行為{(3,5,6) (1,2) (3,2) (2,1)}，代表節(jié)點(diǎn)2的后向節(jié)點(diǎn)共有3個(gè)，分別是節(jié)點(diǎn)3、節(jié)點(diǎn)5和節(jié)點(diǎn)6，其中到節(jié)點(diǎn)3的公、鐵2種費(fèi)用分別為1和2，到節(jié)點(diǎn)5的分別為3和2，到節(jié)點(diǎn)6的則為2和1.文中采用實(shí)數(shù)編碼，設(shè)整個(gè)運(yùn)輸網(wǎng)絡(luò)有n個(gè)城市節(jié)點(diǎn)n∈V，整個(gè)染色體長度為2n-1，分為2個(gè)區(qū)域，第一區(qū)域是隨機(jī)生成的各個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)，長度為n；第二區(qū)域長度為n-1，在2種運(yùn)輸方式中隨機(jī)生成，代表n個(gè)節(jié)點(diǎn)間的n-1段路徑所采用的運(yùn)輸方式，染色體結(jié)構(gòu)如圖2所示.

圖2 染色體結(jié)構(gòu)Figure 2 Chromosome structure

解碼：針對(duì)第一區(qū)域的解碼，采用基于優(yōu)先級(jí)的染色體解碼[14]，從起點(diǎn)開始，比較其后向節(jié)點(diǎn)的優(yōu)先級(jí)，優(yōu)先級(jí)大的節(jié)點(diǎn)被選中，進(jìn)而將該后向節(jié)點(diǎn)作為新的起始節(jié)點(diǎn)，重復(fù)上述步驟，直到終點(diǎn).通過解碼操作，染色體的第一個(gè)區(qū)域?qū)⑸梢粭l運(yùn)輸路徑，由于每條染色體的優(yōu)先級(jí)均是隨機(jī)產(chǎn)生，故每條染色體對(duì)應(yīng)一條路徑，且如此編碼解碼的方式每次產(chǎn)生的路徑均為有效路徑，避免了因交叉變異等可能導(dǎo)致的不可行解，極大提升算法效率.

交叉：基于優(yōu)先級(jí)的交叉實(shí)質(zhì)是對(duì)優(yōu)先級(jí)進(jìn)行交叉，對(duì)被選父代的第一區(qū)域進(jìn)行部分一致交叉法[15]，染色體交叉過程如圖3所示.

變異：對(duì)染色體進(jìn)行雙點(diǎn)變異[16]，即隨機(jī)生成2個(gè)基因位，位于這2個(gè)基因位上的2個(gè)基因兩兩對(duì)換.

選擇：文中采用輪盤賭選擇法，適應(yīng)度值越高，被選擇的概率越大，故將適應(yīng)度函數(shù)標(biāo)定為目標(biāo)函數(shù)式(11)的倒數(shù)，即運(yùn)輸費(fèi)用，轉(zhuǎn)運(yùn)費(fèi)用以及懲罰費(fèi)用之和的倒數(shù)，總費(fèi)用越小，被選中的概率則越大.

2.2 雙信息素蟻群算法描述

圖3 交叉操作Figure 3 Cross operation

其中allowedk表示螞蟻可選節(jié)點(diǎn)或可選運(yùn)輸方式集合，α為信息素影響因子，表示螞蟻選擇節(jié)點(diǎn)或運(yùn)輸方式時(shí)對(duì)信息素的依賴程度；β為先驗(yàn)影響因子，表示蟻群對(duì)上代較好解的依賴程度[18]，ηij(t)為適應(yīng)度函數(shù)值，與遺傳算法所采用的適應(yīng)度函數(shù)計(jì)算方法一致.

隨著時(shí)間的增長，信息素濃度會(huì)隨之降低，其更新函數(shù)如式(13)所示.

τij(t+1)=(1-ρ)×τij(t)+Δτbest

(13)

其中τij(t)表示路徑(i,j)在t時(shí)刻的信息素強(qiáng)度，1-ρ表示信息素衰減程度，Δτbest取本次迭代的最好解的倒數(shù)，如此可保證信息素的增量取決于可行解的優(yōu)劣.

2.3 算法改進(jìn)策略

為避免蟻群算法搜索停滯，每條弧上的信息素須在區(qū)間(τmin,τmax)內(nèi)，采用式(14)～(15)來確定初始信息素的區(qū)間值[19].

同時(shí)為了避免蟻群算法在初始階段就因遺傳算法收斂至局部最優(yōu)而陷入局部最優(yōu)解，設(shè)計(jì)自適應(yīng)災(zāi)變算子[20]，在最大最小螞蟻的基礎(chǔ)下對(duì)信息素矩陣的值進(jìn)行適時(shí)調(diào)整，設(shè)ρ的初始值為0.1，當(dāng)算法求得的可行解在多次迭代內(nèi)沒有改進(jìn)時(shí)，采用以下規(guī)則對(duì)信息揮發(fā)因子進(jìn)行自適應(yīng)調(diào)整：

其中ρmin為設(shè)定的揮發(fā)因子的最小值，避免因ρ過小而影響算法的收斂速度.

3 算例測(cè)試

3.1 算例描述

現(xiàn)有如圖5的多式聯(lián)運(yùn)網(wǎng)絡(luò)，一批貨物由節(jié)點(diǎn)1運(yùn)送到節(jié)點(diǎn)35，各路段采用鐵路運(yùn)輸、公路運(yùn)輸?shù)木嚯x不同，且每個(gè)路段容量也有所不同，表1給出了所有路徑的之間不同運(yùn)輸方式的運(yùn)輸距離，括號(hào)里的數(shù)據(jù)為不同運(yùn)輸方式的最大容量.鐵路運(yùn)輸具有嚴(yán)格的行車計(jì)劃，不同節(jié)點(diǎn)有各自的出發(fā)時(shí)間，各節(jié)點(diǎn)的鐵路計(jì)劃出發(fā)時(shí)間如表2所示，由于考慮了“規(guī)模效應(yīng)”，隨著運(yùn)量增大，運(yùn)費(fèi)的單價(jià)隨之降低，包括運(yùn)量區(qū)間、運(yùn)費(fèi)單價(jià)以及換裝費(fèi)用等其他屬性則由表3給出.

圖4 城市節(jié)點(diǎn)連接圖Figure 4 City node connection diagram

3.2 算法測(cè)試

根據(jù)上述算法，本文設(shè)定相關(guān)算法參數(shù)如表4所示，考慮到遺傳算法及蟻群算法均屬于啟發(fā)式算法，收斂結(jié)果具有一定隨機(jī)性，由此本文在主頻2.3 GHz的i5筆記本平臺(tái)上使用MATLAB R2018a軟件對(duì)各算法分別運(yùn)行20次，取其中最好解及平均性能評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比.各算法迭代收斂對(duì)比圖如圖5所示，最好結(jié)果如表5所示.

表1 各路段鐵、公路距離及容量

表2 各節(jié)點(diǎn)列車計(jì)劃出發(fā)時(shí)間

表3 運(yùn)輸方式特征概括

表4 算法初始值

圖5 各算法收斂迭代圖Figure 5 Convergence iteration graph of each algorithm

表5 各算法求解結(jié)果Table 5 The result of each algorithm

通過表5及圖5-A對(duì)比可知，在其他外部條件相同的情況下，文中提出的混合算法同傳統(tǒng)單GA、ACO算法均能求得最優(yōu)解，運(yùn)輸方案最好路徑為1→2→8→9→13→24→30→32→34→35，最好運(yùn)輸方式搭配為鐵→鐵→鐵→鐵→鐵→公→公→鐵→鐵，但混合算法在求解準(zhǔn)確度上有顯著提高，平均解較GA算法優(yōu)化了約3.18%，較單ACO算法優(yōu)化了約1.38%；其次，混合算法解的平均偏差和最大偏差較單GA算法分別降低了約3.278%和15.534%，較單ACO算法分別降低了約1.410%和12.537%，說明算法在提高最優(yōu)解質(zhì)量的同時(shí)，對(duì)算法的穩(wěn)健性也有改善，最后，混合算法的平均收斂代數(shù)也較另外兩種算法有了較大提升.由此證明了混合算法收斂速度更快，且具有更高的準(zhǔn)確性，更好的穩(wěn)定性.

為了探討模型中相關(guān)條件對(duì)最終路徑選擇的影響以及測(cè)試算法效率，分別探討了改變運(yùn)到時(shí)限、容量約束以及運(yùn)輸量的情況下的最優(yōu)解.考慮托運(yùn)人對(duì)時(shí)間有不同要求，通過提前、延后貨物的運(yùn)到時(shí)限，探討模型對(duì)時(shí)間的敏感程度，求解結(jié)果如表6所示，算法詳細(xì)收斂情況如圖5-B.當(dāng)運(yùn)輸網(wǎng)絡(luò)某個(gè)節(jié)點(diǎn)的容量發(fā)生變化時(shí)，如由于擁堵等原因?qū)е履彻?jié)貨物發(fā)出受限(路徑容量減小)，或由于改擴(kuò)建等引起的節(jié)點(diǎn)容量增大等情況，求解結(jié)果如表7所示，算法迭代圖如圖6-C所示.當(dāng)托運(yùn)人與承運(yùn)人簽訂長期、定量合同時(shí)，承運(yùn)人會(huì)調(diào)整報(bào)價(jià)從而影響運(yùn)輸方案制定，即采用平均成本代替分段成本進(jìn)行計(jì)算，其結(jié)果如表8所示，算法迭代收斂圖如圖6-D所示.

圖6 不同網(wǎng)絡(luò)環(huán)境下各算法平均收斂代數(shù)Figure 7 Average convergence algebra for different networks

通過上述拓展結(jié)果對(duì)比發(fā)現(xiàn)，混合算法能夠?qū)δＰ椭懈黝愖兞康恼{(diào)整做出響應(yīng)并給出滿意解，且均能在循環(huán)約35次求得最優(yōu)解，可見文中構(gòu)建的模型可行，且最終選擇的運(yùn)輸方案與運(yùn)到時(shí)限、容量約束以及運(yùn)輸成本都具有密不可分的關(guān)系，所提出的算法有效且能夠快速收斂.

為了進(jìn)一步驗(yàn)證混合算法對(duì)網(wǎng)絡(luò)的適用性，文中保持網(wǎng)絡(luò)起點(diǎn)不變，多次改變終點(diǎn)，分別使用3種算法進(jìn)行求解，所求得結(jié)果如表9所示，其平均迭代次數(shù)則由圖7給出，可以看出當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)小于30時(shí)，單遺傳算法和單蟻群算法在收斂代數(shù)上略占優(yōu)勢(shì)，而混合算法由于前期的遺傳迭代操作，其收斂代數(shù)較高，但隨著網(wǎng)絡(luò)網(wǎng)絡(luò)復(fù)雜度增加，單遺傳算法和單蟻群算法的收斂代數(shù)隨之上升，而混合算法的收斂代數(shù)基本維持不變，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)大于30時(shí)，混合算法的平均收斂代數(shù)較單遺傳算法和單蟻群算法相比則有明顯的優(yōu)勢(shì).

表6 運(yùn)到時(shí)限約束改變情況下的混合算法求解結(jié)果

4 結(jié)論

本文考慮了運(yùn)輸經(jīng)濟(jì)的“規(guī)模效應(yīng)”，結(jié)合多式聯(lián)運(yùn)實(shí)際操作和客戶需求，采用連續(xù)分段線性函數(shù)表示運(yùn)輸費(fèi)用，建立了以運(yùn)輸費(fèi)用最小為目標(biāo)的組合優(yōu)化模型.并結(jié)合遺傳算法前期全局搜索能力好和蟻群算法后期利用正負(fù)反饋收斂能力強(qiáng)的特點(diǎn)，設(shè)計(jì)了雙信息素混合算法，用以搜索多式聯(lián)運(yùn)路徑和轉(zhuǎn)運(yùn)方式的合理搭配.為避免組合算法陷入局部最優(yōu)解，在蟻群尋優(yōu)過程中引入引入最大最小螞蟻策略和自適應(yīng)災(zāi)變因子，在保證種群多樣性的基礎(chǔ)上也提高了算法全局優(yōu)化能力.

表7 容量約束改變情況下的混合算法求解結(jié)果

表8 運(yùn)量變化的混合算法求解結(jié)果

表9 終點(diǎn)改變(網(wǎng)絡(luò)結(jié)構(gòu)變化)情況下的混合算法求解結(jié)果

通過算例分析可知，混合算法具有更快的收斂能力、更好的穩(wěn)定性和更高的準(zhǔn)確性，尤其對(duì)大型復(fù)雜網(wǎng)絡(luò)可保證算法的收斂代數(shù)不隨網(wǎng)絡(luò)的增大而急劇增加，為求解大型復(fù)雜網(wǎng)絡(luò)環(huán)境下多式聯(lián)運(yùn)路徑問題給出了參考.