仅通过公共交通工具find最佳路线的策略？
寻找汽车的路线非常简单：您可以存储所有道路的加权graphics，并且可以使用Djikstraalgorithm [1]。 公交线路不太明显。 有了公共汽车，你必须代表“等待下一class车10分钟”或者“走一个车站到另一个公交车站”，然后把它们input你的寻路algorithm。
这对于汽车来说并不总是那么简单。 在一些城市，有些道路早上只能单向进城，晚上只能单向进城。 一些先进的GPS知道如何避免高峰时段的繁忙路线。
你将如何高效地表示这种时间相关图并find路线？ 没有必要有一个可certificate的最佳解决scheme; 如果旅客想要准时，他们会买车。 😉
[1]一个很好的algorithm，在一个例子中提到，因为每个人都听说过它，虽然A *是这个应用程序的更可能的select。
我参与了在瑞典为斯德哥尔摩公共交通发展一个周到的规划系统。 它基于Djikstra的algorithm，但是在系统中每个节点被访问之前终止。 今天当每个站点都有可靠的坐标时，我猜A *algorithm就是select。
关于即将到来的stream量的数据是从数个数据库中定期提取的，并被编译成大型表格，并加载到我们的search服
一个成功的algorithm的关键是使用基于旅行和等待时间乘以不同的权重的path成本函数。 在瑞典语中被称为“kresu”时间 – 这些加权时间反映了这样一个事实，例如，一分钟的等待时间通常与两分钟旅行时间的“不便”相当。
KRESU重量表
- x1 – 旅行时间
- x2 – 在两站之间行走
- x2 – 在旅途中等待。 停在屋顶下，有商店等，可以得到稍低的重量，拥挤的台站可以调整algorithm。
- 在第一站的等待时间的重量是交通强度的函数，可以在0.5到3之间。
数据结构
区域你旅途中的一个命名区域可以开始或结束。 巴士站可能是一个有两个站的区域。 一个拥有多个平台的大型站点可能是每个站台一个站点的区域。 数据：名称，停在区域
停止与所有巴士站，火车站和地铁站arrays。 请注意，您通常需要两站，每个方向一站，因为需要一段时间穿过街道或步行到另一个平台。 数据：名称，链接，节点
链接列出其他站点，您可以从此站点步行到达。 数据：其他停止，时间走到其他停止
线路/旅游您在巴士和目的地有一个号码。 公共汽车从一个站点开始，经过几个站点到目的地。 数据：号码，姓名，目的地
节点通常你有一个时间表，至less应该在巡回赛的第一站和最后一站的时间。 每当公共汽车/火车经过一站时，您都会向arrays添加一个新节点。 这个表格每天可以有数百万个值。 数据：线路/巡视，停车，到达时间，出发时间，误差，巡回中的下一个节点
searcharrays与Nodesarrays具有相同的大小，用于存储您到达的方式和path成本。 数据：与之前节点的反向链接（如果节点未访问，则不设置），path成本（未访问的无限大）
你所说的比像简单的数据结构（如graphics）和“简单”的algorithm（如Djikstra's）可以描述的math模型更复杂。 你所要求的是一个更复杂的问题，就像在自动化物streampipe理领域遇到的那样。
一种考虑问题的方式是，你正在问一个多维问题，你需要能够计算出：
- 距离优化
- 时间优化
- 路线优化
- “时间范围”优化（如果是5:25，公交车只在7:00出现，则select另一条路线。）
鉴于所有这些情况，您可以尝试使用复杂的多层数据结构进行确定性build模。 例如，仍然可以使用加权的图来表示现有的潜在路线，其中每个节点还包含有限状态自动机，其根据时间值向路线添加权重偏差（所以通过在5:25处交叉节点你会得到一个不同的价值，如果你的模拟在7点穿过它）。
但是，我认为在这一点上，你会发现自己的模拟越来越复杂，当build议被转移到现实世界中时，最可能不提供最佳路线的“极好”近似。 事实certificate，在遇到现实世界的混沌行为和dynamic时，软件和mathbuild模和模拟充其量只是一个薄弱的工具。
我的build议是去使用另一种策略。 我会尝试使用遗传algorithm，其中一个人的DNA计算一个潜在的路线，然后我会创build一个适应性函数，编码成本和权重在一个更容易维护查找表时尚。 然后，我会让遗传algorithm试图在公共交通路线search器的近乎最优的解决scheme上收敛。 在现代计算机上，像这样的遗传algorithm可能会performance得相当好，对现实世界的活力至less应该是比较强大的。
我认为大多数做这种事情的系统采取“简单的方式”，只是做一个像A *searchalgorithm，或类似于贪婪的成本加权有向图行走的东西。 要记住的是，公共交通的使用者本身并不知道最佳路线是什么，所以90％的最佳解决scheme对于一般情况仍然是一个很好的解决scheme。
从公共交通领域需要了解的一些数据点：
- 每次换乘都会在车手心中产生10分钟的罚分（除非是定时换乘）。 也就是说，在精神上，一个单程车需要40分钟的旅程大约相当于需要转车的30分钟的旅程。
- 大多数人愿意走到一个公共汽车站的最大距离是1/4英里。 火车站/轻轨约1/2英里。
- 距离与公共交通工具无关。 （只有时间很重要）
- 频率很重要（如果连接错过了下一个总线需要多长时间）。 如果替代scheme被搁置一个小时，下一个快递公司会select更频繁的服务选项。
- 铁路比公共汽车有更高的偏好（更多的信心，火车会走向正确的方向）
- 不得不支付新的票价是一个很大的打击。 （加上大约15-20分钟的惩罚）
- 总行程时间也很重要（以上处罚）
- 连接如何无缝？ 骑手是否必须在火车站穿过繁忙的街道？ 还是只是下一class火车，步行四步到公共汽车？
- 穿越繁忙的街道 – 转让的另一个重大惩罚 – 可能会错过连接，因为不能快速穿过街道。
为汽车寻找路线非常简单：您可以存储所有道路的加权图，并且可以使用Djikstra的algorithm。 公交线路不太明显。
这可能不太明显，但现实是，这只是汽车问题的另一个维度，增加了无限的成本计算。
例如，您将时间已过的巴士标记为具有无限的成本 – 那么它们就不包含在计算中。
然后您可以决定如何衡量每个方面。
运输时间可能会加权1等待时间可能会得到加权1转移可能会加权0.5（因为我宁愿更早到达并有额外的转移）
然后，使用任何通常的成本algorithm计算图中的所有路线，并添加无限的成本：
每次沿着边缘移动时，必须跟踪“当前”时间（加上通行时间），如果到达vector，则必须为当前时间之前的任何巴士分配无限的成本。 当前时间增加了该vector的等待时间，直到下一class车离开，然后你可以自由地沿着另一个边移动并find新的成本。
换句话说，有一个新的约束，即“当前时间”，这是首次公交车起步的时间，与所有公交车的等候时间和停靠时间相加。
这只会使algorithm复杂一点点，但algorithm仍然是一样的。 你可以看到，大多数algorithm可以应用到这个，有些可能需要多次通过，有几个不会工作，因为你不能添加时间 – >无限成本计算内联。 但大多数应该工作得很好。
只要简单地假定公交车正在按照时间表进行简化，并且总是有另一辆公交车，但是会增加等待时间。 做algorithm只是增加运输成本，然后再次通过树，并增加等待成本，取决于下一class车何时到来。 它有时会导致效率较低的版本，但是即使是一个大城市的总图也是非常小的，所以这不是一个真正的问题。 在大多数情况下，一条或两条路线将是明显的赢家。
谷歌有这个function，但是还包括从一个公交车站到另一个公交站点的更多优势，所以如果你愿意走在拥有大型公共汽车系统的城市，你可能会发现一条稍微更理想的路线。
-亚当
如果及时测量每一段旅程的成本，那么唯一的复杂因素就是时间表 – 这就是将每个节点的成本改变为当前时间t的函数，其中t就是总的旅行时间。远（假设时间表从t = 0开始标准化）。
所以不是节点A的成本是10分钟，而是将f（t）的成本定义为：
- t1 = nextScheduledStop（t）; //在时间t或之后获得下一个停止时间
- baseTime = 10 //例如，10分钟的旅程
- 返回（t1-t）+ baseTime
因此，等待时间被dynamic地包括在每条腿的成本中，并且在公交车站之间的步行仅仅是具有恒定时间成本的弧
有了这个表示，你应该能够直接应用A *或Dijkstra的algorithm
我认为这个问题的方式是，最终你正在试图优化你的平均速度，从你的出发点到结束点。 特别是，如果不妨碍自己的行驶方式节省时间，则完全不关心总行程。 因此，解决scheme空间的基本部分将需要确定可用的有效路线，这些路线涵盖从起点到终点之间相对较高速度的总距离的非平凡部分。
以您的原始观点，GPS导航单元使用汽车行驶的典型汽车路线algorithm是目标最佳总时间和最佳路线评估的良好界限。 换句话说，您的巴士旅行将会非常好地接近基于汽车的解决scheme。 显然，基于公交线路的系统将比基于汽车的解决scheme具有更多的约束，但是以汽车解决scheme作为参考（时间和距离）给总线algorithm提供了针对*进行优化的框架。 所以，放松一下，你想要将汽车解决scheme以迭代的方式转向可能的公共汽车解决scheme集，或者更可能采用可能的公共汽车解决scheme，并将其与您的基于汽车的解决scheme进行比较，以确定您是否做得“好” 。
在某个特定的起飞时间内，使这个更具体些，在任何合理的时间段内可以使用的公交车数量是有限的，可以覆盖总距离的很大一部分。 基于直接的汽车分析合理的时间段和显着的距离百分比可以使用一些温和的主观指标来量化。 当然，从更绝对的意义上说，相对于另一种可能性来评分每个可能性变得更容易。
一旦在解决scheme中有一组可能的主要部分可用作为可能的答案，则需要将它们与其他可能的步行和等待path挂钩在一起……或者如果距离足够远，则recursionselect附加的短路总线运行。 直觉地说，由于约束悖论 （见下面的脚注），似乎并不是真的会有一组禁止性的select。 即使你不能从那里强制所有可能的组合，仍然应该能够使用模拟退火 （SA）型algorithm来优化。 蒙地卡罗方法将是另一种select。
我们将问题解决到这一点的方式给我们留下了一些非常类似于SAalgorithm如何应用于ASIC芯片，FPGA的自动布局和布线以及印刷电路板布局和布线的方法相当多的关于优化这种问题forms的已发表的工作 。
*注：我通常把这称为“约束悖论” – 我的名词。 虽然人们自然会想到更多的约束问题难以解决，但约束条件会减lessselect，而select更less意味着更容易暴力。 当你可以蛮横的时候，那么即使是最佳的解决scheme也是可用的。
基本上，图中的一个节点不仅应该代表一个位置，而且也是最早可以到达的位置。 你可以把它看作（地点，时间）空间中的图表探索。 另外，如果你有（place，t1）和（place，t2）其中t1 <t2，放弃（place，t2）。
从理论上讲，这将会从您的起始节点获得所有可能的目的地的最早到达时间。 在实践中，你需要一些启发式修剪道路，让你离目的地太远。
你还需要一些启发式的方法来考虑有希望的路线，而不是那些有希望的路线 – 如果一条路线远离你的目的地，则不太可能（但不是完全不可能）成功。
我认为你的问题比你期望的更复杂。 最近的COST行动着重于解决这个问题： http : //www.cost.esf.org/domains_actions/tud/Actions/TU1004 ：“智能交通系统时代的公共交通客stream模型”。
从我的angular度来看，普通的SPSalgorithm不适合这个。 你有dynamic的networking状态，在某些选项向前行驶是不死的（对于汽车，自行车，行人来说，路线总是“打开”的，而只有在特定的驻留时间才有可用的过境连接）。
我认为这里需要新的多标准（时间，可靠性，成本，舒适度和更多标准）方法。 需要实时计算1）在短时间内向terminal用户发布信息2）能够实时调整path（基于实时交通状况 – 从ITS）。
我将在接下来的几个月里考虑这个问题（甚至在整个博士论文中）。
问候拉法尔
我不认为有任何其他特殊的数据结构可以满足这些特定的需求，但是您仍然可以像链接列表一样使用正常的数据结构，然后按照给定的因子进行path计算 – 您将需要某种input应用影响结果的variables，然后根据input进行相应的计算。
至于等待和东西，这些是与一个特定节点相关的因素吗？ 您可以将此因子转换为连接到该节点的每个分支的路由节点。 例如，你可以说节点X的每个分支，如果在节点X上有一个等待的时间，那么通过[m /某个基值* 100]％来扩大分支的权重（只是一个例子）。 通过这种方式，您可以统一考虑其他因素，但同时要简单地表示您想要解决的问题。
如果我正在处理这个问题，我可能会从一个带注释的图表开始。 图上的每个节点代表城市中的每个路口，无论公交系统是否停在那里 – 这有助于说明走路的需要等。在与路口服务的交叉点上，用停车标签来标注这些标签 – 标签允许你要查找停止的服务时间表。
那么你有select。 你需要最好的路线，还是只需要一条路线？ 您是实时显示路线，还是可以计算和caching解决scheme？
如果你需要“实时”计算，你可能会想用一个贪婪的algorithm，我认为一个A *algorithm可能会很好地适应这个问题的领域。
如果你需要最佳的解决scheme，你应该看图dynamic编程解决scheme…最佳的解决scheme可能需要更长的时间来计算，但你只需要find他们一次，然后他们可以被caching。 也许你的A *algorithm可以使用预先计算的最佳path来通知其有关“相似”路由的决定。
可能工作的可怕的低效率的方法是每天在城市存储每个路口的副本。 从Elm St.和2nd到Main St.和25th的公共汽车路线将被表示为，例如，
elm_st_and_2nd[12][30].edges : elm_st_and_1st[12][35] # 5 minute walk to the next intersection time = 5 minutes transport = foot main_st_and_25th[1][15] # 40 minute bus ride time = 40 minutes transport = bus elm_st_and_1st[12][36] # stay in one place for one minute time = 1 minute transport = stand still 在这个图表上运行你最喜欢的寻路algorithm，并祈求一个好的虚拟内存实现。
你自己正在回答这个问题。 使用A *或Dijkstra的algorithm，您所需要做的就是决定每条路线的每个部分的成本。
对于巴士路线，你意味着你不想要最短，但最快的路线。 因此，路线的每个部分的成本必须包括该部分中的公共汽车的平均行驶速度以及在公共汽车站的任何等待。
find最合适的路线的algorithm仍然和以前一样。 与A *，所有的魔术发生在成本函数…
你需要不同的重量腿。 例如 – 在一个下雨天，我认为有人可能更喜欢在车里旅行比在雨中行走更长。 另外，厌恶步行或不能走路的人可能会比不介意走路的人做出不同的/更长的行程。
这些边缘是成本，但我认为你可以扩大成本的概念/概念，并且可以有不同的相对价值。
algorithm保持不变，只需根据不同的场景（总线时间表等）增加每个graphics边缘的权重。
前段时间我把一个地铁路线查找器作为一个graphicspath查找的练习：
