Определить правильный порядок остановки GTFS без использования stop_sequence?

Я использую канал GTFS для приложения, над которым я работаю. Я пытаюсь перечислить все остановки для выбранного маршрута. В настоящее время я пытаюсь заказать список stop_sequence, но это не работает должным образом, так как некоторые поездки не идут на каждую остановку, и полученные мной данные увеличивают значение stop_sequence на 1 за каждую остановку в поездке. Значимость этого заключается в том, что stop_sequence не учитывает другие поездки, которые могут иметь более или менее остановки.Определить правильный порядок остановки GTFS без использования stop_sequence?

Вот пример:

Это порядок остановок для маршрута, (игнорируя тот факт, что не каждая поездка остановится на каждой остановке)

Stop A 
Stop B 
Stop C 
Stop D 
Stop E

Теперь здесь некоторые примеры поездок для маршрута:

Trip 1: A, B, C, D 
Trip 2: A, B, E

Что мои данные делают:

для Trip 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?

ОБНОВЛЕНО с реального мира, например

Вот пример вывода запроса к базе данных, которая получает все остановки для маршрута 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 & ЮЖНОЙ RING RD ЕВ»

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

Я пытаюсь сделать это приложение пригородным дружественным, как это возможно, но при остановке вышла из строя по сравнению с тем, что обычно используют пассажиры, это может вызвать много путаницы.

UPDATE 2:

Я до сих пор не понимаю, как топологическая сортировка может быть использован, чтобы получить правильную последовательность. Да, это может привести к последовательности , но не гарантируется правильная последовательность, которую легко узнает пригородный. Давайте посмотрим на другой пример, используя предоставленный мной pdf-файл. Мы посмотрим на поездки 1 и 5 и до остановки «Columbia Mall».Я хотел бы создать следующие ребра:

Ребра, созданные из Trip 1

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

Лезвия, созданные из Trip 5

Lotte Plaza --> Columbia Mall

Единственное, что топологическая сортировка обеспечивает является

для каждый направленный край уф от вершины и в вершину V, U предшествует V в заказе

Это означает, что существует множество действительных упорядоченности, но только один является фактическим правильно один, что я хочу (но у меня нет способа прогромтически выбирать это по другим действительным порядкам, по крайней мере, не так, как я могу думать).

Допустимое упорядочение может быть (это тоже правильный):

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

или даже

Cedar Lane 
Gray Star 
... 
Lotte Plaza 
Columbia Mall

Как вы можете видеть, в соответствии с топологической сортировки, оба они являются действительными , но только один из них - тот, который я хочу. Я не могу придумать способ последовательно выбирать правильную последовательность, основанную на данных, предоставленных каналом GTFS.

Пожалуйста, дайте мне знать, если я рассматриваю это неправильно.

источник

2013-07-05 btse

Помните, что stop_sequence может использоваться только для того, чтобы заказывать стопы, принадлежащие одному и тому же маршруту (aka rows with the same trip_id в stop_times.txt). Как я упоминал ниже, чтобы создать более общий порядок остановок в разных поездках (ака разных последовательностей остановок), вам нужно будет использовать метод, описанный ниже. –

Я добавил еще одно обновление: почему я не могу себе представить, как топологический сорт достигнет того, что я хочу. – btse

Возможно, эта диаграмма поможет: https://docs.google.com/file/d/0B2T8yNIP0VUQeG1fUVY2X25jcGs/edit Я согласен с тем, что остановка Lotte Plaza сложна, так как она упорядочивает ее относительно вариации Фермы Харпера. Я обновил свой ответ ниже, чтобы описать, как естественным образом вилки, ветви и другие варианты. Определенно взгляните на код OBA, поскольку он уже обрабатывает этот случай. –

Вы можете построить ориентированный граф (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) При заказе двух ветвей относительно друг друга сначала поместите ветку ближе к точке ветвления.

источник

2013-07-06 07:22:44

Я попробую это и дам вам знать, как это происходит. Это такая боль, что вся эта дополнительная работа требуется, когда люди, создающие канал GTFS, могли бы использовать поле stop_sequence более разумно. – btse

Я не уверен, что это сработает, поскольку на каждом переходе от остановки останавливаются только данные из одного и того же маршрута. Поэтому для меня нет возможности правильно рисовать края между остановками из разных поездок. Чтобы связать это с моим примером, мне не удастся определить, что 'Stop C' должен наступить до' Stop E' (по крайней мере, это не так, как я могу понять). – btse

И почему именно нужно остановить C до остановки E (английский алфавит в сторону)? Возможно, у вашего маршрута есть ветка в конце, с половиной автобусов, идущих на C-D, а другая половина - на E. В такой ситуации действительно есть «правильный» порядок остановок? –

Определить правильный порядок остановки GTFS без использования stop_sequence?

ответ

Смежные вопросы