1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
<h2>DESCRIPTION</h2>
<em>v.net.timetable</em> finds the shortest path between two points
using timetables. <em>v.net.timetable</em> reads input, one query per line,
from the standard input and writes output to the standard output as well as
to the <b>output</b> map and to tables linked to layers 1 and 2.
Each line of input must follow one of the following formats:
<div class="code"><pre>
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
</pre></div>
where PATH_ID is the identificator of a query that is used in the
output map to differentiate between queries. Search begins at
START_TIME. MIN_CHANGE gives the minimum number of time
(inclusively) for a change from one route to another. MAX_CHANGES
denotes the maximum number of changes allowed or -1 if infinity.
WALK_CHANGE is 1 or 0 depending whether walking from a stop to
another stop is considered a change or not. Finally, the path is
found from FROM_STOP to TO_STOP in latter case and from the stop
closest to (FROM_X, FROM_Y) coordinates to the stop closest to
(TO_X, TO_Y) coordinates in former case.
<br>
For each input query, module outputs a description of the shortest
path to the standard output. For example, using the tables given
below, for the following input:
<div class="code"><pre>
47 130 300 0 1 5 0
</pre></div>
the following output is produced:
<div class="code"><pre>
Route 15, from 130 leaving at 15 arriving to 250 at 22
Walk from 250 leaving at 22 arriving to 300 at 24
</pre></div>
Moreover, the module writes the path to the <b>output</b> map and
stores all the information necessary to reconstruct the path to the
tables. Table corresponding to stops/points is linked to layer 1 and
looks, after the query, as follows:
<div class="code"><pre>
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
</pre></div>
where CAT is the category of a point in the map, PATH_ID is the path
identificator, STOP_ID is the identificator of the stop as used in
the input map, INDEX is the index of the stop on the path (i.e,
index=1 is the first stop visited, ...) and ARR_TIME and DEP_TIME
denote the arrival time and departure time respectively. Arrival
time for the first stop on the path is always equal to START_TIME
and departure time for the last stop is always equal to the arrival
time.
<br>
The table linked to the second layer corresponds to subroutes taken
between stops. The following table is obtainedd for the above query:
<div class="code"><pre>
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
</pre></div>
where CAT is the category of lines of subroute between stops FROM_ID
to TO_ID, ROUTE_ID is the identificator of the route taken or -1 if
walking, INDEX and PATH_ID are as above and FROM_TIME and TO_TIME
denote the times between which the route is taken.
<br>
The <b>output</b> map contains the points on the positions of used
stops. If a subroute is taken between two stops then a line segment
is added between two corresponding points. Finally, instead of
straight line segment, the actual paths of routes can be given in <b>
paths</b> layer. If this parameter is used then each line in the
input map must contain identificators as category numbers of all
routes passing through the line. The module then finds the path
between two stops and writes this path instead. In case of walking
from one stop to another, straight line between the stops is used.
<h2>NOTES</h2>
Timetables are stored in a table linked to the given <b>layer</b> of
the <b>input</b> map. Timetable consists of routes and each route is
just a sequence of stops with specified arrival times. If two
sequences of stops differ only in times then they still correspond
to two routes. For example, if there is a bus line that leaves every
20 minutes and follow exactly the same path every time then there
still needs to be a separate route for every time. For each stop
(given by the category number of the point) the table storing
information about the routes must contain the list of all routes
stopping at the stop(given by route identificators) together with
arrival times. That is, the table must contain three columns: stop -
which is the key of the table, <b>route_id</b> and <b>stop_time</b>
where each triple corresponds to a route arriving to a stop and a
certain time. For example, a valid table might look as
follows:
<div class="code"><pre>
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
</pre></div>
Note that <b>stop_time</b> is an integer and so you can use any
units and offset to specify arrival times.<br> Also, walking
connections between stops can be given by a table linked to <b>
walking</b> layer of the <b>input</b> 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, <b>to_stop</b>
and <b>length</b>. A record in the table says that it takes <b>length
</b> units of time to walk from stop to <b>to_stop</b>. The
following is a valid table:
<div class="code"><pre>
cat|length|to_stop
250|2|300
</pre></div>
Beware that this only means that it is possible to walk from stop
250 to stop 300 but not the other way round.
<h2>EXAMPLES</h2>
To find a path from stop with identificator 130 to stop with
category 300, starting at time 0, with one time unit for change,
maximum of 5 changes and with walking not considered a change of
route, we use the following command:
<div class="code"><pre>
echo "47 130 300 0 1 5 0" | v.net.timetable \
input=buses output=path layer=5 walking=6 path=7
</pre></div>
If, on the other hand, we know the coordinates of the places then the
following command might be used:
<div class="code"><pre>
echo "47 10.31 54.31 90.21 28.21 0 1 5 0" | v.net.timetable \
input=buses output=path layer=5 walking=6 path=7
</pre></div>
<h2>SEE ALSO</h2>
<em>
<a href="v.net.html">v.net</a>,
<a href="v.net.path.html">v.net.path</a>,
<a href="v.net.distance.html">v.net.distance</a>
</em>
<h2>AUTHORS</h2>
Daniel Bundala, Google Summer of Code 2009, Student<br>
Wolf Bergenheim, Mentor
|
