基于最短工期的鐵路集中修作業(yè)計(jì)劃編制及優(yōu)化研究

李　軍

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

為滿足繁忙運(yùn)輸鐵路線路維修施工的需求，綜合利用施工天窗并集中調(diào)配各類資源的鐵路集中修模式得到了大規(guī)模的使用和推廣。集中修作業(yè)計(jì)劃的編制是集中修作業(yè)順利完成的前提和重要保證[1]。鐵路工程是一種最具有代表性的線性工程，在其上展開的各類維修作業(yè)活動(dòng)往往具有典型的重復(fù)性及線性特征。各類施工計(jì)劃的編制依賴于CPM等網(wǎng)絡(luò)計(jì)劃類的方法，然而，由于線性工程上各類施工活動(dòng)所具有的重復(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ì)劃方法利用一個(gè)時(shí)間-空間二維直角坐標(biāo)系來描繪線性工程的施工作業(yè)計(jì)劃。一般而言，Y軸描繪時(shí)間，X軸描繪空間。對于在線性工程之上展開的各類線性作業(yè)活動(dòng)，用一條帶有斜率的直線，在坐標(biāo)系內(nèi)進(jìn)行標(biāo)注，標(biāo)注后的線性施工活動(dòng)則具有了確定的空間位置及時(shí)間信息。

在線性計(jì)劃圖中，斜線的斜率反映了線性活動(dòng)的施工速率。線性活動(dòng)施工速率與該活動(dòng)得到的資源有著密切的關(guān)系，通常線性活動(dòng)的施工速率與該活動(dòng)所得資源量呈正比。相應(yīng)地用于表示該線性活動(dòng)的那根斜線的斜率則與該活動(dòng)所得資源量呈反比。線性計(jì)劃圖中，兩個(gè)具有施工搭接時(shí)間的線性活動(dòng)間在水平方向上的間隔長度，被稱作兩個(gè)活動(dòng)的距離間隔。距離間隔的存在能夠?yàn)樽鳂I(yè)計(jì)劃預(yù)留出一定的緩沖余地，同時(shí)能夠保證活動(dòng)在搭接作業(yè)時(shí)的安全。線性活動(dòng)之間所規(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)行了建模及求解，但是這個(gè)過程依賴于一個(gè)已有的施工計(jì)劃，且模型只考慮了非關(guān)鍵路徑上活動(dòng)的資源量的調(diào)整，不夠靈活。文獻(xiàn)[1]提出的模型具有編制計(jì)劃的功能，且考慮了工期的約束與資源量的可變性，但是滿足約束的施工計(jì)劃要依靠隨機(jī)的方式獲得，獲取時(shí)間長，效率低。另外，作者雖允許間隔在一定范圍之內(nèi)隨機(jī)取值，但卻人為地給活動(dòng)之間設(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ǔ)上編制一個(gè)施工計(jì)劃，不具備資源優(yōu)化能力。

鐵路集中修作業(yè)涉及多個(gè)專業(yè)與部門，管理較為復(fù)雜。我國現(xiàn)有鐵路維修作業(yè)計(jì)劃的編制大多依賴于CPM等網(wǎng)絡(luò)計(jì)劃類的方法，并不適用于鐵路工程。同時(shí)維修作業(yè)計(jì)劃管理多為手工作業(yè)，效率較低[8]。維修作業(yè)計(jì)劃的不合理性會(huì)導(dǎo)致大機(jī)作業(yè)時(shí)間的縮短,會(huì)導(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)建一個(gè)基于約束滿足問題(Constraint Satisfaction Problem，CSP)的調(diào)度優(yōu)化模型，并結(jié)合約束規(guī)劃技術(shù)求得優(yōu)化問題的最優(yōu)解。這個(gè)基于CSP的調(diào)度優(yōu)化模型以工期最短為優(yōu)化目標(biāo)，以施工先后順序約束、最小時(shí)間間隔約束為邏輯約束。為增強(qiáng)模型的實(shí)用性、靈活性，本模型設(shè)定2類決策變量：活動(dòng)施工速率、活動(dòng)開工時(shí)間。允許這2類變量在其各自的取值范圍內(nèi)任意取值。

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

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

②在滿足活動(dòng)之間最小距離間隔約束的基礎(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個(gè)方面:①一個(gè)n元變量集合X={x1，…,xn}；②對 集合中任意的一個(gè)變量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框架下的線性活動(dòng)之間的邏輯關(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ì)劃中第一個(gè)活動(dòng)；

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

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

qi——第i個(gè)活動(dòng)的施工總里程，

(1)

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

4.2　決策變量

ri——第i個(gè)活動(dòng)的資源量，

(2)

(3)

4.3　決策表達(dá)式

(4)

di——第i個(gè)活動(dòng)的持續(xù)時(shí)間，

(5)

(6)

Wi，j——第j個(gè)活動(dòng)在第i天是否開工，

Wi, j∈{0,1}

(7)

(8)

4.4　約束

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

(9)

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

(10)

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

(11)

當(dāng)活動(dòng)i的作業(yè)速率大于活動(dòng)h的作業(yè)速率，且活動(dòng)i的起點(diǎn)位置在活動(dòng)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)證

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

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

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

表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è)活動(dòng)之間的最小距離約束，同時(shí)整個(gè)作業(yè)計(jì)劃在21個(gè)天窗內(nèi)完成。

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

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

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

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

6　結(jié)論

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

2)該模型在線性活動(dòng)施工速率概念的基礎(chǔ)上，實(shí)現(xiàn)進(jìn)度計(jì)劃的編制以及工期的最小化優(yōu)化。同時(shí)，模型涵蓋了活動(dòng)的資源量和活動(dòng)的開始時(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.