基于Petri网的顾及转向延误的最优路径算法

杨 琰，廖伟志，李文敬，杨 文，李 杰

（广西师范学院 计算机与信息工程学院，广西 南宁530023）

0 引 言

城市道路交叉口转向引起的时间延误不能忽略。有调查表明，城市交通网络中车辆在交叉口的延误可以达到全部行驶时间的17%－35%。考虑转向延误的最短路径算法［1］具有重要的现实意义。针对这一问题国内外有些代表性的研究成果：唐小勇［2］和杜牧青［3］从数据存储结构和算法两方面着手求解最优路径；高明霞［4］为网络中的各个弧设置了一个距离标号和紧前弧标号，通过不断迭代、更新弧的标号来寻找最短路径；郑年波［5］把交通路网表达为动态对偶网络，推导了满足先进先出特性的动态行程计算方法，设计了时间依赖的标号设定最短路径算法。

现有的这些研究均针对有向网络，然而现实交通网络是无向的。当网络规模增大时，无向图向有向图的转化以及转换后网络结构的规模会导致问题求解的复杂度急剧增加。再者，目前常用的扩展网络法和对偶网络法均需对初始网络进行变换，处理过程复杂且其处理结果将原本直观的网络结构变的不再一目了然。基于Petri网的最短路算法［6］是通过求解网图中 “托肯”从指定起点到达终点的最短运行时间来寻求最短路径，较传统直接计算路长而言，更为直观和方便。据此，本文针对双向通行的交通网络，提出基于无向Petri网［7］的顾及转向延误的最优路径智能搜索算法。

1 基于无向Petri网的交通网络模型

1.1 Petri网概述

Petri网 （PN）［8］是一种进行系统分析和模拟的图形化建模工具，它既能刻画系统的结构，又能模拟系统的运行，适合描述离散事件的动态过程。……