帶時(shí)間窗約束的集裝箱空箱調(diào)運(yùn)隨機(jī)機(jī)會(huì)約束模型研究

石紅國(guó)，高明瑤

SHI Hongguo, GAO Mingyao

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756)

0 引言

隨著我國(guó)“一帶一路”戰(zhàn)略的實(shí)施，集裝箱運(yùn)輸在我國(guó)社會(huì)經(jīng)濟(jì)發(fā)展中起著越來(lái)越重要的作用。由于我國(guó)生產(chǎn)力發(fā)展水平和自然資源分布不均衡，區(qū)域之間的貿(mào)易也呈現(xiàn)出不均衡性，最終造成集裝箱運(yùn)輸過(guò)程中空重箱需求不均衡問(wèn)題。為了解決該問(wèn)題，需要在不同地區(qū)之間進(jìn)行空箱調(diào)運(yùn)?？茖W(xué)合理的調(diào)運(yùn)方法能夠壓縮集裝箱調(diào)運(yùn)時(shí)間，降低調(diào)運(yùn)成本，提高集裝箱運(yùn)輸效率。通過(guò)深入分析集裝箱空箱調(diào)運(yùn)過(guò)程，研究集裝箱空箱調(diào)運(yùn)費(fèi)用、運(yùn)達(dá)時(shí)間的多目標(biāo)綜合優(yōu)化方法。

近年來(lái)，隨著集裝箱運(yùn)輸?shù)目焖侔l(fā)展，很多學(xué)者對(duì)集裝箱運(yùn)輸進(jìn)行了一系列的研究。張得志等[1]對(duì)鐵路集裝箱空箱調(diào)度問(wèn)題建立基于顧客偏好的運(yùn)輸規(guī)劃模型和帶時(shí)間窗的運(yùn)輸規(guī)劃模型，并采用遺傳算法對(duì)其進(jìn)行求解；閆海峰等[2]充分考慮集裝箱班列的開(kāi)行特點(diǎn)，建立了混合箱流輸送時(shí)間最少，距離最短，費(fèi)用最低為優(yōu)化目標(biāo)的混合0-1 規(guī)劃模型，并設(shè)計(jì)了二級(jí)耦合反饋系統(tǒng)算法進(jìn)行求解；Song 等[3]針對(duì)動(dòng)態(tài)和隨機(jī)環(huán)境下的空箱配送問(wèn)題，將其分成空箱裝載和卸載2 個(gè)部分，分別制定配送策略，該方法在貿(mào)易不均衡時(shí)的求解結(jié)果明顯優(yōu)于傳統(tǒng)的方法，降低了20%的成本；Chou 等[4]建立了混合模糊決策模型，將空箱配送問(wèn)題分為兩個(gè)階段：模糊缺貨存儲(chǔ)模型和網(wǎng)絡(luò)模型，優(yōu)化各個(gè)港口之間的空箱調(diào)運(yùn)問(wèn)題；Cheung 等[5]針對(duì)帶時(shí)間窗和帶回程的車輛徑路問(wèn)題，建立了多屬性標(biāo)號(hào)匹配算法；Braekens 等[6]對(duì)滿載集裝箱和空集裝箱的調(diào)運(yùn)進(jìn)行綜合規(guī)劃并采用啟發(fā)式算法進(jìn)行求解；Imai等[7]將單個(gè)集裝箱卡車運(yùn)輸問(wèn)題描述成0-1 線性規(guī)劃模型，并設(shè)計(jì)了拉格朗日松弛算法對(duì)其進(jìn)行求解；Jula 等[8]將單個(gè)集裝箱接駁運(yùn)輸問(wèn)題描述成帶社會(huì)約束的帶時(shí)間窗的非對(duì)稱多旅行商問(wèn)題，并基于動(dòng)態(tài)規(guī)劃和遺傳算法的混合算法對(duì)其進(jìn)行求解；Fischer 等[9]將鐵路智能體系統(tǒng)應(yīng)用于集裝箱運(yùn)輸資源的調(diào)度中。

在上述研究中，各個(gè)鐵路集裝箱車站的集裝箱需求量(供給量)均設(shè)置為確定值。而在實(shí)際應(yīng)用中，集裝箱供給和需求一般是不確定的，準(zhǔn)確地估算集裝箱調(diào)運(yùn)數(shù)量能夠降低成本，提高整個(gè)運(yùn)輸系統(tǒng)的運(yùn)營(yíng)效益。針對(duì)這種不確定的問(wèn)題可以將集裝箱需求量與供給量處理為服從一定分布的隨機(jī)變量。在此基礎(chǔ)上，以最小化集裝箱運(yùn)輸費(fèi)用和最大化集裝箱到達(dá)時(shí)刻總體滿意度為優(yōu)化目標(biāo)，構(gòu)建帶有時(shí)間窗約束的集裝箱調(diào)運(yùn)隨機(jī)機(jī)會(huì)約束模型，通過(guò)將隨機(jī)機(jī)會(huì)約束轉(zhuǎn)化為確定性的等價(jià)類，將模型轉(zhuǎn)化為對(duì)應(yīng)的確定性模型，并設(shè)計(jì)基于TOPSIS方法和限定參數(shù)區(qū)間搜索的模型求解方法。

1帶時(shí)間窗約束的集裝箱調(diào)運(yùn)隨機(jī)機(jī)會(huì)約束模型構(gòu)建

在整個(gè)鐵路網(wǎng)中，存在多個(gè)集裝箱站對(duì)集裝箱有需求的情況，設(shè)D= {D1，…，Dn}為集裝箱需求站；同時(shí)也存在多個(gè)集裝箱站能夠供給集裝箱，設(shè)S= {S1，…，Sn}為集裝箱供給站。為便于模型描述，在此對(duì)變量統(tǒng)一定義，變量定義如表1 所示：

表1 變量定義Tab.1 Variables definition

在實(shí)際的集裝箱運(yùn)輸問(wèn)題中，如果集裝箱過(guò)早到達(dá)，則需要在目的地進(jìn)行等待，降低了集裝箱的運(yùn)用效率；如果集裝箱到達(dá)過(guò)晚，則會(huì)影響其他的貨物運(yùn)輸，引起損失，因而集裝箱的到達(dá)時(shí)刻應(yīng)在一定范圍內(nèi)，可考慮利用函數(shù)來(lái)描述這種時(shí)間限制。集裝箱調(diào)運(yùn)到達(dá)時(shí)刻滿意度如圖1 所示。

用函數(shù)μij(tij)來(lái)描述上述集裝箱到達(dá)時(shí)刻滿意度，如公式 ⑴。

圖1 集裝箱調(diào)運(yùn)到達(dá)時(shí)刻滿意度Fig.1 Arrival time satisfaction of container transportation

以最小化集裝箱運(yùn)輸費(fèi)用和最大化集裝箱到達(dá)時(shí)刻總體滿意度為優(yōu)化目標(biāo)，考慮車站的集裝箱供給量與需求量的不確定性，構(gòu)建帶有時(shí)間窗約束的集裝箱調(diào)運(yùn)隨機(jī)機(jī)會(huì)約束規(guī)劃模型如下。

式中：αi，βj分別表示供給與需求滿足的概率；N為正整數(shù)集合。

公式 ⑵ 表示最小化總的集裝箱調(diào)運(yùn)費(fèi)用；公式⑶ 表示最大化集裝箱總體調(diào)運(yùn)滿意度；公式 ⑷ 表示車站i的第k種集裝箱供給量發(fā)生變化時(shí)，從車站i到車站j運(yùn)輸?shù)牡趉種集裝箱的數(shù)量小于等于車站i的第k種集裝箱供給量的概率在αi以上，即車站i的第k種集裝箱供給量發(fā)生變化時(shí)的機(jī)會(huì)約束條件成立的概率在αi以上；公式 ⑸ 表示車站i的第k種集裝箱需求量發(fā)生變化時(shí)，從車站i到車站j運(yùn)輸?shù)牡趉種集裝箱的數(shù)量小于等于車站j的第k種集裝箱需求量的概率在βj以上，即車站j的第k種集裝箱需求量發(fā)生變化時(shí)的機(jī)會(huì)約束條件成立的概率在βj以上；公式 ⑹ 為對(duì)變量取值的約束。

2集裝箱空箱調(diào)運(yùn)隨機(jī)機(jī)會(huì)約束模型求解

2.1 不確定性變量的處理

當(dāng)各車站的需求和供給量為確定值時(shí)，集裝箱的調(diào)運(yùn)問(wèn)題即轉(zhuǎn)換成運(yùn)輸問(wèn)題，采用表上作業(yè)法進(jìn)行求解。當(dāng)各車站的需求和供給量為不確定值時(shí)，即對(duì)于第2 節(jié)建立的隨機(jī)機(jī)會(huì)約束模型，可以考慮將其轉(zhuǎn)換成一個(gè)確定的等價(jià)類模型。

設(shè)隨機(jī)變量Sik服從正態(tài)分布N(μi，σi2)，將其分布函數(shù)代入公式 ⑷，可得公式 ⑺。

式中：F(*)表示分布函數(shù)。

公式 ⑺ 將不確定的概率表達(dá)式轉(zhuǎn)化為常規(guī)不等式。對(duì)公式 ⑺ 進(jìn)行標(biāo)準(zhǔn)化，得

對(duì)公式 ⑻ 兩邊取反函數(shù)，得公式 ⑼。

同理，可得

利用分布函數(shù)的相關(guān)知識(shí)做上述不等式化簡(jiǎn)，可以得出關(guān)于兩地集裝箱運(yùn)輸量的限制條件，為模型的求解奠定基礎(chǔ)。

2.2 多目標(biāo)模型的非劣解擇優(yōu)

TOPSIS 方法根據(jù)有限個(gè)評(píng)價(jià)對(duì)象與理想化目標(biāo)的接近程度進(jìn)行排序，在現(xiàn)有的對(duì)象中進(jìn)行相對(duì)優(yōu)劣的評(píng)價(jià)，是多目標(biāo)決策分析中常用的有效方法。為此采用TOPSIS 方法評(píng)價(jià)方案。

式中：β1，β2分別為關(guān)于集裝箱調(diào)運(yùn)的總的調(diào)運(yùn)費(fèi)用與總體到達(dá)滿意度所占的權(quán)重，且β1+β2= 1；f1(Xa)為方案Xa的集裝箱調(diào)運(yùn)總調(diào)運(yùn)費(fèi)用；f2(Xa)為方案Xa的集裝箱調(diào)運(yùn)總體滿意度。

則方案Xa對(duì)理想點(diǎn)的相對(duì)接近度εa為

εa越大，方案越優(yōu)。

2.3 限定范圍的帕累托最優(yōu)解搜索算法

非劣解是滿足帕累托最優(yōu)條件的解集中的向量。多需求站，多供給站，多集裝箱種類的集裝箱調(diào)運(yùn)問(wèn)題屬于具有復(fù)雜、不連續(xù)的帕累托前沿的多目標(biāo)優(yōu)化問(wèn)題，其非劣解的數(shù)量，將隨系統(tǒng)內(nèi)需求站，供給站和集裝箱種類的增加而呈幾何級(jí)數(shù)增長(zhǎng)。為有效減少計(jì)算量，提高計(jì)算效率，采用一種限定參數(shù)區(qū)間的帕累托最優(yōu)解搜索方法進(jìn)行模型求解。

選擇總調(diào)運(yùn)費(fèi)用為限定參數(shù)。若限定調(diào)運(yùn)費(fèi)用不超過(guò)某值，則定義該值為限定調(diào)運(yùn)費(fèi)用，用表示。設(shè)調(diào)運(yùn)總費(fèi)用單目標(biāo)模型對(duì)應(yīng)的最少調(diào)運(yùn)費(fèi)用為，調(diào)運(yùn)總體滿意度最大單目標(biāo)對(duì)應(yīng)的最少調(diào)運(yùn)費(fèi)用為，則可以將非劣方案的調(diào)運(yùn)費(fèi)用限定在閉區(qū)間[，]，由于＜方案是實(shí)際不可行的方案，而＞的方案對(duì)應(yīng)的費(fèi)用不少于總體滿意度單目標(biāo)模型最優(yōu)解，顯然也為較劣解。當(dāng)＞時(shí)，不考慮該方案，令所有的為0，并將該約束加入總體滿意度最大單目標(biāo)模型。求解費(fèi)用在[，]之間，且滿意度最大的非劣解，確保得到的帕累托最優(yōu)解均在帕累托前沿，并通過(guò)與理想點(diǎn)的相對(duì)接近度確定最優(yōu)方案。具體求解步驟如下。

（1）不考慮目標(biāo)函數(shù)公式 ⑶，以目標(biāo)函數(shù)公式 ⑵為單優(yōu)化目標(biāo)，求解公式 ⑵ 對(duì)應(yīng)的最優(yōu)解，即最少調(diào)運(yùn)總費(fèi)用。

（2）不考慮目標(biāo)函數(shù)公式 ⑵，以目標(biāo)函數(shù)公式 ⑶為單優(yōu)化目標(biāo)，求解公式 ⑶ 對(duì)應(yīng)的最優(yōu)解，即最大調(diào)運(yùn)滿意度。

（5）比較所有方案對(duì)理想點(diǎn)的相對(duì)接近度，選出最優(yōu)方案。

限定參數(shù)區(qū)間的帕累托最優(yōu)解搜索算法，能在求解大規(guī)模問(wèn)題時(shí)，減少最優(yōu)解的搜尋次數(shù)。

3算例分析

3.1 參數(shù)設(shè)置及模型處理

設(shè)某鐵路區(qū)域共有4 個(gè)集裝箱供給站S1，S2，S3，S4，4 個(gè)集裝箱需求站D1，D2，D3，D4。車站集裝箱供應(yīng)數(shù)量分布情況如表2 所示，表中數(shù)據(jù)表示各個(gè)集裝箱供給站集裝箱供給量的分布函數(shù)，例如，在表2 中，供給量參數(shù)S11服從均值為20，方差為2 的正態(tài)分布N(20，2)。車站集裝箱需求數(shù)量分布情況如表3 所示，表3 中數(shù)據(jù)表示各個(gè)集裝箱需求站的集裝箱需求量的分布函數(shù)，具體含義與表2 類似。車站間的集裝箱單位調(diào)運(yùn)成本如表4 所示，表中數(shù)據(jù)表示各個(gè)集裝箱供給站到各個(gè)集裝箱需求站的單個(gè)集裝箱的運(yùn)輸費(fèi)用。

表2 車站集裝箱供應(yīng)數(shù)量分布情況Tab.2 Distribution of container supply quantity at station

設(shè)供給站i將集裝箱送達(dá)時(shí)刻tij分別為12 : 00，15 : 30，15 : 00，15 : 20。需求站j的集裝箱預(yù)計(jì)的最晚到達(dá)時(shí)間lj為15 : 00，16 : 00，14 : 20，15 : 30。lj與Lj之間間隔30 min。置信水平αi，βj均取95%，

表3 車站集裝箱需求數(shù)量分布情況Tab.3 Distribution of container demand quantity at station

表4 車站間的集裝箱單位調(diào)運(yùn)成本 百元/TEUTab.4 Container unit transfer cost between stations

則

計(jì)算可得S11= -1.645×2 + 20 = 16.71，取整可得S11= 16。同理，處理其他隨機(jī)變量，得到各個(gè)車站的供給量和需求量分別為：

3.2 求解與分析

利用MATLAB中的GUROBI優(yōu)化軟件對(duì)集裝箱調(diào)運(yùn)費(fèi)用最小單目標(biāo)模型進(jìn)行求解，得到最優(yōu)解X1′和最劣解X1′′；對(duì)集裝箱總體到達(dá)滿意度最大單目標(biāo)模型進(jìn)行求解，得到最優(yōu)解X2′和最劣解X2′′，其對(duì)應(yīng)的目標(biāo)函數(shù)值分別如下。

考慮到運(yùn)輸費(fèi)用和集裝箱到達(dá)滿意度在集裝箱調(diào)運(yùn)系統(tǒng)中占的比重，取權(quán)重系數(shù)β1為0.6，β2為0.4。按公式(11)—(12)分別計(jì)算不同的方案與正負(fù)理想點(diǎn)的相對(duì)距離Ra和ra，按照公式 ⒀ 計(jì)算和理想點(diǎn)的相對(duì)接近度εa，最終得到的最優(yōu)方案X*的總費(fèi)用與總滿意度為

如果αi=βj= 100%，則問(wèn)題轉(zhuǎn)換為確定性問(wèn)題，即可用表上作業(yè)法進(jìn)行求解。集裝箱需求/供給量確定情形與不確定情形下的集裝箱調(diào)運(yùn)結(jié)果對(duì)比如表5 所示。

表5 集裝箱需求/供給量確定情形與不確定情形下集裝箱 調(diào)運(yùn)結(jié)果對(duì)比Tab.5 Comparison between the certain and uncertain amount of container demand (supply)

由表5 可知，與確定性情形相比較，不確定情形下的集裝箱調(diào)運(yùn)總費(fèi)用由7 120 減少為6 680，降低了6.2%，總體滿意度由58.7%提高為75.2%，提高了16.5%。綜合考慮需求/供給量不確定性、集裝箱調(diào)運(yùn)總費(fèi)用與總體滿意度，最優(yōu)調(diào)運(yùn)方案如表6 所示。表6 中數(shù)據(jù)是各個(gè)集裝箱供給站到各個(gè)集裝箱需求站的最優(yōu)供給量。例如，表中第1 個(gè)數(shù)據(jù)16 表示第1 個(gè)集裝箱供給站S1到第1 個(gè)集裝箱需求站D1的第1 種集裝箱的最優(yōu)供給量為16 TEU。

表6 最優(yōu)調(diào)運(yùn)方案 TEUTab.6 Optimal container transfer plan

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

近年來(lái)，集裝箱運(yùn)輸在我國(guó)經(jīng)濟(jì)發(fā)展中扮演著舉足輕重的作用，解決集裝箱空箱調(diào)運(yùn)的均衡問(wèn)題成為重中之重。合理分析完善集裝箱運(yùn)輸過(guò)程，提高集裝箱運(yùn)輸效率，可以使得集裝箱運(yùn)輸發(fā)揮更大的經(jīng)濟(jì)效益。在整個(gè)集裝箱運(yùn)輸問(wèn)題中，涉及到的因素比較多，主要包括如何使集裝箱運(yùn)輸時(shí)間最短，運(yùn)輸費(fèi)用最低，到達(dá)時(shí)間方面的約束，出發(fā)時(shí)間的約束，集裝箱存儲(chǔ)問(wèn)題，接駁問(wèn)題，空箱調(diào)運(yùn)問(wèn)題等，這些問(wèn)題的妥善解決將有助于穩(wěn)固與發(fā)展集裝箱在國(guó)民經(jīng)濟(jì)中的作用。