1v.net.salesman(1) GRASS GIS User's Manual v.net.salesman(1)
2
6 v.net.salesman - Creates a cycle connecting given nodes (Traveling
7 salesman problem).
8 Note that TSP is NP-hard, heuristic algorithm is used by this module
9 and created cycle may be sub optimal
10
12 vector, network, salesman
13
15 v.net.salesman
16 v.net.salesman --help
17 v.net.salesman [-tg] input=name output=name center_cats=range
18 arc_layer=string arc_type=string[,string,...] node_layer=string
19 [arc_column=string] [arc_backward_column=string]
20 [turn_layer=string] [turn_cat_layer=string] [sequence=name]
21 [--overwrite] [--help] [--verbose] [--quiet] [--ui]
22 Flags:
24 -t
25 Use turntable
26 -g
28 Use geodesic calculation for longitude-latitude locations
29 --overwrite
31 Allow output files to overwrite existing files
32 --help
34 Print usage summary
35 --verbose
37 Verbose module output
38 --quiet
40 Quiet module output
41 --ui
43 Force launching GUI dialog
44 Parameters:
46 input=name [required]
47 Name of input vector map
48 Or data source for direct OGR access
49 output=name [required]
51 Name for output vector map
52 center_cats=range [required]
54 Category values
55 Categories of points (’cities’) on nodes (layer is specified by
56 nlayer)
57 arc_layer=string [required]
59 Arc layer
60 Vector features can have category values in different layers. This
61 number determines which layer to use. When used with direct OGR ac‐
62 cess this is the layer name.
63 Default: 1
64 arc_type=string[,string,...]Â [required]
66 Arc type
67 Input feature type
68 Options: line, boundary
69 Default: line,boundary
70 node_layer=string [required]
72 Node layer (used for cities)
73 Vector features can have category values in different layers. This
74 number determines which layer to use. When used with direct OGR ac‐
75 cess this is the layer name.
76 Default: 2
77 arc_column=string
79 Arc forward/both direction(s) cost column (number)
80 arc_backward_column=string
82 EXPERIMENTAL: Arc backward direction cost column (number)
83 turn_layer=string
85 Layer with turntable
86 Relevant only with -t flag
87 Default: 3
88 turn_cat_layer=string
90 Layer with unique categories used in turntable
91 Relevant only with -t flag
92 Default: 4
93 sequence=name
95 Name for output file holding node sequence ("-" for stdout)
96
98 v.net.salesman calculates the optimal route to visit nodes on a vector
99 network.
100 Costs may be either line lengths, or attributes saved in a database ta‐
102 ble. These attribute values are taken as costs of whole segments, not
103 as costs to traverse a length unit (e.g. meter) of the segment. For
104 example, if the speed limit is 100 km / h, the cost to traverse a 10 km
105 long road segment must be calculated as
106 length / speed = 10 km / (100 km/h) = 0.1 h.
107 Supported are cost assignments for arcs, and also different costs for
108 both directions of a vector line. For areas, costs will be calculated
109 along boundary lines.
110 The input vector needs to be prepared with v.net operation=connect in
112 order to connect points representing center nodes to the network.
113 Points specified by category must be exactly on network nodes, and the
115 input vector map needs to be prepared with v.net operation=connect.
116 Application of flag -t enables a turntable support. This flag requires
118 additional parameters turn_layer and turn_cat_layer that are otherwise
119 ignored. The turntable allows to model e.g. traffic code, where some
120 turns may be prohibited. This means that the input layer is expanded
121 by turntable with costs of every possible turn on any possible node
122 (intersection) in both directions. Turntable can be created by the
123 v.net module. For more information about turns in the vector network
124 analyses see wiki page.
125
127 Arcs can be closed using cost = -1. Turns support: The costs of turns
128 on visiting nodes are not taken in account.
129
131 Traveling salesman for 6 digitized nodes (Spearfish):
132 Shortest path, along unimproved roads:
134 Fastest path, along highways:
136 Searching for the shortest path using distance and the fastest path us‐
138 ing traveling time according to the speed limits of different road
139 types:
140 # Spearfish
141 g.copy vect=roads,myroads
142 # we have 6 locations to visit on our trip
143 echo "1|601653.5|4922869.2|a
144 2|608284|4923776.6|b
145 3|601845|4914981.9|c
146 4|596270|4917456.3|d
147 5|593330.8|4924096.6|e
148 6|598005.5|4921439.2|f" | v.in.ascii in=- cat=1 x=2 y=3 out=centers col="cat integer, \
149 east double precision, north double precision, label varchar(43)"
150 # verify data preparation
151 v.db.select centers
152 v.category centers op=report
153 # type count min max
154 # point 6 1 6
155 # create lines map connecting points to network (on layer 2)
156 v.net myroads points=centers out=myroads_net op=connect thresh=500
157 v.category myroads_net op=report
158 # Layer / table: 1 / myroads_net
159 # type count min max
160 # line 837 1 5
161 #
162 # Layer: 2
163 # type count min max
164 # point 6 1 5
165 # find the shortest path
166 v.net.salesman myroads_net center_cats=1-6 out=mysalesman_distance
167 # set up costs as traveling time
168 # create unique categories for each road in layer 3
169 v.category in=myroads_net out=myroads_net_time opt=add cat=1 layer=3 type=line
170 # add new table for layer 3
171 v.db.addtable myroads_net_time layer=3 col="cat integer,label varchar(43),length double precision,speed double precision,cost double precision,bcost double precision"
172 # copy road type to layer 3
173 v.to.db myroads_net_time layer=3 qlayer=1 opt=query qcolumn=label columns=label
174 # upload road length in miles
175 v.to.db myroads_net_time layer=3 type=line option=length col=length unit=miles
176 # set speed limits in miles / hour
177 v.db.update myroads_net_time layer=3 col=speed val="5.0"
178 v.db.update myroads_net_time layer=3 col=speed val="75.0" where="label=’interstate’"
179 v.db.update myroads_net_time layer=3 col=speed val="75.0" where="label=’primary highway, hard surface’"
180 v.db.update myroads_net_time layer=3 col=speed val="50.0" where="label=’secondary highway, hard surface’"
181 v.db.update myroads_net_time layer=3 col=speed val="25.0" where="label=’light-duty road, improved surface’"
182 v.db.update myroads_net_time layer=3 col=speed val="5.0" where="label=’unimproved road’"
183 # define traveling costs as traveling time in minutes:
184 # set forward costs
185 v.db.update myroads_net_time layer=3 col=cost val="length / speed * 60"
186 # set backward costs
187 v.db.update myroads_net_time layer=3 col=bcost val="length / speed * 60"
188 # find the fastest path
189 v.net.salesman myroads_net_time arc_layer=3 node_layer=2 arc_column=cost arc_backward_column=bcost center_cats=1-6 out=mysalesman_time
190 To display the result, run for example:
191 # Display the results
192 g.region vector=myroads_net
193 # shortest path
194 d.mon x0
195 d.vect myroads_net
196 d.vect centers -c icon=basic/triangle
197 d.vect mysalesman_distance col=green width=2
198 d.font Vera
199 d.vect centers col=red disp=attr attrcol=label lsize=12
200 # fastest path
201 d.mon x1
202 d.vect myroads_net
203 d.vect centers -c icon=basic/triangle
204 d.vect mysalesman_time col=green width=2
205 d.font Vera
206 d.vect centers col=red disp=attr attrcol=label lsize=12
207
209 d.path, v.net, v.net.alloc, v.net.iso, v.net.path, v.net.steiner
210
212 Radim Blazek, ITC-Irst, Trento, Italy
213 Markus Metz
214 Documentation: Markus Neteler, Markus Metz
215 TURNS SUPPORT
217 The turns support was implemnented as part of GRASS GIS turns cost
218 project at Czech Technical University in Prague, Czech Republic.
219 Eliska Kyzlikova, Stepan Turek, Lukas Bocan and Viera Bejdova partici‐
220 pated in the project.
221 Implementation: Stepan Turek
223 Documentation: Lukas Bocan
224 Mentor: Martin Landa
225
227 Available at: v.net.salesman source code (history)
228 Accessed: Saturday Oct 28 18:18:41 2023
230 Main index | Vector index | Topics index | Keywords index | Graphical
232 index | Full index
233 © 2003-2023 GRASS Development Team, GRASS GIS 8.3.1 Reference Manual
235GRASS 8.3.1 v.net.salesman(1)