基于地鐵車(chē)輛維保項(xiàng)目的進(jìn)度計(jì)劃優(yōu)化模型研究

李美玲，陳 新

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

基于地鐵車(chē)輛維保項(xiàng)目的進(jìn)度計(jì)劃優(yōu)化模型研究

李美玲，陳 新

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

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

地鐵車(chē)輛維保；進(jìn)度計(jì)劃；遺傳算法

1 概述

1.1 研究背景

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

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

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

1.2 地鐵車(chē)輛維保項(xiàng)目進(jìn)度計(jì)劃特征分析

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

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

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

（2）因?yàn)榈罔F車(chē)輛維保項(xiàng)目不具有唯一性，所以其進(jìn)度計(jì)劃可以通過(guò)實(shí)踐進(jìn)行檢驗(yàn)，并根據(jù)實(shí)際情況進(jìn)行優(yōu)化調(diào)整。這是其他項(xiàng)目所不具備的特點(diǎn)。

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

2 模型的建立

2.1 地鐵車(chē)輛維保項(xiàng)目進(jìn)度計(jì)劃優(yōu)化模型

（1）地鐵車(chē)輛維保項(xiàng)目進(jìn)度計(jì)劃優(yōu)化模型建立思路

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

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

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

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

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

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

（3）地鐵車(chē)輛維保項(xiàng)目進(jìn)度優(yōu)化的“時(shí)間-資源”平衡模型

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

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

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

2.2 項(xiàng)目進(jìn)度計(jì)劃優(yōu)化模型求解

2.2.1 遺傳算法

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

2.2.2 算法設(shè)計(jì)

本文利用遺傳算法進(jìn)行模型求解，具體過(guò)程包括以下幾個(gè)步驟：

（1）編碼

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

（2）選擇和交叉算子

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

（3）變異算子

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

（4）遺傳算法流程

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

3 實(shí)例分析

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

用單代號(hào)網(wǎng)絡(luò)圖表示項(xiàng)目進(jìn)度進(jìn)化如圖4所示。

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

圖3　 遺傳算法流程圖

表1　 月檢項(xiàng)目信息

圖4　 項(xiàng)目進(jìn)度計(jì)劃網(wǎng)絡(luò)圖

由此可以得到項(xiàng)目工序的資源用量及其所需時(shí)間如表2所示。

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

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

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

圖5　 項(xiàng)目資源動(dòng)態(tài)曲線(xiàn)

4 結(jié)論

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

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

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

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

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

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

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

［7］廖良才，張琦.基于混合遺傳算法和關(guān)鍵鏈的多資源多項(xiàng)目進(jìn)度計(jì)劃優(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)蒙古赤峰人，碩士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸工程。

2015-09-22）