我正在一個可以找到公交路線的離線C＃應用程序。 我可以提取時間表/巴士/路線數據。我正在尋找最基本的數據解決方案。公交公交算法
什麼算法可以用來找到從公交車站「A」到公交車站「B」的路線？是否有適用於C＃/ Java的開源解決方案？ 數據庫的谷歌GTFS格式是否適合簡單的解決方案？ http://code.google.com/transit/spec/transit_feed_specification.html
感謝您的幫助。我堅持這一點。我不知道從哪裏開始 - 如何存儲數據以及如何查找路線。 我知道Dijkstra/A *，但是我只在沒有時間依賴的圖表上使用它們...
從概念上講，您採用相同的基本算法來評估A和B之間的距離，但不是距離，而是您應該是評估時間。迪傑斯特拉可以做到這一點，如果你給它適當的投入。
您已經習慣將地圖看作距離的度量。但是，同樣的地圖也可以用來衡量時間。您所需要的只是添加有關平均速度的數據，並且覆蓋特定道路的特定距離所需的時間將自行消失。你甚至可以根據時間想象地圖。花費更長時間的路線會更長。迪傑斯特拉並不關心它評估的是什麼，真的;它只關心尋找具有最低數量的連續路線，以及該數字是代表長度還是時間並不重要。
爲了融入速度，天真的算法只是使用白天的速度限制，並假設你從A到B時不必停下來;更先進的算法可以包含有關一天中的時間和交通模式的信息（這將影響您當時在該道路上行駛的平均速度），以及道路是高速公路還是地面街道（並且因此對所花費的時間進行了教育性的猜測在十字路口）。你使用什麼取決於你有什麼可用的，但基本的4層或5層時間尺度應該適用於除絕對時間最關鍵的應用程序之外的所有應用程序。對於地圖中每條道路的每個方向，您需要早上急流，白天，晚上高峯和夜間的平均速度，可能還需要午餐時間。一旦你有了這些，對Dijkstra算法來說，這是一個相對基本的變化，可以在一天中的某個時間傳遞，並根據時間評估路由。
Dijkstra算法在這個應用程序中的問題是，路線時間以下列方式變化：如果您有從A到B到C的路線，您必須在B處等待您的轉移。等待時間將取決於其餘時間表。然後，從B到C的路線將依次取決於您進行的轉賬，因爲並非所有轉賬都將直接從B轉到C. – Pete 2010-09-02 16:06:34
這就是我面臨的問題，路徑成本（在我的情況下的運輸時間）發生變化隨着時間的推移。您可以採取從A到B的路徑，需要10分鐘。現在從B到C，路徑將取決於當前時間+旅行時間。 在這一點上，我只是試圖規劃前進的編程，但它似乎太複雜了。我試圖谷歌的一切，但我沒有找到一個算法，將路徑成本根據時間表變化的工作。感謝您的幫助。 – 2010-09-02 16:32:24
編輯：我發現了一些可能對Dijsktra +時間表有價值的東西： http://blog.eldslott.org/tag/dijkstra/ – 2010-09-02 16:47:23
如果您對時間信息感興趣，那麼爲什麼不使用時間信息來標記圖邊上的距離值，而是使用時間信息而不是物理距離。這樣你將搜索最快的路線，而不是最短的路線。然後，您可以使用Dijkstra/A *來計算您的結果。
我有點不清楚你的意思是依賴於時間。如果你的意思是你需要回答表單'上午10點之前從x到y'的查詢，那麼你可以計算出上午10點之前到達的巴士路線，看起來像是一個簡單的數據過濾器。然後將Dijkstra/A *應用於數據。
您正在處理的問題不是一項簡單的任務。如此多，這是一個名字：混合整數非線性規劃問題（MINLP）。在一個作者（1998 DEB）的話：
「當數學配製時， 時間調度問題成爲具有的資源和服務 - 大量 一個 混合整數非線性規劃問題 （MINLP）相關的 限制。雖然嘗試 已經發了過去採用經典的優化 技術（書籍裝訂& DCsilets， 1992;菊池& Parameswaran，1993年），以找到一個簡化模型 的 最優調度， 可以觀察到，這是一個 極即使對於小型運輸網絡也是困難的任務。困難 主要出現因爲大量 數量的變量和約束，變量 離散性，以及參與 目標函數 非線性和 約束。」
在Deb的一篇論文中他提出了一種遺傳算法
你的其他選擇是使用模擬，只是爲了拋出一些東西，你可以立即嘗試 - 選擇成千上萬的隨機路線開始在你的起源，並找出合理的工作，到目的地
對此算法進行描述：您正試圖從某個時刻開始，從停止A到停止B，尋找最快的路線。你僱用了1000人，並用四分之一的手臂將它們掰起來翻轉。你告訴他們每次有機會上車或下車時都要拋硬幣。頭，下車（或上車，如果已經關閉）。尾巴，留在（或等待，如果關閉）。他們每個人都有一張索引卡，用於記錄他們隨時做出的選擇。你去B點，等待第一個人出現並拿走他的牌。
這是一個非常受歡迎的「車輛路徑問題」，它是NP-Complete。找到最佳的解決方案是可能的，儘管不太可能。一個<插入計算智能算法>可以在不同程度的成功下工作，唯一的因素是解決方案應該是「多麼正確」。 – gpampara 2010-09-02 17:05:48
我不明白爲什麼在給定的開始時間找到從A到B的路線應該比Dijkstra實現的O（n）慢。如果你想把許多人考慮到巴士的容量，事情就會變得複雜。 – CodesInChaos 2010-11-08 14:10:40
這不是所謂的「旅行推銷員難題」嗎？ – MirroredFate 2011-06-24 23:01:06
試試這個作爲你的數據模型。
總線1進到停止A，B和C總線2前進到停止B，d和E
我將存儲一個唯一的節點基於兩個總線上，並停止，隨着距離的節點是基於時間。我們將有節點A1，B1，C1，B2，D2和E2。在傳輸的特殊情況下，等待下一個總線作爲節點之間的距離。例如，如果巴士1在巴士2前30分鐘到達B站，則從B1到B2的旅行時間爲30分鐘。
您應該能夠應用Dijkstra算法。
閱讀此：
多模態路線規劃。 碩士論文，卡爾斯魯厄大學（TH），Fakultät獻給Informatik公司，在http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf
鐵路路由，可參考2009年 網上也適用於總線佈線。
它的要點：將空間和時間擴展爲單個圖形的幼稚方法不適用於大型網絡。有更聰明的解決方案。
只是想分享我對這個問題的最後方法。這是大學項目的一部分，因此它可能不完全適合現實世界的使用。它必須相當快才能在Windows Mobile設備上運行。
我結束了使用4個表（SQLite）。一張桌子上保存着公共汽車的列表，另一張保留了一個車站清單。另一張桌子保留組合 - 哪些巴士停在某個特定的車站，以及哪個車站從該車站出發，需要多長時間（分鐘）。所有組合都必須存儲。最後一張表是一個簡單的時間表。對於每一個車站，它都列出了每一站停靠的時間和時間（我將時間存儲爲整數值 - 14:34爲1434，以便比較更快）。
我使用了一個雙向寬度優先搜索算法。鄰居站（可直接訪問）被檢索用於起始站和目的地站。如果這兩個「圖形」在一個電臺上重疊，則有從A站到X站的路徑。例如，從A站可以到達站點B，C，D，E（通過使用特定的總線）。從目標站X你可以直接到達N，C，Z。這兩個圖形在C站重疊。因此存在A→C→X的路徑。如果在第一次迭代中找不到路徑，則該算法繼續並再次展開圖（BFS）。
第一步沒有考慮時間 - 這使得速度足夠快。您只會列出可能的路徑列表，並列出必須使用這些路徑的總線列表。 在最後一步中評估時間，查看可能路徑列表並檢查公交車是否在特定時間內行駛（增加每次停車時間）。
在一個擁有250個車站和100多輛公共汽車/鐵路的小城市裏，這些方法最多可以進行3次更改（必須在旅程中更換公交車）。計算只需幾秒鐘。但我不得不將整個數據庫加載到內存（字典）中以加快查詢時間，因爲查詢時間過長。
我不認爲這將適用於大型網絡。但它適用於單箇中小城市的公共交通工具。
有一個廣泛的出版物清單（30+）上已經由貢獻者編譯隨着時間的推移開源（JAVA）OpenTripPlanner project這裏的公共交通路由算法：
https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography
OpenTripPlanner是多模式路由引擎，其中還包括自行車和步行 - 從上述鏈接：
這是一篇文章，論文，和書籍，已啓發和通知現有的OTP路由引擎nd一些正在進行的實驗。目前，OpenTripPlanner使用單個時間相關（而不是時間展開）圖，其中包含街道和公交網絡。通常使用具有歐幾里得啓發式或收縮層次結構的A *算法來計劃僅步行和僅自行車旅行。步行+過境或自行車+過境旅行計劃使用MOA *算法的一個變種，其中包含用於路徑修剪的ε-優勢和用於隊列排序的Tung-Chew啓發式（提供總重量下限的圖）。
上面的路由書目包括算法和相關工作以下幾類引用：
如果你發現新的東西，這不是在名單上，請隨時將其添加到維基！
至於其他開源公共交通路由圖書館 - 也有通過Bliksem實驗室的RRRR項目：
https://github.com/bliksemlabs/rrrr
從上面的鏈接：
RRRR（通常發音R4）是RAPTOR公共交通路由算法的C語言實現。它是Bliksem旅行計劃和旅客信息系統的核心路由組件。該項目的目標是在大的地理區域（例如BeNeLux或全歐洲）生成一系列帕累托最優路線，改善現有更靈活替代品的資源消耗和複雜性。該系統最終應支持行程計劃中反映的實時車輛/行程更新，並且能夠直接在沒有互聯網連接的移動設備上運行。
OpenTripPlanner和RRRR都使用GTFS數據。
[OSRM]（http://project-osrm.org/）是一個基於C++的最短路徑的開源路由引擎。你可能會覺得它很有用。 – 2015-10-23 13:13:03