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

(1. 西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院， 四川 成都 610031；2. 西南交通大學(xué) 綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室， 四川 成都 610031)

調(diào)車作業(yè)計(jì)劃是規(guī)定車輛如何調(diào)移及其作業(yè)程序的具體行動(dòng)計(jì)劃[1]。按站順編組摘掛列車是一類較為復(fù)雜且重要的車站日常調(diào)車作業(yè)，調(diào)車作業(yè)計(jì)劃質(zhì)量對(duì)技術(shù)站及中間站的工作效率有重要影響。

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

隨著高速鐵路的迅猛發(fā)展，動(dòng)車運(yùn)用成為制約通過能力的一個(gè)重要因素。動(dòng)車所調(diào)車作業(yè)計(jì)劃的優(yōu)化編制等問題也成為了研究的熱點(diǎn)，為摘掛列車調(diào)車作業(yè)計(jì)劃的優(yōu)化提供了新的思路。文獻(xiàn)[11]以最小化調(diào)車鉤總數(shù)為目標(biāo)，構(gòu)建動(dòng)車所調(diào)車作業(yè)計(jì)劃整數(shù)規(guī)劃模型，設(shè)計(jì)了粒子群算法進(jìn)行求解。文獻(xiàn)[12]以動(dòng)車運(yùn)用所內(nèi)動(dòng)車組總延誤時(shí)間最小為目標(biāo)建立優(yōu)化模型，并設(shè)計(jì)微進(jìn)化算法進(jìn)行求解。

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

基于上述思路，本文提出了在調(diào)車鉤數(shù)最優(yōu)的基礎(chǔ)上，對(duì)調(diào)移車輛數(shù)進(jìn)行優(yōu)化的摘掛列車調(diào)車作業(yè)計(jì)劃編制方法。首先，建立了面向調(diào)移車輛數(shù)優(yōu)化的調(diào)車作業(yè)計(jì)劃編制0-1線性規(guī)劃模型；其次，設(shè)計(jì)了基于消逆規(guī)則啟發(fā)式算法對(duì)模型進(jìn)行求解；最后通過算例對(duì)模型及算法的有效性進(jìn)行驗(yàn)證，歸納了相關(guān)結(jié)論。

1 問題描述

1.1 問題相關(guān)定義

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

為了提高調(diào)車作業(yè)計(jì)劃的編制質(zhì)量，應(yīng)使摘掛列車編組過程中的調(diào)車作業(yè)量最少，在既有文獻(xiàn)中多以調(diào)車鉤數(shù)多少作為調(diào)車作業(yè)計(jì)劃質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)[3,5,8-9]，其中以連掛鉤數(shù)最少為目標(biāo)最為常見[3,8-9]。在保證調(diào)車鉤數(shù)最優(yōu)并以調(diào)移車輛數(shù)最少為編制目標(biāo)的情況下，調(diào)車作業(yè)計(jì)劃編制的問題描述并無變化，但需引入如下定義：

(1) 車輛調(diào)移

調(diào)車機(jī)車在執(zhí)行調(diào)車作業(yè)的各行程中車輛移動(dòng)的過程，機(jī)車每連掛一個(gè)車輛即產(chǎn)生一個(gè)連掛車輛調(diào)移，每溜放一個(gè)車輛則產(chǎn)生一個(gè)溜放車輛調(diào)移，統(tǒng)稱為車輛調(diào)移。

(2) 調(diào)車鉤調(diào)移車輛數(shù)

單一調(diào)車鉤移動(dòng)的車輛數(shù)量。如果某鉤作業(yè)為連掛作業(yè)，則其移動(dòng)車輛數(shù)稱為連掛鉤調(diào)移車輛數(shù)，由連掛鉤推送行程中移動(dòng)的車輛數(shù)和連掛鉤回拉行程中的移動(dòng)車輛數(shù)組成；若為溜放作業(yè)，則為溜放鉤調(diào)移車輛數(shù)，由溜放鉤推送行程中移動(dòng)的車輛數(shù)和回拉行程中移動(dòng)的車輛數(shù)組成。

(3) 調(diào)車作業(yè)計(jì)劃調(diào)移車輛數(shù)

調(diào)車作業(yè)計(jì)劃各調(diào)車鉤的調(diào)移車輛數(shù)總和。一個(gè)調(diào)車作業(yè)計(jì)劃所有連掛鉤移動(dòng)的車輛數(shù)稱為連掛作業(yè)調(diào)移車輛總數(shù)，所有溜放鉤移動(dòng)的車輛數(shù)稱為溜放作業(yè)調(diào)移車輛總數(shù)。

車輛調(diào)移及調(diào)移車輛數(shù)的定義目的在于對(duì)同一調(diào)車鉤內(nèi)對(duì)各個(gè)車輛的操作進(jìn)行微觀描述。應(yīng)注意的是，車輛調(diào)移發(fā)生在調(diào)車機(jī)車的每一次行程中，一次行程包含多個(gè)車輛調(diào)移，一個(gè)調(diào)車鉤可以包含多個(gè)行程，其調(diào)移車輛數(shù)統(tǒng)計(jì)時(shí)應(yīng)涵蓋每一次行程中的調(diào)移車輛個(gè)數(shù)。一個(gè)連掛鉤的調(diào)移車輛數(shù)，應(yīng)是圖1(a)推送行程的2個(gè)車輛調(diào)移與圖1(b)回拉行程4個(gè)車輛調(diào)移之和，即該連掛調(diào)車鉤產(chǎn)生了6個(gè)車輛調(diào)移。

1.2 問題假設(shè)

為便于模型建立，本文研究的按站順編組的摘掛列車調(diào)車作業(yè)計(jì)劃編制問題基于以下假設(shè)：

(1) 任意一列車列的調(diào)車作業(yè)由一臺(tái)調(diào)機(jī)完成，調(diào)車作業(yè)在一端咽喉進(jìn)行，且調(diào)車過程中不允許出現(xiàn)中斷。

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

2 模型構(gòu)建

2.1 符號(hào)說明

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

K為車輛調(diào)移作業(yè)編號(hào)集合，K={1,2,…,k,…,|K|，k∈N+}，按車輛調(diào)移先后順序進(jìn)行排序，同一調(diào)車鉤行程產(chǎn)生多個(gè)車輛調(diào)移時(shí)，調(diào)機(jī)連掛車列末位車輛的調(diào)移作業(yè)先于其他車輛調(diào)移。k為車輛調(diào)移作業(yè)次序索引，|K|為調(diào)車作業(yè)過程最后一次車輛調(diào)移作業(yè)的編號(hào)。

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

T為調(diào)車場(chǎng)調(diào)車線集合，t為調(diào)車線編號(hào)。

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

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

機(jī)帶車列及停放車列中車輛位置等參數(shù)示意見圖2。

建模過程以每個(gè)車輛的調(diào)移為單位建立決策變量，主要決策變量如下:

(1) 車輛分布狀態(tài)變量

(2) 車輛連掛調(diào)移作業(yè)相關(guān)變量

(3) 車輛溜放調(diào)移作業(yè)相關(guān)變量

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

基于上述決策變量定義，可建立調(diào)車鉤數(shù)最優(yōu)前提下面向調(diào)移車輛數(shù)優(yōu)化模型的目標(biāo)函數(shù)

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

( 1 )

式中：α為每一連掛調(diào)移車輛數(shù)的權(quán)重；yc為調(diào)車作業(yè)計(jì)劃連掛鉤調(diào)移車輛總數(shù)；β為每一溜放調(diào)移車輛數(shù)的權(quán)重；yh調(diào)車作業(yè)計(jì)劃溜放鉤調(diào)移車輛總數(shù)；γ為每一連掛鉤的權(quán)重；xc為實(shí)際連掛鉤總數(shù)；δ為每一溜放鉤的權(quán)重；xh為實(shí)際溜放鉤總數(shù)。

為保證基于調(diào)車鉤數(shù)最優(yōu)討論調(diào)移車輛數(shù)優(yōu)化，可以調(diào)整α、β、γ、δ的取值，使調(diào)車鉤的權(quán)重γ、δ遠(yuǎn)遠(yuǎn)大于調(diào)移車輛數(shù)的權(quán)重α、β。

( 2 )

( 3 )

xc和xh的計(jì)算為

( 4 )

( 5 )

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

2.3 約束條件

為使用所定義決策變量描述調(diào)車作業(yè)計(jì)劃過程，引入如下約束條件：

(1) 車輛調(diào)移作業(yè)執(zhí)行約束

當(dāng)每一車輛調(diào)移作業(yè)(連掛或溜放)執(zhí)行時(shí)，將導(dǎo)致機(jī)帶車列的末位車輛發(fā)生變化，對(duì)應(yīng)的其中一條調(diào)車線上末位車輛也會(huì)發(fā)生變化。該類約束可表示為

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

( 6 )

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

( 7 )

(2) 調(diào)車鉤作業(yè)車輛守恒約束

車輛調(diào)移作業(yè)執(zhí)行時(shí)，機(jī)帶車列的車輛變化會(huì)導(dǎo)致調(diào)車場(chǎng)內(nèi)車輛的相應(yīng)變化為

( 8 )

( 9 )

模型規(guī)定調(diào)機(jī)每次只能連掛或溜放一輛車，約束為

(10)

(11)

(3) 溜放車輛調(diào)移作業(yè)操作車輛數(shù)約束

溜放車輛調(diào)移作業(yè)執(zhí)行時(shí)，調(diào)機(jī)溜放調(diào)移機(jī)帶車列末位一個(gè)車輛，同時(shí)該車輛溜放進(jìn)調(diào)車場(chǎng)后只能溜放至某條調(diào)車線?？寇嚵械哪┪?。該類約束可表示為

?k∈Ko,o+1∈O

(12)

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

(13)

(4) 連掛車輛調(diào)移作業(yè)操作車輛數(shù)約束

連掛車輛調(diào)移作業(yè)執(zhí)行時(shí)，調(diào)機(jī)僅從調(diào)車場(chǎng)內(nèi)某條調(diào)車線上的車列末位掛走一個(gè)車輛，同時(shí)該車輛只能連掛至機(jī)帶車列的末位。該類約束可以表示為

?k∈Ko,o+1∈O

(14)

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

(15)

(5) 容車能力約束

機(jī)帶車列與每一條調(diào)車線的每個(gè)位置最多停放一個(gè)車輛。該類約束可表示為

(16)

(17)

?k∈Kt∈Tp∈P

(18)

?k∈Kt∈Tp∈P

(19)

(6) 車輛調(diào)移作業(yè)選擇與順序約束

每一個(gè)車輛調(diào)移最多只能執(zhí)行連掛車輛調(diào)移作業(yè)與溜放車輛調(diào)移作業(yè)中的一個(gè)，該約束可表示為

(20)

(21)

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

(7) 車輛初始狀態(tài)及目標(biāo)順序約束

調(diào)車作業(yè)開始前，機(jī)帶車列及各調(diào)車線停放車列中車輛位置及去向?yàn)檐囕v初始狀態(tài)為

(22)

(23)

調(diào)車作業(yè)計(jì)劃應(yīng)在車輛初始狀態(tài)的基礎(chǔ)上進(jìn)行編制，調(diào)車作業(yè)在車輛達(dá)到目標(biāo)順序時(shí)停止。

?o,o+1∈O

(24)

(8) 非線性項(xiàng)處理

?k-1k∈Kt∈T

(25)

(26)

(27)

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

?k-1k∈Kt∈T

(28)

(29)

(30)

剩余的絕對(duì)值項(xiàng)可進(jìn)一步線性化，并可在商業(yè)求解器中方便處理，在此不再贅述。

3 調(diào)車作業(yè)計(jì)劃模型的求解算法

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

3.1 逆序計(jì)算方法

逆序是指待編車列中的相對(duì)車位(車輛位置)順序與目標(biāo)車位順序相反的狀態(tài)，逆序數(shù)是指車列中逆序數(shù)量的總和。逆序數(shù)的大小代表著待編車列車位順序與目標(biāo)車位順序的偏離程度，逆序數(shù)越大，待編車列中存在逆序的車輛就越多，即與目標(biāo)車位順序相差越遠(yuǎn)。當(dāng)逆序數(shù)的值為0時(shí)，待編車列中不存在逆序車輛，即待編車列達(dá)到目標(biāo)順序。

隨著調(diào)車作業(yè)過程中車輛的調(diào)移，待編車列中逆序及其數(shù)量不斷發(fā)生變化，調(diào)車作業(yè)過程中待編車列逆序數(shù)的計(jì)算方法如下。

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

(31)

(32)

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

(2) 調(diào)車線停放車列總逆序數(shù)ns計(jì)算方法

(33)

(34)

式(34)計(jì)算每條調(diào)車線上任意兩車的位置順序關(guān)系并加和。

(3) 逆序總數(shù)計(jì)算方法

n=nl+ns

(35)

式中：n為機(jī)帶車列與調(diào)車線車列的總逆序。

基于逆序定義，進(jìn)一步設(shè)計(jì)啟發(fā)式算法對(duì)調(diào)車作業(yè)計(jì)劃的編制問題進(jìn)行求解。

3.2 基于消逆規(guī)則的分支定界算法

本文使用“消逆法”中的消逆思想(調(diào)車作業(yè)過程中，待編車列的逆序總數(shù)逐漸下降)，設(shè)計(jì)了具有“消逆規(guī)則”的分支定界算法對(duì)調(diào)車作業(yè)計(jì)劃進(jìn)行進(jìn)一步優(yōu)化，下面對(duì)算法節(jié)點(diǎn)、分支過程以及算法中所設(shè)計(jì)的啟發(fā)式規(guī)則進(jìn)行介紹。

(1) 算法節(jié)點(diǎn)及分支過程

(2) 消逆規(guī)則

根據(jù)節(jié)點(diǎn)定義，算法中每個(gè)節(jié)點(diǎn)均對(duì)應(yīng)一個(gè)車輛調(diào)移作業(yè)；根據(jù)節(jié)點(diǎn)分支過程，算法中每個(gè)節(jié)點(diǎn)均由其父節(jié)點(diǎn)進(jìn)行分支得到，并可繼續(xù)分支得到其子節(jié)點(diǎn)；根據(jù)3.1節(jié)中逆序的計(jì)算方法，每個(gè)節(jié)點(diǎn)都能夠計(jì)算出該節(jié)點(diǎn)的逆序總數(shù)。

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

(3) 逆序最速下降法

本文使用“逆序最速下降法”求解初始上界。逆序最速下降法是指：在求解初始上界時(shí)，算法總是優(yōu)先選擇逆序總數(shù)減少最多的節(jié)點(diǎn)進(jìn)行分支，直至求解得到一個(gè)可行解。算法將該可行解作為問題的初始上界。雖然逆序最速下降法不能保證得到的調(diào)車作業(yè)計(jì)劃質(zhì)量，但可以快速的求解初始上界，提高算法效率。

算法根據(jù)待編車列的初始狀態(tài)開始分支，并以逆序、車輛調(diào)移作業(yè)次數(shù)(調(diào)車鉤數(shù))、調(diào)移車輛數(shù)3方面指標(biāo)作為啟發(fā)式剪支規(guī)則進(jìn)行剪支、迭代與優(yōu)化，最終獲得調(diào)車作業(yè)計(jì)劃。

算法中符號(hào)定義見表1。

表1 分支定界算法中的符號(hào)定義

算法步驟為：

Step1初始化。輸入機(jī)帶車列以及各調(diào)車線上停放的車列中車輛的初始位置及去向、可使用的調(diào)車線數(shù)量、設(shè)置權(quán)重α、β、γ、δ的比值。生成根節(jié)點(diǎn)，將根節(jié)點(diǎn)放入集合Cn中，計(jì)算當(dāng)前待編車列的初始逆序n，以逆序最速下降法計(jì)算調(diào)車作業(yè)計(jì)劃初始解，并設(shè)置當(dāng)前最優(yōu)解x*為該初始解，當(dāng)前上界為UB*，轉(zhuǎn)Step2。

Step4剪支。刪除按當(dāng)前節(jié)點(diǎn)，轉(zhuǎn)Step3。

Step5更新當(dāng)前最優(yōu)解x*；更新當(dāng)前最優(yōu)上界UB*；根據(jù)父節(jié)點(diǎn)信息生成當(dāng)前最優(yōu)調(diào)車作業(yè)計(jì)劃；將該節(jié)點(diǎn)標(biāo)記為已分支，轉(zhuǎn)Step3。

Step6找到可行節(jié)點(diǎn)。將當(dāng)前節(jié)點(diǎn)加入Cn，轉(zhuǎn)Step3。

4 算例分析

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

4.1 模型有效性實(shí)驗(yàn)

為驗(yàn)證模型有效性，本實(shí)驗(yàn)在CPLEX求解器中，使用3種權(quán)重取值進(jìn)行小規(guī)模調(diào)車作業(yè)計(jì)劃實(shí)驗(yàn)，見表2，實(shí)驗(yàn)a1以連掛鉤最少為目標(biāo)，實(shí)驗(yàn)a2以調(diào)車鉤數(shù)最優(yōu)為目標(biāo)；實(shí)驗(yàn)a3以基于調(diào)車鉤數(shù)最優(yōu)的調(diào)移車輛數(shù)優(yōu)化為目標(biāo)?；谖墨I(xiàn)[13]中關(guān)于連掛鉤的鉤分約為溜放鉤的3～5倍的統(tǒng)計(jì)，本文將連掛作業(yè)與溜放作業(yè)的取值設(shè)為α∶β=γ∶δ=4∶1。為體現(xiàn)基于調(diào)車鉤數(shù)最優(yōu)的調(diào)移車輛數(shù)優(yōu)化，將調(diào)車鉤與調(diào)移車輛的權(quán)重比值設(shè)為γ∶α=δ∶β=100∶1。因此本文算例中當(dāng)四個(gè)權(quán)重取值不為0時(shí)，分別設(shè)置為α=4，β=1，γ=400，δ=100，以保證：(1)保證連掛鉤和溜放鉤數(shù)的決定性作用；(2)能夠在鉤數(shù)優(yōu)化的基礎(chǔ)上進(jìn)行調(diào)移車輛數(shù)優(yōu)化；(3)體現(xiàn)連掛鉤與溜放鉤、連掛調(diào)移車輛數(shù)與溜放調(diào)移車輛數(shù)的關(guān)系。在各表中分別列出了在不同算例中的權(quán)重取值。在給定調(diào)車線數(shù)量的場(chǎng)景下，針對(duì)5個(gè)待編車列進(jìn)行了求解實(shí)驗(yàn)，計(jì)算結(jié)果見表2。

表2 CPLEX計(jì)算結(jié)果統(tǒng)計(jì)

如表2所示，模型能夠求解不同權(quán)重設(shè)置下的調(diào)車作業(yè)計(jì)劃。在不同權(quán)重設(shè)置下，能夠求解得到連掛鉤最少(實(shí)驗(yàn)a1)、調(diào)車鉤數(shù)最優(yōu)(實(shí)驗(yàn)a2)、基于調(diào)車鉤最優(yōu)的調(diào)移車輛數(shù)最少(實(shí)驗(yàn)a3)目標(biāo)下的不同調(diào)車作業(yè)計(jì)劃，且能夠適應(yīng)不同調(diào)車線數(shù)量的問題，從求解結(jié)果上來看，模型是可行與有效的。在實(shí)驗(yàn)5中CPLEX未求得最優(yōu)解，其原因在于隨著問題規(guī)模的擴(kuò)大、變量規(guī)模加大導(dǎo)致解空間大幅增加，使得求解器無法在給定時(shí)間內(nèi)找到最優(yōu)解。

實(shí)驗(yàn)4a中不同求解目標(biāo)函數(shù)下的具體調(diào)車作業(yè)計(jì)劃見表3，由對(duì)比分析得：(1)連掛鉤數(shù)最少目標(biāo)下的調(diào)車作業(yè)計(jì)劃只能使得連掛鉤數(shù)最少，并不能達(dá)到對(duì)溜放鉤數(shù)量進(jìn)行優(yōu)化的效果；(2)調(diào)車鉤數(shù)最優(yōu)目標(biāo)下的調(diào)車作業(yè)計(jì)劃可以保證調(diào)車鉤數(shù)最優(yōu)，但不能達(dá)到調(diào)移車輛數(shù)的優(yōu)化效果。(3)基于調(diào)車鉤最優(yōu)的調(diào)移車輛數(shù)最少目標(biāo)下調(diào)車作業(yè)計(jì)劃一方面保證了調(diào)車鉤數(shù)的質(zhì)量，另一方面能夠?qū)φ{(diào)移車輛數(shù)進(jìn)行優(yōu)化。由此可以看出，調(diào)車鉤數(shù)最優(yōu)的調(diào)車作業(yè)方案往往并不唯一，對(duì)調(diào)移車輛數(shù)進(jìn)行優(yōu)化可以進(jìn)一步提高計(jì)劃的編制質(zhì)量。

表3 不同求解目標(biāo)函數(shù)下算例4a的具體調(diào)車作業(yè)計(jì)劃

4.2 分支定界算法與求解器的求解效果對(duì)比實(shí)驗(yàn)

本實(shí)驗(yàn)以基于調(diào)車鉤數(shù)最優(yōu)的調(diào)移車輛數(shù)優(yōu)化為目標(biāo)，通過求解實(shí)驗(yàn)比較分支定界算法與求解器的求解效果。實(shí)驗(yàn)中采用了與4.1節(jié)中實(shí)驗(yàn)a3相同的權(quán)重設(shè)置，具體實(shí)驗(yàn)參數(shù)設(shè)置及結(jié)果見表4，包括連掛鉤數(shù)、溜放鉤數(shù)、連掛作業(yè)調(diào)移車輛數(shù)、溜放調(diào)移作業(yè)車輛數(shù)、求解時(shí)間等。

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

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

上述實(shí)驗(yàn)表明，本文所提出的基于消逆規(guī)則的分支定界算法能夠在比求解器更短的時(shí)間求解出具有類似質(zhì)量的調(diào)車作業(yè)計(jì)劃。

4.3 分支定界算法與統(tǒng)籌對(duì)口法求解質(zhì)量對(duì)比實(shí)驗(yàn)

統(tǒng)籌對(duì)口法是常用的調(diào)車作業(yè)計(jì)劃編制方法，基于開口位置的決策在表格上采用“下落”的方法找到連掛鉤數(shù)最少的調(diào)車作業(yè)計(jì)劃，統(tǒng)籌對(duì)口法的優(yōu)勢(shì)在于可以使調(diào)車作業(yè)方案的連掛鉤數(shù)達(dá)到最少，但當(dāng)存在有多個(gè)連掛鉤數(shù)均為最少的調(diào)車作業(yè)方案時(shí)，統(tǒng)籌對(duì)口法在對(duì)溜放鉤數(shù)進(jìn)行優(yōu)化并不方便，且在調(diào)移車輛數(shù)計(jì)算方面沒有考慮。本實(shí)驗(yàn)在4條調(diào)車線的場(chǎng)景下，編制初始順序?yàn)椤?543253213”、目標(biāo)順序?yàn)椤?122333455”的調(diào)車作業(yè)計(jì)劃，實(shí)驗(yàn)c1以連掛鉤最少為目標(biāo)，c2以調(diào)車鉤數(shù)最優(yōu)為目標(biāo)，實(shí)驗(yàn)c3以基于調(diào)車鉤數(shù)最優(yōu)的調(diào)移車輛數(shù)優(yōu)化為目標(biāo)。采用了統(tǒng)籌對(duì)口法與本文所提出分支定界法兩種方法進(jìn)行求解，權(quán)重設(shè)置與上文中實(shí)驗(yàn)一致，求解結(jié)果見表5。

表5 統(tǒng)籌對(duì)口法和分支定界算法求解算例6的結(jié)果

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

4.4 不同權(quán)重取值對(duì)求解結(jié)果影響實(shí)驗(yàn)

本文設(shè)計(jì)了4組對(duì)比實(shí)驗(yàn)對(duì)模型目標(biāo)函數(shù)中權(quán)重取值對(duì)算法求解結(jié)果的影響進(jìn)行分析，見表6。實(shí)驗(yàn)組①為連掛作業(yè)調(diào)移車輛數(shù)權(quán)重α變化下的算例實(shí)驗(yàn)，實(shí)驗(yàn)組②中改變連掛鉤及溜放鉤權(quán)重γ與δ進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)組③在降低連掛作業(yè)調(diào)移車輛數(shù)權(quán)重α條件下，改變連掛鉤及溜放鉤權(quán)重γ與δ進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)組④進(jìn)一步降低連掛作業(yè)調(diào)移車輛數(shù)權(quán)重α，改變連掛鉤及溜放鉤權(quán)重γ與δ進(jìn)行實(shí)驗(yàn)。

表6 不同權(quán)重系數(shù)取值下分支定界算法的求解結(jié)果

實(shí)驗(yàn)組①中實(shí)驗(yàn)d1與實(shí)驗(yàn)組②中實(shí)驗(yàn)d4～d7的結(jié)果表明，隨著調(diào)車鉤權(quán)重的降低，調(diào)移車輛數(shù)較少的調(diào)車作業(yè)方案質(zhì)量逐漸上升，表明調(diào)車鉤與調(diào)移車輛數(shù)之間的權(quán)重比值對(duì)算法求解結(jié)果存在影響；實(shí)驗(yàn)組③中實(shí)驗(yàn)d8～d11與實(shí)驗(yàn)組④中實(shí)驗(yàn)d12～d15的結(jié)果表明，連掛作業(yè)調(diào)移車輛數(shù)與溜放作業(yè)調(diào)移車輛數(shù)間的權(quán)重比值對(duì)算法求解結(jié)果存在影響。

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

5 結(jié)論

按站順編制摘掛列車是眾多調(diào)車作業(yè)計(jì)劃編制中最為復(fù)雜的工作，為此論文以基于調(diào)車鉤最優(yōu)前提下調(diào)移車輛數(shù)最少為目標(biāo)，建立了摘掛列車調(diào)車作業(yè)計(jì)劃編制的0-1線性規(guī)劃模型，并設(shè)計(jì)了基于消逆規(guī)則的分支定界算法。可得出如下結(jié)論：

( 1 ) 考慮了調(diào)車作業(yè)過程中每一調(diào)車鉤的調(diào)移車輛數(shù)，對(duì)調(diào)車作業(yè)過程進(jìn)行了精細(xì)化的描述，在提高調(diào)車作業(yè)效率和能源節(jié)省方面有著積極意義。

( 2 ) 提出了優(yōu)化調(diào)移車輛數(shù)的調(diào)車作業(yè)計(jì)劃0-1線性規(guī)劃模型，所提出模型也適用于調(diào)車鉤數(shù)最優(yōu)的調(diào)車作業(yè)計(jì)劃求解。

( 3 ) 提出了調(diào)車鉤數(shù)最優(yōu)基礎(chǔ)上調(diào)移車輛數(shù)最少目標(biāo)下、基于消逆規(guī)則的分支定界算法，該算法可求解得到調(diào)車鉤數(shù)不劣于統(tǒng)籌對(duì)口法，調(diào)移車輛數(shù)更少的調(diào)車作業(yè)計(jì)劃。

研究基于溜放調(diào)車法的平面調(diào)車作業(yè)計(jì)劃編制方法，同樣適用于推送調(diào)車法的調(diào)車作業(yè)計(jì)劃編制問題，其不同之處在于各類調(diào)車程的權(quán)重取值。在進(jìn)一步研究中，將關(guān)注兩個(gè)方面問題的研究：

( 1 ) 模型目標(biāo)函數(shù)中連掛與溜放鉤的權(quán)重取值對(duì)求解結(jié)果有著重要影響，連掛、溜放調(diào)移車輛數(shù)的權(quán)重取值與連掛、溜放鉤的權(quán)重取值在調(diào)車作業(yè)計(jì)劃編制過程的作用是否相同，是需要進(jìn)一步分析證明的問題。

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