基于拉格朗日松弛的鐵路行包運(yùn)輸方案編制方法研究

王 澤，潭宇燕，魏玉光

(北京交通大學(xué) 交通運(yùn)輸學(xué)院， 北京 100044)

我國(guó)鐵路行包運(yùn)輸少數(shù)采用行包專列車，多數(shù)仍依托旅客列車編掛的行李車，具有全天候、安全、快速、通達(dá)范圍廣、低碳環(huán)保的優(yōu)點(diǎn)。旅客列車開(kāi)行方案依據(jù)客流流量、流向以及變化規(guī)律確定，考慮行包流的因素較少，因此存在行包運(yùn)輸能力與行包流量、流向不完全匹配的問(wèn)題。解決該問(wèn)題的關(guān)鍵是編制行包運(yùn)輸方案，為行包指定明確的裝運(yùn)和接續(xù)車次。目前，行包運(yùn)輸方案的編制依舊采用傳統(tǒng)編制原則與人工經(jīng)驗(yàn)相結(jié)合的方式，自動(dòng)化水平較低，且難以提高服務(wù)水平。

既有研究主要將行包運(yùn)輸方案編制問(wèn)題分解為行包運(yùn)輸路徑生成和行包流分配兩個(gè)子問(wèn)題來(lái)考慮。

對(duì)于行包運(yùn)輸路徑生成問(wèn)題，文獻(xiàn)[1-2]綜合考慮運(yùn)輸成本、時(shí)間、能力和現(xiàn)場(chǎng)作業(yè)等因素，給出鐵路行包運(yùn)輸路徑的基本形式和選擇策略，設(shè)計(jì)行包運(yùn)輸路徑搜索算法，以實(shí)現(xiàn)對(duì)始發(fā)和中轉(zhuǎn)列車的合理選取。文獻(xiàn)[3]基于先直達(dá)、后1次中轉(zhuǎn)和2次中轉(zhuǎn)的路徑搜索策略，以準(zhǔn)裝區(qū)段限制、作業(yè)接續(xù)時(shí)間等作為約束條件，設(shè)計(jì)基于發(fā)到站坐標(biāo)位置網(wǎng)格圖的行包運(yùn)輸路徑快速算法。文獻(xiàn)[4-5]基于旅客列車運(yùn)行圖構(gòu)建動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)，考慮行包辦理站裝卸作業(yè)時(shí)間、行包中轉(zhuǎn)次數(shù)等限制因素，以時(shí)效性為核心，為每個(gè)OD需求生成可行路徑集合。

對(duì)于行包流分配問(wèn)題。文獻(xiàn)[6-7]基于行包合理路徑集，以利潤(rùn)最大、成本最小或運(yùn)輸時(shí)間最短為目標(biāo)，考慮行李車載運(yùn)能力、車站作業(yè)能力、裝卸作業(yè)時(shí)間等約束，建立線性規(guī)劃模型，使用求解器求解。文獻(xiàn)[8]針對(duì)行包到站分散的特點(diǎn)，以集中到發(fā)為目標(biāo)建立模型，保證行包作業(yè)盡可能集中，降低運(yùn)營(yíng)管理成本。

構(gòu)建行包路徑備選集可以簡(jiǎn)化行包運(yùn)輸網(wǎng)絡(luò)，但備選集的質(zhì)量和合理性極大影響求解結(jié)果；當(dāng)部分行李車運(yùn)能緊張時(shí)，固化的路徑集合也無(wú)法適應(yīng)變化條件下的中轉(zhuǎn)路徑調(diào)整。此外，既有研究普遍未能設(shè)計(jì)有效的求解算法，因此所能求解的模型規(guī)模極大依賴于求解器的計(jì)算能力，耗時(shí)長(zhǎng)、精度差。

本文認(rèn)為該問(wèn)題實(shí)質(zhì)上是行包流在既有旅客列車服務(wù)網(wǎng)絡(luò)上的配流問(wèn)題，其網(wǎng)絡(luò)不能僅僅理解為行包運(yùn)輸?shù)奈锢砭W(wǎng)絡(luò)，而應(yīng)當(dāng)拓展為能體現(xiàn)旅客列車服務(wù)網(wǎng)絡(luò)特點(diǎn)的時(shí)空網(wǎng)絡(luò)。

受限于旅客列車運(yùn)程，長(zhǎng)程行包運(yùn)輸往往需要由相互銜接的旅客列車配合完成，在各旅客列車的銜接點(diǎn)進(jìn)行中轉(zhuǎn)作業(yè)。少量行包可以在中間站利用途經(jīng)列車停站時(shí)間完成中轉(zhuǎn)裝卸作業(yè)，大批量的行包只能在前一個(gè)列車的終到站同時(shí)也是接續(xù)列車的始發(fā)站進(jìn)行中轉(zhuǎn)作業(yè)。主要采用行包裝卸方式實(shí)現(xiàn)中轉(zhuǎn)，在一定條件下也可以采用行李車整車換掛方式。因此，這一類時(shí)空網(wǎng)絡(luò)配流問(wèn)題又具有不同于其他時(shí)空網(wǎng)絡(luò)配流問(wèn)題的特點(diǎn)和復(fù)雜性。

針對(duì)既有研究的不足，本文根據(jù)該問(wèn)題的性質(zhì)和特點(diǎn)將行包運(yùn)輸物理網(wǎng)絡(luò)拓展為時(shí)空網(wǎng)絡(luò)，通過(guò)引入行包中轉(zhuǎn)弧，可實(shí)現(xiàn)在一定變化條件下行包中轉(zhuǎn)路徑的調(diào)整；為突破大規(guī)模網(wǎng)絡(luò)問(wèn)題受限于求解器計(jì)算能力的瓶頸，提出基于拉格朗日松弛的求解算法，通過(guò)將原始問(wèn)題分解為相互獨(dú)立的子問(wèn)題，實(shí)現(xiàn)模型的高效精確求解；針對(duì)拉格朗日下界解不可行的缺點(diǎn)，設(shè)計(jì)相應(yīng)的上界啟發(fā)式算法，進(jìn)一步提高求解效率。

1 行包運(yùn)輸時(shí)空網(wǎng)絡(luò)構(gòu)建

行包運(yùn)輸作業(yè)包括發(fā)送作業(yè)、在途運(yùn)輸、到達(dá)作業(yè)3個(gè)主要過(guò)程，其中在途運(yùn)輸包括途中運(yùn)輸和中轉(zhuǎn)作業(yè)兩個(gè)子過(guò)程。行包運(yùn)輸方案編制問(wèn)題的核心是確定在途運(yùn)輸過(guò)程中行包中轉(zhuǎn)作業(yè)的辦理車站以及行包流在各旅客列車間的合理分配。旅客列車按照列車運(yùn)行圖開(kāi)行，而列車運(yùn)行圖是列車具體時(shí)空位置的圖解，因此行包的在途運(yùn)輸過(guò)程可以用時(shí)空網(wǎng)絡(luò)來(lái)描述。

A為旅客列車車次集合，a∈A；r為規(guī)劃時(shí)段內(nèi)車次a的開(kāi)行列數(shù)序號(hào)，r=1,2,…,ra；tarr(a,r,i)、tdep(a,r,i)分別為車次a的第r列車在行包辦理站i的到達(dá)、發(fā)出時(shí)刻；K為行包集合，k∈K；O(k)、D(k)分別為行包k始發(fā)站、終到站；tEDT(k)為最早發(fā)出時(shí)刻，指行包k發(fā)送作業(yè)的最早完成時(shí)刻；tLAT(k)為最晚到達(dá)時(shí)刻，指行包k到達(dá)作業(yè)的最晚開(kāi)始時(shí)刻；vk為該批行包的質(zhì)量,t；ek為行包的最大在途時(shí)間,h，ek=tLAT(k)-tEDT(k)。行包作業(yè)過(guò)程及各項(xiàng)時(shí)間關(guān)系見(jiàn)圖1。

G′=(V′,E′)為行包物理網(wǎng)絡(luò)；V′為行包辦理站集，i，j∈V′；E′為相鄰站間的運(yùn)行區(qū)間集，(i,j)∈E′。引入時(shí)間維度t∈T，將其拓展為時(shí)空網(wǎng)絡(luò)G=(V,E)，其中：V為時(shí)空點(diǎn)集，(i,t)∈V；E為時(shí)空弧集，(i,j,t,t′)∈E。行包物理網(wǎng)絡(luò)與對(duì)應(yīng)的時(shí)空網(wǎng)絡(luò)見(jiàn)圖2。

時(shí)空網(wǎng)絡(luò)的構(gòu)建步驟如下：

Step1將每個(gè)行包辦理站i拓展為列車到達(dá)層和列車出發(fā)層，按照時(shí)間順序分別排列列車到達(dá)時(shí)空點(diǎn)(i,t)∈Varr和出發(fā)時(shí)空點(diǎn)(i,t)∈Vdep，其中Varr為達(dá)到時(shí)空點(diǎn)集，Vdep為出發(fā)時(shí)空點(diǎn)集，以此來(lái)表示旅客列車的進(jìn)站和出站操作。

Step2為每批行包k∈K添加起始時(shí)空點(diǎn)(i=O(k),t=tEDT(k))∈Vsource、終到時(shí)空點(diǎn)(j=D(k),t′=tLAT(k))∈Vsink及虛擬弧(i=O(k),j=D(k),t=tEDT(k),t′=tLAT(k))∈Evirtual，Vsource、Vsink、Evirtual分別為起始時(shí)空點(diǎn)集、終到時(shí)空點(diǎn)集、虛擬弧集。起訖時(shí)空點(diǎn)既表示其在途運(yùn)輸過(guò)程的開(kāi)始和結(jié)束，也體現(xiàn)了最大在途時(shí)間約束；虛擬弧則保證了起訖時(shí)空點(diǎn)間的連通性。

Step3添加區(qū)間運(yùn)行弧和列車停站弧。區(qū)間運(yùn)行弧(i,j,t,t′)∈Etrain表示行包隨列車a于時(shí)刻t=tdep(a,r,i)從行包辦理站i發(fā)出，然后于時(shí)刻t′=tarr(a,r,i)到達(dá)相鄰行包辦理站j的途中運(yùn)輸過(guò)程；列車停站弧(i,i,t,t′)∈Etrain表示行包隨列車a于時(shí)刻t=tarr(a,r,i)到達(dá)行包辦理站i，在站停靠，然后于時(shí)刻t′=tdep(a,r,i)從該站發(fā)出的過(guò)程，Etrain為區(qū)間運(yùn)行弧和列車停站弧并集。

Step5添加行包終到弧(i,i,t,t′)∈Esink。該弧表示行包k于時(shí)刻t=tarr(a,r,i)隨列車a抵達(dá)終到站i=D(k)，其中t′=tLAT(k)為行包的最晚到達(dá)時(shí)刻。

(1)

區(qū)間運(yùn)行弧和列車停站弧的費(fèi)用為相應(yīng)的持續(xù)時(shí)間，行包終到弧的費(fèi)用為0，行包虛擬弧的費(fèi)用為行包的最大在途時(shí)間。為減少行包在站停留時(shí)間，引入在站懲罰系數(shù)βk=(|T|/ek)·(1+0.1gi)≥1，其中：gi為行包辦理站的車站等級(jí)(0、1、2、3、4、5分別對(duì)應(yīng)特等站、一等站、二等站、三等站、四等站、五等站)；|T|為規(guī)劃時(shí)長(zhǎng)。行包越緊急、行包辦理站的車站等級(jí)越低，其懲罰性越強(qiáng)。使用在站懲罰系數(shù)將行包始發(fā)弧和中轉(zhuǎn)弧的費(fèi)用修正為βk·(t′-t)。各時(shí)空弧的費(fèi)用為

(2)

2 行包運(yùn)輸方案編制模型

2.1 問(wèn)題假設(shè)和輸入

模型基于以下假設(shè)：

①行李車能力假設(shè)。僅以重量來(lái)衡量行李車的載運(yùn)能力，不考慮行包體積對(duì)載運(yùn)能力的影響；不考慮行包的混裝限裝規(guī)定。

②行包辦理站能力假設(shè)。假設(shè)行包辦理站的站存能力富裕，能夠滿足行包大量堆放的要求；不考慮裝卸工人、裝卸機(jī)械的數(shù)量和效率對(duì)行包裝卸作業(yè)的影響，假設(shè)行包在規(guī)定的中轉(zhuǎn)時(shí)間內(nèi)均能完成中轉(zhuǎn)作業(yè)。

③運(yùn)輸路徑唯一假設(shè)。每批行包不可拆分，僅能選擇唯一的運(yùn)輸路徑來(lái)完成途中運(yùn)輸。

④模型優(yōu)化目標(biāo)假設(shè)。僅以時(shí)間最短作為優(yōu)化目標(biāo)，不考慮行包作業(yè)各項(xiàng)收支對(duì)運(yùn)輸方案的影響。

模型輸入為：

①各批行包k∈K的始發(fā)站O(k)、終到站D(k)、最早發(fā)出時(shí)間tEDT(k)、最晚到達(dá)時(shí)間tLAT(k)及重量vk。

②行包物理網(wǎng)絡(luò)G′=(V′,E′)。

③規(guī)劃時(shí)段范圍T內(nèi)的列車時(shí)刻表，包括列車車次a∈A、開(kāi)行列數(shù)r=1,2,…,ra，以及列車在各途經(jīng)站的到達(dá)時(shí)刻tarr(a,r,i)和出發(fā)時(shí)刻tdep(a,r,i)。

2.2 模型構(gòu)建

行包運(yùn)輸方案編制問(wèn)題本質(zhì)上是大規(guī)模有限時(shí)空網(wǎng)絡(luò)資源利用問(wèn)題。基于已構(gòu)建的時(shí)空網(wǎng)絡(luò)，將行包運(yùn)輸方案編制問(wèn)題轉(zhuǎn)化為多商品流問(wèn)題。通過(guò)對(duì)時(shí)空網(wǎng)絡(luò)中各項(xiàng)弧權(quán)的合理設(shè)定，如費(fèi)用、時(shí)間或兩者的加權(quán)求和，可以根據(jù)不同的優(yōu)化目標(biāo)對(duì)目標(biāo)方程進(jìn)行改進(jìn)。以行包方案編制問(wèn)題中最具代表性的總時(shí)間最短作為優(yōu)化目標(biāo)。由于最大在途時(shí)間約束、始發(fā)時(shí)間約束和中轉(zhuǎn)接續(xù)時(shí)間約束已嵌入時(shí)空網(wǎng)絡(luò)中，模型僅需考慮行李車載運(yùn)能力約束和行包中轉(zhuǎn)次數(shù)約束。

目標(biāo)方程為

(3)

式中：X={xk(i,j,t,t′)}k∈K,(i,j,t,t′)∈E為0-1變量，若行包k選擇時(shí)空弧(i,j,t,t′)，則xk(i,j,t,t′)為1，否則為0。

約束條件：

(1)行包流守恒約束

(4)

式中：(i=O(k),t=tEDT(k))、(i=D(k),t=tLAT(k))分別為行包k的起訖時(shí)空點(diǎn)。該約束規(guī)定了各時(shí)空點(diǎn)的流量平衡。

(2)行李車載運(yùn)能力約束

?(i,j,t,t)∈Etrain

(5)

該約束規(guī)定行李車載運(yùn)的行包重量不可超過(guò)其最大載重量。

(3)行包中轉(zhuǎn)次數(shù)約束

(6)

(4)二元變量約束

(7)

由此得到原問(wèn)題P為

(8)

s.t.

式(4)～式(7)

3 基于拉格朗日松弛的求解方法

在行包運(yùn)輸網(wǎng)絡(luò)中，每批行包的中轉(zhuǎn)站點(diǎn)在一定范圍內(nèi)都是可選擇的，中轉(zhuǎn)自由度的增加使可行徑路集增大，問(wèn)題的規(guī)模也隨之?dāng)U大。為此，本文引入拉格朗日松弛技術(shù)。

拉格朗日松弛是選擇原問(wèn)題P中的困難約束(式(5)、式(6))，添加拉格朗日乘子，將其乘積作為懲罰項(xiàng)帶入原目標(biāo)方程中，從而將原問(wèn)題分解為多個(gè)易于求解的子問(wèn)題。通過(guò)求解拉格朗日松弛問(wèn)題，可以獲得原問(wèn)題P的最優(yōu)邊界。經(jīng)過(guò)拉格朗日乘子的不斷迭代更新，松弛解逐步逼近原問(wèn)題的最優(yōu)解[9]。

3.1 原問(wèn)題的拉格朗日松弛

引入車載能力乘子λ={λ(i,j,t,t′)≥0}(i,j,t,t′)∈Etrain和行包中轉(zhuǎn)次數(shù)乘子μ={μk≥0}k∈K，將行李車載運(yùn)能力約束和行包中轉(zhuǎn)次數(shù)約束松弛至原目標(biāo)方程中，得到新的目標(biāo)方程FLR(X,λ,μ)為

(9)

(10)

由此得到拉格朗日松弛問(wèn)題LR為

(11)

s.t.

式(4)、式(7)、式(9)

給定拉格朗日乘子，松弛問(wèn)題LR為|K|個(gè)相互獨(dú)立的最小費(fèi)用路徑子問(wèn)題，可通過(guò)標(biāo)號(hào)設(shè)定算法求解[10]。求解該問(wèn)題得到是原問(wèn)題P的松弛域下界，為獲得最逼近上界可行解的下界，需要構(gòu)造拉格朗日對(duì)偶問(wèn)題LD為

(12)

s.t.

式(4)、式(7)、式(9)、式(11)

一般采用次梯度方法來(lái)求解該問(wèn)題[11]，通過(guò)迭代更新拉格朗日乘子來(lái)逐步逼近原問(wèn)題P的最優(yōu)解。詳細(xì)求解步驟見(jiàn)3.3節(jié)。

3.2 上界啟發(fā)式算法

由于原問(wèn)題P的可行域被擴(kuò)大，拉格朗日對(duì)偶問(wèn)題LD的下界解可能違背部分松弛約束[11]。因此，本節(jié)給出啟發(fā)式算法來(lái)獲得上界可行解。該算法結(jié)合下界解中行包流在時(shí)空網(wǎng)上的路徑信息，依照最晚到達(dá)時(shí)間的先后順序，檢索出不滿足中轉(zhuǎn)次數(shù)約束和行李車載運(yùn)能力約束的行包，然后將其分配至運(yùn)能充足且時(shí)間最短的可行路徑中，從而將不可行解調(diào)整為可行解。本算法先對(duì)每條時(shí)空弧進(jìn)行行包的試分配，通過(guò)將試分配后流量大于能力的飽和時(shí)空弧排除，保證了新時(shí)空路徑的可行性。若新解優(yōu)于已知最優(yōu)可行解，則將其保留。

上界啟發(fā)代算法步驟為

Step0初始化

以“tLAT(k)降序”為主序、“vk升序”為輔序，對(duì)行包排序得到K′；初始化上界時(shí)空弧累計(jì)流量為

fUB(i,j,t,t′)←fLB(i,j,t,t′) ?(i,j,t,t′)∈Etrain

初始化上界可行解

Step1檢索超過(guò)最大中轉(zhuǎn)次數(shù)限制的行包：

O(|K|·|E|)

Step1.1更新已分配和待分配行包集合為

Step1.2更新時(shí)空弧累計(jì)流量為

Step1.3中轉(zhuǎn)弧費(fèi)用為

Step1.4重置變量為

Step2檢索使行李車能力過(guò)載的行包：

O(|Ktrain|2·|E|)

Step2.2時(shí)空弧累計(jì)流量為

Step2.3重置變量為

Step2.4若fUB(i,j,t,t′)≤Ccap(i,j,t,t′) 則跳出Step2.1，繼續(xù)檢驗(yàn)下一條列車時(shí)空弧。

否則返回Step2.1，檢索下一批行包。

Step3行包再分配：

O(|K|·(log2|V|+|Etrain|))

Step3.1識(shí)別能力飽和的時(shí)空弧：

對(duì)每條列車時(shí)空弧(i,j,t,t′)∈Etrain，若fUB(i,j,t,t′)+vk>Ccap(i,j,t,t′)，則ck(i,j,t,t′)←+∞。

Step3.4更新時(shí)空弧累計(jì)流量為

Step4計(jì)算上界并更新上界可行解：

O(|K|·|E|)

算法結(jié)束。

3.3 拉格朗日求解算法

在每步迭代中，拉格朗日求解算法基于當(dāng)前各時(shí)空弧的懲罰費(fèi)用(車載能力乘子λ和中轉(zhuǎn)次數(shù)乘子μ)更新弧權(quán)、分配各批行包至最小費(fèi)用路徑中，并計(jì)算中轉(zhuǎn)次數(shù)、累計(jì)流量以及下界值。通過(guò)調(diào)用3.2節(jié)中的上界啟發(fā)式算法，下界解被調(diào)整為新的上界可行解。若上、下界值收斂至容許誤差范圍內(nèi)，則算法結(jié)束。否則，基于當(dāng)前行包流對(duì)行李車載運(yùn)能力約束和行包中轉(zhuǎn)次數(shù)約束的違反程度，次梯度和拉格朗日乘子將得到更新，以作為各時(shí)空弧新的懲罰費(fèi)用。若迭代次數(shù)達(dá)到設(shè)定的最大值，算法結(jié)束，否則將進(jìn)入下一輪迭代。

拉格朗日求解算法步驟為

初始化：初始化迭代步數(shù)和最優(yōu)下界值：n←0；zLB←-∞；初始化車載能力乘子和中轉(zhuǎn)次數(shù)乘子為

初始化上界可行解和上界值為

zUB←+∞

Step1對(duì)每批行包執(zhí)行Step1.1 ～ Step1.3：O(|K|·(log2|V|+|E|))

Step1.1更新時(shí)空弧費(fèi)用

區(qū)間運(yùn)行弧和列車停站弧為

行包中轉(zhuǎn)弧為

?(i,i,t,t′)∈Etr

Step1.2搜尋最小費(fèi)用路徑得到

Step1.3更新中轉(zhuǎn)次數(shù)為

Step2更新時(shí)空弧累計(jì)流量為

Step3更新下界值

Step4更新上界可行解為

O[|K|·|E|+|Ktrain|2·|E|+|K|·(log2|V|+|Etrain|)]

Step5計(jì)算誤差率：若(zUB-zLB)/zUB≤εgap，算法結(jié)束，否則執(zhí)行Step6。

Step6更新次梯度及迭代步長(zhǎng)：

O(|K|+|Etrain|)

車載能力次梯度為

中轉(zhuǎn)次數(shù)次梯度為

Step7更新乘子：O(|K|+|Etrain|)

車載能力乘子為

中轉(zhuǎn)次數(shù)乘子為

Step8更新迭代步數(shù)：n←n+1；若n>N，算法結(jié)束，否則返回Step1。

本文模型為多商品流問(wèn)題，屬二元整數(shù)組合規(guī)劃，因此必存在有限最優(yōu)解[9]。拉格朗日算法是針對(duì)該類問(wèn)題的一種有效算法，已被廣泛應(yīng)用。但在求解過(guò)程該算法松弛了模型的部分困難約束，擴(kuò)大了相應(yīng)可行域，導(dǎo)致拉格朗日求解算法收斂至平衡態(tài)時(shí)未必能夠得到原問(wèn)題的最優(yōu)可行解，僅為其下界[11]。盡管本文提出的上界啟發(fā)式算法能彌補(bǔ)解不可行的不足，但也依賴于下界解的質(zhì)量，難以保證解的最優(yōu)性。

4 案例驗(yàn)證

相關(guān)算法基于Python編程語(yǔ)言實(shí)現(xiàn)，所有實(shí)驗(yàn)均在一臺(tái)Intel Core i7-9750 H CPU @2.60 GHz, 16 GB RAM的個(gè)人計(jì)算機(jī)上進(jìn)行。

4.1 小規(guī)模案例

以包含8個(gè)行包辦理站、單日10對(duì)列車的小規(guī)模網(wǎng)絡(luò)驗(yàn)證算法的計(jì)算效率。線站示意圖見(jiàn)圖3。

列車時(shí)刻表見(jiàn)表1。每批行包的重量和初始行李車載運(yùn)能力分別從均值為1.5，標(biāo)準(zhǔn)差為0.3以及均值為5，標(biāo)準(zhǔn)差為1.5的正態(tài)分布中隨機(jī)抽樣產(chǎn)生，單位為噸。運(yùn)到期限按400 km內(nèi)為3 d、每增加400 km遞增1 d的方法確定[12]。各辦理站間的運(yùn)價(jià)里程和運(yùn)到期限見(jiàn)圖4。假定行包的發(fā)送和到達(dá)作業(yè)共耗時(shí)1 d，則最大在途時(shí)間為其運(yùn)到期限減去1 d。最早發(fā)出時(shí)間均為規(guī)劃時(shí)段首日的18:00。每列車編掛一輛行李車。最大在途時(shí)間為2～3、4～5、6 d及以上的行包最大中轉(zhuǎn)次數(shù)分別為1、2、3。最大迭代次數(shù)N為200，容許誤差率εgap為5%，中轉(zhuǎn)弧懲罰系數(shù)γ取1.5，系數(shù)α初值取2。求解器GUROBI 9.0保持默認(rèn)設(shè)置。

表1 小規(guī)模案例列車時(shí)刻表(單日)

為詳細(xì)對(duì)比拉格朗日算法和求解器GUROBI的計(jì)算效率，設(shè)計(jì)4組不同規(guī)模的實(shí)驗(yàn)。各組模型規(guī)模見(jiàn)表2,實(shí)驗(yàn)信息見(jiàn)表3，時(shí)空網(wǎng)絡(luò)規(guī)模見(jiàn)表4。

表2 小規(guī)模案例模型規(guī)模

表3 小規(guī)模案例實(shí)驗(yàn)信息

表4 小規(guī)模案例時(shí)空網(wǎng)絡(luò)規(guī)模

不同規(guī)模網(wǎng)絡(luò)下算法上界、下界隨迭代次數(shù)變化曲線見(jiàn)圖5，其中下界與上界分別可在第75、35步迭代時(shí)趨于穩(wěn)定。誤差率隨迭代次數(shù)變化曲線見(jiàn)圖6。由圖6可知，不同規(guī)模網(wǎng)絡(luò)下的上下界誤差率均可在第75步迭代時(shí)達(dá)到6%左右，證明算法的收斂性較好。圖7為不同規(guī)模下兩者達(dá)到相同誤差率的耗時(shí)對(duì)比。由圖7可見(jiàn)，隨著規(guī)模的增大，拉格朗日求解算法較GUROBI的計(jì)算時(shí)間增長(zhǎng)較為緩慢，由此證明了拉格朗日求解算法的高效性。若增大步長(zhǎng)系數(shù)α的初值，預(yù)計(jì)算法的收斂效果會(huì)更好。

4.2 大規(guī)模實(shí)例

以哈爾濱鐵路局和沈陽(yáng)鐵路局集團(tuán)有限公司管轄范圍內(nèi)的行包運(yùn)輸網(wǎng)絡(luò)為背景，驗(yàn)證模型和算法對(duì)真實(shí)案例的適用性。本實(shí)例包含行包辦理站205個(gè)，單日列車299對(duì)，行包500批。|T|=8 d。列車停站時(shí)間小于3 min則視作從該站通過(guò)。車站等級(jí)與各站單日經(jīng)停列車數(shù)見(jiàn)圖8、圖9。最大在途時(shí)間為2～3、4～6 d的行包最大中轉(zhuǎn)次數(shù)分別為2、3、6 d及以上的行包不限制中轉(zhuǎn)次數(shù)。由于求解效率過(guò)低且內(nèi)存占用較大，不使用GUROBI進(jìn)行求解。為減少求解時(shí)間，設(shè)置拉格朗日步長(zhǎng)系數(shù)α初值為5，并采取前100次迭代中每10步、后續(xù)每50步調(diào)用一次上界啟發(fā)式算法的求解策略。其他設(shè)定同4.1節(jié)。

時(shí)空網(wǎng)絡(luò)規(guī)模與模型規(guī)模見(jiàn)表5、表6。

表5 大規(guī)模實(shí)例時(shí)空網(wǎng)絡(luò)規(guī)模

表6 大規(guī)模實(shí)例模型規(guī)模

經(jīng)300次迭代，耗時(shí)5 h 50 min，求得的上界、下界分別為16 734.375、15 607.310 t·h，誤差率為8.735%，上、下界及誤差率隨迭代次數(shù)的變化曲線見(jiàn)圖10。算法的收斂效果良好。

最大在途時(shí)間側(cè)面反映了行包的運(yùn)距。運(yùn)輸時(shí)間情況見(jiàn)圖11。由圖11可知，運(yùn)距每增長(zhǎng)400 km，運(yùn)輸時(shí)間約增加4～5 h，在站停留時(shí)間約增加2 h。中轉(zhuǎn)情況見(jiàn)圖12,由圖12可知，隨著運(yùn)距的增加，直達(dá)行包占比下降，中轉(zhuǎn)行包占比上升。

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

基于旅客列車行李車的時(shí)空特性，本文將行包運(yùn)輸方案編制問(wèn)題轉(zhuǎn)化為基于時(shí)空網(wǎng)絡(luò)的多商品流問(wèn)題；并以時(shí)間最短為目標(biāo)，考慮行李車載運(yùn)能力、中轉(zhuǎn)次數(shù)及各項(xiàng)時(shí)間約束，建立了混合整數(shù)規(guī)劃模型。針對(duì)模型規(guī)模龐大、求解困難的問(wèn)題，設(shè)計(jì)了基于拉格朗日松弛的求解算法，將原問(wèn)題分解為一系列易于求解的子問(wèn)題；并給出了上界可行解啟發(fā)式算法。

算例結(jié)果表明，與商用求解器相比，本文提出的模型與算法具備高效求解大規(guī)模行包運(yùn)輸方案編制問(wèn)題的能力。若算法采用更為高級(jí)的C++語(yǔ)言編程實(shí)現(xiàn)，且在性能更強(qiáng)的工作站中引入并行計(jì)算技術(shù)，計(jì)算效率將進(jìn)一步提升。

在未來(lái)研究中，我們會(huì)進(jìn)一步考慮行包辦理站裝卸作業(yè)能力和倉(cāng)儲(chǔ)能力對(duì)行包運(yùn)輸方案編制問(wèn)題的影響。