涂玉芬

（武汉铁路职业技术学院电子电气工程系，武汉 430205）

基于Graph的铁道工程工期估算算法及实现

涂玉芬

（武汉铁路职业技术学院电子电气工程系，武汉 430205）

为有效帮助铁道工程技术管理人员进行工程工期估算，合理调度和控制各子工程的施工进度，运用Graph结构中的AOE网分析工期估算算法，可实现计算机辅助管理，有利于科学管理铁道工程。

Graph；铁道工程；工期估算；AO E网；关键活动

0 引 言

当前，中国正进入史无前例的高速铁路建设期，中国铁路已经站在新的历史起点上，迎来大发展、大建设的黄金时期。面对庞大而复杂的铁道系统工程，进行工程工期估算，合理调度和控制各子工程的施工进度，是保证工程顺利实施的前提。运用Gr aph结构中的AOE网，分析铁道工程工期估算算法，并给出了算法的C语言描述，从而实现了计算机辅助管理，对科学管理铁道工程具有重要意义。

1 Graph结构

Graph（图）是一种复杂的非线性结构，该数据结构中任意两结点之间都可能存在联系。Gr aph结构可用二元组形式表示为：

其中，n表示Graph中顶点的数量，el em t ype表示Graph中顶点（数据元素）的数据类型，P（Vi，Vj）表示存在从Vi到Vj的一条边[1-2]。

根据Graph中存在的边是否有方向性，Graph分为有向图和无向图；根据Gr aph中存在的边是否具有权，Graph分为有权图和无权图；根据Graph中是否存在回路，Graph分为有环图和无环图[1-4]。Graph结构适合于描述各种关系复杂的数据对象，在自然科学及社会科学等许多科学技术领域有着非常广泛的应用。

2 AO E网

任何一个工程项目在实施之前，都要进行工程的可行性分析、工程造价评估、工程工期估算等前期规划工作。一个大的铁道工程一般由许多小的子工程组成，子工程之间通常存在一些时序上的约束关系，有一些子工程可同时进行，而有一些子工程则必须在另一些子工程完成之后才能开始，这就给工程的规划工作带来一定的难度。

AOE网是一种用来表示工程中各项活动（子工程）间关系的带权有向无环图，在此带权有向无环图中，用弧（有向边）表示活动，弧上的权表示活动的持续时间，用顶点表示事件，事件是标志某些活动已经完成和另一些活动开始的信号[2-6]，如图1所示。

图1 一个铁道工程的AOE网

使用AOE网来描述一个铁道工程项目中各子项目及子项目之间时序上的约束关系，可有效地帮助工程技术管理人员进行工程工期估算，合理调度和控制各子工程的工作进度，确保工程如期完成。

3 工程最短工期估算方法

在如图1所示的一个铁道工程的AOE网中，通常只有一个入度为0的顶点，V1表示工程的开始点，称为源点；只有一个出度为0的顶点，V7表示工程的终止点，称为汇点。从源点到汇点的最长路径长度，即最长路径上所有活动（子工程）持续时间之和，就是完成工程所需的最短时间，最长路径上的活动（子工程）是影响整个工程进度的关键。因此，找出AOE网中从源点到汇点的最长路径和该路径上的活动，是计算和控制工程工期的关键。

从源点到汇点的长度最长的路径，称为关键路径，关键路径上的活动，称为关键活动。在没有延误的情况下，时间余量（允许延迟的时间）为0的活动即为关键活动；活动的时间余量等于该活动的最早开始时间与该活动的最迟开始时间之差。要计算AOE网中所有活动的最早开始时间与该活动的最迟开始时间，先要计算出AOE网中所有事件的最早发生时间与最迟发生时间[2][5-6]。

如图2所示，如果活动ai的前一事件为Vm，活动ai的后一事件为Vn，设活动ai的最早开始时间为E（i），活动ai的最迟开始时间为L（i），事件Vj的最早发生时间为VE（j），事件Vj的最迟发生时间为VL（j），则有：

如图3所示，如果事件Vj的前一事件为Vx，事件Vx到Vj的活动为ax，则求事件Vj的最早发生时间VE（j），应从源点开始，向汇点方向按下列公式进行计算：

图2 活动ai

图3 事件Vj的前一事件

如图4所示，如果事件Vj的后一事件为Vy，事件Vj到Vy的活动为ay，则求事件Vj的最迟发生时间VL（j），应从汇点开始，向源点方向按下列公式进行计算：

图4 事件Vj的后一事件

根据上述计算方法，如图1所示的一个铁道工程的AOE网中，所有事件Vj的最早发生时间VE（j）和最迟发生时间VL（j）见表1，所有活动ai的最早开始时间E（i）和最迟开始时间L（i）见表2。

表1 事件Vj的最早发生时间VE（j）和最迟发生时间VL（j）

由表2可知，如图1所示的一个铁道工程的AOE网的关键活动为a1，a4，a7，a10，控制子工程a1，a4，a7，a10的进度就是保证工程工期的关键。其关键路径如图5所示。

表2 所有活动ai的最早开始时间E（i）和最迟开始时间L（i）

图5 一个铁道工程AOE网的关键路径

4 基于C语言的算法及实现

分析铁道工程最短工期估算方法，可得到求关键路径的算法[2][5-6]如下：

（1）输入n条弧，建立AOE网的链接表存储结构。

（2）从源点V1出发，计算AOE网中所有事件Vj的最早发生时间VE（j）。令VE（1）=0，按拓扑顺序计算其余各事件的最早发生时间VE（j）（2≤j≤n） ；如果得到的拓扑有序序列中的顶点个数小于AOE网中的顶点个数，则该网有环，不能求关键路径，算法终止，否则，执行步骤（3）。

（3）从汇点Vn出发，计算AOE网中所有事件Vj的最迟发生时间VL（j）。令VL（n）=VE（n），按拓扑逆序计算其余各事件的最早发生时间VL（j）（n≥j≥2）。

（4）根据各事件的最早发生时间VE和最迟发生时间VL，计算AOE网中所有活动ai的最早开始时间E（i）和最迟开始时间L（i），找出E（i）=L（i）的关键活动并输出。

以上算法可用C语言描述如下：

5 结束语

大规模的铁路建设，将给地方经济带来巨大的拉动作用。基于Gr aph的铁道工程工期估算算法及其实现，将有效地帮助铁道工程技术管理人员进行工程管理，合理调度和控制各子工程的施工进度，降低工程成本，提高工作效率。

[1]李益民，邓文华.数据结构:C语言版[M].北京:电子工业出版社，2004:85-86.

[2]陈明.数据结构[M].北京:清华大学出版社，2005:179-219.

[3]徐士良.实用数据结构[M].北京:清华大学出版社，2006:123-139.

[4]将文容.数据结构[M].北京:高等教育出版社，2005:85.

[5]薛铁鹰.数据结构基础与应用[M].北京:海洋出版社，2005:128-148.

[6]陈雁.数据结构[M].第2版.北京:高等教育出版社，2004:73-99.

Calculation of Time Limit for Railway Engineering on Basis of Graph and its Implementations

TU Yufen
（Department of Electronic & Electric Engineering, Wuhan Railway Vocational College of Technology, Wuhan, 430205, China）

In order to help the manager of railway engineering to calculate the time limit for an engineering, to control the construction schedule of sub-projects, the AOE net in Graph structure is applied and it can achieve the goal of computer-assisted management and is beneficial for the scientific management of railway engineering.

Graph; Railway engineering; Time limit for an engineering; AOE net; Key activities

TU712.1

A

1671-4326（2011）04-0052-04

2011-07-15

涂玉芬（1966—），女，湖北武汉人，武汉铁路职业技术学院电子电气工程系副教授．

王志梅]