外文文獻與翻譯---在實際路網(wǎng)中基于路徑重疊的最短路徑算法

1、<p><b>　　外文文獻與翻譯</b></p><p><b>　　文獻原文：</b></p><p>　　A SHORTEST PATH ALGORITHM FOR REAL ROAD NETWORK BASED ON PATH OVERLAP</p><p>　　1 INTRODUCTION</p&

2、gt;<p>　　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 wide range

3、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 prov

4、ision, there is a need to provide some rational alternative paths for road u</p><p>　　On the other hand existing shortest path algorithms such as Dijkstra, Moore build the optimal path based on the node they

5、 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 net

6、work optimization technique to deal with. Banned and penalized turns may be not described appropriately for in the standard node/link method of network definit</p><p>　　This paper proposes a link-based short

7、est 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

8、 is inappropriate, because the Bellman’s 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. Bu

9、t link-based shortest </p><p>　　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

10、on both the degree of overlapping between each path and travel cost, and stops building when the degree of overlapping ratio exceeds its criterion. Because proposed algorithm generates the shortest path based on the link

11、-end cost instead of node cost and constructs path between origin and destination by link connection, the</p><p>　　This paper has been organized as follows. In the next section, two problems of existing shor

12、test path algorithms are given. A detailed description of 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

13、some numerical examples. Finally, conclusions are drawn in section 5.</p><p><b>　　二、中文翻譯：</b></p><p>　　在實際路網(wǎng)中基于路徑重疊的最短路徑算法</p><p><b>　　1介紹</b></p><

14、;p>　　最短路徑問題是尋找一個花費最低的出行路徑從一個或多個起點到一個或多個目的地通過連接的網(wǎng)絡(luò)。這是一個重要問題因為它在運輸中的廣泛應(yīng)用。在某些應(yīng)用中，它也是有利于了解兩個節(jié)點之間的第二或第三最短路徑。例如，為了提高效益提供旅游資訊，有需要提供一些合理的可供選擇的路徑供道路使用者在實際路網(wǎng)中駕駛。為了滿足它，k最短路徑算法已用于一般情況中。Yen（1971年）首先提出K最短路徑搜索方法，它可以產(chǎn)生在最短路徑上刪去若干節(jié)點的其他

15、路徑。因為Yen，若干個 k最短路徑算法被提議。雖然K最短路徑算法可以提供多種可供選擇的路徑，但是它具有重中派生路徑重疊內(nèi)在的限制，這可能導(dǎo)致錯誤的旅游資訊給用戶。在第一條路徑上很大一部分鏈接是重疊的，按照此方法又被第二條和第三條路徑重復(fù)計算了，因此這些駕駛員可能遭受嚴重塞車如果他們遵循旅游信息。這是國際投資協(xié)定同樣的問題在羅吉特為基礎(chǔ)的隨機分配（不相關(guān)的替代獨立）。另一方面現(xiàn)有的如狄克斯特拉最短路徑算法，穆爾建立了到達最優(yōu)路徑的節(jié)點。

16、然而，在考慮網(wǎng)絡(luò)組成的幾個轉(zhuǎn)向限制，如限制左轉(zhuǎn)，這是在現(xiàn)實世界中的網(wǎng)絡(luò)普遍采用的情況下，它為傳統(tǒng)的網(wǎng)絡(luò)優(yōu)化技術(shù)，處理困難。轉(zhuǎn)向禁止和延誤</p><p>　　本文在存在轉(zhuǎn)向限制的真實路網(wǎng)中提出了一種基于鏈接的最短路徑算法，以便提供旅游資訊。當在沒有明顯的擴展網(wǎng)絡(luò)時解決轉(zhuǎn)向延誤問題，基于節(jié)點的最短路徑算法是不適當?shù)?，因為貝爾曼的最?yōu)性條件有任何節(jié)點可能從源頭接觸不到前面所選擇的節(jié)點上的費用也由一個最短路徑達到成本的

17、財產(chǎn)。但是，基于鏈接的最短路徑算法使得可以有效地反映所有轉(zhuǎn)彎，因為它擁有搜索步驟貝爾曼的最佳條件。</p><p>　　該模型的主要優(yōu)點是提供根據(jù)審議中的路徑重疊路徑誘導(dǎo)有效的替代途徑。該算法生成新的路徑上都與每個路徑之間的重疊度的旅行費用，并停止建筑物的時候，重疊程度比超過其標準。由于算法生成最短路徑的鏈路成本為基礎(chǔ)的，而不是結(jié)束節(jié)點成本和結(jié)構(gòu)出發(fā)地和目的地之間的路徑鏈路連接，網(wǎng)絡(luò)擴大并不需要。這樣就可以節(jié)省了