基于綜合滿意度的多式聯(lián)運路徑模型及其算法*

裴 驍 蘆有鵬 張長澤

（蘭州交通大學(xué)交通運輸學(xué)院 蘭州 730070）

0 引 言

多式聯(lián)運是指將貨物采用2種或2種以上的運輸方式運送到指定地點的運輸過程[1]。隨著“一帶一路”國家戰(zhàn)略的逐步深入，中歐集裝箱多式聯(lián)運迅速發(fā)展，其路徑選擇問題也日漸成為研究的熱點和難點。

在現(xiàn)有多式聯(lián)運路徑優(yōu)選建模的相關(guān)研究中，熊桂武等[2]從實現(xiàn)多式聯(lián)運廣義運輸總費用最小化的原則出發(fā)，建立了多式聯(lián)運含時間窗約束的組織優(yōu)化模型，并設(shè)計了啟發(fā)式算法進行求解；Juliana Verga等[3]、Jingshu Wang等[4]針對多式聯(lián)運的堵塞，碳排放等問題提出標(biāo)準(zhǔn)化計算方法，并設(shè)計元啟發(fā)式算法與經(jīng)典算法進行優(yōu)劣對比，通過評價轉(zhuǎn)運節(jié)點的性能來提供多式聯(lián)運網(wǎng)絡(luò)合理布局和低碳制定的決策依據(jù)運輸政策；陶學(xué)宗[5]、劉松等[6]基于碳排放限制的視角，從集裝箱多式聯(lián)運的鐵路運輸碳排放研究入手，建立了考慮裝卸作業(yè)，接駁等條件下鐵路運輸鏈的碳排放估算模型，為國際聯(lián)運碳排放量提供了數(shù)據(jù)支持。Lim等[7]主要考慮了路徑條件限制，并探討了如何在客戶需求存在差異的情況下做出決策；Rekik等[8]、王嬌[9]、梁曉慷[10]則考慮了個體需求敏感度差異，從服務(wù)質(zhì)量的角度出發(fā)，建立了相應(yīng)的目標(biāo)模型，并根據(jù)決策者偏好給出對應(yīng)優(yōu)化決策方案，尋找參與各方的滿意平衡點。同時，張小龍等[11]、李卓等[12]考慮了時間窗問題，針對多式聯(lián)運網(wǎng)絡(luò)中鐵、水路具有發(fā)班時間限制，將時間作為一種有價資源拓展至交通運輸領(lǐng)域，以減少費用成本、時間價值成本為目標(biāo)建立了路徑優(yōu)化模型。在此類模型求解算法的研究中，Yue等[13]根據(jù)無人機路徑規(guī)劃特點改進蟻群算法，通過添加懲罰策略來搜索歷史較差值從而提高信息素易變性引導(dǎo)螞蟻搜索其他未知區(qū)域；魏宇[14]分析了蟻群算法中揮發(fā)因子的特點，設(shè)計自適應(yīng)改進算子，對信息揮發(fā)因子進行自適應(yīng)調(diào)整，使螞蟻在“探索”和“利用”之間保持平衡；賀政綱等[15]根據(jù)多式聯(lián)運的運輸特性重新設(shè)定蟻群的環(huán)境刺激值等屬性，使算法更具動態(tài)性和公平性；而劉杰等[16]和呂學(xué)偉等[17]則從低碳運輸入手，考慮弧段以及轉(zhuǎn)運過程中的碳排放，并根據(jù)模型的點設(shè)計了相應(yīng)的非支配排序遺傳算法。上述文獻(xiàn)大多以多式聯(lián)運中單一參與者為研究對象并建立模型，并未將多個參與者協(xié)同考慮，同時在求解過程中將運輸方式與運輸路徑同時優(yōu)化，在增加算法復(fù)雜度的同時容易產(chǎn)生不可行解。

通過分析整個多式聯(lián)運環(huán)節(jié)中各參與者（托運人、承運人和政府）間的需求，建立了基于綜合滿意度的數(shù)學(xué)模型，并針對此類組合優(yōu)化問題設(shè)計了遺傳-蟻群混合算法，將參與者間的差異化需求融入算法設(shè)計，為中歐集裝箱多式聯(lián)運路徑優(yōu)選提供參考。

1 基于綜合滿意度的模型構(gòu)建

1.1 問題描述

假設(shè)1批貨物從出發(fā)點O運輸至目的地D，任意相連的2個節(jié)點之間有公路、鐵路、水運3種運輸方式可供選擇，途中節(jié)點均可提供運輸方式中轉(zhuǎn)服務(wù)，其中每個節(jié)點發(fā)往下1個節(jié)點的鐵路、水路運輸有固定的到達(dá)和離開時間限制，公路則可隨時出發(fā)，且托運人對貨物的最終運到時間有可接受的軟時間窗限制。

表1 模型參數(shù)說明Tab.1 Model symbol description

1.2 問題假設(shè)

1）承運商每次承擔(dān)1項運輸任務(wù)，貨物在運輸途中不能分割。

2）任意2個節(jié)點之間只能使用多種運輸方式中的1種。

3）運輸方式轉(zhuǎn)換只發(fā)生在節(jié)點處且每個節(jié)點最多只能進行1次中轉(zhuǎn)。

4）轉(zhuǎn)運成本與運量成線性關(guān)系，且所有節(jié)點設(shè)施均滿足轉(zhuǎn)運過程的要求。

1.3 模型參數(shù)及變量

模型參數(shù)說明見表1。

1.4 滿意度分析與模型構(gòu)建

多式聯(lián)運環(huán)節(jié)中各大參與者主要包括托運人、承運人以及政府，三者的需求側(cè)重點各不相同，可將影響其各自滿意度的主要因素做詳細(xì)劃分。

1）托運人滿意度。由于早到或遲到對倉儲和運營產(chǎn)生的不便將直接影響到托運人的滿意度，因此托運人會根據(jù)剩余庫存量將貨物的到達(dá)時間分為可接受到達(dá)時間和最佳到達(dá)時間，并組成軟時間窗，其中客戶滿意度與貨物到達(dá)時間見圖1[10]，式（1）為二者的函數(shù)關(guān)系，其中α和β分別為客戶對貨物早到和遲到的敏感系數(shù)。

圖1 客戶滿意度與運輸時限關(guān)系Fig.1 Customer satisfaction and transportation time limit

2）承運商滿意度。在運量和起訖點相同的情況下，承運商會權(quán)衡不同路徑與運輸方式搭配，在滿足客戶需求的前提下選擇總成本較低的運輸方案，使此次交易達(dá)到利潤最大化。其滿意度見式（2）

式中：Bn為運輸方案γn的總成本，包含節(jié)點間的運輸、中轉(zhuǎn)、等待成本；BMAX和BMIN分別為本代群體中成本最高與最低值。

3）政府滿意度。由于二氧化碳排放對生態(tài)的破壞與其排量直接相關(guān)，因此單次運輸中的二氧化碳排放量是影響政府滿意度的重要指標(biāo)，即政府滿意度與單次運輸中二氧化碳排放量有關(guān)，碳排放量越少，政府對此運輸方案的滿意度越高。由此設(shè)計政府滿意度見式（4）。

式中：En為本次運輸?shù)奶寂欧帕?，包含?jié)點間運輸?shù)奶寂欧帕亢凸?jié)點轉(zhuǎn)運時的碳排放量；Emax和Emin分別為本代群體中最高與最低的碳排放量。

綜上可知，對運輸方案綜合滿意度的考量指標(biāo)包括費用、時間和碳排放，在處理此類問題時多數(shù)文獻(xiàn)采用加入主觀權(quán)重的方法，而在實際運輸過程中，各項指標(biāo)不僅本身具有復(fù)雜性，且對運輸方案的影響程度也具有不確定性，為了更加客觀地進行對比和決策，筆者引入了不確定多屬性決策的思想[18]，綜合考量各參與者的主觀偏好及各項指標(biāo)對運輸方案的客觀影響，采用帶有效用值偏好信息的多屬性賦權(quán)法對運輸方案的綜合滿意度進行測。假設(shè)：各參與者對運輸方案γn中各指標(biāo)Zm的主觀偏好以效用值?m表示，越接近1，表示參與者越偏好指標(biāo)Zm；此外，由指標(biāo)Zm所得規(guī)范化矩陣Rn×m中的屬性值rnm即為運輸方案γn中指標(biāo)Zm的客觀偏好值。為使指標(biāo)權(quán)重向量ω更具合理性，即參與者的主觀偏好值?m與指標(biāo)的客觀屬性值rnm總偏差最小，建立下列單目標(biāo)優(yōu)化模型。

解之易得

綜上所述，結(jié)合運輸過程的各方需求，兼顧各參與者的效用偏重，建立基于綜合滿意度的多式聯(lián)運路徑模型

式（8）為綜合滿意度目標(biāo)函數(shù)；式（9）保證貨物只有1個起點；式（10）保證貨物只有1個終點；式（11）表示相鄰2節(jié)點之間只能選擇1種運輸方式；式（12）表示在同1節(jié)點至多發(fā)生1次運輸方式的轉(zhuǎn)換；式（13）表示中間節(jié)點的流量守恒約束，保證運輸?shù)倪B續(xù)性；式（14）表示實際運輸轉(zhuǎn)換次數(shù)不能超過允許最大換裝次數(shù)；式（15）表示總的運輸時間，包括運輸時間、中轉(zhuǎn)時間、在節(jié)點處等待運輸工具到達(dá)的時間，以及在運輸工具上等待離開節(jié)點的時間；式（16）表示在節(jié)點i處等待第k種運輸方式到達(dá)的時間；式（17）表示在節(jié)點i處等待第k種運輸方式離開的時間；式（18）表示選擇第k種運輸方式在第i個節(jié)點處的總等待時間，即19）表示貨物到達(dá)時間需在托運人可接受時間窗內(nèi)。

2 求解算法設(shè)計

2.1 混合算法描述

此類組合優(yōu)化問題的核心在于路徑的選擇與運輸方式的匹配，依據(jù)問題特點設(shè)計“雙信息素矩陣”儲存方法實現(xiàn)目標(biāo)對象間的匹配與搜索引導(dǎo)，實現(xiàn)路徑與運輸方式間的“交互選擇”，并利用遺傳算法具有快速的全局搜索能力和蟻群算法的正負(fù)反饋能力[19]設(shè)計混合算法：算法前期應(yīng)用基于遺傳算法的小生境技術(shù)，降低方案間的相似性，得到幾組更具有解空間代表性的可行解，取各小生境中的最優(yōu)路徑與運輸方式組合，以此更新蟻群算法中的雙信息素啟發(fā)矩陣，使初始蟻群具有較優(yōu)的路徑和運輸方式匹配依據(jù)，從而引導(dǎo)并加速螞蟻的尋優(yōu)，提高混合算法的求解精度和收斂速度。

2.1.1 小生境遺傳算法

為了保證種群的多樣性，防止算法向目標(biāo)空間中1個固定區(qū)域進行采樣的趨勢，在此引入小生境遺傳算法[20]，并設(shè)計掩碼交叉（見圖2）和雙點變異作為遺傳算子。

圖2 掩碼交叉Fig.2 Mask crossing

2.1.2 動態(tài)雙信息素蟻群算法

為了消除路徑與運輸方式匹配的盲目性，本文設(shè)計“雙信息素矩陣”儲存方法：螞蟻依據(jù)各節(jié)點路徑啟發(fā)矩陣和路徑信息素矩陣生成路徑選擇概率，采用輪盤賭法選取所要到達(dá)的下1個節(jié)點，同理依照運輸方式啟發(fā)矩陣和運輸方式信息素矩陣生成運輸方式選擇概率，為路徑匹配合適的運輸方式直至終點。雙信息素信息儲存結(jié)構(gòu)見圖3。

圖3 雙信息素矩陣信息儲存結(jié)構(gòu)Fig.3 Dual pheromone algorithm information storage structure

式中：τij(t)表示路徑(i,j)在t時刻的信息素強度；表示螞蟻a可選節(jié)點或可選運輸方式集合；為影響因子，分別表示螞蟻選擇節(jié)點或運輸方式時對信息素矩陣和啟發(fā)矩陣的依賴程度。

為避免算法后期搜索停滯，采用最大最小螞蟻策略，每條弧以及各運輸方式的信息素值須在區(qū)間(τmin,τmax)內(nèi)。將各小生境所得的較好解通過式（21）～（22）來確定初始信息素范圍[21]。

式中：L(Sbest)為各小生境較好解或蟻群算法本次迭代最優(yōu)解，小生境遺傳算法結(jié)束后，則開始采用式（23）來確定 τmax(t)；τmin(t)仍采用式（22）來確定。

2.1.3 改進時變信息素?fù)]發(fā)算子

為避免混合算法陷入局部最優(yōu)解，設(shè)計如下時變信息素?fù)]發(fā)算子。

通過分析影響算法搜索空間和收斂性的因素發(fā)現(xiàn)，信息素?fù)]發(fā)系數(shù)在路徑或運輸方式選擇中的重要性成正比，因此結(jié)合混合算法的算法機制，設(shè)計在算法過程中信息素?fù)]發(fā)系數(shù)ρ的取值隨迭代次數(shù)正向增加

式中：ρ0為初始信息素?fù)]發(fā)系數(shù)；μ0為信息素?fù)]發(fā)速度參數(shù)，λ為蟻群算法迭代次數(shù)[11]。其中μ0的大小與信息素?fù)]發(fā)系數(shù)隨算法代數(shù)增加的快慢成正比，并控制信息素?fù)]發(fā)系數(shù)最終趨于ρ0。

2.2 算法流程

雙信息素混合算法流程見圖（4）。

圖4 雙信息素混合算法流程圖Fig.4 Double pheromone hybrid algorithm flowchart

3 算例分析

3.1 算例設(shè)計

以連云港到馬德里為例，現(xiàn)有集裝箱貨物，需從連云港集拼運往西班牙馬德里，途徑城市及港口見圖4。各運輸方式的特征概括和節(jié)點內(nèi)的操作明細(xì)消耗分別見表2和表3。

假設(shè)各節(jié)點開往下1個節(jié)點的鐵路每天有5班，時間窗寬度是3 h，船舶每天是4班，時間窗寬度是4 h，假設(shè)貨物從00：00開始發(fā)出,表4給出了各節(jié)點首班發(fā)車（船）時間[15]。

使用Matlab 2018a對本文模型進行編程求解，其中算法主要參數(shù)初始值見表5，文中對各算法分別運行20次，取其中最好解和性能評價指標(biāo)進行對比。

3.2 結(jié)果分析

為驗證模型中各參與者的需求偏重對最終方案選擇的影響，同時顧及所得運輸方案的可行性，在保持其他條件不變的情況下，設(shè)計在同1個例中分別改變各參與者需求效用比重，求解結(jié)果見表6，可以看出隨著決策者的傾向不同，在追求綜合滿意度盡可能大的前提下，其路徑與運輸方式的組合結(jié)果會明顯不同。

圖5 連云港到馬德里運輸網(wǎng)絡(luò)Fig.5 Lianyungang to Madrid Transportation Network

表2 各運輸方式特征概括Tab.2 Summary of characteristics of each mode of transport

表3 節(jié)點內(nèi)換裝費用/時間/碳排放量Tab.3 In-node replacement cost/time/carbon emissions

表4 各節(jié)點首班發(fā)車（船）時間Tab.4 First departure time oftrain(ship)

表5 算法初始值Tab.5 Algorithm initial value

為進一步驗證模型的有效性，將運輸方案與已有研究成果進行對比，其結(jié)果見表7。以文獻(xiàn)[10]所采用的求解總費用最少模型為例，代入本案例計算可得最好運輸路徑為連云港→上?！鷱B門→里斯本→馬德里，最好運輸方式搭配為?！＿\→海運→鐵路，其計算結(jié)果與表6中著重考慮費用時所得最優(yōu)運輸方案一致，但由于其完全未考慮發(fā)車（船）及其等待時間和碳排放因素，與表6中給出的綜合滿意度最高的方案相比，其中后者運到時間較延后17.038 4 h，碳排放量增加23.4 kg，導(dǎo)致綜合滿意度降低了約10.01%。綜合對比表6和表7可知，在側(cè)重某一特定指標(biāo)時，該模型能夠給出相應(yīng)的最優(yōu)解，而在綜合考慮各方滿意度指標(biāo)時，該模型能夠給出更加具有指導(dǎo)性的運輸方案。

表6 不同需求效用比重的運輸方案Tab.6 Different demand-utility transportation schemes

表7 現(xiàn)有運輸方案指標(biāo)對比Tab.7 Comparison of indicators of existing transport schemes

3.3 算法性能測試

為測試混合算法的性能，以此算例作為測試集，分別從驗證時變改進算子效果、與經(jīng)典算法進行對比、調(diào)節(jié)算例參數(shù)和改變算例規(guī)模的角度出發(fā)進行驗證，單次結(jié)果見表8，運行對比分別見圖6（a）～（d），可以看出時變信息素?fù)]發(fā)算子具有較好的算法優(yōu)化能力，且較其他傳統(tǒng)算法能更高效地解決此類組合優(yōu)化問題。通過調(diào)節(jié)綜合滿意度模型參數(shù)可見其對算法收斂速度和解的尋優(yōu)能力擾動不大，說明算法在提高最優(yōu)解質(zhì)量的同時，對穩(wěn)健性也有改善，表現(xiàn)出良好的求解性能。同時隨著算例規(guī)模的增大，混合算法相對傳統(tǒng)算法仍能保持較低的收斂代數(shù)，可見此算法設(shè)計對大規(guī)模問題的求解依然是高效可行的。

表8 各算法實驗統(tǒng)計結(jié)果Tab.8 Experimental results of each algorithm

圖6 算法對比結(jié)果Fig.6 Results of each algorithm solution

4 結(jié)束語

本文研究了國際多式聯(lián)運的路徑優(yōu)選問題，在充分考慮了客戶、承運商和政府滿意度的基礎(chǔ)上，以綜合滿意度最高為目標(biāo)建立了模型；采用帶有效用值偏好信息的多屬性決策方法，減小了主客觀權(quán)重賦值的偏差所帶來的影響，并進一步研究了對方案有偏好情形下的決策結(jié)果；結(jié)合小生境遺傳算法具有保留物種多樣性的特點和雙信息素蟻群算法在算法后期利用正負(fù)反饋收斂能力強的特點，設(shè)計了混合算法來并行搜索多式聯(lián)運路徑和轉(zhuǎn)運方式的合理搭配，并改進收斂算子避免算法陷入局部最優(yōu)解，最后結(jié)合實例，驗證了模型較同類模型的優(yōu)越性以及算法的有效性；未來可針對動態(tài)網(wǎng)絡(luò)下的多式聯(lián)運路徑優(yōu)化模型做進一步研究，為運輸過程中同時顧及戰(zhàn)略層、戰(zhàn)術(shù)層以及執(zhí)行層多方面利益的人性化決策提供依據(jù)。