江雨星，李和壁

(1. 蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070;2. 中國(guó)鐵道科學(xué)研究院 鐵道科學(xué)技術(shù)研究發(fā)展中心，北京 100081)

作為貨物運(yùn)輸物流化的主要形式，鐵路集裝箱運(yùn)輸在現(xiàn)代物流和國(guó)際集裝箱多式聯(lián)運(yùn)體系中居于重要地位[1].每日有大量的集裝箱通過(guò)公路交通送至鐵路集裝箱辦理站，由辦理站間組織開(kāi)行的集裝箱班列進(jìn)行運(yùn)輸.對(duì)于這樣的鐵路集裝箱運(yùn)輸決策問(wèn)題，最重要的任務(wù)就是設(shè)計(jì)合理的集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò).高質(zhì)量的運(yùn)輸服務(wù)網(wǎng)絡(luò)，不僅可滿(mǎn)足多樣化的運(yùn)輸需求、提高客戶(hù)滿(mǎn)意度，同時(shí)還能保證鐵路企業(yè)的高效運(yùn)營(yíng)及盈利.可見(jiàn)，鐵路集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)與優(yōu)化具有重要的現(xiàn)實(shí)意義.

運(yùn)輸服務(wù)網(wǎng)絡(luò)理論在交通運(yùn)輸領(lǐng)域中的應(yīng)用極為廣泛，如航空企業(yè)中航班時(shí)刻表的優(yōu)化[2]、公路貨運(yùn)中車(chē)輛運(yùn)行路徑的確定[3]、海洋運(yùn)輸中船舶在各航線(xiàn)上的合理分配[4]、鐵路運(yùn)輸中旅客列車(chē)開(kāi)行方案的編制[5]及客流分配[6].對(duì)于鐵路貨物運(yùn)輸服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)，國(guó)內(nèi)外學(xué)者作了大量研究.Crainic[7]系統(tǒng)性的闡述了運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的理論與方法.Newton等[8]將貨物列車(chē)編組計(jì)劃轉(zhuǎn)化為服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題.王保華等[9]為解決快捷貨物運(yùn)輸動(dòng)態(tài)服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題，建立了線(xiàn)性整數(shù)規(guī)劃模型.沈睿[10]針對(duì)鐵路行包快運(yùn)服務(wù)產(chǎn)品，研究了運(yùn)輸服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)方法.唐金金等[11]將列車(chē)開(kāi)行方案轉(zhuǎn)化為服務(wù)網(wǎng)絡(luò)，構(gòu)建了服務(wù)網(wǎng)絡(luò)動(dòng)態(tài)配流的優(yōu)化模型.Duan等[12]在設(shè)計(jì)運(yùn)輸服務(wù)網(wǎng)絡(luò)時(shí)，綜合考慮了鐵路貨物運(yùn)輸?shù)臅r(shí)效性及可靠性.

部分學(xué)者專(zhuān)門(mén)研究了鐵路集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的問(wèn)題.Newman等[13]以成本最小為優(yōu)化目標(biāo)建立了整數(shù)規(guī)劃模型，將大量集裝箱有效分配到開(kāi)行的班列上.閆海峰等[14]采用遺傳算法求解構(gòu)建的集裝箱班列開(kāi)行方案優(yōu)化模型.張小強(qiáng)等[15]為分析運(yùn)輸價(jià)格制定與班列開(kāi)行決策之間的關(guān)系，構(gòu)建了雙層規(guī)劃模型.夏陽(yáng)等[16]研究了客運(yùn)化模式下集裝箱班列開(kāi)行方案的編制問(wèn)題.

現(xiàn)有的鐵路集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的研究，雖已通過(guò)建立數(shù)學(xué)模型及設(shè)計(jì)求解算法，確定出班列運(yùn)行徑路、開(kāi)行頻度及箱流分配方案，但是在此過(guò)程中較少考慮集裝箱辦理站裝卸能力及鄰接路段通過(guò)能力的約束.同時(shí)，隨著鐵路企業(yè)運(yùn)輸服務(wù)質(zhì)量的不斷改進(jìn)，客戶(hù)對(duì)于集裝箱運(yùn)輸?shù)臅r(shí)效性提出了更高的要求，而現(xiàn)有文獻(xiàn)很少考慮.本文綜合考慮集裝箱辦理站裝卸能力、鄰接路段通過(guò)能力及集裝箱運(yùn)到期限的要求，構(gòu)建鐵路集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的線(xiàn)性混合整數(shù)規(guī)劃模型，并設(shè)計(jì)基于遺傳算法的求解方法.

1 問(wèn)題描述

目前，我國(guó)鐵路企業(yè)組織開(kāi)行的集裝箱班列主要為直達(dá)班列，即班列從出發(fā)站至到達(dá)站間途中不辦理任何集裝箱裝卸和車(chē)組甩掛作業(yè).基于此，本文考慮任意兩集裝箱辦理站間開(kāi)行的集裝箱班列均為直達(dá)班列.依據(jù)運(yùn)輸服務(wù)網(wǎng)絡(luò)構(gòu)建思想，將鐵路物理網(wǎng)絡(luò)中的辦理站作為服務(wù)網(wǎng)絡(luò)中的節(jié)點(diǎn)，辦理站間開(kāi)行的所有直達(dá)去向作為服務(wù)網(wǎng)絡(luò)中有向服務(wù)弧段集合.如圖1所示，已知設(shè)有4個(gè)辦理站和4條有向路段的鐵路網(wǎng)絡(luò)，其對(duì)應(yīng)開(kāi)行的全部可能直達(dá)去向如圖2所示.將這4個(gè)辦理站作為服務(wù)網(wǎng)絡(luò)中的節(jié)點(diǎn)，所有直達(dá)去向作為節(jié)點(diǎn)間的服務(wù)弧段集合，如圖3所示.需要說(shuō)明的是，本次研究中各服務(wù)弧段對(duì)應(yīng)的直達(dá)去向在物理網(wǎng)絡(luò)中的實(shí)際運(yùn)行路徑均已給定，為出發(fā)站至到達(dá)站間的最短路徑.例如：圖3中服務(wù)弧段1對(duì)應(yīng)的直達(dá)去向?yàn)檗k理站1→辦理站4，其在物理網(wǎng)絡(luò)中(圖1)的實(shí)際運(yùn)行路徑由路段1和路段2組成.

依據(jù)鐵路貨運(yùn)系統(tǒng)中同股車(chē)流不可拆分的性質(zhì)，本文假設(shè)同一OD間的箱流同樣是不可拆分的.鐵路集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)，就是在服務(wù)弧段集合中選出一系列連續(xù)的弧段組成服務(wù)路徑來(lái)運(yùn)輸節(jié)點(diǎn)間的集裝箱，并確定各弧段的服務(wù)頻度(即服務(wù)弧段關(guān)聯(lián)起點(diǎn)與終點(diǎn)間開(kāi)行的直達(dá)班列數(shù)量).對(duì)于任意兩節(jié)點(diǎn)間的箱流，可能有多條服務(wù)路徑供其選擇，不同的服務(wù)路徑表示不同的運(yùn)輸作業(yè)過(guò)程.例如：對(duì)于起點(diǎn)為節(jié)點(diǎn)1、終點(diǎn)為節(jié)點(diǎn)3的箱流，可選擇服務(wù)弧段2作為服務(wù)路徑，也可選擇服務(wù)弧段3和5組成服務(wù)路徑.若選擇弧段2，則表示該箱流由1站開(kāi)往3站的集裝箱班列進(jìn)行直達(dá)運(yùn)輸；若選擇弧段3和5，則表示該箱流先由1站開(kāi)往2站的班列承運(yùn)，到達(dá)2站后卸下，再裝至2站開(kāi)往3站的班列將其運(yùn)至終到站.同時(shí)，集裝箱辦理站裝卸能力、鄰接路段通過(guò)能力及集裝箱運(yùn)到期限的限制，對(duì)服務(wù)弧段的選擇有很大的影響.例如：弧段3和5組成服務(wù)路徑的運(yùn)輸時(shí)間超過(guò)了節(jié)點(diǎn)1去往節(jié)點(diǎn)3箱流的運(yùn)到期限，而弧段2的運(yùn)輸時(shí)間在運(yùn)到期限范圍內(nèi)，則該箱流只能選擇弧段2.服務(wù)弧段的選擇及其頻度的確定，不僅要滿(mǎn)足運(yùn)輸需求，還要盡可能減小支出成本，再加上辦理站裝卸能力、鄰接路段通過(guò)能力及運(yùn)到期限約束，使得問(wèn)題求解比一般的網(wǎng)絡(luò)設(shè)計(jì)更為困難.

2 優(yōu)化模型構(gòu)建

2.1 參變量定義

2.2 優(yōu)化模型

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

本文以成本最小為優(yōu)化目標(biāo)，總成本分為兩部分,一部分是服務(wù)成本(班列的開(kāi)行成本),另一部分是與集裝箱運(yùn)輸有關(guān)的成本，后者包括途中運(yùn)輸成本及中轉(zhuǎn)裝卸成本，則目標(biāo)函數(shù)如式(1)所示.

(1)

2.2.2 約束條件

1) 箱流唯一性約束

(2)

表示任意1組箱流在途中是不可拆分的.

2) 流量守恒約束

(3)

表示任意1組箱流在途經(jīng)站的中轉(zhuǎn)裝卸是連續(xù)的，并保證全部集裝箱能從出發(fā)站點(diǎn)運(yùn)送至終到站點(diǎn).

3) 箱流中轉(zhuǎn)裝卸約束

(4)

4) 運(yùn)到期限約束

(5)

表示任意箱流的運(yùn)輸時(shí)間不能超過(guò)規(guī)定的運(yùn)到期限，其中箱流的運(yùn)輸時(shí)間包括出發(fā)站點(diǎn)收箱至將集裝箱發(fā)出的時(shí)間、途經(jīng)辦理站的中轉(zhuǎn)裝卸作業(yè)時(shí)間及途中運(yùn)行時(shí)間.

5) 辦理站裝卸能力約束

(6)

6) 路段通過(guò)能力約束

(7)

表示物理網(wǎng)絡(luò)中任意有向路段上通過(guò)的班列數(shù)量，不能超過(guò)該路段的通過(guò)能力.

7) 服務(wù)能力與箱流量的關(guān)系約束

(8)

表示弧段的服務(wù)能力應(yīng)滿(mǎn)足所運(yùn)輸?shù)南淞髁?

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

本文構(gòu)建的模型為線(xiàn)性混合整數(shù)規(guī)劃模型，隨著鐵路網(wǎng)絡(luò)規(guī)模、集裝箱運(yùn)輸需求的增加，精確求解算法或商業(yè)優(yōu)化軟件無(wú)法在接受時(shí)間內(nèi)得到優(yōu)化結(jié)果.遺傳算法是一種基于隨機(jī)搜索的群體智能算法，具有較高的求解效率，本文將運(yùn)用遺傳算法求解構(gòu)建的數(shù)學(xué)模型.

3.1 染色體編碼

(9)

3.2 初始種群

在滿(mǎn)足運(yùn)輸完整性的約束下，箱流通過(guò)連續(xù)的服務(wù)弧段組成1條由出發(fā)站點(diǎn)至終到站點(diǎn)的服務(wù)路徑，因此，確定箱流與服務(wù)弧段的對(duì)應(yīng)關(guān)系可視為服務(wù)路徑的選擇.服務(wù)路徑選擇的前提和基礎(chǔ)是要確定出各箱流可選擇的服務(wù)路徑集合.為此，本文運(yùn)用回溯法的思想，搜索滿(mǎn)足箱流唯一性、流量守恒及運(yùn)到期限約束的的可行服務(wù)路徑.對(duì)于箱流q，可行服務(wù)路徑的搜索流程如下：

Step1：令Lq表示箱流q的運(yùn)輸時(shí)間，選定箱流q的出發(fā)站點(diǎn)o(q)作為搜索起點(diǎn)，并將起點(diǎn)o(q)視為當(dāng)前節(jié)點(diǎn)，初始化運(yùn)輸時(shí)間Lq=wq，轉(zhuǎn)Step2；

Step2：檢查以當(dāng)前節(jié)點(diǎn)為起點(diǎn)的服務(wù)弧段是否都已遍歷，若都已遍歷，轉(zhuǎn)Step5；否則，轉(zhuǎn)Step3；

Step3：在以當(dāng)前節(jié)點(diǎn)為起點(diǎn)的服務(wù)弧段中，選擇未遍歷的弧段a，已知該弧段的終點(diǎn)為u，更新運(yùn)輸時(shí)間Lq=Lq+τa，判斷運(yùn)輸時(shí)間是否滿(mǎn)足運(yùn)到期限的要求，若Lq≤Tq，轉(zhuǎn)Step4；否則，將弧段a標(biāo)記為已遍歷，返回該弧段起點(diǎn)，同時(shí)還原運(yùn)輸時(shí)間Lq=Lq-τa，轉(zhuǎn)Step2；

得到各OD箱流可選的服務(wù)路徑集合后，依次讓各箱流在其可行路徑方案中隨機(jī)選取1條路徑，以此產(chǎn)生一定數(shù)量的初始方案.再將各初始方案代入式(9)，計(jì)算不同方案下的服務(wù)頻度.

上述生成初始種群的方法可使各染色體均滿(mǎn)足箱流唯一性、流量守恒及運(yùn)到期限約束.對(duì)于其中不滿(mǎn)足辦理站裝卸能力及路段通過(guò)能力約束的初始染色體，則運(yùn)用下文設(shè)計(jì)的啟發(fā)式策略進(jìn)行修復(fù).

3.3 染色體修復(fù)

算法設(shè)計(jì)的核心思想，就是通過(guò)交叉、變異等操作對(duì)箱流選擇的服務(wù)路徑進(jìn)行不斷改變.顯然，初始染色體及遺傳操作后產(chǎn)生的新染色體始終滿(mǎn)足箱流唯一性、流量守恒及運(yùn)到期限約束，但是各OD箱流選擇的服務(wù)路徑及各弧段服務(wù)頻度的不斷變化，使得辦理站裝卸集裝箱數(shù)量及路段通過(guò)班列數(shù)量隨之改變，部分染色體可能不滿(mǎn)足辦理站裝卸能力及路段通過(guò)能力要求.對(duì)于這些不可行染色體，需設(shè)計(jì)適宜的方法進(jìn)行處理.相較于既有文獻(xiàn)常采用的罰函數(shù)法和直接刪除法，染色體修復(fù)可使種群規(guī)模不改變的同時(shí)，保證染色體組合的多樣性.為此，本文考慮對(duì)不可行的染色體進(jìn)行修復(fù)，并設(shè)計(jì)相應(yīng)的啟發(fā)式修復(fù)規(guī)則.

啟發(fā)式修復(fù)規(guī)則的實(shí)現(xiàn)過(guò)程具體為：檢驗(yàn)各節(jié)點(diǎn)裝卸的集裝箱數(shù)量，對(duì)于節(jié)點(diǎn)n，若裝卸的集裝箱數(shù)量超過(guò)裝卸能力kn，則選出在該節(jié)點(diǎn)進(jìn)行中轉(zhuǎn)裝卸的任意1組箱流，在其可選的路徑集合中選出不在節(jié)點(diǎn)n中轉(zhuǎn)的1條路徑，替換當(dāng)前路徑.同時(shí)，檢驗(yàn)各路段上通過(guò)的班列數(shù)量是否滿(mǎn)足要求，若路段e上通過(guò)的班列數(shù)量大于其通過(guò)能力fe，則先選出對(duì)應(yīng)的直達(dá)去向在物理網(wǎng)絡(luò)中的實(shí)際運(yùn)行路徑經(jīng)過(guò)路段e的服務(wù)弧段a，再選取通過(guò)服務(wù)弧段a的任意1組箱流，在該箱流可選的路徑集合中選出不經(jīng)過(guò)弧段a的1條路徑替換當(dāng)前路徑.以此進(jìn)行調(diào)整，直至各辦理站裝卸箱數(shù)及各路段上通過(guò)的班列數(shù)量滿(mǎn)足約束要求.

3.4 遺傳算法流程

設(shè)計(jì)遺傳算法流程如下：

Step1：生成初始種群.

Step2：令目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，將當(dāng)前所有染色體帶入適應(yīng)度函數(shù)計(jì)算適應(yīng)度值.

Step3：選擇操作.為避免優(yōu)秀個(gè)體被破壞，采用輪盤(pán)賭與精英保留相結(jié)合的策略進(jìn)行選擇.

Step4：交叉操作.隨機(jī)選取1組箱流，將表示該箱流及之后所有箱流與服務(wù)弧段對(duì)應(yīng)關(guān)系的基因，與另一染色體中相同位置的基因進(jìn)行互換，修復(fù)不可行染色體.

Step5：變異操作.在執(zhí)行變異操作的染色體中，隨機(jī)選取1組箱流，改變?cè)撓淞髋c服務(wù)弧段對(duì)應(yīng)關(guān)系，即在其可選的服務(wù)路徑集合中任選1條與當(dāng)前不同的路徑進(jìn)行替換，修復(fù)不可行染色體.

Step6：判斷循環(huán)終止條件，若迭代次數(shù)沒(méi)有達(dá)到設(shè)定的最大循環(huán)次數(shù)，則轉(zhuǎn)Step2；否則算法結(jié)束.

4 求解算例

4.1 參數(shù)輸入

構(gòu)造如圖5所示的路網(wǎng)結(jié)構(gòu)對(duì)本文模型和算法進(jìn)行仿真計(jì)算，圖中圓圈表示鐵路集裝箱辦理站，連線(xiàn)為車(chē)站之間的有向路段.鐵路物理網(wǎng)絡(luò)中路段相關(guān)參數(shù)如表1所列，服務(wù)網(wǎng)路中服務(wù)弧段相關(guān)參數(shù)如表2所列，各OD箱流相關(guān)參數(shù)如表3所列.各OD箱流的出發(fā)站收箱至將集裝箱發(fā)出的時(shí)間均為4 h，途經(jīng)各站辦理中轉(zhuǎn)裝卸作業(yè)的時(shí)間均為8 h，運(yùn)到期限均為24 h.各服務(wù)弧段對(duì)應(yīng)直達(dá)去向上班列的運(yùn)行時(shí)間，由物理網(wǎng)絡(luò)中該去向途經(jīng)各路段的運(yùn)行時(shí)間相加而得，各辦理站裝卸能力均為1 800箱，中轉(zhuǎn)裝卸成本為10元/箱，班列的最大編成箱數(shù)為50箱.

表1 路段相關(guān)參數(shù)Tab.1 Related parameters of each section

表2 服務(wù)弧段相關(guān)參數(shù)Tab.2 Related parameters of each service arc

表3 箱流相關(guān)參數(shù)Tab.3 Related parameters of container flow

4.2 求解結(jié)果分析

運(yùn)用Matlab2014編程對(duì)算例進(jìn)行測(cè)試，種群規(guī)模取30，交叉概率取0.9，變異概率取0.09，迭代次數(shù)為500次.計(jì)算過(guò)程中適應(yīng)度函數(shù)值的變化如圖6所示，在運(yùn)行了104 s后得到最終解，其適應(yīng)度值為6.264 890 86×10-8，目標(biāo)函數(shù)值為15 961 970元.由圖6可知，隨著迭代次數(shù)的增加，適應(yīng)度函數(shù)值逐漸增加，在260次以后，適應(yīng)度值已無(wú)明顯變化，表明算法的收斂性良好，具有較高的計(jì)算效率.

表4 箱流經(jīng)過(guò)的服務(wù)弧段Tab.4 Passing service arcs of each container flow

表5 服務(wù)頻度Tab.5 Service frequency

表6 各集裝箱辦理站裝卸箱數(shù)Tab.6 Number of containers loaded and unloaded at each container terminal

表7 各路段通過(guò)的班列數(shù)量Tab.7 Number of trains passing each section

5 結(jié)論

本文對(duì)鐵路集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)的設(shè)計(jì)方法進(jìn)行了研究，運(yùn)用遺傳算法求解構(gòu)建的線(xiàn)性混合整數(shù)規(guī)劃模型，通過(guò)算例的求解表明：對(duì)于大規(guī)模的集裝箱運(yùn)輸服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，提出的模型及算法可在較短時(shí)間內(nèi)獲得滿(mǎn)意解，具有較高的計(jì)算效率；所得結(jié)果中，各OD間箱流的運(yùn)輸時(shí)間均在運(yùn)到期限范圍內(nèi)，集裝箱辦理站裝卸箱數(shù)和路段通過(guò)班列數(shù)量均滿(mǎn)足能力要求，驗(yàn)證了本文提出的方法是有效可行的，可為鐵路企業(yè)優(yōu)化集裝箱運(yùn)輸組織提供決策參考.現(xiàn)實(shí)中部分班列需在途經(jīng)站辦理集裝箱裝卸或車(chē)組甩掛作業(yè)，未來(lái)研究會(huì)針對(duì)這一情況做深入分析，使設(shè)計(jì)的方案與現(xiàn)實(shí)更好的吻合.