1v.net.salesman(1) Grass 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, networking
13
15 v.net.salesman
16 v.net.salesman help
17 v.net.salesman [-g] input=name output=name [type=string[,string,...]]
18 [alayer=integer] [nlayer=integer] [acolumn=string] ccats=range
19 [--overwrite] [--verbose] [--quiet]
20 Flags:
22 -g
23 Use geodesic calculation for longitude-latitude locations
24 --overwrite
26 Allow output files to overwrite existing files
27 --verbose
29 Verbose module output
30 --quiet
32 Quiet module output
33 Parameters:
35 input=name
36 Name of input vector map
37 output=name
39 Name for output vector map
40 type=string[,string,...]
42 Type
43 Arc type
44 Options: line,boundary
45 Default: line,boundary
46 alayer=integer
48 Layer number
49 Arc layer
50 Default: 1
51 nlayer=integer
53 Layer number
54 Node layer (used for cities)
55 Default: 2
56 acolumn=string
58 Arcs' cost column (for both directions)
59 ccats=range
61 Category values
62 Categories of points ('cities') on nodes (layer is specified by
63 nlayer)
64
66 v.net.salesman calculates the optimal route to visit nodes on a vector
67 network.
68
70 Traveling salesman for 6 digitized nodes (Spearfish):
71 g.copy vect=roads,myroads
72 v.db.addcol myroads col="cost double precision"
73 # define traveling costs as inverse of speed limit:
74 v.db.update myroads col=cost val=1/50
75 v.db.update myroads col=cost val=1/75 where="label='interstate'"
76 v.db.update myroads col=cost val=1/5 where="label='unimproved road'"
77 v.db.update myroads col=cost val=1/25 where="label='light-duty road,
78 improved surface'"
79 v.db.select myroads
80 # we have 6 locations to visit on our trip
81 echo "1|601653.5|4922869.2|a
82 2|608284|4923776.6|b
83 3|601845|4914981.9|c
84 4|596270|4917456.3|d
85 5|593330.8|4924096.6|e
86 6|598005.5|4921439.2|f" | v.in.ascii cat=1 x=2 y=3 out=centers col="cat
87 integer, \
88 east double precision, north double precision,
89 label varchar(43)"
90 v.db.select centers
91 v.category centers op=report
92 # type count min max
93 # point 6 1 6
94 #create lines map connecting points to network (on layer 2)
95 v.net myroads points=centers out=myroads_net op=connect thresh=500
96 v.category myroads_net op=report
97 # Layer / table: 1 / myroads_net
98 # type count min max
99 # line 837 1 5
100 #
101 # Layer: 2
102 # type count min max
103 # point 6 1 5
104 # The network is now prepared.
105 g.region vect=myroads_net
106 d.mon x0
107 d.vect myroads_net
108 d.vect -c centers icon=basic/triangle
109 d.font verdana
110 d.vect centers col=red disp=attr attrcol=label lsize=12
111 # due to the costs (?, TODO), the result looks like a Steiner tree:
112 # v.net.salesman myroads_net acol=cost ccats=1-6 out=mysalesman
113 # run without traveling costs
114 v.net.salesman myroads_net ccats=1-6 out=mysalesman
115 d.vect mysalesman col=green width=2
116 d.vect centers col=red disp=attr attrcol=label lsize=12
117
120 d.path, v.net, v.net.alloc, v.net.iso, v.net.path, v.net.steiner
121
123 Radim Blazek, ITC-Irst, Trento, Italy
124 Documentation: Markus Neteler
125 Last changed: $Date: 2007-08-03 14:21:50 +0200 (Fri, 03 Aug 2007) $
127 Full index
129 © 2003-2008 GRASS Development Team
131GRASS 6.3.0 v.net.salesman(1)