物流和运输计划技术

Question

实际上，我正在开发一个汽车票预订系统。提供商有许多路线和不同的行程。我已经建立了一个相当全面的数据库，将所有这些都映射在一起，但当我涉及到跨路线预订时，我遇到了让路径算法工作的问题。

例如，用户想要从蒙特利尔到舍布鲁克，他将只走我们在这里称为路由#47的路线。但如果他去萨顿而不是舍布鲁克，他现在必须在某个时候转乘53号路线。

现在，检测一个且只有一个传输并不太难。但当我发现他可以做什么来跨越多条路线时，我有点害怕。我已经设计了一种可爱且相对有效的方法，仅使用SQL就可以在1-3跳内完成此操作，但我想知道如何在更广泛的范围内组织这一切，因为客户端可能不会在余生中停留在2条路由上。

到目前为止我想到的例子：

StartingStop
joins to Route
joins to StopsOfTheRoute
joins to TransfersOnThatStop
joins to TargetStopOfThatTransfer
joins to RouteOfThatStop
joins to StopsOfThatNewRoute
[wash rince repeat for more hops]
where StopsOFThatNewRoute = EndingStop

问题是，如果我有3个以上的跃点，我肯定我的SQL服务器在压力下会很快卡住，即使我正确地索引了我的数据库，我也可以很容易地预测最终会出现重大故障……

谢谢

Answer 1

我对你的问题的理解是:你正在寻找一种算法，可以帮助你确定一条合适的路径(覆盖一条或多条路由的路段)。

正如Jason正确指出的那样，这是一个寻路问题。对于这类问题，您可能应该先看看维基百科的article on pathfinding，然后深入研究Djikstra's algorithm的细节。这可能会让您开始使用它。

但是，您很可能很快就会意识到，从结构和性能的角度来看，您的数据模型可能会带来问题。典型的例子是如果你需要管理时间限制:假设你找到了几条路径，哪条路径的旅行时间最短？一条路径可能是最短的，但每天只提供一次乘车，而另一条路径可能更长，但每天提供几次乘车。

一种可能的处理方法是创建一个图，其中每个节点对应于特定时间的特定停靠点。一条边将在房间时间内从这个停靠点连接到其他两个地理停靠点，以及下一个时间点的自身。

我的建议是从阅读寻路算法开始，然后重新检查您的数据模型，了解您可能遇到的任何约束。然后，重点介绍用于存储数据的结构和用于搜索路径的结构。

建议(效率不高，但如果有足够的RAM可以使用)。使用关系数据库服务器存储基本信息:停靠点，哪些路线连接到哪些停靠点，等等。看起来你已经讲过了。然后，在给定约束的情况下，构建图的内存表示。您可能会很快地为此构建自己的库(我不知道有任何这样的PHP库)。

另一种选择是使用图形数据库，如Neo4j及其REST接口。我猜这需要对你的应用程序进行一些重大的重新设计。

希望这篇文章能给你一些有用的建议。