1v.net.salesman(1)             Grass User's Manual            v.net.salesman(1)
2
3
4

NAME

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

KEYWORDS

12       vector, network, salesman
13

SYNOPSIS

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
23   Flags:
24       -t
25           Use turntable
26
27       -g
28           Use geodesic calculation for longitude-latitude locations
29
30       --overwrite
31           Allow output files to overwrite existing files
32
33       --help
34           Print usage summary
35
36       --verbose
37           Verbose module output
38
39       --quiet
40           Quiet module output
41
42       --ui
43           Force launching GUI dialog
44
45   Parameters:
46       input=name [required]
47           Name of input vector map
48           Or data source for direct OGR access
49
50       output=name [required]
51           Name for output vector map
52
53       center_cats=range [required]
54           Category values
55           Categories  of  points  (’cities’)  on nodes (layer is specified by
56           nlayer)
57
58       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
62           access this is the layer name.
63           Default: 1
64
65       arc_type=string[,string,...] [required]
66           Arc type
67           Input feature type
68           Options: line, boundary
69           Default: line,boundary
70
71       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
75           access this is the layer name.
76           Default: 2
77
78       arc_column=string
79           Arc forward/both direction(s) cost column (number)
80
81       arc_backward_column=string
82           EXPERIMENTAL: Arc backward direction cost column (number)
83
84       turn_layer=string
85           Layer with turntable
86           Relevant only with -t flag
87           Default: 3
88
89       turn_cat_layer=string
90           Layer with unique categories used in turntable
91           Relevant only with -t flag
92           Default: 4
93
94       sequence=name
95           Name for output file holding node sequence ("-" for stdout)
96

DESCRIPTION

98       v.net.salesman calculates the optimal route to visit nodes on a  vector
99       network.
100
101       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
111       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
114       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
117       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

NOTES

127       Arcs can be closed using cost = -1.  Turns support: The costs of  turns
128       on visiting nodes are not taken in account.
129

EXAMPLE

131       Traveling salesman for 6 digitized nodes (Spearfish):
132
133       Shortest path, along unimproved roads:
134
135       Fastest path, along highways:
136
137       Searching  for  the  shortest  path using distance and the fastest path
138       using 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

SEE ALSO

209       d.path, v.net, v.net.alloc, v.net.iso, v.net.path, v.net.steiner
210

AUTHOR

212       Radim Blazek, ITC-Irst, Trento, Italy
213       Markus Metz
214       Documentation: Markus Neteler, Markus Metz
215
216   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 at the  project.   Implementation:  Stepan  Turek  Documentation:
221       Lukas Bocan Mentor: Martin Landa
222
223       Last changed: $Date: 2016-11-14 00:05:32 +0100 (Mon, 14 Nov 2016) $
224

SOURCE CODE

226       Available at: v.net.salesman source code (history)
227
228       Main  index  | Vector index | Topics index | Keywords index | Graphical
229       index | Full index
230
231       © 2003-2019 GRASS Development Team, GRASS GIS 7.6.0 Reference Manual
232
233
234
235GRASS 7.6.0                                                  v.net.salesman(1)
Impressum