运输网络最大流的Petri网图仿真算法

孙同江; 黄圣国

运输网络最大流的Petri网图仿真算法

南京航空航天大学民航学院, 江苏南京 210016

基金项目:

国家自然科学基金项目 79870032

详细信息

作者简介:
孙同江(1978-), 男, 山东青州人, 南京航空航天大学硕士生, 从事控制导航与智能化系统研究

中图分类号: U113;TP391;O224;TP4
计量
- 文章访问数: 308
- HTML全文浏览量: 146
- PDF下载量: 191
- 被引次数: 0
出版历程
- 收稿日期: 2002-02-18
- 刊出日期: 2002-09-25

Petri net simulation algorithm of maximum flow in transportation network

School of Civil Aviation, Nanjing University of Aeronautics & Astronautics, Nanjing 210016, China

More Information

Author Bio:
SUN Tong-jiang(1978-), male, a graduate student of Nanjing University of Aeronautics & Astronautics, engaged in research of control navigation and intelligent system

摘要

摘要: 现代化的综合交通体系和智能交通系统要求必须首先解决运输需求分析和运输网络分析的技术问题。Petri网理论可以被引进到运输网络理论中, 用来解决最基本也是应用最广泛的最大流问题。首先介绍了Petri网与有向网络的Petri网模型; 然后, 给出有向网络最大流的求最短路法; 在此基础上, 采用Petri网论法和计算机图形仿真法相结合的方法, 求解运输网络最大流。即用Petri网图仿真器把无向运输网络转化为有向运输网络, 然后求有向运输网络G的对偶网络DG, 再用Petri网图仿真器将对偶网络DG转换成Petri图模型, 并自动求得DG最短路(原网络G的最小割容量), 即运输网络最大流。该方法比现有方法更方便, 速度更快, 而且形象、直观, 是更实用的方法和手段。
- 运输网络 /
- 最大流 /
- Petri网 /
- 仿真
Abstract: With the development of the research about comprehensive traffic system and intelligent traffic system, the technical problem of transportation requirement analysis and network analysis is supposed to be resolved firstly. Petri net theory can be used to solve the maximum flow problem in the ransportation network.Petri net and Petri net model of directional network are first introduced, then, a more applied method of seeking the maximum flow is given out.With the use of Petri net simulator, nondirectional transportation network is converted into a directional network, and its dual graph, denoted by DG, is converted into its Petri net model, then automatically get the maximum flow of the transportation network by seeking the DG's shortest path, i.e. the G's minimum cut capacity. This visual and intuitionistic method is more convenient and faster than the existing methods.
- transportation network /
- maximum flow /
- Petri net /
- simulating

HTML全文

图 1 Petri网与有向网络的Petri网模型

Figure 1. Petri net and the Petri net model of directional network

下载: 全尺寸图片幻灯片

图 2 网络图 1(b)的对偶图

Figure 2. The dual of fig.1 (b)

下载: 全尺寸图片幻灯片

图 3 GEPN变迁的实施规则

Figure 3. The execution rules of the transition of GEPN

下载: 全尺寸图片幻灯片

图 4 无向网络和按最短有向路处理的有向网图

Figure 4. Nondirectional network and its directional graph model

下载: 全尺寸图片幻灯片

图 5 DG网的GEPN网图模型

Figure 5. The GEPN model of the DG network

下载: 全尺寸图片幻灯片

参考文献(5)

[1]	Lu Huapu, Shi Qixin. Progress in the research of intelligent transportation system and their prospects[J]. Science and Technology Review, 1996, 17(10): 54-57.
[2]	袁崇义.Petri网原理[M]. 北京: 电子工业出版社, 1998.
[3]	Huang Shengguo. Petri net simulation of discrete event system[J]. Acta Aeronautica et Astronautica Sinica, 1991, 12(9): 548-551. http://en.cnki.com.cn/Article_en/CJFDTotal-HKXB199109018.htm
[4]	胡运权. 运筹学教程[M]. 北京: 清华大学出版社, 1998.
[5]	郭辉煌. 运筹学与工程系统分析[M]. 北京: 建筑工业出版社, 1986.