李琦，魏玉光

(北京交通大學，交通運輸學院，北京 100044)

0 引言

鐵路集裝箱中心站是鐵路集裝箱運輸?shù)年P鍵場所，也是公鐵聯(lián)運的重要節(jié)點。中心站的集卡承擔著公鐵聯(lián)運箱流在中心站與貨源地間的集疏任務，其集疏效率直接影響整個公鐵聯(lián)運集疏系統(tǒng)的作業(yè)效率。多車程集卡集疏調度旨在確定集裝箱的集疏方案和集卡的調度方案，以最小化綜合運營成本，并提高中心站的集疏效率與能力。

帶時間窗的中心站多車程集卡調度問題是車輛路徑優(yōu)化問題的拓展，是帶時間窗的取送貨問題(VRPSPDTW)與多行程問題(MTVRP)相結合的綜合性問題。國內外學者對這兩類問題展開了廣泛的研究。Mahmoudi等[1]提出前向動態(tài)規(guī)劃算法，用于解決單車VRPSPDTW，利用拉格朗日松弛法，將多車路線問題分解為多個單車路線子問題。Wu等[2]利用帶有破壞和修復策略的蟻群算法求解VRPPDTW。Shi等[3]采用兩階段算法來解決VRPSPDTW，第1階段提出基于學習目標函數(shù)的改進變量鄰域搜索方法，第2階段設計了基于雙結構的禁忌搜索算法，以優(yōu)化車輛數(shù)量與走行距離。王超等[4]以最小化運輸距離和車輛數(shù)為目標，設計離散布谷鳥算法，使用2-opt法、shift/swap法改進路徑的搜索過程。于江霞等[5]設計遺傳算法求解基于客戶分類的配送路徑優(yōu)化模型。Francois等[6]構建以車輛總行駛時間最小為目標的多行程車輛路徑模型，并設計帶有多行程算子的自適應大鄰域算法。Pan等[7]研究了城市物流配送中，時變路網下的多行程車輛路徑問題，并采用混合元啟發(fā)式算法進行求解。彭勇等[8]設計混合遺傳算法用于求解基于交換箱甩掛的路徑優(yōu)化問題。

上述學者所研究的問題具有車輛容量大、時間窗較為寬松的特點，并使用啟發(fā)式算法來確定最優(yōu)成本及車輛使用數(shù)量。本文與前述研究的不同之處在于：首先，由于公鐵聯(lián)運集疏系統(tǒng)注重集裝箱集疏作業(yè)的時效性，需要考慮公路與鐵路的銜接，故采用由列車到發(fā)時刻確定的混合時間窗作為模型的時間約束，以確保集卡能夠按時完成集裝箱的集疏任務；其次，與一般配送車輛不同，集卡通常只能裝載一個集裝箱，因此，采用多車程作業(yè)模式進行集卡調度；最后，通過啟發(fā)式算法求解出的集卡調度方案無法保證集卡作業(yè)時間的均衡性，需要解決集卡作業(yè)時間不均衡的問題。

對集卡調度優(yōu)化問題的研究集中在港站內的集卡調度和集卡預約分配兩個方面，對中心站與收(發(fā))貨地間集卡調度問題的研究相對較少。He等[9]研究了碼頭外集卡的任務分配問題，以任務均衡和集卡到達均衡為優(yōu)化目標，建立了外集卡調度模型。Jiang等[10]研究了多式聯(lián)運樞紐節(jié)點的箱流分配及集卡調度問題，采用分支定價法求解模型。Nossack等[11]在集卡調度優(yōu)化模型中考慮了硬時間窗約束，采用兩階段法解決多式聯(lián)運港站的外集卡調度問題。Hong等[12]研究了港站內無人集卡的配置與調度問題。靳志宏等[13]針對甩箱模式下多箱型任務組合的集卡調度問題，在考慮箱位變化的基礎上，以最小化集卡綜合調度成本為目標，設計了基于不可行弧過濾策略的蟻群算法。許波梔等[14]研究早晚高峰擁堵情況下的集卡預約調度問題，利用自適應量子遺傳算法確定集卡數(shù)量及到港時間窗。

綜上所述，為解決鐵路集裝箱中心站與周邊貨源地間的集卡調度問題，本文綜合考慮中心站箱流集疏和集卡調度的特點，將車輛路徑理論應用于公鐵聯(lián)運集裝箱的集疏問題。同時引入多車程的概念，即集卡能夠在完成當前集疏任務后，繼續(xù)從中心站出發(fā)執(zhí)行其余集疏任務。此外，通過列車到發(fā)時刻來確定集裝箱的集疏時間窗，以體現(xiàn)集卡與班列在中心站集疏系統(tǒng)中的時間關系。在研究多車程集卡調度的基礎上，進一步探討集卡的車程分配問題。

1 問題描述

公鐵聯(lián)運主要包括“集”“疏”“運”這3個過程，如圖1所示，其中a，b，c為貨源地節(jié)點，m為中心站節(jié)點。“集”是通過公路運輸將公鐵聯(lián)運集裝箱送達中心站，“疏”是通過公路運輸將貨物從中心站送達收貨地，“運”是將中心站的貨物轉運至其他集裝箱中心站或鐵路車站。

圖1 集疏運組織模式Fig.1 Collection and distribution organization model

在公鐵聯(lián)運的3個作業(yè)環(huán)節(jié)中，集裝箱的集疏作業(yè)主要在公路運輸系統(tǒng)中完成，運輸作業(yè)主要在鐵路運輸系統(tǒng)中完成。為體現(xiàn)公鐵聯(lián)運集裝箱集疏運作業(yè)的協(xié)調性，本文利用中心站的列車到發(fā)時刻來確定集裝箱的集疏時間窗。由于中心站內的列車針對同一貨源地可能具有不同的集疏箱流任務，導致集裝箱的集疏時間窗存在一定的差異。因此，采用虛擬節(jié)點拆分的方法，將貨源地節(jié)點拆分成多個虛擬節(jié)點，如圖2所示。虛擬節(jié)點數(shù)量等于原節(jié)點的集疏箱量。虛擬節(jié)點與原節(jié)點具有相同的地理位置，但集裝箱的集疏性質及時間窗存在差異。

圖2 虛擬節(jié)點拆分Fig.2 Virtual node splitting

集卡的集疏作業(yè)主要有單車程和多車程兩種模式。所謂車程，是指集卡從中心站出發(fā)，并最終返回中心站的作業(yè)行程。圖2 包含兩個車程，車程1 為m-a1-b-m，車程2 為m-c-m。以圖2 為例，單車程作業(yè)模式要求每輛集卡僅執(zhí)行一項車程任務，因此需要兩輛集卡各完成一項車程任務；而多車程作業(yè)模式允許每輛集卡執(zhí)行多項無時間沖突的車程任務，即一輛集卡可以連續(xù)完成這兩項車程任務。這表明采用單車程作業(yè)模式能夠更快地完成中心站的集疏任務，但會大幅增加集卡的使用數(shù)量，從而增加集卡的調度成本。因此，本文基于多車程的概念，對公鐵聯(lián)運背景下的中心站多車程集卡集疏調度優(yōu)化問題展開研究。

2 模型構建

2.1 模型假設

基本假設如下：

(1)集卡是同質的，集卡1次最多裝載1個40 ft集裝箱；

(2)允許集卡重復使用；

(3)節(jié)點間的路徑為雙向連通路徑，節(jié)點優(yōu)先級相同；

(4)集裝箱箱型一致；

(5)中心站的裝卸作業(yè)能力充足，不存在集卡在裝卸線上等待的情況。

2.2 符號說明

模型所涉及的符號及說明如表1所示。

表1 集合、參數(shù)及變量說明Table 1 Set,parameter,and variable descriptions

在時間窗的設定方面，采用隨機設定的方法難以滿足公鐵聯(lián)運作業(yè)過程中對集裝箱集疏時間的要求。因此，本文根據(jù)列車的到發(fā)時刻確定集裝箱的集疏時間窗。其中，列車到發(fā)時間窗設置為[A,D]，A為列車到達時刻，D為列車出發(fā)時刻，則集裝箱的疏運時間窗為[A+dOjv+tc,D+dOjv+tc]，集運時間窗為[A-dOj′c,D-dOj′c] 。

2.3 帶時間窗的中心站多車程集卡集疏調度模型

(1)目標函數(shù)

模型目標為最小化集卡的調度成本。調度成本由集卡走行成本，與運輸距離無關的集卡固定成本和時間懲罰成本組成。通過引入懲罰成本來體現(xiàn)允許集卡提前到達節(jié)點的軟時間窗。

(2)約束條件

模型的約束條件包括3個方面：集卡作業(yè)接續(xù)關系、運輸需求與集卡容量、作業(yè)時間關系的相關約束。

①集卡作業(yè)接續(xù)關系約束

式(2)和式(3)表示每個集卡車程中的節(jié)點都有唯一的前序節(jié)點和后序節(jié)點，且每個節(jié)點僅被訪問一次；式(4)表示集卡不存在從節(jié)點出發(fā)又返回該節(jié)點的情況；式(5)和式(6)表示集卡從中心站出發(fā)，執(zhí)行完當前車程任務后均需返回中心站；式(7)表示集卡車程中節(jié)點的連續(xù)性。

②運輸需求與集卡容量約束

式中：|R|為車程數(shù)；Q為集卡容量；M為較大的正數(shù)。

式(8)和式(9)表示集疏作業(yè)能力應滿足集疏需求；式(10)和式(11)表示節(jié)點的集運量與疏運量平衡約束，確保各節(jié)點的集疏任務都能被滿足；式(12)和式(13)表示每輛集卡在執(zhí)行車程任務時，每個節(jié)點的裝卸箱量均不超過集卡容量；式(14)表示集卡在完成當前節(jié)點集疏任務后的裝載量；式(15)表示集卡僅訪問有集疏需求的節(jié)點。

③作業(yè)時間關系約束

式(16)表示集卡到達各節(jié)點的時間等于集卡到達前序節(jié)點的時間、裝卸作業(yè)時間和節(jié)點間走行時間這三者之和；式(17)表示集卡車程在時間上的接續(xù)關系；式(18)表示不允許集卡晚于規(guī)定的時間到達節(jié)點，這與目標函數(shù)中懲罰成本所代表的軟時間窗相結合，構成本文的混合時間窗；式(19)表示集卡在節(jié)點間的走行時間。

2.4 多車程分配優(yōu)化模型

(1)目標函數(shù)

帶時間窗的中心站多車程集卡集疏調度模型可以確定最佳集卡數(shù)量、車程集合及調度方案，但無法保證每輛集卡作業(yè)時間的均衡。因此，本文以最小化集卡間作業(yè)時間差值為目標，構建多車程分配優(yōu)化模型為

(2)約束條件

模型的約束條件包括兩個方面：任務接續(xù)關系和集卡走行時間的相關約束。

①任務接續(xù)關系約束

式(21)表示每個車程只能由一輛集卡提供服務；式(22)和式(23)引入虛擬車程“0”，以確保每輛集卡都有唯一的起止車程；式(24)表示當前車程的前后續(xù)車程必須由同一輛集卡完成。

②集卡走行時間約束

式(25)表示每輛集卡的總作業(yè)時間；式(26)表示集卡作業(yè)時間不超過規(guī)定的最大作業(yè)時間，規(guī)定Tmax=8；式(27)表示集卡車程的開始時刻，若車程為集卡的起始車程，則開始時刻為該車程的最早開始時刻，否則為前序車程的結束時刻；式(28)表示車程時間窗，集卡需要在規(guī)定的時間范圍內完成當前車程任務。

對模型的目標函數(shù)及非線性約束進行線性化處理。通過引入輔助變量fmax，fmin將式(20)線性化表示為

引入0-1變量αk，將式(30)線性化表示為

式(31)同理。

3 求解方法

帶時間窗的中心站多車程集卡調度優(yōu)化問題的求解主要分為兩部分，如圖3 所示。首先，采用改進的遺傳算法求解中心站集疏調度模型，旨在獲取最佳的集卡調度成本及方案。其次，為提高集卡間調度作業(yè)的均衡性，以調度模型得到的集卡數(shù)量及車程集合為輸入，借助Gurobi優(yōu)化器確定作業(yè)時間更為均衡的集卡調度方案?？紤]到車輛路徑問題的特點和遺傳算法在全局搜索中的優(yōu)勢，本文在遺傳算法中引入模擬退火算法的Metropolis接受準則，通過改進的遺傳算法求解中心站集卡集疏調度模型，關鍵設計如下。

圖3 求解流程圖Fig.3 Flowchart of solution

(1)種群初始化

種群的初始化過程實際上是車程的規(guī)劃過程。采用虛擬節(jié)點拆分法將貨源地節(jié)點拆分成集疏任務節(jié)點，將虛擬節(jié)點隨機排列組成染色體的基因。根據(jù)集卡容量、時間窗等約束條件，利用中心站節(jié)點分割序列得到車程集合，如圖4所示。適應度函數(shù)為F=1Z。

圖4 分割過程Fig.4 Segmentation process

(2)車程時間窗

根據(jù)集裝箱的集疏時間及裝卸作業(yè)時間來確定車程的最早開始時刻、最晚開始時刻及持續(xù)時間。

式(34)表示集卡執(zhí)行車程任務的最晚開始時刻，其中，集合N由0～n組成，表示車程的節(jié)點。從n-1 逆推出車程中各節(jié)點的最晚出發(fā)時刻ltrr,iip，從而得到車程的最晚開始時刻ltrrip。式(35)表示集卡執(zhí)行車程任務的最早開始時刻。式(36)表示車程的持續(xù)時間。

(3)車程分配策略

通過車程分配策略確定集卡的數(shù)量及行駛計劃，步驟如下：

Step 1 確定車程集合R。

Step 2 計算集合R中車程的開始時間窗和持續(xù)時間。

Step 3 若集合R非空，則執(zhí)行Step 4；否則，執(zhí)行Step 5。

Step 4 按照車程的最早開始時刻升序排列，遍歷集合R，依次將車程插入到集卡作業(yè)計劃Pk中。假設集卡作業(yè)的結束時刻為，若則將車程r分配到Pk中，更新集卡作業(yè)的結束時刻為，從集合R中刪除車程r，跳轉至Step 3；若，則將車程r分配到Pk中，更新集卡作業(yè)的結束時刻為，從集合R中刪除車程r，跳轉至Step 3；若，則車程無法插入Pk中，重復Step 4，直至遍歷完集合R，選取新的集卡執(zhí)行新一輪的車程分配過程。

Step 5 返回集卡作業(yè)計劃及起止時間。

(4)選擇過程

傳統(tǒng)的輪盤賭選擇法可能會淘汰優(yōu)良個體。本文設計改進的輪盤賭選擇法，以保留優(yōu)良個體。首先，將染色體{x1,x2,…,xn} 按照適應度的大小降序排列，得到新的染色體序列{y1,y2,…,yn} 。其次，計算適應度總和，個體選擇概率，其 中，i∈{1,2,…,n}，累計適應度，x為染色體序號。隨后在每輪選擇中生成n個[0,1]區(qū)間內的隨機數(shù){r1,r2,…,rn}，選擇隨機數(shù)分布最多的個體作為子代，如圖5所示。

圖5 隨機數(shù)分布Fig.5 Random number distribution

(5)搜索策略

當父代染色體相同時，傳統(tǒng)的部分匹配交叉會產生基因相同的子代，影響算法的搜索能力與搜索范圍。因此，本文通過設計改進的交叉算子增強種群的多樣性。首先，設定4個隨機數(shù)來確定染色體中的兩個待交叉區(qū)域；其次，將其置于對方染色體前端并消除重復元素，最終得到交叉后的子代染色體，如圖6所示。

圖6 交叉操作Fig.6 Cross-operation

為提高搜索能力，在交叉過程中嵌入Metropolis原則，利用退火尋優(yōu)的方法，在保留優(yōu)良解的同時，以一定概率接受劣質解，以此擾動搜索過程。具體步驟如下：

Step 1 設定初始溫度T與衰減系數(shù)α。

Step 2 模擬退火操作，對染色體A1，A2執(zhí)行交叉操作，得到子代染色體a1，a2，計算適應度FAi,Fai。若Fai>FAi，i=1,2，則子代取代父代染色體，否則以概率P接受子代染色體。

變異過程采用Swap算子來交換路徑間的單個節(jié)點，如圖7 所示。采用貪婪搜索策略，保留變異結果中適應度最大的個體。

圖7 Swap算子操作Fig.7 Swap operator operation

4 算例分析

4.1 數(shù)據(jù)準備

本文以鄭州鐵路集裝箱中心站為配送中心，構建腹地集裝箱集疏網絡，集疏網絡相關信息如表2所示。設計不同規(guī)模算例驗證模型的有效性和穩(wěn)定性，算例參數(shù)如表3 所示。實驗在i7 處理器，2.6 GHz 的計算機上運行，使用MATLAB2020a 編寫程序。種群規(guī)模設置為300，迭代次數(shù)為500，交叉概率為0.95，變異概率為0.05，初始溫度為100 ℃，衰減系數(shù)為0.99。

表2 集疏網絡節(jié)點信息Table 2 Collection and distribution network node information

表3 相關參數(shù)Table 3 Relevant parameters

4.2 小規(guī)模算例

設置小規(guī)模算例(集疏箱量為20、30、40，列車數(shù)為1、2、3)比較多車程作業(yè)模式與單車程作業(yè)模式在中心站集卡調度過程中的不同，利用本文的算法將每個算例獨立運行10 次，得到不同模式下的集卡調度總成本，結果如表4 所示。其中，T1、T2分別為多車程作業(yè)模式及單車程作業(yè)模式下的中心站總體集疏作業(yè)時間，即最后一項集疏任務的完成時間與最早一項集疏任務的開始時間之差。

表4 兩種車程模式的求解結果Table 4 Result of two transportation modes

由表4可知，多車程作業(yè)模式的集卡調度成本低于單車程作業(yè)模式的集卡調度成本，平均減少了60.31%。相較于單車程作業(yè)模式，多車程作業(yè)模式能夠有效減少集卡的使用數(shù)量，進而降低集卡調度成本。比較不同模式下中心站的總作業(yè)時間發(fā)現(xiàn)，單車程作業(yè)模式能夠在6 h 左右完成所有集疏任務，比多車程作業(yè)模式下的總體作業(yè)完成時間平均縮短了29.4%，說明單車程作業(yè)模式能夠更快地完成集疏任務，縮短中心站的總體作業(yè)時間。雖然多車程模式下中心站總作業(yè)時間相對較長，但使用的集卡數(shù)量遠少于單車程模式，隨著箱流規(guī)模增大，兩種模式下的集卡數(shù)量差距也隨之增大。通過比較實驗2，實驗5 和實驗8 發(fā)現(xiàn)，實驗8 的集卡數(shù)量增加了1 輛。這是由于集裝箱集疏時間窗受班列到發(fā)時間窗的影響，隨著班列數(shù)量的增加，集裝箱具有更加復雜的集疏時間窗，限制了集卡的作業(yè)順序，導致集卡數(shù)量增加。

4.3 大規(guī)模算例

為進一步驗證集卡調度模型的有效性及多車程分配優(yōu)化模型的效果，設置大規(guī)模算例(集疏箱量為90、120，列車數(shù)為4、5、6)，利用本文算法求解多車程作業(yè)模式下的集卡調度模型，借助Gurobi優(yōu)化器求解車程分配優(yōu)化模型，實驗結果如表5 所示，其中，ΔT1為優(yōu)化前的集卡作業(yè)時間差，ΔT2為優(yōu)化后的集卡作業(yè)時間差。

表5 多車程作業(yè)模式求解結果Table 5 Result of multi-trip operation scheduling

由表5可知，增大箱流規(guī)模會增加集卡的使用數(shù)量及調度成本，而班列數(shù)量對集卡使用數(shù)量的影響并不明顯。班列數(shù)量直接影響集裝箱的集疏時間窗，進而對箱流集疏次序及集卡走行路徑產生影響，從而改變集卡運輸距離成本。實驗6的迭代曲線如圖8 所示，迭代約350 次得到最優(yōu)解并進入收斂狀態(tài)。此外，通過對集卡車程的優(yōu)化，集卡作業(yè)時間最大差值減少了14.3%以上，這表明多車程分配優(yōu)化模型在均衡集卡作業(yè)時間方面具有一定的效果。

圖8 實驗6迭代曲線Fig.8 Iterative curve of experiment 6

考慮時間均衡的箱流集疏方案及集卡調度計劃如表6所示。結合表6和圖9展現(xiàn)的優(yōu)化前后集卡作業(yè)時間可以看出，優(yōu)化后的集卡作業(yè)時間更為均衡，作業(yè)時間差值較優(yōu)化前降低了0.06 h。集卡8承擔2項車程任務，作業(yè)時間為7.69 h，集卡10承擔6項車程任務，作業(yè)時間為7.68 h，盡管集卡間承擔的車程任務數(shù)量不同，但優(yōu)化模型保證了集卡作業(yè)時間的均衡。這表明多車程分配優(yōu)化模型可以在滿足作業(yè)要求的前提下，調整集卡的車程分配方案，縮短各集卡作業(yè)時間的差距，以實現(xiàn)多車程集卡作業(yè)的均衡。這對于實際站內多列車集疏作業(yè)的多車程集卡調度具有一定的優(yōu)化效果。

表6 實驗6車程分配優(yōu)化結果Table 6 Optimization results of distance allocation in experiment 6

圖9 實驗6集卡作業(yè)時間對比Fig.9 Comparison of truck operation time in experiment 6

5 結論

本文探討了公鐵聯(lián)運集裝箱集疏領域中帶時間窗同時取送貨的多車程車輛路徑問題，構建了多車程集卡集疏調度優(yōu)化模型。通過使用中心站列車到發(fā)時刻確定集裝箱的集疏時間窗，以體現(xiàn)集卡與班列在公鐵聯(lián)運集疏系統(tǒng)中的時間關系。設計改進的遺傳算法，并通過算例驗證了模型與算法的有效性。此外，構建多車程分配優(yōu)化模型，以解決集卡車程在時間上分配不均的問題。本文的主要結論如下：

(1)將集卡多車程作業(yè)模式引入公鐵聯(lián)運集裝箱的集疏問題中，能夠有效減少集卡的使用數(shù)量，從而降低集卡調度成本。相較于單車程模式，集卡調度成本平均減少60.31%，且隨著規(guī)模增大，集卡多車程作業(yè)的優(yōu)勢越明顯。

(2)在多車程集卡集疏調度模型中，將列車到發(fā)時刻與集裝箱的集疏時間窗相結合，解決了公鐵聯(lián)運系統(tǒng)中的集卡集疏調度問題。通過研究班列數(shù)量及箱流規(guī)模對集卡調度的影響可以發(fā)現(xiàn)，隨著集疏箱流規(guī)模增大，集卡數(shù)量和調度成本也相應增加，而班列數(shù)量對集卡數(shù)量的影響較小。

(3)本文設計的多車程分配優(yōu)化模型能夠均衡地對作業(yè)任務進行分配，進而得出不同箱流規(guī)模下的集卡作業(yè)時間和作業(yè)序列，集卡作業(yè)時間最大差值減少了14.3%以上，能夠有效解決中心站內實際多列車運營場景下集卡作業(yè)時間不均衡的問題。