c# - 公交公交算法

Question

我正在开发一个可以查找公交路线的离线 C# 应用程序。我可以提取时间表/巴士/路线数据。我正在寻找适用于基本数据的最简单的解决方案。

可以使用什么算法找到从巴士站“A”到巴士站“B”的路线？是否有适用于 C#/Java 的开源解决方案？用于数据库的 google GTFS 格式是否适合简单的解决方案？ http://code.google.com/transit/spec/transit_feed_specification.html

感谢您的帮助。我被这个困住了。我不知道从哪里开始——如何存储数据以及如何查找路线。我知道 Dijkstra/A*，但我只在与时间无关的图表上使用它们...

Answer 1

您正在解决的问题并非易事。这么多，它有一个名字:混合整数非线性规划问题(MINLP)。用一位作者的话来说(Deb 1998):

"When formulated mathematically, the time scheduling problem becomes a mixed integer nonlinear programming problem (MINLP) having a large number of resource- and service-related constraints. Although attempts have been made in the past to find an optimal schedule of a simplified model using classical optimization techniques (Bookbinder & DCsilets, 1992; Kikuchi & Parameswaran, 1993), it is observed that this is an extremely difficult task even for a small transit network. The difficulty arises mainly because of the large number of variables and constraints, discrete nature of variables, and nonlinearities involved in the objective function and the constraints."

在 Deb 的论文中，他提出了一种遗传算法。

您的另一个选择是使用模拟。只是为了扔东西，您可以立即尝试 - 选择从您的起点开始的数千条随机路线，并找出那些在到达目的地时运行良好的路线。

想象一下这样的算法:您正试图从某个时间开始，找到从 A 站到 B 站的最快路线。你雇佣了 1000 人，然后用四分之一的钱来武装他们。你告诉他们每次有机会上下车时都要掷硬币。头，下车(或上车，如果已经下车)。尾部，保持打开(或继续等待，如果关闭)。他们每个人都有一张索引卡，用来记下他们所做的选择。你去 B 点，等待第一个人出现并拿走他的卡片。