李　軍

(中國神華神朔鐵路分公司,陜西 榆林　719316)

為滿足繁忙運(yùn)輸鐵路線路維修施工的需求，綜合利用施工天窗并集中調(diào)配各類資源的鐵路集中修模式得到了大規(guī)模的使用和推廣。集中修作業(yè)計(jì)劃的編制是集中修作業(yè)順利完成的前提和重要保證[1]。鐵路工程是一種最具有代表性的線性工程，在其上展開的各類維修作業(yè)活動往往具有典型的重復(fù)性及線性特征。各類施工計(jì)劃的編制依賴于CPM等網(wǎng)絡(luò)計(jì)劃類的方法，然而，由于線性工程上各類施工活動所具有的重復(fù)性及線性的特征，使得基于此類方法而編制的作業(yè)計(jì)劃往往復(fù)雜而龐大，可用性、可讀性較差。在此背景下，線性計(jì)劃方法(Linear Scheduling Method，LSM)因其所具有的能夠展現(xiàn)時(shí)空二維信息、保證資源使用的連續(xù)性、簡潔明了等諸多優(yōu)勢，在線性工程作業(yè)計(jì)劃的編制中得到了越來越多的關(guān)注及應(yīng)用[2-3]。

鐵路集中修作業(yè)資源通常包括機(jī)械、人力、資金、材料等，為了保證集中修作業(yè)能夠控制在給定的施工天窗以及預(yù)算內(nèi)，需要對資源進(jìn)行科學(xué)的分配及管理[4]。資源的管理包括資源分配和資源均衡2大類，資源均衡優(yōu)化主要用于實(shí)現(xiàn)固定工期條件下工程項(xiàng)目資源的均衡使用，而資源分配則是用于實(shí)現(xiàn)工程項(xiàng)目工期的最小化。顯然，對于施工天窗極其寶貴的繁忙運(yùn)輸線路的集中修作業(yè)而言，資源分配問題顯得尤為現(xiàn)實(shí)而重要。

本文主要研究了利用LSM進(jìn)行中國鐵路集中修作業(yè)計(jì)劃編制及優(yōu)化的問題，建立了調(diào)度優(yōu)化模型，并利用約束規(guī)劃方法對模型進(jìn)行了求解。最后，利用一段鐵路線路集中修數(shù)據(jù)對模型的有效性進(jìn)行了驗(yàn)證。

1　線性計(jì)劃方法概述

針對線性工程的特征，線性計(jì)劃方法利用一個時(shí)間-空間二維直角坐標(biāo)系來描繪線性工程的施工作業(yè)計(jì)劃。一般而言，Y軸描繪時(shí)間，X軸描繪空間。對于在線性工程之上展開的各類線性作業(yè)活動，用一條帶有斜率的直線，在坐標(biāo)系內(nèi)進(jìn)行標(biāo)注，標(biāo)注后的線性施工活動則具有了確定的空間位置及時(shí)間信息。

在線性計(jì)劃圖中，斜線的斜率反映了線性活動的施工速率。線性活動施工速率與該活動得到的資源有著密切的關(guān)系，通常線性活動的施工速率與該活動所得資源量呈正比。相應(yīng)地用于表示該線性活動的那根斜線的斜率則與該活動所得資源量呈反比。線性計(jì)劃圖中，兩個具有施工搭接時(shí)間的線性活動間在水平方向上的間隔長度，被稱作兩個活動的距離間隔。距離間隔的存在能夠?yàn)樽鳂I(yè)計(jì)劃預(yù)留出一定的緩沖余地，同時(shí)能夠保證活動在搭接作業(yè)時(shí)的安全。線性活動之間所規(guī)定的距離間隔的極限則被稱作它們的最小距離間隔。

一些學(xué)者對基于LSM的施工計(jì)劃的編制及優(yōu)化問題進(jìn)行了研究。文獻(xiàn)[5]討論了基于LSM的施工計(jì)劃的編制問題，但是模型的應(yīng)用場景較為簡單，無法處理工期約束，無法實(shí)現(xiàn)資源量的靈活配置，也無法實(shí)現(xiàn)間隔的靈活配置。文獻(xiàn)[6]利用整數(shù)規(guī)劃方法對LSM框架下的資源均衡問題進(jìn)行了建模及求解，但是這個過程依賴于一個已有的施工計(jì)劃，且模型只考慮了非關(guān)鍵路徑上活動的資源量的調(diào)整，不夠靈活。文獻(xiàn)[1]提出的模型具有編制計(jì)劃的功能，且考慮了工期的約束與資源量的可變性，但是滿足約束的施工計(jì)劃要依靠隨機(jī)的方式獲得，獲取時(shí)間長，效率低。另外，作者雖允許間隔在一定范圍之內(nèi)隨機(jī)取值，但卻人為地給活動之間設(shè)定了最大間隔的約束值，人為削減了間隔的取值范圍。這對模型的靈活性及解的質(zhì)量都造成了影響。同時(shí)，該模型基于遺傳算法進(jìn)行求解，這一求解算法的選擇使得所得施工計(jì)劃的質(zhì)量難以得到保證。文獻(xiàn)[7]對LSM框架下施工計(jì)劃編制問題進(jìn)行了研究，構(gòu)建了計(jì)劃編制模型。該模型能夠?qū)崿F(xiàn)變化速率條件下施工計(jì)劃的編制，具有較高的實(shí)用性。然而，該模型只能實(shí)現(xiàn)最基本的施工計(jì)劃的編制，也就是只能在滿足最小間隔約束的基礎(chǔ)上編制一個施工計(jì)劃，不具備資源優(yōu)化能力。

鐵路集中修作業(yè)涉及多個專業(yè)與部門，管理較為復(fù)雜。我國現(xiàn)有鐵路維修作業(yè)計(jì)劃的編制大多依賴于CPM等網(wǎng)絡(luò)計(jì)劃類的方法，并不適用于鐵路工程。同時(shí)維修作業(yè)計(jì)劃管理多為手工作業(yè)，效率較低[8]。維修作業(yè)計(jì)劃的不合理性會導(dǎo)致大機(jī)作業(yè)時(shí)間的縮短,會導(dǎo)致維修作業(yè)無法按照應(yīng)有的標(biāo)準(zhǔn)展開，不能保證施工質(zhì)量，構(gòu)成了潛在的行車安全隱患。

2　鐵路集中修作業(yè)調(diào)度優(yōu)化模型的構(gòu)建思路

本文針對中國鐵路集中修作業(yè)計(jì)劃編制存在的不足，結(jié)合LSM計(jì)劃編制及優(yōu)化問題研究現(xiàn)狀，提出鐵路集中修調(diào)度優(yōu)化模型的構(gòu)建思路。

在LSM框架的基礎(chǔ)上，將鐵路線路集中修作業(yè)計(jì)劃編制問題用約束滿足問題進(jìn)行描述，構(gòu)建一個基于約束滿足問題(Constraint Satisfaction Problem，CSP)的調(diào)度優(yōu)化模型，并結(jié)合約束規(guī)劃技術(shù)求得優(yōu)化問題的最優(yōu)解。這個基于CSP的調(diào)度優(yōu)化模型以工期最短為優(yōu)化目標(biāo)，以施工先后順序約束、最小時(shí)間間隔約束為邏輯約束。為增強(qiáng)模型的實(shí)用性、靈活性，本模型設(shè)定2類決策變量：活動施工速率、活動開工時(shí)間。允許這2類變量在其各自的取值范圍內(nèi)任意取值。

與既有研究成果相比，本文提出的基于LSM的調(diào)度模型有以下創(chuàng)新之處：

①該模型能夠在滿足固定工期約束基礎(chǔ)上，實(shí)現(xiàn)線性工程進(jìn)度計(jì)劃的自動編制以及工期的最小化。

②在滿足活動之間最小距離間隔約束的基礎(chǔ)上，設(shè)定施工速率和開工時(shí)間2類決策變量。由于多種變量的引入，使得模型的靈活性得以加強(qiáng)。

③模型與約束規(guī)劃技術(shù)相結(jié)合，能夠以較高的效率求得問題的最優(yōu)解。

3　約束規(guī)劃

計(jì)劃編制及優(yōu)化問題屬于組合優(yōu)化問題，對于這類問題的算法，除了數(shù)學(xué)方法和啟發(fā)式方法外，約束規(guī)劃(Constraint Programming，CP)作為一種新的技術(shù)得到了應(yīng)用[9-10]。

約束規(guī)劃最早可以追溯到20世紀(jì)70年代人工智能領(lǐng)域的約束滿足問題(Constraint Satisfaction Problems，CSP)。此類方法綜合了人工智能及數(shù)學(xué)方法，主要用于解組合問題(Combinatorial Problems)和約束滿足問題[11]。

CP通常包含3類要素：問題描述、一致性(相容性)技術(shù)以及搜索策略。問題描述通常包含3個方面:①一個n元變量集合X={x1，…,xn}；②對 集合中任意的一個變量xi，都存在值域Di，D={D1，…,Dn}；③變量間存在的約束關(guān)系C={c1，…,cn}。CP為用戶提供了不同的一致性技術(shù)，例如節(jié)點(diǎn)一致性、弧一致性以及路徑一致性。這些一致性技術(shù)可以被用于在求解的過程中用削減搜索空間，從而達(dá)到提高搜索效率的目的。此外，CP技術(shù)還提供了不同的搜索策略如生成-測試法(Generate and Test,GT)、回溯法(Back Tracking,BT)以及前向搜索法(Forward Checking,FC)等[11-12]。

資源分配優(yōu)化問題作為一類以最短工期為最優(yōu)化目標(biāo)的約束滿足問題，其求解可以采用數(shù)學(xué)規(guī)劃方法如線性規(guī)劃等，或啟發(fā)式算法如蟻群算法、遺傳算法等。數(shù)學(xué)方法在此類問題中應(yīng)用時(shí)的特點(diǎn)是:雖然可以得到最優(yōu)解，但是隨著變量數(shù)量的增加求解及建模變得愈發(fā)困難。啟發(fā)式方法在此類問題中應(yīng)用時(shí)的特點(diǎn)是:雖然可以在相對短的時(shí)間內(nèi)得到問題的可行解，但無法保證所得到作業(yè)計(jì)劃的質(zhì)量。相比之下，約束規(guī)劃方法能夠依據(jù)用戶選擇的搜索算法較為簡便地對問題予以求解，并且模型的構(gòu)建過程不受線性方程等特定的限制，尤其對于LSM框架下的線性活動之間的邏輯關(guān)系，約束規(guī)劃還具有簡化邏輯關(guān)系描述的天然優(yōu)勢。同時(shí)，約束規(guī)劃方法能夠保證所得到的解的質(zhì)量。

本文采用約束規(guī)劃方法對模型進(jìn)行求解，并以ILOG OPL[13]作為建模語言。

4　調(diào)度模型

采用以下常量、變量、約束、目標(biāo)函數(shù)等建立CSP模型。

4.1　常量

f——作業(yè)計(jì)劃中第一個活動；

l——作業(yè)計(jì)劃中最后一個活動；

ui——第i個活動的單位資源對應(yīng)的施工速率；

qi——第i個活動的施工總里程，

(1)

D——項(xiàng)目總天窗數(shù)。

4.2　決策變量

ri——第i個活動的資源量，

(2)

(3)

4.3　決策表達(dá)式

(4)

di——第i個活動的持續(xù)時(shí)間，

(5)

(6)

Wi，j——第j個活動在第i天是否開工，

Wi, j∈{0,1}

(7)

(8)

4.4　約束

1)最小時(shí)間約束?；顒觟的先序活動h對i的開工時(shí)間及完工時(shí)間的約束分為4種情形。當(dāng)活動i的作業(yè)速率小于活動h的作業(yè)速率，且活動i的起點(diǎn)位置在活動h的起點(diǎn)位置之后時(shí)

(9)

當(dāng)活動i的作業(yè)速率小于活動h的作業(yè)速率，且活動i的起點(diǎn)位置在活動h的起點(diǎn)位置之前時(shí)

(10)

當(dāng)活動i的作業(yè)速率大于活動h的作業(yè)速率，且活動i的起點(diǎn)位置在活動h的起點(diǎn)位置之前時(shí)

(11)

當(dāng)活動i的作業(yè)速率大于活動h的作業(yè)速率，且活動i的起點(diǎn)位置在活動h的起點(diǎn)位置之后時(shí)

(12)

2)工期固定的約束

(13)

(14)

(15)

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

問題的目標(biāo)函數(shù)定義為該目標(biāo)函數(shù)可以保證作業(yè)計(jì)劃所需總天窗數(shù)最少，也即工期最短。即

(16)

5　模型驗(yàn)證

本文采用一個鐵路線路集中修案例，對模型進(jìn)行驗(yàn)證。該次集中修作業(yè)里程為K490—K590，共包含4個作業(yè)活動，實(shí)際使用40個天窗。最小距離間隔、單位資源施工速率等集中修作業(yè)信息見表1。

表1　集中修作業(yè)信息

表2為該工程的實(shí)際作業(yè)計(jì)劃。該作業(yè)計(jì)劃由現(xiàn)場工程師依據(jù)個人經(jīng)驗(yàn)而編制，圖1是基于此數(shù)據(jù)而繪制的線性計(jì)劃。由表2中數(shù)據(jù)及圖1可知，該計(jì)劃的實(shí)施共占用了40個天窗。

表2　實(shí)際作業(yè)計(jì)劃

在表1中數(shù)據(jù)的基礎(chǔ)上，利用本文提出的調(diào)度優(yōu)化模型對該集中修作業(yè)計(jì)劃進(jìn)行了編制，并在表3中對計(jì)劃數(shù)據(jù)進(jìn)行了展現(xiàn)。在此數(shù)據(jù)的基礎(chǔ)上，繪制了該作業(yè)計(jì)劃的線性計(jì)劃，如圖2所示。由表3中數(shù)據(jù)及圖2可見，該作業(yè)計(jì)劃滿足了作業(yè)活動之間的最小距離約束，同時(shí)整個作業(yè)計(jì)劃在21個天窗內(nèi)完成。

可見，本文在線性計(jì)劃方法的基礎(chǔ)上所提出的調(diào)度優(yōu)化模型具有自動編制作業(yè)計(jì)劃的能力，大大提高了計(jì)劃編制的效率。由該調(diào)度模型所生成的作業(yè)計(jì)劃(目標(biāo)函數(shù)值：21個天窗)比該工程實(shí)際施工時(shí)所編制的作業(yè)計(jì)劃(目標(biāo)函數(shù)值：40個天窗)在最小化工期這一優(yōu)化目標(biāo)上，具有明顯的優(yōu)越性。

圖1　本文提出的調(diào)度模型生成的作業(yè)計(jì)劃線性計(jì)劃

活動資源使用量開始時(shí)間天窗序號結(jié)束時(shí)間天窗序號工期/d換軌大修202020大機(jī)清篩2165大機(jī)線路維修搗固121816鋼軌預(yù)打磨212219

圖2　實(shí)際作業(yè)線性計(jì)劃

6　結(jié)論

1)在線性計(jì)劃方法的基礎(chǔ)上，針對鐵路這類線性工程集中修計(jì)劃編制問題進(jìn)行了研究，并給出了一個基于CSP的調(diào)度優(yōu)化模型。

2)該模型在線性活動施工速率概念的基礎(chǔ)上，實(shí)現(xiàn)進(jìn)度計(jì)劃的編制以及工期的最小化優(yōu)化。同時(shí)，模型涵蓋了活動的資源量和活動的開始時(shí)間2類決策變量，使得模型的靈活性得以加強(qiáng)。該模型利用CP技術(shù)進(jìn)行了求解，由于CP技術(shù)的高效性，計(jì)劃編制者可以在較短時(shí)間內(nèi)得到問題的最優(yōu)解。

3)利用一段鐵路線路集中修數(shù)據(jù)，驗(yàn)證了模型的有效性。

[1]GEORGY M E.Evolutionary Resource Scheduler for Linear Projects[J].Automation in Construction,2008,5(17):573-583.

[2]LUCKO G,ALVES T D,ANGELIM V L.Challenges and Opportunities for Productivity Improvement Studies in Linear,Repetitive,and Location-based Scheduling[J].Construction Management and Economics,2013,11(7):1-20.

[3]SHAH R K.A New Approach for Automation of Location-based Earthwork Scheduling in Road Construction Projects[J].Automation in Construction,2014,3(3):156-169.

[4]PARK M.Model-based Dynamic Resource Management for Construction Projects[J].Automation in Construction,2005,5(14):585-598.

[5]KALLANTZIS A,LAMBROPOULOS S.Critical Path Determination by Incorporation Minimum and Maximum Time and Distance Constraints into Linear Scheduling[J].Engineering,Construction and Architectural Management,2004,11(3):211-222.

[6]MATTILA K G,ABRAHAM D M.Resource Leveling of Linear Schedules Using Integer Linear Programming[J].Journal of Construction Engineering and Management,1998,124(3): 263-268.

[7]DUFFY G,WOLDESENBET A,JEONG H S,et al.Advanced Linear Scheduling Program with Varying Production Rates for Pipeline Construction Projects[J].Automation in Construction,2012,27(6):99-110.

[8]李玉括.鐵路施工計(jì)劃管理信息系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].成都:西南交通大學(xué),2007.

[9]OZTURK C,ORNEK A M.Optimisation and Constraint Based Heuristic Methods for Advanced Planning and Scheduling Systems[J].International Journal of Industrial Engineering,2016,23(1):26-48.

[10]MENESI W,GOLZARPOOR B,HEGAZY T.Fast and Near-Optimum Schedule Optimization for Large-Scale Projects[J].Journal of Construction Engineering and Management,2013,139(9): 1117-1124.

[11]LIU S S,WANG C J.Optimizing Linear Project Scheduling with Multi-skilled Crews[J].Automation in Construction,2012,7(24):16-23.

[12]WANG T,MESKENS N,DUVIVIER D.Scheduling Operating Theatres:Mixed Integer Programming vs Constraint Programming[J].European Journal of Operational Research,2015,247(2):401-413.

[13]IBM.IBM ILOG CPLEX Optimization Studio V12.3[M].New York: ARMONK N Y,2012.