外文文献与翻译.docx

外文文献与翻译文献原文：A SHORTEST PATH ALGORITHM FOR REAL ROAD NETWORKBASED ON PATH OVERLAP1 INTRODUCTIONA shortest path problem is for finding a path with minimum travel cost from one or moreorigins to one or more destinations through a connected network. It is an important issuebecause of its wide range of applications in transportations. In some applications, it is alsobeneficial to know the second or third shortest paths between two nodes. For instance, inorder to improve the effectiveness of travel information provision, there is a need to providesome rational alternative paths for road users driving in real road network. To meet it, kshortest path algorithms have been used in general. Yen (1971) first proposed k shortest pathsearching method, which could generate several additional paths by deleting node on theshortest path. Since Yen, Several k-shortest algorithms have been suggested. Although kshortest path algorithm can provide several alternative paths, it has inherent limit of heavyoverlapping 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 thirdpath calculated from the method, so the drivers on those links may suffer severe congestionsif they follow the travel information. This is the same problem of IIA (Independence ofIrrelevant Alternatives) in logit-based stochastic assignment.On the other hand existing shortest path algorithms such as Dijkstra, Moore build the optimalpath based on the node they reach. However, in the case of considering the network consistingof several turn prohibitions such as restricting left-turn, which are popularly adopted in realworld network, it makes difficult for the traditional network optimization technique to dealwith. Banned and penalized turns may be not described appropriately for in the standardnode/link method of network definition with intersections represented by nodes only.Thereason is that Bellman`s Princ