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

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

Petri net simulation algorithm of maximum flow in transportation network

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.