李美玲，陳 新

（南京理工大學(xué)自動化學(xué)院，江蘇 南京 210094）

基于地鐵車輛維保項目的進度計劃優(yōu)化模型研究

李美玲，陳 新

（南京理工大學(xué)自動化學(xué)院，江蘇 南京 210094）

合理地開展地鐵車輛維保工作對提高地鐵車輛運行安全性以及降低運營成本有十分重要的意義。文章根據(jù)地鐵車輛維保項目進度計劃的特點，建立了“時間-資源”平衡的進度計劃優(yōu)化模型，運用遺傳算法進行模型求解，同時實現(xiàn)了工期和資源分配的優(yōu)化；并對平衡模型及求解方法進行實例分析，驗證了模型及算法的有效性。

地鐵車輛維保；進度計劃；遺傳算法

1 概述

1.1 研究背景

隨著我國城市化進程的加快，地鐵交通在緩解大城市交通擁堵，實現(xiàn)城市可持續(xù)發(fā)展中起到越來越重要的作用。自1969-10-01北京第一條地鐵線路建成通車以來，至2015年我國已有北京、上海、廣州、深圳、天津、南京、重慶等許多城市開通了地鐵線路。目前我國地鐵交通仍保持迅猛發(fā)展態(tài)勢，“十二五”期間的建設(shè)規(guī)模約為2 500 km，預(yù)計2020年地鐵線路總里程將達到7 000 km左右，地鐵線路將覆蓋全國主要大中城市，地鐵交通將在城市交通系統(tǒng)中發(fā)揮至關(guān)重要的作用［1］。

地鐵車輛是地鐵交通中的核心部分，一切地鐵交通的建設(shè)及維護都是為地鐵車輛安全而平穩(wěn)運行這個最重要目的而服務(wù)的。地鐵車輛的維修和保養(yǎng)正是其中重要的環(huán)節(jié)，合理地開展地鐵車輛維保工作對確保地鐵車輛安全運行、提升車輛運行品質(zhì)以及降低運營成本有十分重要的意義。

在此背景下，為了提高地鐵車輛維保管理效率，降低維保工作成本，保證地鐵車輛安全平穩(wěn)地運行，本文將在項目化管理理論的分析和地鐵車輛維修的實踐基礎(chǔ)上，用項目化管理的方法和工具去指導(dǎo)地鐵車輛維保管理工作，構(gòu)建地鐵車輛維保的“時間-資源”平衡模型，促進地鐵車輛維保管理的高效化和規(guī)范化。

1.2 地鐵車輛維保項目進度計劃特征分析

項目進度計劃是在進行項目工作分解的基礎(chǔ)上對項目各項工作在時間進度方面所作的安排［2-3］。項目進度計劃作為項目體系中最重要的部分，它是項目管理及進度控制的依據(jù)，同時也是質(zhì)量控制、風(fēng)險分析等工作的基礎(chǔ)。

地鐵車輛維保項目并不是嚴格意義上的項目，地鐵車輛的各個修程都需要在一定時間范圍內(nèi)重復(fù)進行，如日檢需要每天進行，月檢則可能每月進行一次。各項維保工作也都有相應(yīng)的應(yīng)遵循的標準或規(guī)范。因此地鐵車輛維保項目的進度計劃及其優(yōu)化具有其特殊性。

（1）由于地鐵車輛維保的重復(fù)性和規(guī)范性的特點，其各項工作的資源需求以及持續(xù)的時間都相對明確，因此無需對項目各工序時間進行估算，由此避免了很多不確定性因素，對項目工期的估算也相對準確。

（2）因為地鐵車輛維保項目不具有唯一性，所以其進度計劃可以通過實踐進行檢驗，并根據(jù)實際情況進行優(yōu)化調(diào)整。這是其他項目所不具備的特點。

（3）地鐵車輛維保項目是已經(jīng)多次進行的工作，對其進度計劃的優(yōu)化中，若考慮對工序的順序進行調(diào)整，則優(yōu)化空間較小。因此本文選擇從網(wǎng)絡(luò)資源分配的角度進行地鐵車輛維保項目進度計劃的優(yōu)化，通過改變對各項工作投入的資源量來實現(xiàn)資源和工期的雙重目標的最優(yōu)化。

2 模型的建立

2.1 地鐵車輛維保項目進度計劃優(yōu)化模型

（1）地鐵車輛維保項目進度計劃優(yōu)化模型建立思路

本文根據(jù)地鐵車輛維保項目的特點，同時以時間（工期）和資源為優(yōu)化目標，建立“時間-資源”平衡進度計劃優(yōu)化模型［3］，并利用遺傳算法進行模型求解，模型的建立思路如圖1所示。

（2）時間與資源的關(guān)系

地鐵維保項目每個工序所要花費的時間與投入的資源有直接的關(guān)系。為了便于計算，將地鐵車輛維保項目所有工序的資源根據(jù)其價值按統(tǒng)一的單位量化，并認為資源和時間是線性關(guān)系，如圖2所示，則“時間”和“資源”的關(guān)系為：

（i=1，2，…，N；R（i）0≤R（i）≤Rm（i） ）

式中：N為項目的總工序數(shù)；R（i）為對工序i投入的資源數(shù)；T（i）為工序i所花費的時間；R0（i）為完成工序i最少需要的資源數(shù)；Rm（i） 為對工序i投入的資源上限；T0（i）為對工序i投入的資源數(shù)為R0（i）時工序 i所花費的時間；Tm（i）為對工序i投入的資源數(shù)為Rm（i）時工序i所花費的時間。

圖2　 時間和資源關(guān)系圖

（3）地鐵車輛維保項目進度優(yōu)化的“時間-資源”平衡模型

“時間-資源”平衡模型有兩個優(yōu)化目標，對于這一類的多目標優(yōu)化問題，可以利用權(quán)函數(shù)將其轉(zhuǎn)化為單目標的優(yōu)化問題［4］。用EarlyFinish（i）表示工序i的最早結(jié)束時間，則“時間-資源”平衡模型的兩個優(yōu)化目標的目標函數(shù)分別為：minf1=max由于兩個目可以采用平方權(quán)函數(shù)構(gòu)造模型的目標函數(shù)［5-6］。由此建立“時間-資源”平衡模型：

式中：ω，ω分別為f2，f2的權(quán)值；EF為項目的最遲1212m工期。

模型中ω1、ω2的求解思路為：先求出單個目標函數(shù)最優(yōu)解，minf、minf2的最優(yōu)解解集分別用P1、P2表示，代入模型目標函數(shù)，通過求解線性方程組式（3）來求得ω1、ω2的值。

2.2 項目進度計劃優(yōu)化模型求解

2.2.1 遺傳算法

遺傳算法（Genetic Algorithm）是模擬自然界遺傳機制和生物進化規(guī)律而產(chǎn)生的一種并行的隨機搜索最優(yōu)化方法［4］。其基本思想是:首先對優(yōu)化參數(shù)進［EarlyFinish（i）］標函數(shù)均大于0，行編碼形成種群，按適應(yīng)度函數(shù)對種群中的個體進行篩選，經(jīng)過遺傳中的復(fù)制、交叉及變異等操作進行篩選，這樣適應(yīng)度高的個體就被保留下來，組成了新的群體，新群體更優(yōu)于上一代同時也繼承了上一代的信息。如此周而復(fù)始，種群中個體的適應(yīng)度不斷地提高，直到滿足一定的條件［7-10］。遺傳算法的算法簡單，可并行處理，并能得到全局最優(yōu)解。

2.2.2 算法設(shè)計

本文利用遺傳算法進行模型求解，具體過程包括以下幾個步驟：

（1）編碼

基因碼的位數(shù)根據(jù)R（i）的值域區(qū)間長度確定，基因碼位數(shù)確定后再對R（i）進行編碼。例如，若基因碼位數(shù)為6，則用長度為6位的二進制碼將資源R（i）的取值區(qū)間［R0（i），Rm（i）］離散化為72個等值區(qū)域，區(qū)間［R0（i），Rm（i）］中的值分別對應(yīng)000000～111111之間的二進制碼，再將表示R（1）～R（n）的二進制碼串聯(lián)起來就得到了遺傳算法的染色體，這樣遺傳算法的搜索空間和解空間是一一對應(yīng)的關(guān)系，染色體為6n位的二進制碼。

（2）選擇和交叉算子

選擇操作采用輪盤賭方式進行，適應(yīng)度大的個體被選中的概率較大，交叉算子采用部分映射交叉（Partially Mapping Crossover），首先隨機選取兩個交叉點，交換兩個父代在交叉點的基因片段，保留交叉點以外的基因。例如，兩個父代染色體［x1，x2，x3，x4，x5，x6］和［y1，y2，y3，y4，y5，y6］，如果交叉點為2和4，則進行交叉操作后得到的子代染色體為［x1，y2，y3，y4，x5，x6］和［y1，x2，x3，x4，y5，y6］。

（3）變異算子

變異即基因以一個較低的概率變化操作0-1，1-0，變異操作使遺傳算法具有局部搜索的功能。

（4）遺傳算法流程

在對“時間-資源”平衡模型的求解中，適應(yīng)度函數(shù)為1/F（T，R），遺傳算法的基本步驟如圖3所示。

3 實例分析

為了測試“時間-資源”平衡模型及其算法的有效性，本文采用Matlab編程，并選取地鐵車輛月檢項目作為案例進行實例分析。為了便于量化，將資源量簡化為維保工作需要的人數(shù)，月檢項目的項目信息如表1所示。

用單代號網(wǎng)絡(luò)圖表示項目進度進化如圖4所示。

該項目各工序的資源量R（i）的值域區(qū)間長度較小，因此采用4位二進制碼進行編碼，染色體位數(shù)為60。遺傳算法各參數(shù)選取如下：種群規(guī)模M=1 000；進化代數(shù)T=500；交叉概率Pc=0.6；變異概率Pm=0.05。以MinF（T，R）為優(yōu)化目標進行求解。ω1，ω2的值分別為0.763和0.237。優(yōu)化后目標函數(shù)值為3 974.189。得到的染色體解碼后為：3-6-8-6-1-1-2-3-10-2-2-4-4-5-7。

圖3　 遺傳算法流程圖

表1　 月檢項目信息

圖4　 項目進度計劃網(wǎng)絡(luò)圖

由此可以得到項目工序的資源用量及其所需時間如表2所示。

此時項目網(wǎng)絡(luò)計劃圖的關(guān)鍵鏈為：

根據(jù)各工序所需時間計算得到項目所需工時為27.13 h。由運算結(jié)果及項目進度計劃網(wǎng)絡(luò)圖可以得到項目資源動態(tài)曲線，如圖5所示。由曲線可知，該月檢項目的資源峰值為10，即完成該項目至少需要10名檢修人員。

表2　 優(yōu)化后項目信息

圖5　 項目資源動態(tài)曲線

4 結(jié)論

本文根據(jù)地鐵車輛維保項目進度計劃的特點，建立了“時間-資源”平衡的進度計劃優(yōu)化模型，并用遺傳算法進行模型的求解，實現(xiàn)了工期和資源分配的優(yōu)化，并以月檢項目為例進行實例分析，驗證模型及算法的有效性。文中在建立“時間-資源”平衡模型中，將時間與資源量的關(guān)系簡化為線性關(guān)系，而實際上并非如此，因此對兩者的函數(shù)關(guān)系需要進一步分析。另外，對地鐵車輛維保資源具體的量化方法也需要進一步研究。

［1］蘇志才.地鐵公司地鐵車輛架大修項目管理的應(yīng)用研究［D］.廣州：華南理工大學(xué)，2012.

［2］王樹明.工程項目進度優(yōu)化管理研究［D］.天津：天津大學(xué)，2004：6-10.

［3］張猛，曹德成. GA及模糊理論在資源優(yōu)化配置中的應(yīng)用［J］.土木工程學(xué)報，2004，37（6）：105-110.

［4］邵立波. NB-3項目網(wǎng)絡(luò)計劃技術(shù)的應(yīng)用［D］.山東：山東大學(xué)，2009.

［5］李士勇.智能優(yōu)化算法原理與應(yīng)用［M］.哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2012：31-38.

［6］ 王會玲，劉民，吳澄.啟發(fā)式算法在網(wǎng)絡(luò)計劃多資源平衡中的應(yīng)用［J］.計算機工程與應(yīng)用，2003（14）：226-228.

［7］廖良才，張琦.基于混合遺傳算法和關(guān)鍵鏈的多資源多項目進度計劃優(yōu)化［J］.科學(xué)技術(shù)與工程，2014，14（6）：190-195.

［8］ Chia-Chun Hsu，Hsun-Jung Cho. A genetic algorithm for the maximum edge-disjoint paths problem［J］. Neurocomputing，2015（148）：17-22.

［9］Xiaolei Zhu，Rujie He，Xiaofeng Lu，et. A optimization technique for the composite strut using genetic algorithms［J］. Materials and Design，2015（65）：482-488

［10］Miguel Angel Bautista，Ergio Escalera，Xavier Baro，et. On the design of an ECOC-Compliant Genetic Algorithm［J］. 2014，47（2）：865-884.

Study on Schedule Optimization Model Based on Subway Vehicle Maintenance Project

Li Meiling, Chen Xin
（School of Automation, Nanjing University of Science & Technology, Nanjing 210094, China）

It was of great significance to carry out the maintenance work of metro vehicles rationally for improving the safety of the subway and reducing operating costs. According to the characteristics of the projects of maintenance on metro vehicles, this paper set up a optimization model of “time-resources” balance to optimize the time limit for a project and the allocation of resources at the same time. And the model and algorithm were verified by the example of the balance model and the solution method.

maintenance of metro vehicles; scheduled plan; genetic algorithm

U231+92

A

1672-9889（2016）04-0081-03

李美玲（1990-），女，內(nèi)蒙古赤峰人，碩士研究生，研究方向為交通運輸工程。

2015-09-22）