鐵路集裝箱班列開行方案與定價綜合優化研究

張小強， 李保軼， 吳 桐, 陳婭娜

(1. 西南交通大學 交通運輸與物流學院， 四川 成都 610031； 2. 綜合交通運輸智能化國家地方聯合工程實驗室， 四川 成都 610031；3. 中國鐵道科學研究院集團有限公司 運輸及經濟研究所， 北京 100081)

在現代化貨物運輸方式中，鐵路貨運在大宗物資運輸及長遠距離運輸方面占據優勢，具有適應性強、安全程度高、運輸成本低、運輸能力大、環境污染程度小等特點。其中集裝箱運輸是鐵路運輸的重要組成部分，具有標準化、低成本、高效率等優勢。目前集裝箱運輸在我國鐵路貨運中占比逐年上升，至2017年占比達到11%，但仍遠低于發達國家40%的比例。因此，加快鐵路集裝箱發展是促進我國鐵路貨運可持續發展的必經之路。

就目前我國鐵路貨運定價現狀來看，基本仍然按照原鐵道部鐵運〔2005〕46號《鐵路貨物運價規則》[1]等有關規定執行，采用貨物品類適用運價號等計費方法。在當前市場化的競爭環境下，實施固定運價的定價機制并不能為鐵路運輸企業帶來較好的收益。為了推動鐵路貨運價格市場化，2015年國家發改委發布了《關于調整鐵路貨運價格進一步完善價格形成機制的通知》[2]，指出應適當調整鐵路貨運價格，并建立上下浮動機制。2016年中國鐵路總公司拿到高鐵定價權，這給予了鐵路運輸企業根據運輸市場供求關系實行一定的折扣票價的權利。由此可見，鐵路運價的改革是大勢所趨，鐵路貨運必須建立靈活的定價機制來參與市場競爭，進而提高運營效率。

另一方面，我國鐵路部門在集裝箱班列開行和?？繘Q策方面仍然缺乏科學合理的制定機制，運營管理水平相對落后。決策制定主要依靠決策者的經驗及以往的數據，帶有很大的主觀性，不適用于競爭市場。

從國內外的研究來看，海運集裝箱以及多式聯運集裝箱運輸是集裝箱運輸收益管理最早開始應用的領域。對于海運集裝箱的空箱調運問題，Zhou等通過空箱調運策略與最優定價策略對運輸網絡中的貨運流量進行平衡，其需求模型是只與價格有關的線性模型。Wang等[4]研究了客戶面對多條集裝箱貨輪線路時如何進行選擇的問題，其中的選擇行為采用Logit模型描述。楊華龍等[5]同時考慮了集裝箱班輪運輸現貨市場的定價策略與合同市場的艙位分配，并建立了現貨市場分時段動態定價模型、班輪公司空箱調運的艙位分配模型以及合同市場客戶重箱運輸模型。Xie等[6]研究了班輪公司與鐵路公司組成的多式聯運系統中的空箱運輸問題，對于集中式模型，推導出最優的交付策略，并展示策略如何隨初始庫存狀態而變化。劉迪等[7]在集裝箱海鐵聯運問題的研究中,考慮了協議銷售與自由銷售之間定價的差異性，以此切入建立了關于集裝箱海鐵聯運的綜合箱位分配動態定價模型。Martín等[8]分析了進口集裝箱的定價問題，并以實際集裝箱碼頭的數據進行了實驗。這些研究對于制定運輸開行方案以及優化定價策略都有重要的貢獻，但是都沒有考慮運輸網絡的貨物積壓，即運輸的服務水平，本文在考慮服務水平的基礎上優化鐵路運營企業的利潤，得出最優的開行方案和運價。

對于鐵路運輸動態定價和開行方案的研究，研究重點集中在鐵路客運服務上。Crevier等[9]提出了一種鐵路貨運企業運營規劃與收益管理相結合的新模式。藍伯雄等[10]構造了一個優化旅客列車開行方案和客流分配的混合整數規劃模型，且此模型能夠在較短的時間內獲得高質量的列車開行優化方案。鄧連波等[11]構造乘客出行的彈性需求函數，將乘客乘車選擇歸結為具有能力約束的彈性需求用戶均衡問題。張小強等[12-13]在鐵路集裝箱班列運輸動態定價的基礎之上，考慮了以公路集裝箱運輸為代表的競爭環境，研究鐵路集裝箱動態定價與開行決策模型。

大多數學者將鐵路集裝箱運輸價格制定與開行方案決策看成兩個獨立版塊進行研究，而這二者實則互相影響，因此本文將這二者進行綜合優化，同時將運輸網絡的穩定性納入考慮。為求解復雜的優化問題，本文提出一種優化算法，能夠將時變網絡中的優化問題轉化為在單一時隙上進行貪婪求解，且從數學層面上證明了轉化后問題的最優值與原問題時間平均下的最優值無限接近。不僅可通過將用于保證網絡穩定性的無限時間積壓約束轉化為最小化李雅普諾夫函數(Lyapunov)問題使得求解方便，同時，動態調整權重值的大小也能夠實現原優化目標與運輸網絡貨物積壓之間的平衡。

1 模型描述

本文考慮鐵路集裝箱班列運輸，在單一線路上有多個?？空军c。一趟列車由始發站發車，途徑若干中間站后到達終到站。在需求已知的情況下，決策者對列車開行及停靠方案，各OD之間的貨運量，以及各OD之間的運輸價格做出決策，從而優化使得運輸部門獲得最大運營收益。

模型參數及各個變量的描述，見表1。

表1 模型參數及變量描述

2 模型假設

討論具體優化模型之前，首先做出如下基本假設：

(1) 本文研究的集裝箱運輸網絡不存在與外界的流量轉移，即為封閉網絡，未被滿足的貨運需求將在網絡中產生積壓。

(2) 列車一定在始發站發車，在終到站結束。

(3) 不包含從目的地運往出發地的情況。

(5) 同一OD上貨物運輸價格相同，運費以箱計。

(6) 列車固定其開行成本和?？砍杀尽?/p>

3 模型建立

本文優化目標是在滿足所有約束條件的情況下使列車運行的利潤最大，建立優化問題P1為

{[pij(t)-m]·bij(t)-F(t)·K-τi(t)·Si}

s.t.

i

(1)

τi(t)≤F(t)

(2)

τN(t)=F(t)

(3)

Mτi(t)≥bij(t)

(4)

Mτj(t)≥bij(t)

(5)

(6)

(7)

bij(t)≤aij(t)

(8)

aij(t)≤amax

(9)

bij(t)≤bmax

(10)

(11)

式中：pij(t)、bij(t)、F(t)為模型的決策變量；Sij為ODi和j之間的最大運輸需求，為常數；M為一個很大的常數；u是一個正整數；α、β為已知參數；ε為一個無窮大的正數。

式(2)表示列車開行時才有列車?？繘Q策。式(3)表示開行的列車一定在終點站結束行程，這兩個約束共同用于表明列車的OD固定，不存在中間站發車或是終止的情況。式(4)和式(5)表示若ODi和j間有貨運量，則列車一定在i、j站點均停靠。式(6)表明列車在站點i的裝箱數不能超過當前列車剩余的容量。式(7)為用于表明ODi和j間的實際需求量與貨運價格之間的關系的Logit價格反應函數。式(8)限制實際貨運量不能超過需求量。式(9)限制實際需求量不能超過最大需求量。式(10)限制實際貨運量不能超過最大貨運量。式(11)用于保證運輸網絡的穩定性，當時隙數量T趨于無窮時，貨物積壓之和小于一個無窮大的正數ε。

貨物積壓隊列演變等式為

Qij(t+1)=Qij(t)+aij(t)-bij(t)

(12)

問題P1是時間周期T內的全局優化問題，涉及很多的變量，求解復雜度高。對于時變網絡優化問題中的這種NP難問題，目前還沒有算法可以對NP難問題求出準確的全局最優解。如果各變量之間存在一定的因果關系，則不能保證每一時隙所做決策的獨立性，以本問題為例，當前的貨運價格會影響下一時隙的貨運需求，從而影響接下來的列車開行與?？繘Q策。因此，本文提出一種算法對問題P1進行轉化，以便于求解。

4 求解算法

4.1 BCPO算法

本節提出一種積壓控制與價格優化BCPO(Backlog Control and Pricing Optimization)算法以解決問題P1，BCPO算法將難以求解的時變網絡優化問題P1轉化為僅在單一時隙進行網絡優化的問題P2，問題P2的最優值與問題P1在時間平均下的最優值無限接近，且動態調整參數的大小可以實現在目標函數和貨物積壓隊列之間的權衡。應用文獻[14-15]提出的李雅普諾夫優化技術，本文將解決貨運定價，列車開行與停靠決策，貨物積壓控制等一系列決策問題。

BCPO算法在保證鐵路集裝箱運輸網絡穩定性的基礎上，綜合優化了貨運價格和列車開行方案，他可以解決時變網絡優化中每一時隙結果互相影響難以求解的問題。該算法的核心是構建二次李雅普諾夫函數和李雅普諾夫加罰漂移，通過最小化加罰漂移保證網絡穩定性，同時在時間平均的目標函數和時間平均的積壓隊列之間達到權衡。

在t時隙，定義Lyapunov函數L(t)為

(13)

可以看出，當最小化Lyapunov函數L時，運輸隊列將處于低擁塞狀態(貨物積壓Q趨于0)。

定義一個時隙內的Lyapunov漂移Δ(t)為

(14)

從式(14)構造的Lyapunov漂移看出，最小化Lyapunov漂移也就是最小化相鄰時隙的網絡積壓的平方差，約束(11)將會始終滿足，即運輸網絡始終保持穩定。因此，在下面問題討論中，可去掉約束(11)。

[aij(t)-bij(t)]+[aij(t)-bij(t)]2}≤

[aij(t)-bij(t)]+[aij(t)2+bij(t)2]}≤

B+Qij(t)·[aij(t)-bij(t)]

(15)

Lyapunov漂移反映了貨物積壓水平。當最小化Δ(t)時，也就是最小化[aij(t)-bij(t)]，即做出運輸決策后未被滿足的貨運需求。

現在定義Lyapunov加罰漂移ΔV(t)為

(16)

F(t)·K-τi(t)·Si}

(17)

問題P1轉化為P2

F(t)·K-τi(t)·Si}

(18)

s.t. 式(1)～式(10)

推論1在對問題P1應用BCPO算法后轉化得到的問題P2中，令

O*=max{[pij(t)-m]·bij(t)-

F(t)·K-τi(t)·Si}

(19)

(20)

式中：B*為一個非負實數。

證明：給定時間周期T

(21)

對式(21)兩邊同時求時間平均得

(22)

假設

[aij(t)-bij(t)]-V·O*+φ

(23)

(24)

通過上式可得

(25)

由式(15)可知

4.2 和聲搜索算法

對轉化得到的單時隙鐵路貨運集裝箱班列定價策略與開行方案問題，其目標函數非凸，仍具有相互影響的決策變量。故本文采用和聲搜索算法進行求解，和聲搜索優化算法是一種啟發式的全局搜索智能算法，其結構簡單、收斂速度快、穩健性好，且具有較高的通用性，對連續變量和離散變量的優化問題均適用。具體求解流程見圖1。

建立用于保存初始可行解和迭代過程中的解的和聲記憶庫HM(Harmony Memory)之后，和聲搜索算法中需要確定的參數值有：HMS為聲記憶庫大小，指和聲記憶庫中解向量的個數，取值過大會使計算量過大，取值過小則無法保證樣本多樣性;HMCR為和聲記憶庫取值概率，指從現有種群(HM和聲庫)中拿出一個和聲的概率;PAR為音調微調概率，是對從和聲記憶庫中選擇的解向量進行音調微調的概率;BW為音調微調帶寬，指音調微調的幅度，一般情況下此參數對于離散優化問題不需考慮。

主要流程為先對和聲記憶庫進行初始化，然后隨機產生新的和聲，若新的和聲優于和聲記憶庫中最差的和聲，則淘汰最差的和聲，并用新產生的和聲取代。循環上述過程直到求出最優解或滿足算法的終止條件。

算法的偽代碼如下：

Begin

隨機生成初始庫

將f(x1)，f(x2)，…，f(xHMS)排序

whileItr

隨機生成rand1

ifrand1

rand2=rand1

ifrand2

?

else

?

end

else

end

fbest=fbest

fworst=fworst

fworst=fworst-1

else

fbest=fbest

end

end

end

5 算例分析

考慮從廣州站開往成都站的鐵路集裝箱貨運班列運輸，運輸線路示意見圖2。

站點1表示廣州站，為始發站；站點2和站點3分別表示株洲站和重慶站，均為中間站；站點4表示重慶站，為終到站。參數的設置見表2。

表2 主要參數設置表

注：Tmax為創作次數，通常作為算法的終止條件，指最大迭代次數。

根據鐵路貨運的實際情況，對各OD集裝箱運輸的運價范圍進行限定，見表3。

表3 各OD集裝箱運價范圍

由此根據前文的模型與算法優化求得目標函數值為8.894 9×104，運輸企業所得利潤為8.888 8×104元。此時集裝箱貨運班列從廣州站開行，并在株洲站和重慶站?？?，得到的定價策略與運量決策見表4。

表4 各OD最優價格與貨運量

依據廣州鐵路(集團)公司的實際數據，得到廣州—成都線路上集裝箱運輸班列的現有運價見表5。把各OD的現有運價代入優化模型中，可得到應用當前運價時鐵路部門的運營收益，將其與應用優化后的最優價格時鐵路部門所獲收益值進行對比，可驗證動態定價的優越性。

表5 各OD現行運價

在現行的固定運價策略下，優化得到目標函數值為-3.403 7×103，鐵路部門獲得的利潤為-3.235×103元?？梢园l現這種情況下鐵路部門出現虧損，所獲收益遠低于應用表4中最優化運價時帶來的收益。

同時，本文所設計的算法是完全分布式的，只需要知道當前狀態下各OD的市場潛在貨運需求以及上一時隙的貨物積壓就可以做出貪婪決策。為了進一步分析動態定價和固定運價的優劣性，對這兩種定價策略下的目標函數值、利潤值和貨物積壓值進行對比分析，分析結果見圖3～圖5。

可以發現，廣州鐵路集團在采用優化運價后，獲得的運輸收益遠高于采用現有運輸價格獲得的運輸收益。同時，采用優化后的開行?？繘Q策也可以保證運輸網絡的穩定性，使得貨物積壓大幅度減少，幾乎接近于0。

接下來，我們分析控制參數V對收益值的影響，給定V=[1，10，50，100，1 000，10 000，100 000，1 000 000]，觀察當控制參數V變化時，轉化后的問題P2的最優收益值O*的變化變化情況。分析的結果驗證了3節推論1的正確性。從圖5可以看出，收益值O*隨V的增加而增加，當V值達到10 000以后，利潤值接近于最優值。

在決策時隙的上一時隙，運輸網絡中前一時隙的貨物積壓量Q′會對決策時隙的運輸情況產生影響，調整Q′的值，分析得到以下結果：

從圖7可以看出，當前時隙的貨物積壓Q在各種貨物積壓Q′的水平下總能穩定在較小的水平(小于1)，運輸網絡具有較強的穩定性。由此說明了本文所建立的模型與設計的算法對優化運輸網絡中的貨物積壓和提高服務水平具有優越性。

當Q′的值小于10 000時，當前貨物積壓

始終小于1，鐵路部門收益一直維持在93 000元以上。雖然當Q′值超過10 000時，收益會出現較大幅度的下滑，但是在小規模的單線運輸網絡中，這種情況發生的可能性很低，本文的模型和算法仍具有代表性。

各OD的實際貨運需求量發生變化時，相應的開行停靠決策和運價策略也會發生變化。為盡量避免算法產生結果的隨機性帶來的影響，我們在相同條件下進行了20次實驗，每次實驗中對顧客在各OD的需求進行調整，并取其中使收益達到最優的開行?？?，方案和定價策略，以分析得出影響決策變化的臨界需求量。具體有以下4種情形：

Case1當與站點2?？糠桨负投▋r策略相關的三個運輸區間(1—2、2—3、2—4)的貨運潛在需求量均不超過4箱時，最優?？糠桨甘窃谡军c2不停靠，在站點3停靠。運輸決策為

表6 Case1中各OD最優價格和實際貨運量表

Case2當與站點3?？糠桨负投▋r策略相關的三個運輸區間(1—3、2—3、3—4)的貨運潛在需求量均不超過4箱時，最優?？糠桨甘窃谡军c3不?？?，在站點2停靠。運輸決策見表7。

表7 Case2中各OD最優價格和實際貨運量表

Case3當所有運輸區間的潛在貨運需求量均不超過3箱時，集裝箱班列停開。

Case4在現有參數條件以及需求量不變的情況下多次進行實驗，嘗試不同的列車開行成本和停靠成本對列車的開行停靠決策的影響，結果表明當列車開行成本增加到460 000元時，集裝箱班列停開；當?？砍杀驹黾拥?5 000元時，列車在所有站點均不停靠。

6 結束語

本文在考慮運輸網絡貨物積壓的基礎上，建立了鐵路集裝箱班列開行方案和運價決策的綜合優化模型，此模型高度復雜，是時變網絡中的全局優化問題，本文提出了基于Lyapunov優化的BCPO算法將其轉化為多個單一時隙的確定性優化問題，并從理論上證明了該轉后問題等價于原問題。對于轉化后的問題，運用和聲搜索算法進行求解，通過算例分析，表明鐵路運輸企業在采用本文所得出的最優運價時所得到的總收益比采用現有運價時高。在運輸路段上的需求產生變化時，根據實際需求信息優化出最優的開行方案與價格策略。

對于多周期時變網絡中的復雜優化問題，本文設計的BCPO算法能夠進行優化。此算法僅需當前網絡的需求信息即可做出相應的貪婪決策。

鐵路運輸部門可以靈活調整V值實現利潤與客戶等待運輸時間之間的矛盾問題，V值的選取是企業戰略決策的體現。當運輸企業更重視運營收益時，可以適當調高V值；當運輸企業更重視網絡穩定性時，可以適當減小V值再求得最優定價策略和開行方案，V值越小表示企業越重視運輸服務水平。