面向調移車輛數優化的摘掛列車調車作業計劃編制方法

張博健，彭其淵，李 力，魯工圓

(1. 西南交通大學 交通運輸與物流學院， 四川 成都 610031；2. 西南交通大學 綜合交通運輸智能化國家地方聯合工程實驗室， 四川 成都 610031)

調車作業計劃是規定車輛如何調移及其作業程序的具體行動計劃[1]。按站順編組摘掛列車是一類較為復雜且重要的車站日常調車作業，調車作業計劃質量對技術站及中間站的工作效率有重要影響。

許多學者對此展開了深入研究，為保證按站順編組摘掛列車調車作業計劃質量，文獻[2]提出了“落表法”，其特點是所有車輛只進行一次溜放，并使占用的調車線數達到最少。文獻[3]提出了“統籌對口調車法”理論，將編組調車過程描述為一系列連續的對口過程，該方法可使選編調車的連掛鉤數達到最優。文獻[4]提出了“分析計算法”，該方法使用換算溜放鉤數評估整個調車方案的調車鉤數和調動車數，并據此對方案進行選優。文獻[5]提出了“消逆法”理論，在可用調車線數量受限和可變的條件下使牽推鉤數最優。文獻[6]針對“消逆法”連掛鉤數較多的問題進行優化。文獻[6-7]針對“統籌對口調車法”牽推鉤數較多的問題進行優化。文獻[8]將車組下落問題抽象為排序問題，提出一種基于排序二叉樹的調車作業計劃編制方法。文獻[9]基于基數排序算法對調車作業計劃進行編制。文獻[10]針對可用調車線數量受限情況下的編組調車問題，設計了“位串法”。

隨著高速鐵路的迅猛發展，動車運用成為制約通過能力的一個重要因素。動車所調車作業計劃的優化編制等問題也成為了研究的熱點，為摘掛列車調車作業計劃的優化提供了新的思路。文獻[11]以最小化調車鉤總數為目標，構建動車所調車作業計劃整數規劃模型，設計了粒子群算法進行求解。文獻[12]以動車運用所內動車組總延誤時間最小為目標建立優化模型，并設計微進化算法進行求解。

綜上所述，既有文獻中調車作業計劃編制的目標多以連掛鉤數最少、調車鉤數最優(連掛鉤與溜放鉤的加權調車鉤數最少)為目標，而對每一調車鉤執行過程中調移的車輛數多少考慮較少。調車鉤執行過程中，每鉤調移車輛數的變化直接導致每一鉤調車機車帶動重量的不同，一方面會影響調車機車啟動、制動效率，另一方面也影響著調車機車的能源消耗，綜合兩方面因素來看，更少調移車輛數的調車作業計劃將意味著能夠以更少的能源消耗、更快的速度以及更少的作業量完成調車作業過程，對于調車工作效率的提高有著重要意義。

基于上述思路，本文提出了在調車鉤數最優的基礎上，對調移車輛數進行優化的摘掛列車調車作業計劃編制方法。首先，建立了面向調移車輛數優化的調車作業計劃編制0-1線性規劃模型；其次，設計了基于消逆規則啟發式算法對模型進行求解；最后通過算例對模型及算法的有效性進行驗證，歸納了相關結論。

1 問題描述

1.1 問題相關定義

按站順編組摘掛列車調車作業計劃編制問題可描述為：對多個任意編組順序的待解編車組，通過連掛或摘解作業，確定一個將其改編為編組符合站順要求的調車作業計劃。

為了提高調車作業計劃的編制質量，應使摘掛列車編組過程中的調車作業量最少，在既有文獻中多以調車鉤數多少作為調車作業計劃質量的評價標準[3,5,8-9]，其中以連掛鉤數最少為目標最為常見[3,8-9]。在保證調車鉤數最優并以調移車輛數最少為編制目標的情況下，調車作業計劃編制的問題描述并無變化，但需引入如下定義：

(1) 車輛調移

調車機車在執行調車作業的各行程中車輛移動的過程，機車每連掛一個車輛即產生一個連掛車輛調移，每溜放一個車輛則產生一個溜放車輛調移，統稱為車輛調移。

(2) 調車鉤調移車輛數

單一調車鉤移動的車輛數量。如果某鉤作業為連掛作業，則其移動車輛數稱為連掛鉤調移車輛數，由連掛鉤推送行程中移動的車輛數和連掛鉤回拉行程中的移動車輛數組成；若為溜放作業，則為溜放鉤調移車輛數，由溜放鉤推送行程中移動的車輛數和回拉行程中移動的車輛數組成。

(3) 調車作業計劃調移車輛數

調車作業計劃各調車鉤的調移車輛數總和。一個調車作業計劃所有連掛鉤移動的車輛數稱為連掛作業調移車輛總數，所有溜放鉤移動的車輛數稱為溜放作業調移車輛總數。

車輛調移及調移車輛數的定義目的在于對同一調車鉤內對各個車輛的操作進行微觀描述。應注意的是，車輛調移發生在調車機車的每一次行程中，一次行程包含多個車輛調移，一個調車鉤可以包含多個行程，其調移車輛數統計時應涵蓋每一次行程中的調移車輛個數。一個連掛鉤的調移車輛數，應是圖1(a)推送行程的2個車輛調移與圖1(b)回拉行程4個車輛調移之和，即該連掛調車鉤產生了6個車輛調移。

1.2 問題假設

為便于模型建立，本文研究的按站順編組的摘掛列車調車作業計劃編制問題基于以下假設：

(1) 任意一列車列的調車作業由一臺調機完成，調車作業在一端咽喉進行，且調車過程中不允許出現中斷。

(2) 調機的牽引性能、牽出線的存車能力、調車線的存車能力不受到限制。

2 模型構建

2.1 符號說明

為建立問題模型，定義參數及集合如下：

K為車輛調移作業編號集合，K={1,2,…,k,…,|K|，k∈N+}，按車輛調移先后順序進行排序，同一調車鉤行程產生多個車輛調移時，調機連掛車列末位車輛的調移作業先于其他車輛調移。k為車輛調移作業次序索引，|K|為調車作業過程最后一次車輛調移作業的編號。

D為按站順排列的車輛編組去向集合，D={1,2,…,d,…,|D|，d∈N+}。d為編組去向索引，1為距離本站最遠的車輛去向，|D|為距離本站最近的車輛去向。

T為調車場調車線集合，t為調車線編號。

O為機帶車列中車輛位置集合O={1,2,…,o,…,|O|，o∈N+}，按照距離調機遠近進行排序。o為機帶車列中車輛位置索引。將機帶車列中距離調機最近的車輛位置稱為機帶車列首位置，首位置車輛稱為機帶車列首位車輛；將機帶車列中距離調機最遠的車輛位置稱為末位置，末位置車輛稱為機帶車列末位車輛。

P為調車線上停放的車列中車輛位置集合，P={1,2,…,p,…,|P|，p∈N+}，按照距離牽出線的遠近進行排序。p為調車線上車輛位置索引。將各調車線上停放車列中距離牽出線最遠的車輛位置稱為停放車列首位置，首位置車輛稱為停放車列首位車輛；將各調車線上停放車列中距離牽出線最近的車輛位置稱為停放車列末位置，末位置車輛稱為停放車列末位車輛。

機帶車列及停放車列中車輛位置等參數示意見圖2。

建模過程以每個車輛的調移為單位建立決策變量，主要決策變量如下:

(1) 車輛分布狀態變量

(2) 車輛連掛調移作業相關變量

(3) 車輛溜放調移作業相關變量

2.2 目標函數

基于上述決策變量定義，可建立調車鉤數最優前提下面向調移車輛數優化模型的目標函數

minZ=α×yc+β×yh+γ×xc+δ×xh

( 1 )

式中：α為每一連掛調移車輛數的權重；yc為調車作業計劃連掛鉤調移車輛總數；β為每一溜放調移車輛數的權重；yh調車作業計劃溜放鉤調移車輛總數；γ為每一連掛鉤的權重；xc為實際連掛鉤總數；δ為每一溜放鉤的權重；xh為實際溜放鉤總數。

為保證基于調車鉤數最優討論調移車輛數優化，可以調整α、β、γ、δ的取值，使調車鉤的權重γ、δ遠遠大于調移車輛數的權重α、β。

( 2 )

( 3 )

xc和xh的計算為

( 4 )

( 5 )

上述公式含有非線性項，其線性化方法將在后文介紹。

2.3 約束條件

為使用所定義決策變量描述調車作業計劃過程，引入如下約束條件：

(1) 車輛調移作業執行約束

當每一車輛調移作業(連掛或溜放)執行時，將導致機帶車列的末位車輛發生變化，對應的其中一條調車線上末位車輛也會發生變化。該類約束可表示為

?k,k+1∈Ko∈Od∈D

( 6 )

?k,k+1∈Kt∈Tp∈Pd∈D

( 7 )

(2) 調車鉤作業車輛守恒約束

車輛調移作業執行時，機帶車列的車輛變化會導致調車場內車輛的相應變化為

( 8 )

( 9 )

模型規定調機每次只能連掛或溜放一輛車，約束為

(10)

(11)

(3) 溜放車輛調移作業操作車輛數約束

溜放車輛調移作業執行時，調機溜放調移機帶車列末位一個車輛，同時該車輛溜放進調車場后只能溜放至某條調車線停靠車列的末位。該類約束可表示為

?k∈Ko,o+1∈O

(12)

?k∈Kt∈Tp,p+1∈P

(13)

(4) 連掛車輛調移作業操作車輛數約束

連掛車輛調移作業執行時，調機僅從調車場內某條調車線上的車列末位掛走一個車輛，同時該車輛只能連掛至機帶車列的末位。該類約束可以表示為

?k∈Ko,o+1∈O

(14)

?k∈Kt∈Tp,p+1∈P

(15)

(5) 容車能力約束

機帶車列與每一條調車線的每個位置最多停放一個車輛。該類約束可表示為

(16)

(17)

?k∈Kt∈Tp∈P

(18)

?k∈Kt∈Tp∈P

(19)

(6) 車輛調移作業選擇與順序約束

每一個車輛調移最多只能執行連掛車輛調移作業與溜放車輛調移作業中的一個，該約束可表示為

(20)

(21)

式(20)保證第k鉤只能選擇連掛車輛調移作業與溜放車輛調移作業其中的一個，或者兩者都不選，式(21)保證車輛調移作業從編號1開始逐一執行。

(7) 車輛初始狀態及目標順序約束

調車作業開始前，機帶車列及各調車線停放車列中車輛位置及去向為車輛初始狀態為

(22)

(23)

調車作業計劃應在車輛初始狀態的基礎上進行編制，調車作業在車輛達到目標順序時停止。

?o,o+1∈O

(24)

(8) 非線性項處理

?k-1k∈Kt∈T

(25)

(26)

(27)

因此，式( 2 )可被式(27)線性化的表示出來。同理，式( 3 )可以線性化的表示為

?k-1k∈Kt∈T

(28)

(29)

(30)

剩余的絕對值項可進一步線性化，并可在商業求解器中方便處理，在此不再贅述。

3 調車作業計劃模型的求解算法

本文所建立模型為0-1線性規劃模型，可使用商業求解器求解。當問題涉及的車輛數、調車線數、去向數等規模變大時，問題規模將大大增加，使得求解器在短時間內很難求得最優解。本文根據模型中連掛鉤與溜放鉤決策變量為0-1變量的特點，設計了啟發式規則下的分支定界算法。在介紹算法之前，首先明確“逆序”概念及其計算方法。

3.1 逆序計算方法

逆序是指待編車列中的相對車位(車輛位置)順序與目標車位順序相反的狀態，逆序數是指車列中逆序數量的總和。逆序數的大小代表著待編車列車位順序與目標車位順序的偏離程度，逆序數越大，待編車列中存在逆序的車輛就越多，即與目標車位順序相差越遠。當逆序數的值為0時，待編車列中不存在逆序車輛，即待編車列達到目標順序。

隨著調車作業過程中車輛的調移，待編車列中逆序及其數量不斷發生變化，調車作業過程中待編車列逆序數的計算方法如下。

(1) 機帶車列總逆序nl計算方法

(31)

(32)

式(32)計算機帶車列中任意兩車的位置順序關系并加和。

(2) 調車線停放車列總逆序數ns計算方法

(33)

(34)

式(34)計算每條調車線上任意兩車的位置順序關系并加和。

(3) 逆序總數計算方法

n=nl+ns

(35)

式中：n為機帶車列與調車線車列的總逆序。

基于逆序定義，進一步設計啟發式算法對調車作業計劃的編制問題進行求解。

3.2 基于消逆規則的分支定界算法

本文使用“消逆法”中的消逆思想(調車作業過程中，待編車列的逆序總數逐漸下降)，設計了具有“消逆規則”的分支定界算法對調車作業計劃進行進一步優化，下面對算法節點、分支過程以及算法中所設計的啟發式規則進行介紹。

(1) 算法節點及分支過程

(2) 消逆規則

根據節點定義，算法中每個節點均對應一個車輛調移作業；根據節點分支過程，算法中每個節點均由其父節點進行分支得到，并可繼續分支得到其子節點；根據3.1節中逆序的計算方法，每個節點都能夠計算出該節點的逆序總數。

本文使用的“消逆規則”描述為：進行溜放分支得到的節點逆序總數不能大于其父節點的逆序總數，也即是每個節點進行溜放分支得到的子節點逆序總數不能大于該節點的逆序總數，對于違背以上規則的節點及分支進行剪支。因此，“消逆規則”為算法中的剪支規則，從而保證隨著算法分支的進行，節點逆序總數逐漸減少，直至為0。

(3) 逆序最速下降法

本文使用“逆序最速下降法”求解初始上界。逆序最速下降法是指：在求解初始上界時，算法總是優先選擇逆序總數減少最多的節點進行分支，直至求解得到一個可行解。算法將該可行解作為問題的初始上界。雖然逆序最速下降法不能保證得到的調車作業計劃質量，但可以快速的求解初始上界，提高算法效率。

算法根據待編車列的初始狀態開始分支，并以逆序、車輛調移作業次數(調車鉤數)、調移車輛數3方面指標作為啟發式剪支規則進行剪支、迭代與優化，最終獲得調車作業計劃。

算法中符號定義見表1。

表1 分支定界算法中的符號定義

算法步驟為：

Step1初始化。輸入機帶車列以及各調車線上停放的車列中車輛的初始位置及去向、可使用的調車線數量、設置權重α、β、γ、δ的比值。生成根節點，將根節點放入集合Cn中，計算當前待編車列的初始逆序n，以逆序最速下降法計算調車作業計劃初始解，并設置當前最優解x*為該初始解，當前上界為UB*，轉Step2。

Step4剪支。刪除按當前節點，轉Step3。

Step5更新當前最優解x*；更新當前最優上界UB*；根據父節點信息生成當前最優調車作業計劃；將該節點標記為已分支，轉Step3。

Step6找到可行節點。將當前節點加入Cn，轉Step3。

4 算例分析

為驗證所提出的面向調移車輛數優化的調車作業計劃求解方法，本文采用了4組算例實驗：(1)模型有效性實驗，使用求解器進行模型求解并驗證其效果；(2)分支定界算法與求解器的求解效果對比實驗，包括求解質量、效率的對比等；(3)分支定界算法與統籌對口法的求解質量對比實驗，分析考慮調移車輛數時其求解質量與經典算法的差異；(4)權重取值對算法求解結果影響實驗。在本文算例實驗中，初始待編車列停放在調車場內，調車機車在右端作業，車列編成后距調車機車最遠的車組到站為“1”，從遠到近依次編為2，3,…。0-1線性規劃模型求解器使用了商業求解器CPLEX，分支定界算法使用C#實現，問題求解實驗均在CPU為Inter Core i7 3.4 GHz的個人計算機上執行。

4.1 模型有效性實驗

為驗證模型有效性，本實驗在CPLEX求解器中，使用3種權重取值進行小規模調車作業計劃實驗，見表2，實驗a1以連掛鉤最少為目標，實驗a2以調車鉤數最優為目標；實驗a3以基于調車鉤數最優的調移車輛數優化為目標。基于文獻[13]中關于連掛鉤的鉤分約為溜放鉤的3～5倍的統計，本文將連掛作業與溜放作業的取值設為α∶β=γ∶δ=4∶1。為體現基于調車鉤數最優的調移車輛數優化，將調車鉤與調移車輛的權重比值設為γ∶α=δ∶β=100∶1。因此本文算例中當四個權重取值不為0時，分別設置為α=4，β=1，γ=400，δ=100，以保證：(1)保證連掛鉤和溜放鉤數的決定性作用；(2)能夠在鉤數優化的基礎上進行調移車輛數優化；(3)體現連掛鉤與溜放鉤、連掛調移車輛數與溜放調移車輛數的關系。在各表中分別列出了在不同算例中的權重取值。在給定調車線數量的場景下，針對5個待編車列進行了求解實驗，計算結果見表2。

表2 CPLEX計算結果統計

如表2所示，模型能夠求解不同權重設置下的調車作業計劃。在不同權重設置下，能夠求解得到連掛鉤最少(實驗a1)、調車鉤數最優(實驗a2)、基于調車鉤最優的調移車輛數最少(實驗a3)目標下的不同調車作業計劃，且能夠適應不同調車線數量的問題，從求解結果上來看，模型是可行與有效的。在實驗5中CPLEX未求得最優解，其原因在于隨著問題規模的擴大、變量規模加大導致解空間大幅增加，使得求解器無法在給定時間內找到最優解。

實驗4a中不同求解目標函數下的具體調車作業計劃見表3，由對比分析得：(1)連掛鉤數最少目標下的調車作業計劃只能使得連掛鉤數最少，并不能達到對溜放鉤數量進行優化的效果；(2)調車鉤數最優目標下的調車作業計劃可以保證調車鉤數最優，但不能達到調移車輛數的優化效果。(3)基于調車鉤最優的調移車輛數最少目標下調車作業計劃一方面保證了調車鉤數的質量，另一方面能夠對調移車輛數進行優化。由此可以看出，調車鉤數最優的調車作業方案往往并不唯一，對調移車輛數進行優化可以進一步提高計劃的編制質量。

表3 不同求解目標函數下算例4a的具體調車作業計劃

4.2 分支定界算法與求解器的求解效果對比實驗

本實驗以基于調車鉤數最優的調移車輛數優化為目標，通過求解實驗比較分支定界算法與求解器的求解效果。實驗中采用了與4.1節中實驗a3相同的權重設置，具體實驗參數設置及結果見表4，包括連掛鉤數、溜放鉤數、連掛作業調移車輛數、溜放調移作業車輛數、求解時間等。

表4 分支定界算法與求解器的問題求解質量與效率對比

在基于消逆規則的分支定界算法與求解器的算例實驗中，從解的質量來看，在小規模算例(編號1～4)中算法與CPLEX所得出的調車作業計劃的連掛鉤、溜放鉤相同，調移車輛數也無區別，兩者均找到了問題最優解；在算例編號5中，CPLEX未在給定求解時間內找到最優解，分支定界算法則很快找到了高質量的解；在算例編號6中CPLEX在給定時間內沒有找到可行解，而分支定界算法則找到了連掛鉤5鉤，溜放鉤9鉤，連掛作業調移車輛數38輛，溜放作業調移車輛數70輛的解。

上述實驗表明，本文所提出的基于消逆規則的分支定界算法能夠在比求解器更短的時間求解出具有類似質量的調車作業計劃。

4.3 分支定界算法與統籌對口法求解質量對比實驗

統籌對口法是常用的調車作業計劃編制方法，基于開口位置的決策在表格上采用“下落”的方法找到連掛鉤數最少的調車作業計劃，統籌對口法的優勢在于可以使調車作業方案的連掛鉤數達到最少，但當存在有多個連掛鉤數均為最少的調車作業方案時，統籌對口法在對溜放鉤數進行優化并不方便，且在調移車輛數計算方面沒有考慮。本實驗在4條調車線的場景下，編制初始順序為“1543253213”、目標順序為“1122333455”的調車作業計劃，實驗c1以連掛鉤最少為目標，c2以調車鉤數最優為目標，實驗c3以基于調車鉤數最優的調移車輛數優化為目標。采用了統籌對口法與本文所提出分支定界法兩種方法進行求解，權重設置與上文中實驗一致，求解結果見表5。

表5 統籌對口法和分支定界算法求解算例6的結果

對于該算例統籌對口法可求出56個調車作業方案，表5中實驗c1列出了其連掛鉤最少(5鉤)的方案之一，但該方案并非溜放鉤數最少的方案，要獲得溜放鉤最少方案需將56種可行方案計算出后再逐一比較。在以調車鉤數最優為目標的實驗c2中，消逆規則下的分支定界算法找到了與統籌對口法相比具有相同連掛鉤數且溜放鉤數更少(9鉤)的調車作業方案；在進一步對調移車輛數進行優化的實驗c3中，算法求解得到連掛鉤數和溜放鉤數與實驗c2相同，但調移車輛數更少的調車作業方案，實驗c3求解方案與統籌對口法實驗c1相比，總調移車輛數下降了20.6%，其中連掛調移車輛數減少了17.4%，溜放調移車輛數降低了22.2%；與實驗c2相比，總調移車輛數下降了10.0%，其中連掛調移車輛數減少了11.6%，溜放調移車輛數降低了9.1%。實驗結果說明，算法的求解結果能夠在保證連掛鉤數最少的同時，對溜放鉤數進行優化，并且可進一步對調移車輛數進行優化。

4.4 不同權重取值對求解結果影響實驗

本文設計了4組對比實驗對模型目標函數中權重取值對算法求解結果的影響進行分析，見表6。實驗組①為連掛作業調移車輛數權重α變化下的算例實驗，實驗組②中改變連掛鉤及溜放鉤權重γ與δ進行實驗，實驗組③在降低連掛作業調移車輛數權重α條件下，改變連掛鉤及溜放鉤權重γ與δ進行實驗，實驗組④進一步降低連掛作業調移車輛數權重α，改變連掛鉤及溜放鉤權重γ與δ進行實驗。

表6 不同權重系數取值下分支定界算法的求解結果

實驗組①中實驗d1與實驗組②中實驗d4～d7的結果表明，隨著調車鉤權重的降低，調移車輛數較少的調車作業方案質量逐漸上升，表明調車鉤與調移車輛數之間的權重比值對算法求解結果存在影響；實驗組③中實驗d8～d11與實驗組④中實驗d12～d15的結果表明，連掛作業調移車輛數與溜放作業調移車輛數間的權重比值對算法求解結果存在影響。

從上述實驗的整體規律上看，可總結出如下結論：(1)調移車輛數最小的方案不一定調車鉤最少，亦即：存在調車鉤數更多反而調移車輛數更小的調車作業方案；(2)當溜放調移車輛數權重β的比重增大時，算法傾向于找出溜放調移車輛數更少的方案，此時可理解為不使用溜放作業進行平面調車作業的場景。四個權重值在調車作業計劃編制中的變化對求解結果存在較大影響，其最優取值對于現場調車作業計劃編制具有重要意義，需要配合實際作業過程及需求進行進一步深入分析，這也是本文后續研究工作的重點之一。

5 結論

按站順編制摘掛列車是眾多調車作業計劃編制中最為復雜的工作，為此論文以基于調車鉤最優前提下調移車輛數最少為目標，建立了摘掛列車調車作業計劃編制的0-1線性規劃模型，并設計了基于消逆規則的分支定界算法。可得出如下結論：

( 1 ) 考慮了調車作業過程中每一調車鉤的調移車輛數，對調車作業過程進行了精細化的描述，在提高調車作業效率和能源節省方面有著積極意義。

( 2 ) 提出了優化調移車輛數的調車作業計劃0-1線性規劃模型，所提出模型也適用于調車鉤數最優的調車作業計劃求解。

( 3 ) 提出了調車鉤數最優基礎上調移車輛數最少目標下、基于消逆規則的分支定界算法，該算法可求解得到調車鉤數不劣于統籌對口法，調移車輛數更少的調車作業計劃。

研究基于溜放調車法的平面調車作業計劃編制方法，同樣適用于推送調車法的調車作業計劃編制問題，其不同之處在于各類調車程的權重取值。在進一步研究中，將關注兩個方面問題的研究：

( 1 ) 模型目標函數中連掛與溜放鉤的權重取值對求解結果有著重要影響，連掛、溜放調移車輛數的權重取值與連掛、溜放鉤的權重取值在調車作業計劃編制過程的作用是否相同，是需要進一步分析證明的問題。

( 2 ) 另外當問題規模再增大時，算法的求解效率仍存在局限，需要提高算法求解效率。