GRASS GIS / Síťové analýzy / v.net.timetable

Nejkratší cesty s užitím časových plánů

v.net.timetable nachází nejkratší cestu mezi dvěma body s užitím časových harmonogramů (např. jízdních řádů). v.net.timetable čte vstup po řádkách jko jednotlivé dotazy ze standardního vstupu a vypisuje výstup do standardního výstupu a současně do výstupní mapy a do tabulek připojených k vrstvám 1 a 2. Každá řádka vstupu musí být v jednom z následujících formátů:

PATH_ID FROM_X FROM_Y TO_X TO_Y START_TIME MIN_CHANGE MAX_CHANGES WALK_CHANGE

PATH_ID FROM_STOP TO_STOP START_TIME MIN_CHANGE MAX_CHANGES WALK_CHANGE

kde PATH_ID je identifikátor dotazu, který je užit ve výstupní mapě. Hledání začíná v čase START_TIME. MIN_CHANGE udává minimální čas (hodnota včetně) pro přestup z jedné trasy na jinou. MAX_CHANGES udává maximální povolený počet přestupů nebo -1 pro nekonečno. WALK_CHANGE je 1 nebo 0, podle toho, je-li chůze z jedné zastávky na druhou považována za přestup. Konečně, cesta je nalezena z FROM_STOP do TO_STOP v pozdějším případě a ze zastávky nejblíže souřadnic (FROM_X, FROM_Y) do zastávky nejblíže souřadnic (TO_X, TO_Y) v případě prvním. Pro každý vstupní dotaz modul vyprodukuje popis nejkratší cesty do standardního výstupu. Například, s užitím následujících jízdních řádů, pro následující vstup:

47 130 300 0 1 5 0

Následující výstup je tento:

Route 15, from 130 leaving at 15 arriving to 250 at 22

Walk from 250 leaving at 22 arriving to 300 at 24

Modul navíc vypíše cestu do výstupní mapy a uloží veškeré informace potřebné pro rekonstrukci cesty do jízdních řádů. Tabulka odpovídající zastávkám/bodům je připojena k vrstvě 1 a vypadá takto:

cat|path_id|stop_id|index|arr_time|dep_time

1|47|130|1|0|15

2|47|250|2|22|22

3|47|300|3|24|24

kde CAT je kategorie bodu v mapě, PATH_ID je identifikátor cesty, STOP_ID je identifikátor zastávky stejný jako ve vstupní mapě, INDEX je index zastávky na cestě (např. index=1 je první navštívená zastávka, ...) a ARR_TIME a DEP_TIME časy příjezdu a odjezdu. Čas příjezdu pro první zastávku na cestě je vždy stejný jako START_TIME a čas odjezdu z poslední zastávky je roven času příjezdu. Tabulka připojená ke druhé vrstvě odpovídá "podcestám" projetým mezi zastávkami. Z výše uvedeného dotazu vzejde taková tabulka:

cat|path_id|from_id|to_id|route_id|index|from_time|to_time

1|47|130|250|15|1|15|22

2|47|250|300|-1|2|22|24

kde CAT je kategorie linií "podcesty" mezi zastávkami FROM_ID a TO_ID, ROUTE_ID je identifikátor zvolené trasy nebo -1 pro chůzi, INDEX a PATH_ID jsou jako výše a FROM_TIME a TO_TIME udávají časy mezi nimiž je trasa uskutečněna. Výstupní mapa obsahuje body na pozicích využitých zastávek. Je-li mezi dvěma zastávkami vykonána "podcesta", je mezi dva odpovídající body přidán liniový segment. Konečně, namísto přímého liniového segmentu, lze do vrstvy cest zadat přímo cesty (topologicky) tras. S použitím tohoto parametru každá linie vstupní mapy musí obsahovat identifikátory jako čísla kategorií všech tras vedoucích danou linií. Modul následně nalezne cestu mezi dvěma zastávkami a zapíše tuto cestu (topologicky, ne trasu). V případě chůze z jedné zastávky na jinou je mezi těmito zastávkami užita přímá linie.

POZNÁMKY

Tabulky časových hrmonogramů jsou ukládány do tabulky připojené k dané vrstvě vstupní mapy. Tabulka obsahuje trasy, přičemž každá trasa je posloupností zastávek s danými časy příjezdu. Liší-li se dvě posloupnosti zastávek pouze v časech, stále odpovídají dvěma různým trasám. Npříklad, pokud jedna autobusová linka má 20-ti minutový interval a projíždí pokaždé totožnou cestu, stále je nutné udržovat unikátní trasu pro každý čas. Pro každou zastávku (danou číslem kategorie bodu) musí tabulka udržující informace o trasách obsahovat seznam všech tras procházejících touto zastávkou (daných identifikátory tras) společně s časy příjezdu. Tabulka tedy musí obsahovat 3 sloupce: stop (zastávka) - která je klíč tabulky, route_id a stop_time, kde každá trojice odpovídá trase přijíždějící do zastávky v určitý čas. Například by platná tabulka mohla vypadat takto:

cat|route_id|stop_time

100|5|0

130|5|10

150|5|20

250|5|30

300|5|40

260|15|5

130|15|15

250|15|22

150|35|17

250|35|27

300|35|37

100|35|50

Note that stop_time is an integer and so you can use any units and offest to specify arrival times. Also, walking connections between stops can be given by a table linked to walking layer of the input map. If this parameter is -1 then walking between stops is not allowed. The table must contain three columns: stop - which is the key of the table, to_stop and length. A record in the table says that it takes length units of time to walk from stop to to_stop. The following is a valid table:

cat|length|to_stop

250|2|300

Beware that this only means that it is possible to walk from stop 250 to stop 300 but not the other way round.