兰州交通大学学报
蘭州交通大學學報
란주교통대학학보
JOURNAL OF LANZHOU JIAOTONG UNIVERSITY（Natural Sciences）
2011年
6期
111-114
,共4页
最短路径%交叉口延误和转向限制%弧标号%标号修正算法
最短路徑%交扠口延誤和轉嚮限製%弧標號%標號脩正算法
최단로경%교차구연오화전향한제%호표호%표호수정산법
在考虑交叉口延误和转向限制的情况下,交通网络中的最短路问题较为特殊和复杂,传统的节点标号方式及相应的基于无后效性条件的算法不适用于这类问题.本文对该类问题的特点及已有典型方法进行了分析,提出了一个基于孤标号的标号修正算法.算法分别为每条弧设置一个距离标号和一个紧前弧标号,通过不断迭代、更新弧的标号来寻找最短路径.对给定网络经一定次数的迭代,可得到起点至其它所有节点的最短路径,在“一对多”形式的路径优化中效果较好,应用于一般道路网时计算时间复杂性为O(nm).最后给出了一个数值算例,说明算法的应用.
在攷慮交扠口延誤和轉嚮限製的情況下,交通網絡中的最短路問題較為特殊和複雜,傳統的節點標號方式及相應的基于無後效性條件的算法不適用于這類問題.本文對該類問題的特點及已有典型方法進行瞭分析,提齣瞭一箇基于孤標號的標號脩正算法.算法分彆為每條弧設置一箇距離標號和一箇緊前弧標號,通過不斷迭代、更新弧的標號來尋找最短路徑.對給定網絡經一定次數的迭代,可得到起點至其它所有節點的最短路徑,在“一對多”形式的路徑優化中效果較好,應用于一般道路網時計算時間複雜性為O(nm).最後給齣瞭一箇數值算例,說明算法的應用.
재고필교차구연오화전향한제적정황하,교통망락중적최단로문제교위특수화복잡,전통적절점표호방식급상응적기우무후효성조건적산법불괄용우저류문제.본문대해류문제적특점급이유전형방법진행료분석,제출료일개기우고표호적표호수정산법.산법분별위매조호설치일개거리표호화일개긴전호표호,통과불단질대、경신호적표호래심조최단로경.대급정망락경일정차수적질대,가득도기점지기타소유절점적최단로경,재“일대다”형식적로경우화중효과교호,응용우일반도로망시계산시간복잡성위O(nm).최후급출료일개수치산례,설명산법적응용.
