加班費用影響下多式聯運路徑問題研究

唐 禎 陳 楓 傅志妍 谷朋飛

(重慶交通大學交通運輸學院1) 重慶 400074) (重慶第二師范學院經濟與工商管理學院2) 重慶 400067)

0 引 言

多式聯運可以提高運輸效率、降低物流成本并且減少環境污染，是一種高效的運輸組織方式.多式聯運路徑問題是多式聯運優化研究的重要方向之一，其本質上是最短路問題的延伸與擴展，但由于多式聯運存在應用環境復雜、牽扯主體較多、涉及約束多樣等特征，Dijkstra算法、標號法等傳統最短路問題方法難以直接用于解決多式聯運路徑問題，需要針對特定的研究內容設計優化模型和算法.

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

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

1 問題描述與建模

1.1 問題描述

多式聯運網絡見圖1.在實際運輸過程中，貨主往往對貨物抵達目的地有時間要求；公路、鐵路以及水路等運輸方式一般按設定的班期進行運營；當貨物運抵至某一節點時，若需要以另一種運輸方式運往下一節點，則會產生貨物裝卸轉運費用，如果運抵時間處于工人非正常上班時間，就會產生加班費用進而影響整個貨物運輸的總費用.

圖1 多式聯運網絡

1.2 模型假設

1) 運輸貨物單一且不可分割.

2) 不同運輸方式之間的轉運時間與成本已知.

3) 貨物運抵節點時刻為裝卸轉運開始時刻.

4) 所有轉運節點處裝卸工人正常上班時間段已知，加班薪資系數一定.

5) 貨物在裝卸轉運完成后按所選運輸方式最近班期開始后一行程運輸.

1.3 參數定義

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

決策變量：

1.4 模型建立

(1)

當貨物運抵至某一節點i完成轉運裝卸時刻為

(2)

(3)

節點i實際發生換裝費用為

(4)

考慮加班費用的多式聯運路徑優化模型(以上已給出約束不再在以下模型中重復給出)為

(5)

s.t.

(6)

(7)

(8)

(10)

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

2 求解算法

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

采用不定長度的染色體編碼方式.個體由兩個染色體片段構成，“染色體片段一”代表多式聯運網絡中從起點到終點按順序經歷的各個節點，用整數排列進行編碼；“染色體片段二”代表各節點間的運輸方式，用1、2、3進行編碼(其中，1為公路運輸(H)，2為鐵路運輸(R)，3為水路運輸(W)).以圖1的多式聯運網絡為例，其編碼與解碼方式見圖2.

圖2 編碼與解碼

基于多式聯運網絡路徑問題的特點設計了種群初始化的方法.不考慮運輸方式以權值隨機來生成與該網絡對應的鄰接矩陣，利用floyd算法得到一條起訖點之間的最短路徑，針對最短路徑隨機生成節點間運輸方式，形成初始種群新個體.

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

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

圖3 相同節點交叉

圖4 相同位置交叉

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

圖5 去圈操作

變異操作具體為從種群個體染色體片段一的基因(起訖點除外)中，隨機選取一點，再改變多式聯運網絡的權值，利用floyd算法尋找從該點至終點的一條最短通路.染色體片段二根據染色體片段一的變異基因隨機補填有效基因來實現變異.具體變異操作見圖6.

圖6 變異規則

為了提高遺傳算法的效率，設計了退火式變異.即以一定的退火概率Pm來確定是否發生變異，表達式為

(11)

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

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

(12)

式中：d為遺傳算法迭代次數；Wd為第d次迭代時的退火溫度；W0為初始溫度，設置第一代種群個體適應值的方差為

(13)

多種群策略是進化時每個種群都保持相對的獨立性，將同一代的最優個體進行交叉，生成新個體并計算適應值，從局部最優解、新個體適應值、當前全局最優解中選出最優解，更新全局最優解，并將最優個體保留至下一代種群，流程見圖7.

圖7 多種群策略流程

3 算例分析

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

表1 換裝參數

表2 運輸參數

由表3可知：

1) 針對小規模網絡，四種算法均能找到最優解，而且隨著網絡規模逐漸增大，SGA算法的尋優效果最好，其次是MSGA算法；

2) 對比分析4種算法的最優值B，發現SGA算法的求解質量明顯優于其余三種算法；

3) 對比分析4種算法的平均最優值BAV，發現在穩定性方面，MSGA算法、SGA算法最優，其次是MGA算法，最后為GA算法；

4) 對比分析4種算法尋優平均迭代次數C，發現MSGA算法的尋優速度最快，其次是SA算法.

綜上所述，SGA算法在求解本文所述問題上綜合表現最優.

針對SGA算法，以50節點的網絡規模為例，參數設置中迭代次數為100，種群規模為100，變更交叉概率，運行20次結果見表4.結果顯示當交叉概率為0.8時，整體求解效果最好.

表4 網絡節點數為50時不同交叉概率對比結果

交叉概率確定為0.8后，改變迭代次數I和種群規模Z，分別運行20次，結果見表5.由表5可知：在最優值B一定的情況下，如果迭代次數一定時，種群規模越大，其最優解的平均值BAV越低(即求解質量越高)，最后一代種群的平均適應值A也會越來越低(即SGA算法的收斂性越快)；當種群規模一定、迭代次數超過100時，迭代次數與算法求解質量、收斂性之間未發現明顯相關聯系.

表5 Pc為0.8時不同代次數和種群規模對比結果

4 結 束 語

在實際多式聯運中，加班費用、班期約束和目的地時間窗約束是真實存在的，都會影響到運輸路徑與方式的選擇，從而產生的運輸費用不同，費耗時間不同，若不考慮這些影響因素，將使得優化方案應用效果劣化.本文考慮到加班費用、班期和目的地時間窗對多式聯運路徑與運輸方式決策的影響，建立了以總費用最低為目標的多式聯運路徑決策模型.結合模型特點，設計了求解該問題四種遺傳算法策略，通過算例對給出的算法進行對比，證明了算法的可行性和有效性，其中SGA算法在求解本文所述問題上綜合表現最優.