google-maps-api-3 - 在不使用 stop_sequence 的情况下确定正确的 GTFS 停止顺序？

Question

我正在为我正在开发的应用程序使用 GTFS 提要。我正在尝试列出所选路线的所有停靠点。目前，我正在尝试通过 stop_sequence 对列表进行排序，但是这无法正常工作，因为某些行程不会到达每个站点，并且我收到的数据将 stop_sequence 增加 1，每次行程每次停止。这样做的意义在于 stop_sequence 不考虑可能有更多或更少停靠点的其他行程。

下面是一个例子:

这是路线的停靠点顺序，(忽略并非每次旅行都会在每个停靠点停靠的事实)

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 的所有停靠点的数据库查询的示例输出。
这是针对 AM 计划的。

+---------+---------+---------------+------------------------------------------------+
| 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，直到“哥伦比亚购物中心”站。我会创建以下边缘:

从行程 1 创建的边

Cedar Lane --> Gray Star Way
Gray Star Way --> White Cord Way
...
Harpers Farm Rd --> Columbia Mall

从 Trip 5 创建的边

Lotte Plaza --> Columbia Mall

拓扑排序唯一确保的是

for every directed edge uv from vertex u to vertex v, u comes before v in the ordering

这意味着有多个有效排序，但只有一个是我想要的实际正确排序(但我无法通过编程方式选择这个而不是其他有效排序，至少不是我能想到的)。

有效的排序可能是(这也是正确的排序):

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

甚至

Cedar Lane
Gray Star
...
Lotte Plaza
Columbia Mall

如您所见，根据拓扑排序，这两个都是有效的，但只有其中一个是我想要的。我想不出一种方法可以根据 GTFS 提要提供的数据始终选择正确的序列。

如果我看错了，请告诉我。

Answer 1

您可以构建一个有向图 (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

请注意，有时路线会有 fork 或分支，其中有两组不相互交互的停靠点(每个分支一个)。朴素的拓扑排序可能会任意交错这些停靠点，但 OBA 代码使用以下两种启发式方法来获得更自然的排序:

1) 组站一起在同一个分支。

2) 两个分支相对排序时，先把分支放在离分支点较近的位置。