1、 外文文献与翻译 一、 文献原文 ： A SHORTEST PATH ALGORITHM FOR REAL ROAD NETWORK BASED ON PATH OVERLAP 1 INTRODUCTION A shortest path problem is for finding a path with minimum travel cost from one or more origins to one or more destinations through a connected network. It is an important issue because of its wid
2、e range of applications in transportations. In some applications, it is also beneficial to know the second or third shortest paths between two nodes. For instance, in order to improve the effectiveness of travel information provision, there is a need to provide some rational alternative paths for ro
3、ad users driving in real road network. To meet it, k shortest path algorithms have been used in general. Yen (1971) first proposed k shortest path searching method, which could generate several additional paths by deleting node on the shortest path. Since Yen, Several k-shortest algorithms have been
4、 suggested. Although k shortest path algorithm can provide several alternative paths, it has inherent limit of heavy overlapping among derived paths, which may lead to wrong travel information to the users. This is that significant proportion of links on the first path is overlapped by second and th
5、ird path calculated from the method, so the drivers on those links may suffer severe congestions if they follow the travel information. This is the same problem of IIA (Independence of Irrelevant Alternatives) in logit-based stochastic assignment. On the other hand existing shortest path algorithms
6、such as Dijkstra, Moore build the optimal path based on the node they reach. However, in the case of considering the network consisting of several turn prohibitions such as restricting left-turn, which are popularly adopted in real world network, it makes difficult for the traditional network optimi
7、zation technique to deal with. Banned and penalized turns may be not described appropriately for in the standard node/link method of network definition with intersections represented by nodes only. The reason is that Bellmans Principle of Optimality does not hold in that case. Several approaches hav
8、e been proposed for solving the problem. Among all methods currently available, the most widely used method is network expansion for describing turn penalties, adding extra nodes and extra links to original network and modify the network to be easily implemented the conventional shortest path algori
9、thms. The principal advantage of this method is that it can describe the turn prohibitions perfectly. The method, however, has limitation of expanding network as the size of network increases, so this method could not apply to large networks as well as dynamic case due to its overwhelming additional
10、 works. This paper proposes a link-based shortest path algorithm for the travel information in real road network where exists turn prohibitions. When penalized turns are dealt with without explicitly expanding the network, node-based existing shortest path algorithm is inappropriate, because the Bel
11、lmans optimality condition has the property that no node may be approached from the origin for less cost than the chosen preceding node which is also reached by a shortest cost path. But link-based shortest path algorithm makes possible to reflect all turns effectively because it holds Bellmans opti
12、mal condition in searching step. The main merit of proposed model is to provide efficient alternative paths for route guidance under consideration of overlaps among paths. The algorithm builds new path based on both the degree of overlapping between each path and travel cost, and stops building when
13、 the degree of overlapping ratio exceeds its criterion. Because proposed algorithm generates the shortest path based on the link-end cost instead of node cost and constructs path between origin and destination by link connection, the network expansion does not require. Thus it is possible to save th
14、e time of network modification and of computer running. The algorithm is tested with some example networks and then will be expanded to dynamic case. This paper has been organized as follows. In the next section, two problems of existing shortest path algorithms are given. A detailed description of
15、the proposed algorithm is defined in section 3, and the comparison with conventional algorithm and performance of the algorithm are illustrated in section 4 with some numerical examples. Finally, conclusions are drawn in section 5. 二、 中文翻译 ： 在实际路网中基于路径重叠的最短路径算法 1 介绍 最短路径问题是寻找一个花费最低的出行路径从一个或多个起点到一个或多
16、个目的地通过连接的网络。 这是一个重要问题因为它在运输中的广泛应用。在某些应用中，它也是有利于了解两个节点之间的第二或第三最短路径。例如，为了提高效益提供旅游资讯，有需要提供一些合理的可供选择的路径供道路使用者在实际路网中驾驶。为了满足它， k 最短路径算法已用于一般情况中。 Yen（ 1971年）首先提出 K 最短路径搜索方法， 它可以产生在最短路径上删去若干节点的其他路径。因为 Yen，若干个 k 最短路径算法被提议。虽然 K 最短路径算法可以提供多种可供选择的路径，但是它具有重中派生路径重叠内在的限制，这可能导致错误的旅游资讯给用户。在第一条路径上很大一部分链接是重叠的，按照此方法又被第
17、二条和第三条路径重复计算了，因此这些驾驶员可能遭受严重塞车如果他们遵循旅游信息。这是国际投资协定同样的问题在罗吉特为基础的随机分配（不相关的替代独立）。另一方面现有的如 狄克斯特拉 最短路径算法，穆尔建立了到达最优路径的节点。然而，在考虑网络组成的几个转向限制，如限制左转，这是在现实世界中的网络 普遍采用的情况下，它为传统的网络优化技术，处理困难。转向禁止和延误可能没有说明在适当的标准节点 /链路的网络定义与节点只占交叉口方法。 原因是贝尔曼的最优性原则在这种情况下不成立。为了解决这个问题已经提出了几种方法， 在所有目前可用的方法中，描述转向延误最常用的方法是扩展网络法， 对于原始网络以及 修改后的网络添加额外的节点和额外的弧可以很容易的实现传统的最短路径算法。该方法的主要优点是，这种方法能很好的描述转向限制。然而，随着网络规模的增加这种方法存在网络扩展限制，所以这种方法不能适用于大型动态网络，因为其存在庞大的额外工程。 本文在存在转向限制的真实路网中提出了一种基于链接的最短路径算法，以便提供旅游资讯。当在没有明显的扩展网络时解决转向延误问题， 基于节点的最短路径算法是不适当的，因为贝尔曼的最优性条件有任何节点可能从源头接触不
