面向時(shí)變需求的高鐵快運(yùn)專列時(shí)刻表和配裝方案綜合優(yōu)化研究*

高如虎 ?；菝?楊喜梅

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

0 引 言

為充分發(fā)揮高鐵運(yùn)力資源優(yōu)勢(shì)和快遞公司的兩端服務(wù)網(wǎng)絡(luò)優(yōu)勢(shì)，加快推動(dòng)“高鐵網(wǎng)+快遞網(wǎng)”雙網(wǎng)深度融合，全面深化鐵路運(yùn)輸供給側(cè)結(jié)構(gòu)性改革，一些服務(wù)多元、銜接緊密、時(shí)效嚴(yán)格的高鐵快運(yùn)產(chǎn)品被相繼推出。尤其是以中鐵快運(yùn)股份有限公司與順豐速運(yùn)有限公司聯(lián)合推出的“高鐵極速達(dá)”快運(yùn)產(chǎn)品為代表[1]。此類快運(yùn)產(chǎn)品以高鐵動(dòng)車組為載體，通過快遞公司收派端快速駁接網(wǎng)絡(luò)銜接高速鐵路優(yōu)質(zhì)穩(wěn)定的極速運(yùn)力，為客戶提供指定服務(wù)范圍、承諾運(yùn)到時(shí)限的高端快運(yùn)服務(wù)。

高鐵快運(yùn)主要利用高鐵確認(rèn)車、載客動(dòng)車組、預(yù)留車廂、快運(yùn)專列等運(yùn)力資源對(duì)快件包裹提供快捷的站到站服務(wù)[2]。其中，載客動(dòng)車組、高鐵確認(rèn)車、預(yù)留車廂所對(duì)應(yīng)的列車均為圖定列車，其列車時(shí)刻表已經(jīng)確定。并且在鐵路運(yùn)輸中，客運(yùn)服務(wù)相較于貨物運(yùn)輸具有較高的優(yōu)先權(quán)，因而，在利用此類列車組織貨物快運(yùn)時(shí)，一般不對(duì)列車時(shí)刻表進(jìn)行調(diào)整。電子商務(wù)驅(qū)動(dòng)下，尤其一些購(gòu)物節(jié)（如“雙十一”“雙十二”“六一八”等）瘋狂購(gòu)物的背后，第三方物流企業(yè)迎來了空前的快件包裹量。這時(shí)，高鐵快運(yùn)需求激增，圖定列車的能力不能滿足增長(zhǎng)的快運(yùn)需求，需要增開快運(yùn)專列以提高服務(wù)質(zhì)量。

當(dāng)增開快運(yùn)專列時(shí)，在圖定的列車時(shí)刻表確定的條件下，需要編制新增快運(yùn)專列時(shí)刻表。若靠傳統(tǒng)的手工編制，一方面難以保證時(shí)刻表的質(zhì)量，另一方面無疑增加了調(diào)度人員的工作負(fù)擔(dān)。現(xiàn)有對(duì)列車時(shí)刻表的研究大體可以分為2 類，一類是僅從鐵路運(yùn)營(yíng)者的角度出發(fā)，不考慮需求條件下的列車時(shí)刻表優(yōu)化。文獻(xiàn)[3-5]均以列車旅行時(shí)間為優(yōu)化目標(biāo)，建立了列車時(shí)刻表的混合整數(shù)規(guī)劃模型，其中，文獻(xiàn)[3-4]提出了拉格朗日松弛算法對(duì)問題求解，文獻(xiàn)[5]利用分支定界算法對(duì)問題求解。為了從本質(zhì)上揭示鐵路運(yùn)輸需求與運(yùn)輸服務(wù)供給的耦合關(guān)系，提高鐵路客貨運(yùn)服務(wù)質(zhì)量。另一類從需求角度出發(fā)，對(duì)需求驅(qū)動(dòng)下的列車時(shí)刻表進(jìn)行研究。文獻(xiàn)[6]在時(shí)變客流需求條件下，以乘客在站等待時(shí)間為優(yōu)化目標(biāo)，構(gòu)建了列車時(shí)刻表和列車停站方案的非線性整數(shù)規(guī)劃模型，并利用通用求解軟件GAMS對(duì)模型求解。文獻(xiàn)[7]對(duì)越行許可條件下基于時(shí)變客流需求的列車時(shí)刻表進(jìn)行優(yōu)化，并分別建立了定序無越行、定序有限越行及非定序任意越行3 種數(shù)學(xué)模型，利用通用求解器CPLEX對(duì)模型求解。文獻(xiàn)[8]旨在優(yōu)化動(dòng)態(tài)客流驅(qū)動(dòng)下的列車時(shí)刻表，并綜合考慮了列車能耗問題。文獻(xiàn)[9]以需求為響應(yīng)，構(gòu)建了鐵路集裝箱班列始發(fā)時(shí)刻優(yōu)化模型，充分考慮了集裝箱與集裝箱班列在時(shí)間和數(shù)量方面的匹配關(guān)系，并利用遺傳算法對(duì)模型求解。

貨物配裝是鐵路貨物運(yùn)輸過程中的一個(gè)重要環(huán)節(jié)，配裝方案對(duì)貨物的運(yùn)輸效率、運(yùn)到期限有重要影響[10]。高鐵快運(yùn)配裝方案優(yōu)化問題旨在對(duì)專用快運(yùn)箱的配裝時(shí)間和配裝列車進(jìn)行決策，以期提高快件的運(yùn)到時(shí)限和運(yùn)輸效率?，F(xiàn)高鐵快運(yùn)配裝方案主要靠車站工作人員根據(jù)快運(yùn)箱的到達(dá)情況手工編制。這種傳統(tǒng)的編制方法一方面難以保證配裝效率，另一方面可能導(dǎo)致某些快運(yùn)箱長(zhǎng)時(shí)間“壓倉(cāng)”。隨著高鐵快運(yùn)需求的進(jìn)一步增長(zhǎng)，需要對(duì)快運(yùn)箱的裝配方案優(yōu)化決策，而目前鮮有文獻(xiàn)對(duì)此深入研究。值得說明的是，列車時(shí)刻表決定了快運(yùn)箱的配裝時(shí)間和途中運(yùn)輸時(shí)間，進(jìn)而影響配裝列車的選擇。在需求驅(qū)動(dòng)條件下，高鐵快運(yùn)配裝方案和列車時(shí)刻表關(guān)系密切，需對(duì)二者綜合優(yōu)化。

高鐵快運(yùn)作為一種新興的快運(yùn)方式，正受到前所未有的關(guān)注。目前大多文獻(xiàn)主要從快運(yùn)模式、作業(yè)流程、市場(chǎng)機(jī)遇等宏觀方面進(jìn)行探討[11-12]。而鮮有文獻(xiàn)從運(yùn)輸組織優(yōu)化的角度對(duì)高鐵快運(yùn)進(jìn)行研究。與現(xiàn)有相關(guān)文獻(xiàn)相比，本文的創(chuàng)新點(diǎn)如下。

1） 試圖從運(yùn)輸組織優(yōu)化的視角出發(fā)，對(duì)高鐵快運(yùn)列車時(shí)刻表和配裝方案綜合優(yōu)化，完善高鐵快運(yùn)服務(wù)網(wǎng)絡(luò)設(shè)計(jì)理論，以期提高高鐵快運(yùn)的運(yùn)輸效率。

2） 以是否增開快運(yùn)列車為研究問題的切入點(diǎn)，在需求驅(qū)動(dòng)條件下，分別構(gòu)建了與階段計(jì)劃相切合的分階段優(yōu)化的無新增快運(yùn)專列的配裝方案優(yōu)化模型和新增專列時(shí)刻表和配裝方案綜合優(yōu)化模型。

3） 在模型線性化的基礎(chǔ)上，利用通用求解器CPLEX對(duì)模型精確求解，并通過實(shí)例驗(yàn)證了本文模型的正確性和求解方法的有效性。

1 問題分析及說明

1.1 高鐵快運(yùn)產(chǎn)品分析

高鐵快運(yùn)產(chǎn)品主要針對(duì)緊急寄遞需求的商務(wù)信函、標(biāo)書合同、個(gè)人緊急物品、生鮮禮品、電商中小件包裹、行包類等高附加值貨物。目前，高鐵快運(yùn)服務(wù)已在高鐵路網(wǎng)中多條線路經(jīng)停的車站運(yùn)行或試運(yùn)行，服務(wù)范圍基本實(shí)現(xiàn)了直轄市、省會(huì)城市和經(jīng)濟(jì)發(fā)達(dá)縣域全覆蓋。

高鐵快運(yùn)產(chǎn)品作業(yè)流程見圖1。由于鐵路部門在“門到門”“最后一公里”服務(wù)方面能力還較為薄弱，高鐵快運(yùn)產(chǎn)品目前只提供“站到站”的服務(wù)，快件的收發(fā)和配送作業(yè)由第三方快遞企業(yè)收派點(diǎn)完成。收派點(diǎn)按照快件的目的地分類將快件裝入鐵路部門指定或者提供的專用快運(yùn)箱，統(tǒng)一送往對(duì)應(yīng)高鐵車站。鐵路調(diào)度部門根據(jù)高鐵線路（區(qū)段）各個(gè)車站收到的快運(yùn)箱需求統(tǒng)一編制運(yùn)輸服務(wù)方案，并將編制的快運(yùn)專列時(shí)刻表和配裝方案下達(dá)至各高鐵車站，各車站根據(jù)接收的列車時(shí)刻表和配裝方案組織實(shí)施裝車?？爝\(yùn)箱運(yùn)達(dá)對(duì)應(yīng)車站后，車站人員進(jìn)行卸車、拆包分揀作業(yè)，并在指定地點(diǎn)與第三方快遞企業(yè)接駁人員進(jìn)行交接。

圖1 高鐵快運(yùn)作業(yè)流程Fig. 1 Operation process of high-speed railway immediate delivery

1.2 問題分析及假設(shè)

本文以單條高鐵線路為研究對(duì)象，按照運(yùn)輸生產(chǎn)實(shí)際，線路2個(gè)方向列車相互獨(dú)立運(yùn)行，選取其中的1 個(gè)方向進(jìn)行研究。沿著該線路列車運(yùn)行方向，車站集合定義為U ={1,2,…,n}。其中:1 為始發(fā)站；n 為終點(diǎn)站。我國(guó)鐵路列車時(shí)刻表的精確度為1 min，因而按照1 min為間隔對(duì)運(yùn)營(yíng)時(shí)段進(jìn)行離散處理，以1 min 的整數(shù)倍表示列車在車站的到發(fā)時(shí)刻和在區(qū)間的運(yùn)行時(shí)間?？爝\(yùn)箱運(yùn)達(dá)車站的時(shí)間可能不是整數(shù)分鐘，本文將其向下取整，將快運(yùn)箱運(yùn)達(dá)車站的時(shí)間也精確到分鐘，這種近似處理不會(huì)影響優(yōu)化結(jié)果。

事實(shí)上，鐵路部門按階段計(jì)劃組織快運(yùn)列車和配裝運(yùn)箱，見圖2。事實(shí)上，這種按階段計(jì)劃的鐵路運(yùn)輸調(diào)度問題稱為“列車運(yùn)行調(diào)整”，但列車運(yùn)行調(diào)整也屬于列車時(shí)刻表問題的范疇。為便于描述，本文將研究問題界定為高鐵快運(yùn)專列時(shí)刻表優(yōu)化問題。本文將全天運(yùn)營(yíng)時(shí)段按照3～4 h均分為多個(gè)階段，這與鐵路運(yùn)營(yíng)的階段計(jì)劃（調(diào)整計(jì)劃）相切合，本文以3 h 為1 個(gè)階段。在第q + 1 階段開始之前，根據(jù)前一階段q 到達(dá)各車站的快運(yùn)箱及階段q 之前滯留的快運(yùn)箱驅(qū)動(dòng)優(yōu)化第q + 1 階段的配裝方案和列車時(shí)刻表。每個(gè)階段快運(yùn)箱配裝方案和快運(yùn)專列列車時(shí)刻表的優(yōu)化方法均相同。因而，后文中所定義的符號(hào)和建立的模型都是針對(duì)某一階段的。這種按階段計(jì)劃的分階段的方法可以減少快運(yùn)箱在車站的等待時(shí)間，滿足高鐵快運(yùn)產(chǎn)品當(dāng)日達(dá)、次晨達(dá)、次日達(dá)的快運(yùn)需求。

圖2 按階段的需求與配裝方案和列車時(shí)刻表的關(guān)系Fig. 2 Illustration of relationship for the phase-based demand with assignment plan and train timetable

在時(shí)變需求條件下，每分鐘到達(dá)車站的快運(yùn)箱需求是不均衡的，根據(jù)這種動(dòng)態(tài)時(shí)變的需求安排列車服務(wù)供給并將其指派在具體列車上，如何匹配離散的客流需求與列車運(yùn)行線是構(gòu)模的關(guān)鍵，也是本研究的難點(diǎn)。此外由于列車時(shí)刻表本身的組合特性，本質(zhì)上屬于NP-hard問題，使得問題精確求解異常復(fù)雜。值得說明的是，在時(shí)變需求條件下，可分為需求分布確定與需求分布不確定2 種研究思路，根據(jù)這種分階段優(yōu)化方法，本文的研究屬于需求分布確定的情況，而需求分布不確定的研究是將來作者的研究方向。根據(jù)需求與服務(wù)供給之間的匹配關(guān)系可分為2種情況。一種是當(dāng)每列車的能力均能滿足需求時(shí)，即每列車從車站發(fā)出時(shí)，車站再無滯留需求，這時(shí)，最優(yōu)的配裝方案為“先到先上車”。而高鐵快運(yùn)產(chǎn)品的需求屬于另一種是先于本階段列車運(yùn)達(dá)車站的，當(dāng)列車出發(fā)后有快運(yùn)箱滯留，這相當(dāng)于鐵路客運(yùn)客流需求過飽和（超擁擠）的情況[13]，此時(shí)，需要根據(jù)優(yōu)化目標(biāo)和快運(yùn)箱需求決策最優(yōu)的裝配方案。

為方便模型建立，本文作出如下假設(shè)。

1） 本文研究核心是列車時(shí)刻表及配裝方案，而列車開行數(shù)量和列車停站方案均屬于列車開行方案的范疇。假設(shè)列車開行方案確定是研究列車時(shí)刻表問題的一種普遍做法[13-14]。基于此，本文假定階段內(nèi)增開快運(yùn)專列的數(shù)量及停站方案根據(jù)需求分布預(yù)先確定，并且給定快運(yùn)專列的最小和最大停站時(shí)間，列車在該范圍內(nèi)靈活的選擇停站時(shí)間。對(duì)于列車開行數(shù)量及停站方案不確定的情況是作者未來的研究方向。

2） 假設(shè)新增快運(yùn)專列可被圖定列車越行。

1.3 符號(hào)說明

在研究的階段內(nèi)，定義的各類集合、索引、參數(shù)、變量如下。

1） 集合。 Ie為圖定列車集合；Iz為新增的高鐵快運(yùn)專列集合；I 為所有列車集合，I = Ie∪Iz；U為車站集合；B 為快運(yùn)箱集合。

2） 索引。 i,j 為列車索引，i,j ∈I ；k 為高鐵快運(yùn)專列索引，k ∈Iz；u,v 為車站索引，u,v ∈U 。

3） 參數(shù)。 Tb為快運(yùn)柜b 運(yùn)達(dá)對(duì)應(yīng)裝車站的時(shí)間，b ∈B ；Ob和Db分別為快運(yùn)箱b 對(duì)應(yīng)的裝車站和目的站，b ∈B ；Siu為列車i 在u 站是否停站，若停站，=1，否則，=0，i ∈I ，u ∈U ；Ci為列車i 的裝運(yùn)能力；TRiu為列車i 從u 站到u + 1 站的純運(yùn)行時(shí)間，i ∈I ，u ∈U{n}；分別為高鐵快運(yùn)專列k 的最小和最大停站時(shí)間，k ∈Iz；TEk和TLk分別為高鐵快運(yùn)專列k 在始發(fā)站的最早及最晚出發(fā)時(shí)間，k ∈Iz；Hd和Ha分別為列車最小出發(fā)和最小到達(dá)安全間隔；? 表示高鐵快運(yùn)專列的啟停附加時(shí)分；M 為充分大地正整數(shù)。

4） 變量。 tdiu為列車i 在u 站的出發(fā)時(shí)刻；taui為列車i 在u 站的到達(dá)時(shí)刻；tsiu為列車i 在u 站的停站時(shí)間。對(duì)于新增快運(yùn)專列i ∈Iz，列車到達(dá)出發(fā)時(shí)刻和停站時(shí)間為本文的決策變量；當(dāng)列車i 為圖定列車（i ∈Ie）時(shí)，則為參數(shù)；xbi為快運(yùn)箱配裝決策變量，=1，快運(yùn)箱b 配裝在列車i 上，=0，否則；yui,j為列車在車站的出發(fā)順序，=1，表示列車i 在u 站先于列車j 出發(fā)，=0，否則。

2 模型建立

基于分階段優(yōu)化的特點(diǎn)，可根據(jù)上一階段內(nèi)的需求（包括滯留需求）計(jì)算確定規(guī)劃階段內(nèi)是否需要增開快運(yùn)專列及增開快運(yùn)專列的數(shù)量，具體的確定方法本文不再贅述。當(dāng)無新增快運(yùn)專列時(shí)，僅需對(duì)快運(yùn)箱的配裝方案優(yōu)化，即對(duì)快運(yùn)箱配裝在哪列圖定的列車上進(jìn)行決策，進(jìn)而確定規(guī)劃階段內(nèi)列車裝卸及滯留的快運(yùn)箱數(shù)量。當(dāng)需要增開快運(yùn)專列時(shí)，需對(duì)新增的快運(yùn)專列時(shí)刻表和快運(yùn)箱配裝方案綜合優(yōu)化。

下面分別建立無新增快運(yùn)專列條件下的配裝方案優(yōu)化模型（M1）和新增快運(yùn)專列條件下列車時(shí)刻表及配裝方案綜合優(yōu)化模型（M2）。首先需要厘清快運(yùn)箱需求與列車時(shí)刻表和配裝方案的耦合關(guān)系。圖3 展示了列車在途中運(yùn)行、停站以及在各個(gè)車站對(duì)快運(yùn)箱的配裝過程。為方便說明和模型建立，這里引入關(guān)于列車裝載狀態(tài)的3 個(gè)輔助變量，分別定義如下。

2.1 快運(yùn)箱配裝方案優(yōu)化模型（M1）

2.1.1 優(yōu)化目標(biāo)

為減少快運(yùn)箱的運(yùn)達(dá)時(shí)間，提高快運(yùn)箱的運(yùn)到時(shí)效，本文以所有快運(yùn)箱運(yùn)達(dá)裝車站起到運(yùn)達(dá)目的站的總時(shí)間最短為優(yōu)化目標(biāo)，包括快運(yùn)箱在對(duì)應(yīng)裝車站的等待時(shí)間和途中旅行時(shí)間，可描述為

圖3 列車時(shí)刻表和需求耦合關(guān)系Fig. 3 The essential relationship for the train timetable and demand

如果僅以此時(shí)間為優(yōu)化目標(biāo)，可能導(dǎo)致所有快運(yùn)箱均不能裝車，即= 0 ，?i ∈Ie，b ∈B ，此時(shí)目標(biāo)值為0。為避免這種不合理的情況出現(xiàn)，在優(yōu)化目標(biāo)中，為不能在本階段配裝的快運(yùn)箱一個(gè)較大的懲罰，設(shè)P 為懲罰因子。則所有快運(yùn)箱在本階段不能被配裝的懲罰見式（2）。當(dāng)懲罰因子取足夠大的值時(shí)，不會(huì)對(duì)優(yōu)化結(jié)果起決定性的作用。

2.1.2 約束條件

1） 列車出發(fā)時(shí)刻與快運(yùn)箱配裝變量的關(guān)系。當(dāng)列車i 在快運(yùn)箱b 裝車站的出發(fā)時(shí)間晚于快運(yùn)箱b 運(yùn)達(dá)裝車站的時(shí)間Tb，則快運(yùn)箱b 既可以配裝在列車i 上，也可以不配裝在列車i 上，即為0或者為1；當(dāng)列車i 在快運(yùn)箱b 裝車站的出發(fā)時(shí)間tdObi 早于快運(yùn)箱b 運(yùn)達(dá)裝車站的時(shí)間Tb時(shí)，則快運(yùn)箱b 不能配裝在列車i 上，即= 0 。由于本文考慮的快運(yùn)箱均早于列車出發(fā)時(shí)刻運(yùn)達(dá)裝車站，因而，不存在后一種情況。

2） 列車停站與快運(yùn)箱配裝變量的關(guān)系。當(dāng)列車i 在快運(yùn)箱b 的裝車站Ob和目的站Db均停站時(shí)，則快運(yùn)箱b 可能配裝在列車i 上；否則，快運(yùn)箱b不能配裝在列車i 上。

3） 列車裝載狀態(tài)。由圖3 可知，列車i 在u 站裝載的快運(yùn)箱數(shù)量為

列車i 到達(dá)車站u 卸下的快運(yùn)箱數(shù)量為

列車i 從u 站出發(fā)時(shí)車上裝載的快運(yùn)箱數(shù)量為

4） 列車裝載能力。列車i 從u 站出發(fā)時(shí)車上裝載的快運(yùn)箱數(shù)量不能超過列車的裝運(yùn)能力。即

綜上，無新增快運(yùn)專列條件下的配裝方案優(yōu)化模型為

2.2 面向時(shí)變需求的快運(yùn)專列時(shí)刻表及配裝方案綜合優(yōu)化模型（M2）

當(dāng)有新增快運(yùn)列車時(shí)，由假設(shè)1）可知，新增快運(yùn)專列的數(shù)量和停站方案預(yù)先確定。如前文所言，列車時(shí)刻表問題和配裝方案問題關(guān)系密切，需要對(duì)新增快運(yùn)專列的時(shí)刻表和配裝方案綜合優(yōu)化，即綜合確定新增快運(yùn)專列在車站的到發(fā)及停站時(shí)間和快運(yùn)箱的配裝方案。值得說明的是，為簡(jiǎn)化問題，傳統(tǒng)的對(duì)運(yùn)輸組織中2 個(gè)相互影響的問題一般采用“兩階段”的優(yōu)化方法[15-16]，與綜合優(yōu)化相比，這種兩階段優(yōu)化方法難以保證解的質(zhì)量。后文將對(duì)本文采用的綜合優(yōu)化方法和兩階段優(yōu)化方法進(jìn)行比較。

2.2.1 目標(biāo)函數(shù)

新增快運(yùn)專列條件下，仍以所有快運(yùn)箱運(yùn)達(dá)裝車站起到運(yùn)達(dá)目的站的總時(shí)間最短為優(yōu)化目標(biāo)。顯然，目標(biāo)函數(shù)（11）是非線性的，后文將對(duì)該目標(biāo)函數(shù)進(jìn)行線性化處理。

2.2.2 約束條件

1） 快運(yùn)箱裝配?？爝\(yùn)箱的配裝約束在形式上同模型M1的約束（4）～（9），只是這些約束在這里是對(duì)于階段內(nèi)所有列車（?i ∈I ），包括新增的快運(yùn)專列。

2） 新增快運(yùn)專列運(yùn)行。對(duì)于新增快運(yùn)專列k ，給定在始發(fā)站的出發(fā)時(shí)間窗[TEk,TLk] 是大多研究列車時(shí)刻表文獻(xiàn)的普遍方法。為保證新增快運(yùn)專列時(shí)刻表的靈活性，本文取TEk為研究階段的開始時(shí)刻，TLk為研究階段的結(jié)束時(shí)刻。新增列車的出發(fā)時(shí)刻約束、停站時(shí)間約束和運(yùn)行約束分別為式（18）～（20）。

3） 安全間隔及越行。由于新增的快運(yùn)專列可能被圖定的高速列車越行，因而，引入了關(guān)于任意2列列車在車站出發(fā)的順序變量，統(tǒng)一刻畫列車之間的到發(fā)安全間隔約束和越行約束。當(dāng)列車i 先于列車j 在u 站出發(fā)時(shí)，即= 1 ，此時(shí)后行列車j 與前行列車i 在u 和u + 1站分別滿足最小出發(fā)和到達(dá)安全間隔；反之，不等式（21）～（22）恒成立。

綜上，面向時(shí)變需求的高鐵快運(yùn)專列時(shí)刻表及配裝方案綜合優(yōu)化模型為

2.3 模型分析與求解方法

本質(zhì)上，配裝方案優(yōu)化是非標(biāo)準(zhǔn)指派問題，可以利用經(jīng)典的匈牙利算法對(duì)0-1 整數(shù)規(guī)劃模型M1 精確求解[17]。模型M2 為帶有線性約束的非線性混合整數(shù)規(guī)劃模型，對(duì)于此類問題，可以對(duì)模型的非線性目標(biāo)進(jìn)行線性化處理[18]。具體地，引入新的整數(shù)變量，令

該非線性等式可以利用1 組線性約束等價(jià)代替，即

線性化后的模型LM2 可以利用常用的分解算法（如拉格朗日松弛算法、Benders 分解算法、ADMM方法等）將快運(yùn)專列時(shí)刻表及配裝方案綜合優(yōu)化問題分解為分別求解列車時(shí)刻表和配裝方案的子問題，然后單獨(dú)求解子問題，以獲得最優(yōu)解或者近似解[19-21]。

見表1，模型M1的復(fù)雜度主要取決于新增快運(yùn)專列和快運(yùn)箱的數(shù)量。模型LM2 的復(fù)雜度主要由列車數(shù)量、車站數(shù)量及快運(yùn)箱需求數(shù)量決定。根據(jù)本文分階段優(yōu)化的特點(diǎn)，在研究階段內(nèi)，新增列車的數(shù)量一般較少，模型中變量的組合特性不明顯，從而無需設(shè)計(jì)復(fù)雜的求解算法，可以直接利用通用優(yōu)化求解器直接對(duì)模型求解，在較少的時(shí)間可以獲得最優(yōu)解或近似最優(yōu)解?；诖耍疚膶?duì)模型M1和LM2利用通用優(yōu)化軟件GAMS的CPLEX求解器求解。

表1 模型約束數(shù)量Tab. 1 The number of constraints

3 實(shí)例分析

以寧杭高鐵線路為例，選擇全天運(yùn)營(yíng)時(shí)段內(nèi)的第2個(gè)階段（09:00—12:00）為研究對(duì)象。圖定列車時(shí)刻表來源于列車運(yùn)行圖編制系統(tǒng)（實(shí)驗(yàn)版）的2018年第一季度數(shù)據(jù)，該數(shù)據(jù)可能與實(shí)際存在偏差，但并不影響算例分析說明。為方便描述，對(duì)線路上的車站依次編號(hào)為1～11。限于篇幅，本文所使用的圖定列車時(shí)刻表和快運(yùn)箱需求數(shù)據(jù)以及源代碼全部上傳至https://github.com/ruhugao/paper-resource-code。

3.1 無新增快運(yùn)專列條件下配裝方案分析

當(dāng)線路上無新增快運(yùn)專列時(shí)，在圖定列車時(shí)刻表給定的基礎(chǔ)上，僅需要將運(yùn)達(dá)各站的快運(yùn)箱配裝到圖定的列車上，直接利用CPLEX 求解器求解模型M1即可得到最優(yōu)的快運(yùn)箱配裝方案，快運(yùn)箱不能被配裝的懲罰值設(shè)為P =10 000，給定運(yùn)達(dá)線路上各車站的快運(yùn)箱數(shù)量為1 000個(gè)。程序運(yùn)行時(shí)間為0.01 s，目標(biāo)值為2.375 732×106。限于篇幅，這里不再展示具體的快運(yùn)箱配裝方案。最后滯留的快運(yùn)箱的數(shù)量為209，被配裝的快運(yùn)箱總的運(yùn)達(dá)為2.373 7×106-209×10 000=285 732。各車站快運(yùn)箱被服務(wù)及滯留的數(shù)量見圖4，運(yùn)達(dá)車站1～6和10的快運(yùn)箱全部被配裝，由于圖定列車在第7站均不停車，導(dǎo)致該車站的快運(yùn)箱全部滯留。由于列車能力的限制，車站8和車站9部分快運(yùn)箱沒能被配裝。以第8 站為例，各個(gè)列車對(duì)該車站運(yùn)達(dá)的快運(yùn)箱配裝及滯留情況見圖5。

圖4 各車站快運(yùn)箱的配裝及滯留數(shù)量Fig. 4 The loading and remaining amounts of special delivery boxes at each station

3.2 新增快運(yùn)專列時(shí)刻表和配裝方案分析

在新增快運(yùn)專列條件下，傳統(tǒng)的對(duì)列車時(shí)刻表和配裝方案的優(yōu)化方法是兩階段法，即先對(duì)列車時(shí)刻表優(yōu)化，然后在列車時(shí)刻表的基礎(chǔ)上，再優(yōu)化配裝方案。值得說明的是，這里“兩階段”優(yōu)化方法與前文“分階段”優(yōu)化思路的含義不同，前者表示列車時(shí)刻表與配裝方案分2 個(gè)階段優(yōu)化，后者表示按“階段計(jì)劃”的優(yōu)化思路。為便于和本文提出的綜合同優(yōu)化方法比較，將傳統(tǒng)的兩階段法模型定義為SM2。模型SM2 的列車時(shí)刻表優(yōu)化階段一般以列車旅行時(shí)間最短為優(yōu)化目標(biāo)，配裝方案優(yōu)化同樣以快運(yùn)箱運(yùn)達(dá)時(shí)間最少為優(yōu)化目標(biāo)。模型SM2 為

圖5 各列車在第8站的配裝量及發(fā)車后滯留數(shù)量Fig. 5 The loading and remaining amounts of special delivery boxes at the 8-th station for each train

寧杭高鐵列車最小出發(fā)和最小到達(dá)安全間隔均為4 min，給定運(yùn)達(dá)線路上各車站的快運(yùn)箱數(shù)量為5 400 個(gè)，假定新增列車3 列，運(yùn)載能力均設(shè)為400，假定新增列車停站方案為站站停模式，最小停站時(shí)間為2 min，最大停站時(shí)間為15 min。同樣利用CPLEX 求解器對(duì)兩階段優(yōu)化模型LM2 和綜合優(yōu)化模型SM2 求解，結(jié)果見表2。新增快運(yùn)專列后，列車運(yùn)行圖見圖6。

表2 求解結(jié)果比較Tab. 2 The comparison of computing results for model SM2 and LM2

圖6 2種方法優(yōu)化的列車運(yùn)行圖Fig. 6 The optimized train timetable of two different optimizing methods

從結(jié)果中可以看出，兩階段優(yōu)化方法的計(jì)算時(shí)間較短，并且gap 值為0，但目標(biāo)值較大。綜合優(yōu)化方法在可接受的計(jì)算時(shí)間范圍內(nèi)求得近似最優(yōu)解，目標(biāo)值比兩階段法的目標(biāo)更優(yōu)。有趣的是，2種優(yōu)化方法求得的快運(yùn)箱滯留數(shù)量相同，這意味著總的被配裝的快運(yùn)箱數(shù)量也相同，但2種方法快運(yùn)箱的運(yùn)達(dá)時(shí)間卻相差較大。從列車運(yùn)行圖中可以看出，兩階段法在求解列車時(shí)刻表時(shí)沒有考慮需求，求解得到的新增列車運(yùn)行線均位于本階段的末端，導(dǎo)致配裝方案中快運(yùn)箱運(yùn)達(dá)時(shí)間較大。而綜合優(yōu)化方法，在優(yōu)化新增列車時(shí)刻表時(shí)，以需求為導(dǎo)向，使得快運(yùn)箱的運(yùn)達(dá)時(shí)間大大較少，與兩階段優(yōu)化方法相比，總的快運(yùn)100%= 17.80%。

4 結(jié)束語

以高鐵快運(yùn)列車時(shí)刻表為研究對(duì)象，以快運(yùn)箱運(yùn)達(dá)時(shí)間最少為優(yōu)化目標(biāo)，以高鐵快運(yùn)時(shí)變需求為導(dǎo)向，構(gòu)建了無新增快運(yùn)專列條件下的快運(yùn)箱配裝方案優(yōu)化模型（M1）和新增快運(yùn)專列時(shí)刻表和配裝方案綜合優(yōu)化模型（M2）。對(duì)帶有線性約束的非線性混合整數(shù)規(guī)劃模型M2 進(jìn)行了線性化處理，通過對(duì)模型的復(fù)雜度分析，本文利用高效的通用求解軟件GAMS的CPLEX求解器對(duì)模型精確求解。通過實(shí)例驗(yàn)證表明，在時(shí)變需求驅(qū)動(dòng)下的列車時(shí)刻表和配裝方案綜合優(yōu)化方法與傳統(tǒng)的兩階段法優(yōu)化方法相比，更能縮短快運(yùn)需求的運(yùn)達(dá)時(shí)間，提高快運(yùn)需求運(yùn)到時(shí)效性。未來有必要對(duì)新增列車數(shù)量不確定情況下的列車時(shí)刻表進(jìn)行優(yōu)化，提出相應(yīng)的優(yōu)化算法，使得優(yōu)化的列車時(shí)刻表更加貼合實(shí)際，實(shí)現(xiàn)高鐵快運(yùn)的動(dòng)態(tài)調(diào)度。同時(shí)，針對(duì)高鐵網(wǎng)絡(luò)的快運(yùn)列車時(shí)刻表優(yōu)化也是一個(gè)有趣的研究方向。