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

Petri net simulation algorithm of maximum flow in transportation network

作　　者：孙同江[1] 黄圣国[1] 

机构地区：[1]南京航空航天大学民航学院,江苏南京210016

出　　处：《交通运输工程学报》2002年第3期76-80,共5页Journal of Traffic and Transportation Engineering

基　　金：国家自然科学基金项目 ( 79870 0 32 )

摘　　要：现代化的综合交通体系和智能交通系统要求必须首先解决运输需求分析和运输网络分析的技术问题。Petri网理论可以被引进到运输网络理论中 ,用来解决最基本也是应用最广泛的最大流问题。首先介绍了 Petri网与有向网络的 Petri网模型 ;然后 ,给出有向网络最大流的求最短路法 ;在此基础上 ,采用 Petri网论法和计算机图形仿真法相结合的方法 ,求解运输网络最大流。即用Petri网图仿真器把无向运输网络转化为有向运输网络 ,然后求有向运输网络 G的对偶网络 DG,再用 Petri网图仿真器将对偶网络 DG转换成 Petri图模型 ,并自动求得 DG最短路 (原网络 G的最小割容量 ) ,即运输网络最大流。该方法比现有方法更方便 ,速度更快 ,而且形象、直观 。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.5 figs,5 refs.

关 键 词：算法 运输网络 最大流 PETRI网 仿真 

分 类 号：U113[交通运输工程] TP391.9[自动化与计算机技术—计算机应用技术]