呂學(xué)偉，楊 斌，黃振東

（上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306）

0 引言

在現(xiàn)實(shí)的運(yùn)輸過(guò)程中，公路運(yùn)輸自由靈活，而鐵路、水路和航空運(yùn)輸都有固定的到達(dá)時(shí)間和離開時(shí)間，貨物需要在運(yùn)輸工具離開之前到達(dá)相應(yīng)的節(jié)點(diǎn)位置，并完成相應(yīng)的裝載任務(wù)，否則只能等待下一班次。對(duì)于收貨人而言，也存在一個(gè)收貨時(shí)間段，而這個(gè)時(shí)間段一般比較寬松。因此，在實(shí)際的運(yùn)輸過(guò)程中，存在著運(yùn)輸方式硬時(shí)間窗和收貨人收貨的軟時(shí)間窗組合而成的混合時(shí)間窗。

對(duì)于收貨人的軟時(shí)間窗，國(guó)內(nèi)外的研究均較多，而對(duì)于運(yùn)輸方式硬時(shí)間窗的研究，則國(guó)外的研究相對(duì)較多。Ziliaskopoulos 等[1]以鐵路、航空、水運(yùn)等運(yùn)輸方式的固定出發(fā)時(shí)刻表為約束條件，建立單目標(biāo)或多目標(biāo)模型，尋找最優(yōu)運(yùn)輸路徑和運(yùn)輸方式的組合；Chang[2]研究各節(jié)點(diǎn)處各種運(yùn)輸方式的硬時(shí)間窗，并采用標(biāo)號(hào)法尋找多目標(biāo)下的最優(yōu)路徑和運(yùn)輸方式組合；Cetin 等[3]重點(diǎn)研究收貨人的硬時(shí)間窗要求，規(guī)定在特定時(shí)間段內(nèi)將貨物送達(dá)到收貨人的手里，以此為約束條件進(jìn)行多式聯(lián)運(yùn)最優(yōu)路徑的優(yōu)化；Marjani 等[4]以運(yùn)輸過(guò)程中的軟、硬時(shí)間窗為約束條件，進(jìn)行整車多式聯(lián)運(yùn)、空箱調(diào)運(yùn)等路徑優(yōu)化；付曉鳳等[5]綜合考慮危險(xiǎn)品多式聯(lián)運(yùn)過(guò)程中的安全性和經(jīng)濟(jì)性，建立基于危險(xiǎn)性最小，以及成本、時(shí)間最少的聯(lián)運(yùn)方案優(yōu)化模型；黑秀玲[6]對(duì)時(shí)間窗進(jìn)行敏感性分析；賴志柱[7]考慮到各節(jié)點(diǎn)處的軟時(shí)間窗，創(chuàng)立和聲搜索算法優(yōu)化運(yùn)輸路徑；鄒宗峰等[8]以各個(gè)運(yùn)輸節(jié)點(diǎn)上的軟、硬時(shí)間窗為約束，組成混合時(shí)間窗，采用加權(quán)法處理多目標(biāo)優(yōu)化問(wèn)題；梁曉慷[9]在考慮模糊運(yùn)輸時(shí)限時(shí)間窗的基礎(chǔ)上，以運(yùn)輸費(fèi)用最小、客戶滿意度最高為優(yōu)化目標(biāo)，構(gòu)建多式聯(lián)運(yùn)路徑優(yōu)化問(wèn)題的線性規(guī)劃模型；楊江波[10]從實(shí)際運(yùn)輸情況出發(fā)，考慮到公路運(yùn)輸自由靈活，而鐵路、航空、水運(yùn)在各個(gè)運(yùn)輸節(jié)點(diǎn)處都有固定的發(fā)車時(shí)刻表，以這些固定時(shí)刻表為約束條件，建立總運(yùn)輸成本最低的優(yōu)化模型，采用蟻群算法，為多式聯(lián)運(yùn)經(jīng)營(yíng)人選擇最優(yōu)運(yùn)輸方案。在此，從現(xiàn)實(shí)角度出發(fā)，研究混合時(shí)間窗對(duì)多式聯(lián)運(yùn)最優(yōu)運(yùn)輸方案的影響，以總成本最低為目標(biāo)，構(gòu)建混合時(shí)間窗約束下多式聯(lián)運(yùn)最優(yōu)路徑選擇模型，并通過(guò)案例進(jìn)行驗(yàn)證。

1 混合時(shí)間窗約束下多式聯(lián)運(yùn)最優(yōu)路徑選擇模型構(gòu)建

1.1 問(wèn)題描述及假設(shè)

將一批貨物從起始城市O運(yùn)到終點(diǎn)城市D，采用集裝箱運(yùn)輸方式，中間有多個(gè)節(jié)點(diǎn)城市，構(gòu)成集合N，每個(gè)節(jié)點(diǎn)城市又有多種運(yùn)輸方式，所有運(yùn)輸方式構(gòu)成集合K，在每個(gè)節(jié)點(diǎn)城市都可以轉(zhuǎn)換運(yùn)輸方式。每個(gè)節(jié)點(diǎn)城市發(fā)往下一個(gè)節(jié)點(diǎn)城市的鐵路、水路運(yùn)輸都有固定的到達(dá)和離開時(shí)間，而收貨人在收貨時(shí)有比較寬松的時(shí)間段。以鐵路運(yùn)輸、水路運(yùn)輸?shù)挠矔r(shí)間窗和收貨人的軟時(shí)間窗組成的混合時(shí)間窗為約束，并以總的運(yùn)輸成本最小為目標(biāo)，為承運(yùn)人選擇最優(yōu)的運(yùn)輸方案。

假設(shè)在運(yùn)輸途中貨物沒(méi)有被分割運(yùn)輸，貨物狀態(tài)不發(fā)生任何變化，運(yùn)輸工具和中轉(zhuǎn)工具的載運(yùn)能力充足，能滿足集裝箱的運(yùn)輸需求。

1.2 模型構(gòu)建

以總運(yùn)輸成本最低為目標(biāo)，以混合時(shí)間窗為約束條件，構(gòu)建多式聯(lián)運(yùn)最優(yōu)路徑選擇模型如下。

式中：Z為總的運(yùn)輸成本；n為集裝箱的標(biāo)箱數(shù)；r為 1 標(biāo)箱集裝箱的日租賃成本；Tt為貨主收貨時(shí)間；q為集裝箱的重量；為從第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)，采取第k種運(yùn)輸方式的單位運(yùn)輸成本；為從第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)，采取第k種運(yùn)輸方式的運(yùn)輸時(shí)間；為決策變量，當(dāng)?shù)趇個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)采用第k種運(yùn)輸方式時(shí)，值為 1，否則為 0；為在第i個(gè)節(jié)點(diǎn)，第k種運(yùn)輸方式轉(zhuǎn)變?yōu)榈趌種運(yùn)輸方式時(shí)的單位中轉(zhuǎn)費(fèi)用，當(dāng)k=l時(shí)，值為 0；為決策變量，如果在第i個(gè)節(jié)點(diǎn)處發(fā)生轉(zhuǎn)運(yùn)，則該值為 1，否則為 0；為在第i個(gè)節(jié)點(diǎn)處采用第k種運(yùn)輸方式的單位等待成本；為在第i個(gè)節(jié)點(diǎn)處等待第k種運(yùn)輸方式到達(dá)的時(shí)間，在這個(gè)時(shí)間段內(nèi)會(huì)發(fā)生等待成本；Ct為貨物提前到達(dá)終點(diǎn)的單位倉(cāng)儲(chǔ)成本；Et為收貨人最早收貨時(shí)間點(diǎn)；Pt為延遲到達(dá)終點(diǎn)的單位懲罰成本；Lt為最遲收貨時(shí)間點(diǎn)；為在第i個(gè)節(jié)點(diǎn)，第k種運(yùn)輸方式轉(zhuǎn)變?yōu)榈趌種運(yùn)輸方式時(shí)的中轉(zhuǎn)時(shí)間，當(dāng)k=l時(shí)，值為 0；為在第i個(gè)節(jié)點(diǎn)處第k種運(yùn)輸方式等待離開第i個(gè)節(jié)點(diǎn)的時(shí)間；為第i個(gè)節(jié)點(diǎn)發(fā)往第j個(gè)節(jié)點(diǎn)的路線上，第k種運(yùn)輸方式到達(dá)第i個(gè)節(jié)點(diǎn)的時(shí)間；為第k種運(yùn)輸方式離開第i個(gè)節(jié)點(diǎn)的時(shí)間；，分別為下一班次，第k種運(yùn)輸方式到達(dá)、離開第i個(gè)節(jié)點(diǎn)的時(shí)間；ti為貨物到達(dá)第i個(gè)節(jié)點(diǎn)處的實(shí)際時(shí)間；為第k種運(yùn)輸方式在第i個(gè)節(jié)點(diǎn)處的總等待時(shí)間。

公式 ⑴ 表示總成本最小的函數(shù)，總成本包括租賃成本、運(yùn)輸成本、中轉(zhuǎn)成本、等待成本、因偏離收貨人收貨時(shí)間窗而產(chǎn)生的懲罰成本；公式 ⑵表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)之間只能選擇一種交通工具；公式 ⑶ 表示在第i個(gè)節(jié)點(diǎn)處只能發(fā)生一次轉(zhuǎn)運(yùn)；公式 ⑷ 表示總的運(yùn)輸時(shí)間，包括運(yùn)輸時(shí)間、中轉(zhuǎn)時(shí)間、在節(jié)點(diǎn)處等待運(yùn)輸工具到達(dá)的時(shí)間，以及在運(yùn)輸工具上等待離開節(jié)點(diǎn)的時(shí)間；公式 ⑸ 表示在各節(jié)點(diǎn)處等待運(yùn)輸工具到達(dá)的時(shí)間，在這個(gè)時(shí)間段內(nèi)會(huì)發(fā)生等待成本；公式 ⑹ 表示在第i個(gè)節(jié)點(diǎn)處在第k種運(yùn)輸方式上等待離開第i個(gè)節(jié)點(diǎn)的時(shí)間，在這個(gè)時(shí)間段內(nèi)不發(fā)生等待成本；公式 ⑺ 表示第k種運(yùn)輸方式在第i個(gè)節(jié)點(diǎn)處的總等待時(shí)間，在第i個(gè)節(jié)點(diǎn)處等待第k種運(yùn)輸方式到達(dá)的時(shí)間與在第i個(gè)節(jié)點(diǎn)處在第k種運(yùn)輸方式上等待離開的時(shí)間之和，即公式 ⑸ 與公式 ⑹ 之和。

1.3 算法設(shè)計(jì)

多式聯(lián)運(yùn)最優(yōu)路徑選擇問(wèn)題被證明是 NP-hard問(wèn)題。蟻群算法作為一種模擬進(jìn)化算法，具有分布式、啟發(fā)式計(jì)算的特點(diǎn)，適合求解多式聯(lián)運(yùn)的最優(yōu)路徑選擇問(wèn)題。

在多式聯(lián)運(yùn)的起點(diǎn)和終點(diǎn)之間，有n個(gè)節(jié)點(diǎn)，螞蟻在轉(zhuǎn)移的節(jié)點(diǎn)間釋放信息素，并通過(guò)信息素的交流來(lái)完成最優(yōu)路徑的選擇。螞蟻選擇可行的節(jié)點(diǎn)完成整個(gè)路徑，之后由其他的螞蟻按照剩下的可行節(jié)點(diǎn)完成整個(gè)路徑。當(dāng)每只螞蟻到達(dá)終點(diǎn)后，進(jìn)行局部信息素的更新，當(dāng)所有螞蟻都到達(dá)終點(diǎn)后，進(jìn)行全局信息素的更新，在經(jīng)過(guò)最大迭代次數(shù)后得到最優(yōu)解，具體求解步驟如下。

（1）初始參數(shù)設(shè)置。設(shè)置蟻群數(shù)為m，起始時(shí)間為 0，最大迭代次數(shù)為NCmax，節(jié)點(diǎn)集合為P，讀入所有節(jié)點(diǎn)處所有運(yùn)輸方式的運(yùn)輸時(shí)間、運(yùn)輸成本、中轉(zhuǎn)成本、等待成本、時(shí)間窗等信息，設(shè)定啟發(fā)信息和初始信息素，設(shè)定螞蟻結(jié)構(gòu)包括運(yùn)輸信息、線路選擇信息、中轉(zhuǎn)信息和到達(dá)節(jié)點(diǎn)的時(shí)間。

（2）對(duì)循環(huán)次數(shù)NC進(jìn)行迭代，當(dāng)達(dá)到最大迭代次數(shù)NCmax時(shí)，循環(huán)結(jié)束。即NC=NC+ 1。

（3）將各節(jié)點(diǎn)拆分成進(jìn)入節(jié)點(diǎn)和離開節(jié)點(diǎn)，將螞蟻分配在各節(jié)點(diǎn)上，設(shè)置禁忌表tabum，記錄所有的起始節(jié)點(diǎn)。

（4）所有的螞蟻搜尋滿足條件的節(jié)點(diǎn)，將第r只螞蟻每次允許選擇的節(jié)點(diǎn)加入到候選集合allowedr。

（5）讓螞蟻選擇節(jié)點(diǎn)的公式可以表示為

式中：(t) 為t時(shí)刻，螞蟻r由第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的概率；(t) 為t時(shí)刻路徑 (i，j) 上的信息素濃度；ηij為啟發(fā)函數(shù)，表示螞蟻從第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的期望值，通常取 2 個(gè)節(jié)點(diǎn)城市間距離的倒數(shù)；α為啟發(fā)式因子，指螞蟻在移動(dòng)時(shí)積累的信息量的多少對(duì)螞蟻的指導(dǎo)作用相對(duì)重要程度；β為期望的啟發(fā)式因子，指啟發(fā)信息對(duì)螞蟻搜索的相對(duì)重要程度。

對(duì)信息素進(jìn)行更新的公式可以表示為

式中：τij(t+n) 為在 (t，t+n) 時(shí)間內(nèi)，循環(huán)一次后，螞蟻在所有路徑上更新信息素的規(guī)則；ρ為信息素的揮發(fā)程度系數(shù)；1－ρ為信息素的殘留程度系數(shù)；Δτij(t，t+n) 為整個(gè)蟻群在經(jīng)過(guò) (t，t+n) 的時(shí)間，完成一次循環(huán)遍歷后，邊 (i，j) 上剩余的信息素；Δ(t，t+n) 為螞蟻r在經(jīng)過(guò) (t，t+n) 的時(shí)間，完成一次循環(huán)遍歷后，邊 (i，j) 上剩余的信息素。

（6）當(dāng)所有的螞蟻都完成一次循環(huán)后，以總成本最低選擇最優(yōu)螞蟻。

（7）以最優(yōu)螞蟻的信息為依據(jù)，對(duì)全局進(jìn)行信息素更新。

（8）當(dāng)達(dá)到最大迭代次數(shù)時(shí)，循環(huán)結(jié)束，以步驟（6）的螞蟻所表示的信息為最優(yōu)解，否則返回步驟（2）。

2 案例分析

2.1 基礎(chǔ)數(shù)據(jù)

假設(shè)現(xiàn)有 10 t 貨物采用 20 ft 集裝箱從城市O運(yùn)到城市D，中間有 5 個(gè)節(jié)點(diǎn)城市，分別記為A，B，C，E，F(xiàn)。每 2 個(gè)節(jié)點(diǎn)城市之間最多有 3 種運(yùn)輸方式可供選擇，分別是公路、鐵路、水路。公路運(yùn)輸沒(méi)有時(shí)間窗約束，鐵路、水路運(yùn)輸都有固定的時(shí)間窗，收貨人有收貨的軟時(shí)間窗。各節(jié)點(diǎn)間連接方式如圖 1 所示。

圖 1 各節(jié)點(diǎn)間連接方式Fig.1 Connection modes among different nodes

假設(shè)公路運(yùn)輸單價(jià)是 0.2 元/(t · km)，鐵路運(yùn)輸單價(jià)是 0.15 元/(t · km)，水路運(yùn)輸單價(jià)是 0.02 元/(t · km)，3 種運(yùn)輸方式的速度分別是 60 km/h、60 km/h、30 km/h。假設(shè) 3 種運(yùn)輸工具都是勻速運(yùn)輸，而模型是研究時(shí)間窗對(duì)運(yùn)輸方案的影響，將基于單位運(yùn)輸距離的單位運(yùn)輸成本轉(zhuǎn)化為基于單位運(yùn)輸時(shí)間的成本，轉(zhuǎn)化后的運(yùn)輸單價(jià)分別為 12 元/(t · h)、9 元/(t · h)、0.3 元/(t · h)。每標(biāo)箱的日租賃成本是100 元，在鐵路車站因提前到達(dá)而產(chǎn)生的單位等待成本是 30 元/(t · h)，在碼頭是 20 元/(t · h)。假設(shè)各節(jié)點(diǎn)開往下一節(jié)點(diǎn)的鐵路每天有 4 列，時(shí)間窗寬度是 3 h，即在各個(gè)節(jié)點(diǎn)處，鐵路的停留時(shí)間是 3 h；船舶每天是 3 班，時(shí)間窗寬度是 5 h，即在各個(gè)節(jié)點(diǎn)處，船舶的停留時(shí)間是 5 h。鐵路和船舶的進(jìn)站時(shí)間在指定范圍內(nèi)隨機(jī)生成，貨主收貨的時(shí)間窗是[25，30]，提前到達(dá)的單位儲(chǔ)存成本是 40 元/(t · h)，延遲到達(dá)的單位懲罰成本是 60 元/(t · h)。假設(shè)OA1，O－A3弧中的鐵路和水運(yùn)假設(shè)都是從 0 ∶ 00 開始出站，即貨物從0 ∶ 00 點(diǎn)開始發(fā)出。記某節(jié)點(diǎn)處某運(yùn)輸方式的服務(wù)時(shí)間窗表示為 [a，b]，a表示運(yùn)輸工具到達(dá)節(jié)點(diǎn)的時(shí)間，b表示運(yùn)輸工具離開節(jié)點(diǎn)的時(shí)間。各節(jié)點(diǎn)的運(yùn)輸時(shí)間參數(shù)如表 1 所示，各運(yùn)輸方式間單位轉(zhuǎn)運(yùn)成本、轉(zhuǎn)運(yùn)時(shí)間參數(shù)如表 2 所示，各節(jié)點(diǎn)處鐵路、水路運(yùn)輸?shù)臅r(shí)間窗參數(shù)如表 3 所示。

表 1 各節(jié)點(diǎn)的運(yùn)輸時(shí)間參數(shù) hTab.1 Transport time parameters of each node

2.2 用蟻群算法進(jìn)行求解

設(shè)置相關(guān)參數(shù)值：初始信息素為 0.1，啟發(fā)因子α為 2，期望啟發(fā)因子β為 5，信息素?fù)]發(fā)系數(shù)ρ為0.05，蟻群規(guī)模m為 30，最大迭代次數(shù)NCmax為 200。得到的最優(yōu)解為：OA3A4A5D，運(yùn)輸方式分別為鐵路-水運(yùn)-水運(yùn)-水運(yùn)?；旌蠒r(shí)間窗下最優(yōu)路徑的運(yùn)行數(shù)據(jù)如表 4 所示，各運(yùn)輸方式的運(yùn)行數(shù)據(jù)如表 5 所示。

2.3 比較分析

節(jié)點(diǎn)處沒(méi)有時(shí)間窗約束，相當(dāng)于貨物在中轉(zhuǎn)途中各運(yùn)輸方式無(wú)縫對(duì)接，這是目前大多數(shù)學(xué)者的思考模式。當(dāng)無(wú)時(shí)間窗約束時(shí)，由蟻群算法得到的最優(yōu)解也為：OA3A4A5D，運(yùn)輸方式為鐵路-水路-水路-水路，運(yùn)行總成本是 717 元，運(yùn)行時(shí)間是 23 h，運(yùn)輸費(fèi)用為 501 元，轉(zhuǎn)運(yùn)費(fèi)用為 120 元，租賃費(fèi)用為 96 元。

表 2 各運(yùn)輸方式間單位轉(zhuǎn)運(yùn)成本、轉(zhuǎn)運(yùn)時(shí)間參數(shù)Tab.2 Unit transportatn cost and transport time between different transportation modes

表 3 各節(jié)點(diǎn)處鐵路、水路運(yùn)輸?shù)臅r(shí)間窗參數(shù)Tab.3 Time windows for railway and waterway transport at each node

表 4 混合時(shí)間窗約束下最優(yōu)路徑的運(yùn)行數(shù)據(jù)Tab.4 Operation data of optimal path constrained by mixed time windows

表 5 各運(yùn)輸方式的運(yùn)行數(shù)據(jù)Tab.5 Operating data for each mode of transport

將有混合時(shí)間窗限制與無(wú)混合時(shí)間窗限制下最優(yōu)路徑的費(fèi)用與時(shí)間進(jìn)行對(duì)比，成本對(duì)比如表 6 所示，時(shí)間對(duì)比如表 7 所示。

通過(guò)對(duì)比，無(wú)論是總費(fèi)用、總時(shí)間，還是單個(gè)費(fèi)用、單個(gè)時(shí)間，有混合時(shí)間窗約束的數(shù)值都要比無(wú)時(shí)間窗約束的數(shù)值高，至少是相等?？梢姡诂F(xiàn)實(shí)的運(yùn)輸過(guò)程中，因混合時(shí)間窗而產(chǎn)生的運(yùn)輸費(fèi)用不僅真實(shí)存在，而且這種數(shù)值有時(shí)還很大，對(duì)多式聯(lián)運(yùn)最優(yōu)運(yùn)輸方案的選擇會(huì)產(chǎn)生較大的影響。對(duì)于多式聯(lián)運(yùn)的承運(yùn)人而言，這種費(fèi)用和時(shí)間不能無(wú)視，也就是不能無(wú)視混合時(shí)間窗的真實(shí)存在性，不僅要考慮收貨人軟時(shí)間窗的影響，更要考慮鐵路、水路、飛機(jī)等運(yùn)輸工具硬時(shí)間窗的影響[11-13]。

表 6 成本對(duì)比 元Tab.6 Cost contrast

表 7 時(shí)間對(duì)比 hTab.7 Time contrast

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

基于運(yùn)輸方式硬時(shí)間窗和收貨人收貨的軟時(shí)間窗，構(gòu)成混合時(shí)間窗。在此基礎(chǔ)上，以總成本最少為目標(biāo)，將混合時(shí)間窗納入約束條件，建立多式聯(lián)運(yùn)最優(yōu)路徑選擇優(yōu)化模型，采用蟻群算法，能更精確和實(shí)際地反映多式聯(lián)運(yùn)路徑選擇問(wèn)題。通過(guò)有混合時(shí)間窗約束下的最優(yōu)路徑與無(wú)混合時(shí)間窗約束下的最優(yōu)路徑進(jìn)行數(shù)據(jù)對(duì)比，無(wú)論運(yùn)輸成本，還是運(yùn)輸時(shí)間，兩者都有很大差距，這表明混合時(shí)間窗約束對(duì)多式聯(lián)運(yùn)最優(yōu)運(yùn)輸路徑的選擇具有重要影響，是經(jīng)營(yíng)人和承運(yùn)人不能忽視的重要因素。由于設(shè)計(jì)的硬時(shí)間窗具有固定性，可以考慮隨機(jī)的硬時(shí)間窗進(jìn)行深入研究，包括時(shí)間窗的寬度和時(shí)間窗的位置，以反映更為真實(shí)的運(yùn)輸特征。