唐 禎 陳 楓 傅志妍 谷朋飛

(重慶交通大學(xué)交通運(yùn)輸學(xué)院1) 重慶 400074) (重慶第二師范學(xué)院經(jīng)濟(jì)與工商管理學(xué)院2) 重慶 400067)

0 引 言

多式聯(lián)運(yùn)可以提高運(yùn)輸效率、降低物流成本并且減少環(huán)境污染，是一種高效的運(yùn)輸組織方式.多式聯(lián)運(yùn)路徑問(wèn)題是多式聯(lián)運(yùn)優(yōu)化研究的重要方向之一，其本質(zhì)上是最短路問(wèn)題的延伸與擴(kuò)展，但由于多式聯(lián)運(yùn)存在應(yīng)用環(huán)境復(fù)雜、牽扯主體較多、涉及約束多樣等特征，Dijkstra算法、標(biāo)號(hào)法等傳統(tǒng)最短路問(wèn)題方法難以直接用于解決多式聯(lián)運(yùn)路徑問(wèn)題，需要針對(duì)特定的研究?jī)?nèi)容設(shè)計(jì)優(yōu)化模型和算法.

在模型方面，現(xiàn)有研究的優(yōu)化目標(biāo)主要集中于經(jīng)濟(jì)成本最小、耗費(fèi)時(shí)間最短和碳排放總量最小.劉杰等[1]構(gòu)建了一個(gè)經(jīng)濟(jì)成本最小、碳排放總量最小的多目標(biāo)0-1規(guī)劃模型，其中經(jīng)濟(jì)成本考慮運(yùn)輸成本、裝卸轉(zhuǎn)運(yùn)成本、存儲(chǔ)成本以及運(yùn)輸弧段與代理商匹配關(guān)系的影響，碳排放量由運(yùn)輸、換裝過(guò)程的碳排放構(gòu)成.戶(hù)佐安等[2]構(gòu)建由多個(gè)決策主體目標(biāo)構(gòu)成的廣義費(fèi)用函數(shù)，并建立以廣義費(fèi)用最優(yōu)為目標(biāo)的多式聯(lián)運(yùn)路徑優(yōu)化模型，設(shè)計(jì)符合實(shí)際情況的算例，采用理想點(diǎn)法并借助LINGO軟件進(jìn)行求解，獲得不同權(quán)重組合下的多組全局最優(yōu)解，為不同決策主體提供了參考依據(jù).Bowen等[3]考慮到運(yùn)輸車(chē)輛容量限制和中間節(jié)點(diǎn)可裝卸貨物的情況，構(gòu)建了包含裝卸成本、轉(zhuǎn)運(yùn)成本和運(yùn)輸成本組成的經(jīng)濟(jì)成本最小為目標(biāo)的優(yōu)化模型.在優(yōu)化算法方面，現(xiàn)有研究大部分基于Dijkstra算法、圖論和啟發(fā)式算法.Hendrik等[4]采用一種動(dòng)態(tài)策略分析運(yùn)輸成本的變化，并設(shè)計(jì)了一種基于模擬退火的生成樹(shù)方法用于求解多階段最短路徑.熊桂武等[5]提出了時(shí)間窗約束下基于改進(jìn)遺傳算法的代理商、運(yùn)輸路徑，以及運(yùn)輸方式協(xié)同優(yōu)化的求解算法.Ayed等[6]在分析具有時(shí)間依賴(lài)的多式聯(lián)運(yùn)路徑問(wèn)題時(shí)，設(shè)計(jì)了基于改進(jìn)Dijkstra算法和蟻群算法相結(jié)合的求解算法.Maciek等[7]考慮到貨物運(yùn)輸中存在里程計(jì)價(jià)的方式，構(gòu)建了里程計(jì)價(jià)影響下的路徑優(yōu)化問(wèn)題，并提出了以最小化運(yùn)輸成本為優(yōu)化目標(biāo)的算法.

但是在當(dāng)前的主要研究中，多式聯(lián)運(yùn)路徑問(wèn)題多采用貨物在中轉(zhuǎn)節(jié)點(diǎn)裝卸轉(zhuǎn)運(yùn)完畢后立刻運(yùn)往下一節(jié)點(diǎn)的假設(shè)，但實(shí)際情況是鐵路、水路等運(yùn)輸方式多是按固定的時(shí)刻表發(fā)班(即班期)，考慮到這一情況的研究文獻(xiàn)較少.另外，由于貨物運(yùn)抵中轉(zhuǎn)節(jié)點(diǎn)時(shí)間存在不確定性，在非正常工作時(shí)間裝卸轉(zhuǎn)運(yùn)不可避免，而在非正常工作時(shí)間裝卸轉(zhuǎn)運(yùn)需額外支付相關(guān)費(fèi)用(即加班費(fèi)用)，這必然會(huì)對(duì)路徑選擇產(chǎn)生影響，現(xiàn)有研究尚未注意到這一點(diǎn).因此，本文統(tǒng)籌慮班期、加班費(fèi)用等多式聯(lián)運(yùn)實(shí)際存在的影響因素，建立以成本最小的為目標(biāo)的多式聯(lián)運(yùn)路徑優(yōu)化模型.由于班期的影響，傳統(tǒng)的多式聯(lián)運(yùn)路徑優(yōu)化算法不能直接應(yīng)用于本文提出的問(wèn)題.因此，本文設(shè)計(jì)不定長(zhǎng)度編碼的遺傳算法，并給出算例證明了算法的可行性和有效性.

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

多式聯(lián)運(yùn)網(wǎng)絡(luò)見(jiàn)圖1.在實(shí)際運(yùn)輸過(guò)程中，貨主往往對(duì)貨物抵達(dá)目的地有時(shí)間要求；公路、鐵路以及水路等運(yùn)輸方式一般按設(shè)定的班期進(jìn)行運(yùn)營(yíng)；當(dāng)貨物運(yùn)抵至某一節(jié)點(diǎn)時(shí)，若需要以另一種運(yùn)輸方式運(yùn)往下一節(jié)點(diǎn)，則會(huì)產(chǎn)生貨物裝卸轉(zhuǎn)運(yùn)費(fèi)用，如果運(yùn)抵時(shí)間處于工人非正常上班時(shí)間，就會(huì)產(chǎn)生加班費(fèi)用進(jìn)而影響整個(gè)貨物運(yùn)輸?shù)目傎M(fèi)用.

圖1 多式聯(lián)運(yùn)網(wǎng)絡(luò)

1.2 模型假設(shè)

1) 運(yùn)輸貨物單一且不可分割.

2) 不同運(yùn)輸方式之間的轉(zhuǎn)運(yùn)時(shí)間與成本已知.

3) 貨物運(yùn)抵節(jié)點(diǎn)時(shí)刻為裝卸轉(zhuǎn)運(yùn)開(kāi)始時(shí)刻.

4) 所有轉(zhuǎn)運(yùn)節(jié)點(diǎn)處裝卸工人正常上班時(shí)間段已知，加班薪資系數(shù)一定.

5) 貨物在裝卸轉(zhuǎn)運(yùn)完成后按所選運(yùn)輸方式最近班期開(kāi)始后一行程運(yùn)輸.

1.3 參數(shù)定義

設(shè)多式聯(lián)運(yùn)網(wǎng)絡(luò)為G=(N,E,M)；N為頂點(diǎn)集(節(jié)點(diǎn)o與節(jié)點(diǎn)d分別為起訖節(jié)點(diǎn)，o,d∈N)；E為邊集；M為運(yùn)輸方式集合，E={ei,j,a|i,j∈N,a∈M}；C為運(yùn)輸總費(fèi)用；ci,ja為從節(jié)點(diǎn)i到節(jié)點(diǎn)j采用運(yùn)輸方式a進(jìn)行運(yùn)輸?shù)倪\(yùn)輸費(fèi)用；θia,b為在節(jié)點(diǎn)i處正常工作時(shí)段由運(yùn)輸方式a轉(zhuǎn)為運(yùn)輸方式b的轉(zhuǎn)運(yùn)費(fèi)用；TiG為貨物從節(jié)點(diǎn)i的出發(fā)時(shí)刻，起點(diǎn)貨物出發(fā)時(shí)刻T0G已知；TiR為貨物到達(dá)節(jié)點(diǎn)i的時(shí)刻；δi為貨物在節(jié)點(diǎn)i完成裝卸轉(zhuǎn)運(yùn)的時(shí)刻；ti,ja為從節(jié)點(diǎn)i到節(jié)點(diǎn)j采用運(yùn)輸方式a進(jìn)行運(yùn)輸?shù)倪\(yùn)輸時(shí)間；τia,b為在節(jié)點(diǎn)i處由運(yùn)輸方式a轉(zhuǎn)為運(yùn)輸方式b的裝卸轉(zhuǎn)運(yùn)時(shí)間；α為裝卸轉(zhuǎn)運(yùn)加班薪資系數(shù)；ω為裝卸工人正常工作時(shí)間；TMAX為客戶(hù)要求貨物最遲送達(dá)時(shí)刻.

決策變量：

1.4 模型建立

(1)

當(dāng)貨物運(yùn)抵至某一節(jié)點(diǎn)i完成轉(zhuǎn)運(yùn)裝卸時(shí)刻為

(2)

(3)

節(jié)點(diǎn)i實(shí)際發(fā)生換裝費(fèi)用為

(4)

考慮加班費(fèi)用的多式聯(lián)運(yùn)路徑優(yōu)化模型(以上已給出約束不再在以下模型中重復(fù)給出)為

(5)

s.t.

(6)

(7)

(8)

(10)

式(6)確保每一節(jié)點(diǎn)最多有一次貨物運(yùn)出；式(7)與式(8)保證貨物運(yùn)輸是從節(jié)點(diǎn)o(貨物發(fā)運(yùn)地)運(yùn)出，運(yùn)抵節(jié)點(diǎn)d(貨物目的地)；式(9)為節(jié)點(diǎn)流量平衡關(guān)系；式(10)為貨物運(yùn)抵目的地最遲時(shí)刻約束.

2 求解算法

基于多種群、模擬退火策略，組合設(shè)計(jì)四種遺傳算法.其中對(duì)單個(gè)種群進(jìn)行選擇、交叉、變異操作的算法稱(chēng)之為單種群遺傳算法(GA)；對(duì)單個(gè)種群進(jìn)行選擇、交叉、退火式變異操作的算法稱(chēng)之為單種群模擬退火遺傳算法(SGA)；在單種群遺傳算法的基礎(chǔ)上采用多種群管理策略的算法稱(chēng)之為多種群遺傳算法(MGA)；在單種群模擬退火遺傳算法的基礎(chǔ)上采用多種群管理策略稱(chēng)之為多種群模擬退火遺傳算法(MSGA).

采用不定長(zhǎng)度的染色體編碼方式.個(gè)體由兩個(gè)染色體片段構(gòu)成，“染色體片段一”代表多式聯(lián)運(yùn)網(wǎng)絡(luò)中從起點(diǎn)到終點(diǎn)按順序經(jīng)歷的各個(gè)節(jié)點(diǎn)，用整數(shù)排列進(jìn)行編碼；“染色體片段二”代表各節(jié)點(diǎn)間的運(yùn)輸方式，用1、2、3進(jìn)行編碼(其中，1為公路運(yùn)輸(H)，2為鐵路運(yùn)輸(R)，3為水路運(yùn)輸(W)).以圖1的多式聯(lián)運(yùn)網(wǎng)絡(luò)為例，其編碼與解碼方式見(jiàn)圖2.

圖2 編碼與解碼

基于多式聯(lián)運(yùn)網(wǎng)絡(luò)路徑問(wèn)題的特點(diǎn)設(shè)計(jì)了種群初始化的方法.不考慮運(yùn)輸方式以權(quán)值隨機(jī)來(lái)生成與該網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣，利用floyd算法得到一條起訖點(diǎn)之間的最短路徑，針對(duì)最短路徑隨機(jī)生成節(jié)點(diǎn)間運(yùn)輸方式，形成初始種群新個(gè)體.

交叉運(yùn)算為對(duì)兩個(gè)染色體片段依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體.由于本文采用的是不定長(zhǎng)度染色體編碼機(jī)制，采用傳統(tǒng)的單點(diǎn)交叉或多點(diǎn)交叉策略進(jìn)行交叉操作，將導(dǎo)致非法路徑以較大的概率產(chǎn)生，影響整個(gè)算法的效能，因此需根據(jù)本文所述問(wèn)題的特點(diǎn)對(duì)傳統(tǒng)交叉方法進(jìn)行改進(jìn).

本文將染色體交叉操作的情景分為兩類(lèi)，第一類(lèi)為兩父輩個(gè)體染色體片段一具有相同節(jié)點(diǎn)(起訖點(diǎn)除外)；第二類(lèi)為兩父輩個(gè)體染色體片段一不具有相同節(jié)點(diǎn).

圖3 相同節(jié)點(diǎn)交叉

圖4 相同位置交叉

上述兩類(lèi)情景的交叉操作有可能導(dǎo)致子代染色體出現(xiàn)重復(fù)基因的情況，即運(yùn)輸路徑中出現(xiàn)了“圈”.而包含“圈”的運(yùn)輸路徑一定不是最短路徑，因此本文采用了刪除重復(fù)基因的方法，以消除路徑中的“圈”，提高算法效率.具體見(jiàn)圖5.

圖5 去圈操作

變異操作具體為從種群個(gè)體染色體片段一的基因(起訖點(diǎn)除外)中，隨機(jī)選取一點(diǎn)，再改變多式聯(lián)運(yùn)網(wǎng)絡(luò)的權(quán)值，利用floyd算法尋找從該點(diǎn)至終點(diǎn)的一條最短通路.染色體片段二根據(jù)染色體片段一的變異基因隨機(jī)補(bǔ)填有效基因來(lái)實(shí)現(xiàn)變異.具體變異操作見(jiàn)圖6.

圖6 變異規(guī)則

為了提高遺傳算法的效率，設(shè)計(jì)了退火式變異.即以一定的退火概率Pm來(lái)確定是否發(fā)生變異，表達(dá)式為

(11)

式中：Pm為接受變異概率；Cold為個(gè)體變異前的適應(yīng)值；Cnew為個(gè)體變異后的適應(yīng)值；W為退火溫度.

固體溫度將隨遺傳算法迭代次數(shù)增加而降溫為

(12)

式中：d為遺傳算法迭代次數(shù)；Wd為第d次迭代時(shí)的退火溫度；W0為初始溫度，設(shè)置第一代種群個(gè)體適應(yīng)值的方差為

(13)

多種群策略是進(jìn)化時(shí)每個(gè)種群都保持相對(duì)的獨(dú)立性，將同一代的最優(yōu)個(gè)體進(jìn)行交叉，生成新個(gè)體并計(jì)算適應(yīng)值，從局部最優(yōu)解、新個(gè)體適應(yīng)值、當(dāng)前全局最優(yōu)解中選出最優(yōu)解，更新全局最優(yōu)解，并將最優(yōu)個(gè)體保留至下一代種群，流程見(jiàn)圖7.

圖7 多種群策略流程

3 算例分析

根據(jù)Solomon’s Benchmark中C101案例的100個(gè)點(diǎn)數(shù)據(jù)[8]，構(gòu)造了9個(gè)不同規(guī)模的多式聯(lián)運(yùn)網(wǎng)絡(luò)，兩點(diǎn)之間距離取歐幾里得距離.不同運(yùn)輸方式之間的轉(zhuǎn)運(yùn)時(shí)間、轉(zhuǎn)運(yùn)成本見(jiàn)表1，各種運(yùn)輸方式的行駛速度、單位運(yùn)輸成本及發(fā)班時(shí)刻見(jiàn)表2，各節(jié)點(diǎn)之間的運(yùn)輸方式隨機(jī)給定.鑒于非正常工作時(shí)間裝卸轉(zhuǎn)運(yùn)費(fèi)用高昂，故取裝卸轉(zhuǎn)運(yùn)加班薪資系數(shù)α為2.在不同規(guī)模的網(wǎng)絡(luò)下對(duì)本文設(shè)計(jì)的四種算法進(jìn)行算法性能對(duì)比，四種算法參數(shù)設(shè)置相同，迭代次數(shù)均為100，種群規(guī)模均為100，交叉概率均為0.90，變異概率均為0.15，單種群模擬退火遺傳算法與多種群模擬退火遺傳算法不設(shè)置變異概率.實(shí)驗(yàn)平臺(tái)為CPU：Intel Core(i5)、內(nèi)存：8.0GB的筆記本計(jì)算機(jī)，編程軟件為Matlab2014b，運(yùn)行次數(shù)分別為20次.B為20次運(yùn)行結(jié)果中優(yōu)化目標(biāo)最低值，BAV為20次運(yùn)行結(jié)果的平均值，C表示20次運(yùn)行中第一次找到優(yōu)化目標(biāo)值的迭代次數(shù)的平均值，運(yùn)行結(jié)果見(jiàn)表3.

表1 換裝參數(shù)

表2 運(yùn)輸參數(shù)

由表3可知：

1) 針對(duì)小規(guī)模網(wǎng)絡(luò)，四種算法均能找到最優(yōu)解，而且隨著網(wǎng)絡(luò)規(guī)模逐漸增大，SGA算法的尋優(yōu)效果最好，其次是MSGA算法；

2) 對(duì)比分析4種算法的最優(yōu)值B，發(fā)現(xiàn)SGA算法的求解質(zhì)量明顯優(yōu)于其余三種算法；

3) 對(duì)比分析4種算法的平均最優(yōu)值BAV，發(fā)現(xiàn)在穩(wěn)定性方面，MSGA算法、SGA算法最優(yōu)，其次是MGA算法，最后為GA算法；

4) 對(duì)比分析4種算法尋優(yōu)平均迭代次數(shù)C，發(fā)現(xiàn)MSGA算法的尋優(yōu)速度最快，其次是SA算法.

綜上所述，SGA算法在求解本文所述問(wèn)題上綜合表現(xiàn)最優(yōu).

針對(duì)SGA算法，以50節(jié)點(diǎn)的網(wǎng)絡(luò)規(guī)模為例，參數(shù)設(shè)置中迭代次數(shù)為100，種群規(guī)模為100，變更交叉概率，運(yùn)行20次結(jié)果見(jiàn)表4.結(jié)果顯示當(dāng)交叉概率為0.8時(shí)，整體求解效果最好.

表4 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為50時(shí)不同交叉概率對(duì)比結(jié)果

交叉概率確定為0.8后，改變迭代次數(shù)I和種群規(guī)模Z，分別運(yùn)行20次，結(jié)果見(jiàn)表5.由表5可知：在最優(yōu)值B一定的情況下，如果迭代次數(shù)一定時(shí)，種群規(guī)模越大，其最優(yōu)解的平均值BAV越低(即求解質(zhì)量越高)，最后一代種群的平均適應(yīng)值A(chǔ)也會(huì)越來(lái)越低(即SGA算法的收斂性越快)；當(dāng)種群規(guī)模一定、迭代次數(shù)超過(guò)100時(shí)，迭代次數(shù)與算法求解質(zhì)量、收斂性之間未發(fā)現(xiàn)明顯相關(guān)聯(lián)系.

表5 Pc為0.8時(shí)不同代次數(shù)和種群規(guī)模對(duì)比結(jié)果

4 結(jié) 束 語(yǔ)

在實(shí)際多式聯(lián)運(yùn)中，加班費(fèi)用、班期約束和目的地時(shí)間窗約束是真實(shí)存在的，都會(huì)影響到運(yùn)輸路徑與方式的選擇，從而產(chǎn)生的運(yùn)輸費(fèi)用不同，費(fèi)耗時(shí)間不同，若不考慮這些影響因素，將使得優(yōu)化方案應(yīng)用效果劣化.本文考慮到加班費(fèi)用、班期和目的地時(shí)間窗對(duì)多式聯(lián)運(yùn)路徑與運(yùn)輸方式?jīng)Q策的影響，建立了以總費(fèi)用最低為目標(biāo)的多式聯(lián)運(yùn)路徑?jīng)Q策模型.結(jié)合模型特點(diǎn)，設(shè)計(jì)了求解該問(wèn)題四種遺傳算法策略，通過(guò)算例對(duì)給出的算法進(jìn)行對(duì)比，證明了算法的可行性和有效性，其中SGA算法在求解本文所述問(wèn)題上綜合表現(xiàn)最優(yōu).