[發(fā)明專利]在公共運輸網(wǎng)絡(luò)中的旅行規(guī)劃

在審

• 申請?zhí)枺?/td>: 201210328078.7
• 申請日: 2012-09-06
• 公開（公告）號: CN102915401A
• 公開（公告）日: 2013-02-06
• 發(fā)明（設(shè)計）人: D·德林;A·V·戈德伯格;T·帕約爾;R·F·韋爾內(nèi)克
• 申請（專利權(quán)）人: 微軟公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 顧嘉運

技術(shù)領(lǐng)域

本申請涉及旅行規(guī)劃，特別是在公共運輸網(wǎng)絡(luò)中的旅行規(guī)劃。

背景技術(shù)

通過地圖服務(wù)的推動，存在豐富的關(guān)于確定在運輸網(wǎng)絡(luò)中旅行的研究。許多研究著眼于計算在公路網(wǎng)絡(luò)上的駕駛方向。被稱為公路地圖程序的現(xiàn)有的計算機(jī)程序提供了數(shù)字地圖，通常擁有直到城市-街道級別的詳盡公路網(wǎng)絡(luò)。典型地，用戶可以輸入一個位置，并且公路地圖程序?qū)@示所選位置的屏上地圖。幾個現(xiàn)有的公路地圖產(chǎn)品通常包括計算兩個位置之間最佳路線的能力。換句話說，用戶可以輸入兩個位置，并且公路地圖程序?qū)⒂嬎銖脑次恢玫侥康牡匚恢玫男羞M(jìn)方向。所述方向通常基于距離、旅行時間等。計算位置之間的最佳路線可能要求大量的計算時間和資源。

一些公路地圖程序使用歸因于Dijkstra的公知的方法的變體來計算最短路線。注意，在這種情況下，“最短”意味著“最低成本”，因為每個公路分段都被分配了一個成本或權(quán)重，它們無需與公路分段的長度直接相關(guān)。通過改變計算每個公路的成本的方式，可以為最快、最短或偏好路線生成最短路徑。然而，由于掃描大量位置和可能的路徑，Dijkstra的原始方法在實際應(yīng)用中也不總是有效。相反，許多公知的公路地圖程序使用Dijkstra’s方法的試探變體。

公路地圖算法的最近發(fā)展使用了包括預(yù)處理階段和查詢階段的兩階段過程。在預(yù)處理階段期間，圖形或地圖經(jīng)歷線下處理，以便更高效地完成在圖形上的任意兩個目的地之間的隨后實時查詢。預(yù)處理階段可以花費幾分鐘（或甚至幾小時），并計算一些輔助數(shù)據(jù)，這些數(shù)據(jù)隨后被用于加速查詢。已知的預(yù)處理算法的示例使用地理信息、分層分解以及結(jié)合有地標(biāo)距離的A*搜索。

公共運輸網(wǎng)絡(luò)中的制定路線（例如規(guī)劃在給定時間開始的在公共運輸系統(tǒng)中的兩點之間的旅行）可能表面上看上去是大同小異的，但這個問題在做起來時變得明顯更加困難。為公路網(wǎng)絡(luò)開發(fā)的技術(shù)對于公共運輸來說幫助微乎其微。對于此有兩個原因。第一，公共運輸網(wǎng)絡(luò)不具有公路網(wǎng)絡(luò)的強(qiáng)的分層屬性，在公路網(wǎng)絡(luò)中，幾乎所有的長距離旅行都集中于主要的高速公路。第二，公共運輸網(wǎng)絡(luò)在本質(zhì)上是依賴時間的（例如公交車和火車具有時刻表，在確定最短或最低成本的旅行時要考慮這些時刻表）。第三，除了旅行時間之外，還需要考慮換乘的次數(shù)。這通常通過報告超出一次旅行來完成。另外，公共運輸系統(tǒng)是動態(tài)的，具有頻繁的誤點和取消。不像公路網(wǎng)絡(luò)，小的誤點可能對所得到的路線具有巨大的影響，因為錯過的連接可能導(dǎo)致在中轉(zhuǎn)站或站點（例如，火車站或公交車站點）等待數(shù)小時。還不存在已知的傳統(tǒng)技術(shù)能夠高效地處理大城市區(qū)域的運輸網(wǎng)絡(luò)中的上述特征。

發(fā)明內(nèi)容

提供了用于確定公共運輸網(wǎng)絡(luò)中最佳旅行的技術(shù)。從公共運輸網(wǎng)絡(luò)中的一個站點到另一個站點的Pareto最佳旅行的確定使用了諸如旅行時間和最小換乘之類的條件。

在一個實現(xiàn)中，一種用于在公共運輸網(wǎng)絡(luò)中的雙重條件的旅行規(guī)劃的技術(shù)以循環(huán)（最多K次循環(huán)）方式操作，在循環(huán)k（k≤K）之后，計算直到k次旅程就可以到達(dá)的站點的到達(dá)時間。

在一個實現(xiàn)中，可以使用優(yōu)化技術(shù)。這樣的技術(shù)包括在路線上進(jìn)行迭代，標(biāo)記、收緊停止條件、修剪、平行和后處理以最小化運輸?shù)目倳r間。

提供本概述以便以簡化的形式介紹將在以下詳細(xì)描述中進(jìn)一步描述的一些概念。本概述并不旨在標(biāo)識出所要求保護(hù)的主題的關(guān)鍵特征或必要特征，也不旨在用于限定所要求保護(hù)的主題的范圍。

附圖說明

當(dāng)結(jié)合附圖進(jìn)行閱讀時，可以更好地理解以上概述以及以下對說明性實施例的詳細(xì)說明。出于說明各實施例的目的，在附圖中示出各實施例的示例性構(gòu)造；然而，各實施例不局限于所公開的具體方法和手段。在附圖中：

圖1示出了其中各方面和各實施例可能被利用的計算環(huán)境的示例；

圖2是一種確定在公共運輸網(wǎng)絡(luò)中的旅行的方法的實現(xiàn)的操作流程；

圖3是一種確定在公共運輸網(wǎng)絡(luò)中的旅行的方法的另一實現(xiàn)的操作流程；

圖4是例如如圖3中的一種確定在公共運輸網(wǎng)絡(luò)中的旅行的方法的實現(xiàn)中可使用的優(yōu)化的操作流程；

圖5是說明在查詢期間可掃描的各種路線的圖例；

圖6是一種確定在公共運輸網(wǎng)絡(luò)中的旅行的方法的實現(xiàn)中可使用的另一優(yōu)化的操作流程；

圖7是在確定在公共運輸網(wǎng)絡(luò)中的旅行時可使用的示例數(shù)據(jù)結(jié)構(gòu)的說明；

圖8是在確定在公共運輸網(wǎng)絡(luò)中的旅行時可使用的另一示例數(shù)據(jù)結(jié)構(gòu)的說明；以及

圖9示出了一示例性計算環(huán)境。

具體實施方式