在动态和随机交通网络期待的最短路径（译文附英文原文或原文出处）[外文翻译].doc

附件C：译文


在动态和随机交通网络期待的最短路径
摘要
动态和随机最短路径问题（DSSPP）的定义是在连接旅行时间模拟为随机过程连续时间的交通网络中寻找预期最短路径。本文的目的是研究问题的性质，并确定一个能够用提供资料来解决DSSPP的技术，并在网络与智能交通系统（ITS）得到应用。本文首先对这些网络提出了一整套一个特定的路径的旅行时间在动态和随机链接旅行时间中均值、方差的关系。基于这些关系，它表明该DSSPP是复杂运算和传统的最短路径算法不能保证最佳的解决方案。启发式演算法是基于K最短路径算法来建议，以解决这个问题。最后，解决质量和效率计算之间的转换，提出的方案算法是基于现实的网络来自Edmonton ，Alberta。

关键词：最短路径问题，动态和随机网络，K-最短路径问题，智能交通系统，路径引导系统

1 内容介绍
在近年来最短路径问题在交通运输工程中的应用又被重新掀起热潮。这是直接归因于近期智能交通系统（ITS）的发展，尤其是对外地使用中的车辆进行路线引导（RGS）。中央任何型RGS则是用来计算从原产地到目的地最优路线。对于大多数型RGS目前正在开发的是明确一个始发地和目的地之间最低预计行车时间的最优路径之间。这个最优路径计算普遍应用Dijkstra式在确定路段行程时最短路径算法（Dijkstra 1959年）。这种类型的不利之处是确定性计算，它使得最短路径问题在确定条件下可以在事实上产生分最优解。
反过来说，当双方的性质是动态和随机的路段行程时，很明显，最佳的最短路径算法就成为高成本的无效和/或不切实际的内部使用的一个应用。本文的目的是考察预期的最短路径在交通网络中的问题，在随机性质的路段行程中模拟确定，并发展一种算法，可以提供更好的解决方案，在没有明显增加投入的情况下以计算整体时间。
最短路径的问题已经得到了广泛的研究，在计算机科学、运筹学、交通运输工程等。大部分文献都集中在问题在该路段行程费用（或重量），假设为静态和确定性。许多有效的算法已开发出来（贝尔曼，1958年；Dijkstra，1959年；德莱弗斯，1969年），并在本文中，这些算法被称为标准的最短路径算法。应当指出该标准最短路径算法，也已被证实适用于计算最短路径，在依赖时间的（但不是随机）网络（德莱弗斯，1969年；奥尔达和ROM，1990年；考夫曼等人，1993年；马赫马萨尼，1993年；Chabini，1997年）。