logo标签列表

不使用stop_sequence如何确定正确的GTFS站点顺序？

google-maps-api-3google-apigtfs
3
我正在使用GTFS数据源开发一个应用程序。我正在尝试列出所选路线的所有站点。目前，我正尝试按照停靠顺序对列表进行排序，但由于某些行程不会经过每个站点，我收到的数据每个行程每个站点递增1，因此这种方法不能很好地工作。这意味着停靠顺序没有考虑到其他可能有更多或更少站点的行程。

以下是一个例子：

这是一条路线的站点顺序（忽略不是每个行程都停靠在每个站点）

Stop A
Stop B
Stop C
Stop D
Stop E

现在这里有一些路线的示例旅行：
Trip 1: A, B, C, D
Trip 2: A, B, E

我的数据在做什么：
对于旅行1：
Stop A: stop_sequence = 1
Stop B: stop_sequence = 2
Stop C: stop_sequence = 3
Stop D: stop_sequence = 4

对于旅行2：
Stop A: stop_sequence = 1
Stop B: stop_sequence = 2
Stop E: stop_sequence = 3

所以，当我尝试对路线的所有潜在停靠点进行排序时，最终得到了这个结果：
Stop A
Stop B
Stop C
Stop E
Stop D

"明显是不正确的。有没有人知道其他可能的想法来正确地排序站点，也许使用与GTFS Feed一起提供的其他数据？
更新了一个真实世界的例子：
这是一个数据库查询的示例输出，获取915路线的所有站点。 这是早上的时间表。"
+---------+---------+---------------+------------------------------------------------+
| stop_id | trip_id | stop_sequence | stop_name                                      |
+---------+---------+---------------+------------------------------------------------+
| 11771   | 1269287 |             1 | LOTTE PLAZA US 40 & US 29                      |
| 11772   | 1269280 |             1 | HARPER'S FARM RD & CEDAR LA eb                 |
| 11773   | 1269280 |             2 | LITTLE PATUXENT & GRAY STAR wb                 |
| 11774   | 1269280 |             3 | LITTLE PATUXENT & WHITE CORD WAY wb            |
| 11775   | 1269280 |             4 | LITTLE PATUXENT & BRIGHT PASSAGE eb            |
| 11776   | 1269280 |             5 | LITTLE PATUXENT & HICKORY RID nb               |
| 11777   | 1269280 |             6 | LITTLE PATUXENT & CEDAR LA eb                  |
| 11778   | 1269280 |             7 | LITTLE PATUXENT & HARPER'S FARM opp eb         |
| 11779   | 1269280 |             8 | COLUMBIA MALL & SOUTH RING RD eb               |
| 11782   | 1269280 |             9 | BROKEN LAND & HICKORY RIDGE sb                 |
| 11780   | 1269289 |             9 | LITTLE PATUXENT & GOV WARFIELD nb              |
| 11783   | 1269280 |            10 | BROKEN LAND PARK & RIDE                        |
| 11781   | 1269289 |            10 | LITTLE PATUXENT & VANTAGE PT nb                |
| 11784   | 1269280 |            11 | SCAGGSVILLE PARK & RIDE                        |
| 11785   | 1269280 |            12 | BURTONSVILLE PARK & RIDE                       |
| 11786   | 1269280 |            13 | COLESVILLE RD  & FENTON ST sb                  |
| 11787   | 1269280 |            14 | SILVER SPRING METRO STATION                    |
| 11788   | 1269280 |            15 | WALTER REED HOSP & 16TH ST NW                  |
| 11789   | 1269280 |            16 | 16TH ST & P ST NW                              |
| 11790   | 1269280 |            17 | 16TH ST & M ST NW                              |
| 11718   | 1269280 |            18 | K ST & 16TH ST NW fs eb                        |
| 11719   | 1269280 |            19 | K ST & 14TH ST NW eb                           |
| 11791   | 1269280 |            20 | 13TH ST & H ST NW sb                           |
| 11759   | 1269280 |            21 | PENNSYLVANIA AVE & 12TH ST NW eb               |
| 11793   | 1269280 |            22 | CONSTITUTION AVE & 10TH ST NW fs eb            |
| 12046   | 1269280 |            23 | 7TH ST NW & CONSTITUTION AVE eb                |
| 11650   | 1269280 |            24 | INDEPENDENCE AVE & 7/6 ST SW mid eb            |
| 11601   | 1269280 |            25 | INDEPENDENCE AVE & 4TH/3RD ST SW eb            |
| 13627   | 1269280 |            26 | M ST & 1st ST SE (NAVY YARD) sb                |
| 13628   | 1269280 |            27 | M ST & 4th ST SE (SOUTHEAST FEDERAL CENTER) eb |
| 11569   | 1269280 |            28 | M ST & ISAAC HALL AVE SE eb                    |
| 11795   | 1269280 |            29 | M ST & 8/9TH STS mid eb                        |
+---------+---------+---------------+------------------------------------------------+

这是链接到许多通勤者目前正在使用的时间表的PDF文件。两个列表第一次不同的地方是在“COLUMBIA MALL＆SOUTH RING RD eb”之后。

http://mta.maryland.gov/sites/default/files/915May2011B.pdf

我正在尽可能使这个应用程序适合通勤，但是当车站的顺序与通勤者通常使用的不一致时，可能会导致很多困惑。
更新2： 我仍然看不到拓扑排序如何用于获取正确的顺序。是的，它可能给出一个有效的序列，但不能保证是通勤者容易识别的正确序列。让我们再看看我提供的pdf文件中的另一个例子。我们将查看旅程1和5，一直到“哥伦比亚购物中心”站。我会创建以下边缘：
Cedar Lane --> Gray Star Way
Gray Star Way --> White Cord Way
...
Harpers Farm Rd --> Columbia Mall

从第五次旅行中创建的边缘。
Lotte Plaza --> Columbia Mall

拓扑排序保证的唯一一件事情是：

对于每一条从顶点 u 指向顶点 v 的有向边 uv，在排序中 u 出现在 v 之前。

这意味着存在多个有效的排序方式，但只有一个是我想要的实际正确的排序方式（至少在我能想到的情况下，没有办法以编程方式选择这个正确的排序方式而不是其他有效的排序方式）。

一个有效的排序方式可能是（这也是正确的排序方式）：

Lotte Plaza,
Cedar Lane
Gray Star
...
Columbia Mall

甚至
Cedar Lane
Gray Star
...
Lotte Plaza
Columbia Mall

如您所见，根据拓扑排序，这两个序列都是有效的，但只有其中一个是我想要的。我无法想到一种方法来根据GTFS数据提供的信息一致地选择正确的序列。
如果我看错了，请告诉我。
也许这个图表可以帮助你：https://docs.google.com/file/d/0B2T8yNIP0VUQeG1fUVY2X25jcGs/edit我同意，Lotte Plaza站点相对于Harper's Farm变体的排序确实有些棘手。我已经更新了下面的答案，以自然的方式描述如何处理分叉、分支和其他变体。一定要查看OBA代码，因为它已经处理了这种情况。 - Brian Ferris
非常感谢你的帮助。在再次打扰你之前，我会仔细研究OBA代码，并尽力自己解决这个问题！谢谢！ - btse
1
@btse 天哪，NASA！恭喜！不管怎样，我最后的办法（以防有人看到这个）是列出每条路线的每次行程，并收集结果。到目前为止，效果非常好，尽管运行一个700Mb的GTFS数据库需要几分钟的时间。 - Julian
我已经苦苦挣扎了6天，写了大约6个算法，但是没有一个能够适用于所有当前的GTFS文件。 我首先进行了硬性分组（方向/站点/站点数量），然后尝试将每种“路线”类型合并为一个单一的路线，通过使用角度、距离和模式匹配... 但是总有一个GTFS文件中存在例外情况，其结构是任意的。 主要问题在于一条路线可以在相反的方向上多次使用同一个站点... 在现实生活中，你不能这样做，你怎么知道该乘哪辆公交车才能朝着正确的方向前进呢？ - Eric Liu
在相同线路上使用相同站点和相同行车标志，就像套索般的行程...有趣的是当你在其中有分支时。 - Eric Liu
显示剩余4条评论
3个回答
3
您可以构建一个有向图(DAG)，其中每个路线的停靠点是一个节点，每个行程中两个停靠点之间的转换是一条边。然后，您可以执行该图的拓扑排序(http://en.wikipedia.org/wiki/Topological_sorting)以获取停靠点的顺序。请注意，拓扑排序仅适用于没有循环的图，但是有些行程确实有循环，因此如果添加了一条边会形成循环，则不要添加该边。
这恰好是OneBusAway应用程序套件用于对停靠点进行排序的算法： https://github.com/OneBusAway/onebusaway-application-modules/blob/master/onebusaway-transit-data-federation/src/main/java/org/onebusaway/transit_data_federation/impl/beans/RouteBeanServiceImpl.java#L281 请注意，有时路线将分叉或分支，其中有两组停靠点(每个分支一个)，彼此不相互作用。天真的拓扑排序可能会任意交错这些停靠点，但OBA代码使用以下两个启发式方法来获得更自然的排序：
1)将同一分支中的停靠点分组在一起。
2)在相对于彼此排序两个分支时，先放距离分支点更近的分支。
我会尝试这个，并告诉你进展如何。当创建GTFS数据源的人可以更加智能地使用stop_sequence字段时，所有这些额外的工作真是太麻烦了。 - btse
我不太确定这个方法是否有效，因为只有在同一次行程中的每个站点之间才存在数据转换。因此，我无法正确地在不同行程的站点之间绘制边缘。回到我的例子，我无法确定C站实际上应该在E站之前（至少我找不出来）。 - btse
为什么在停止C之前应该停止E（忽略英文字母顺序）？也许你的路线在最后分为两个分支，一半的公交车去C-D，另一半去E。在这种情况下，是否真的存在一个“正确”的站点顺序？ - Brian Ferris
哈哈，抱歉布莱恩！我在Google群组上的帖子中并不是有意不尊重。由于无法在评论中适当回复，我将在原帖中更新另一个示例。 - btse
0

对于任何遇到这个问题的人，这是我几年前解决问题的方法。

没有一个正确的顺序 - 这里的目标是产生一个“视觉上最佳”的顺序（在大多数情况下）。而不是看个别的站点 - 我将站点分组成逻辑部分，然后以类似拓扑排序的方式合并这些部分。

然后，您可以为不相关的部分添加额外的规则/权重，以确定哪个部分应优先于另一个部分。例如 ABC ---> CDE 或 GHI

https://github.com/mhkey/supersequence

0

构建和排序一张有向无环图（DAG）的站点序列相对简单。基本上，我们将每个行程的站点序列合并成一个整体的站点序列。

唯一令人烦恼的部分是您需要提前处理所有行程，以确保所有站点都得到覆盖。因此，这可能需要一些时间，具体取决于系统中有多少行程。

首先，我们需要一些用于排序DAG的代码。请记住以下JavaScript代码尚未经过广泛测试。

/**
 * This function sorts a directed acyclic graph (DAG) using depth-first search (DFS).
 * 
 * @example
 * 
 * const edges = [
 *   ["a", "b"],
 *   ["a", "c"],
 *   ["a", "e"],
 *   ["b", "d"],
 *   ["c", "d"],
 *   ["d", "e"],
 * ];
 * 
 * const order = sort_dag_dfs(edges); // ["a", "c", "b", "d", "e"]
 */
export const sort_dag_dfs = (edges) => {
    const nodes = new Set();
    const edges_map = new Map();

    for (const [from, to] of edges) {
        nodes.add(from);
        nodes.add(to);

        if (!edges_map.has(from)) {
            edges_map.set(from, new Set());
        }

        edges_map.get(from).add(to);
    }

    const visited = new Set();
    const stack = [];

    const dfs = (node) => {
        if (visited.has(node)) {
            return;
        }

        visited.add(node);

        if (edges_map.has(node)) {
            for (const to of edges_map.get(node)) {
                dfs(to);
            }
        }

        stack.push(node);
    };

    for (const node of nodes) {
        dfs(node);
    }

    return stack.reverse();
};

现在我们需要迭代一个路线上的所有行程。对于每个行程，我们为每一对连续的站点添加一个“边”，这实际上是一个约束条件，要求一个站点必须在另一个站点之后。这些约束条件被组合起来得到最终的序列。
以下是一些伪代码：
const edges = new Set();

for (const trip of trips) {
    const stops = [];

    for (const stop_idx of trip.sorted_stop_indices) {
        stops.push(trip.stop_ids.get(stop_idx));
    }

    for (let i = 1; i < stops.length; i++) {
        edges.add(`${stops[i - 1]}---${stops[i]}`);
    }
}

const sorted_stop_ids = sort_dag_dfs(Array.from(edges).map((edge) => edge.split("---")));

请注意，可能存在多个正确的排序方式，并且根据停靠点的GPS坐标进一步提升排序顺序可能是值得的。如果有两个潜在的停靠点可以接下来（例如，存在一个分支），则选择距离上一个停靠点更近的停靠点可能是值得的。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接