<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <title>GRASS GIS: v.net.salesman</title> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <link rel="stylesheet" href="grassdocs.css" type="text/css"> </head> <body bgcolor="white"> <img src="grass_logo.png" alt="GRASS logo"><hr align=center size=6 noshade> <h2>NAME</h2> <em><b>v.net.salesman</b></em> - Creates a cycle connecting given nodes (Traveling salesman problem).<BR> Note that TSP is NP-hard, heuristic algorithm is used by this module and created cycle may be sub optimal <h2>KEYWORDS</h2> vector, networking <h2>SYNOPSIS</h2> <b>v.net.salesman</b><br> <b>v.net.salesman help</b><br> <b>v.net.salesman</b> [-<b>g</b>] <b>input</b>=<em>name</em> <b>output</b>=<em>name</em> [<b>type</b>=<em>string</em>[,<i>string</i>,...]] [<b>alayer</b>=<em>integer</em>] [<b>nlayer</b>=<em>integer</em>] [<b>acolumn</b>=<em>string</em>] <b>ccats</b>=<em>range</em> [--<b>overwrite</b>] [--<b>verbose</b>] [--<b>quiet</b>] <h3>Flags:</h3> <DL> <DT><b>-g</b></DT> <DD>Use geodesic calculation for longitude-latitude locations</DD> <DT><b>--overwrite</b></DT> <DD>Allow output files to overwrite existing files</DD> <DT><b>--verbose</b></DT> <DD>Verbose module output</DD> <DT><b>--quiet</b></DT> <DD>Quiet module output</DD> </DL> <h3>Parameters:</h3> <DL> <DT><b>input</b>=<em>name</em></DT> <DD>Name of input vector map</DD> <DT><b>output</b>=<em>name</em></DT> <DD>Name for output vector map</DD> <DT><b>type</b>=<em>string[,<i>string</i>,...]</em></DT> <DD>Type</DD> <DD>Arc type</DD> <DD>Options: <em>line,boundary</em></DD> <DD>Default: <em>line,boundary</em></DD> <DT><b>alayer</b>=<em>integer</em></DT> <DD>Layer number</DD> <DD>Arc layer</DD> <DD>Default: <em>1</em></DD> <DT><b>nlayer</b>=<em>integer</em></DT> <DD>Layer number</DD> <DD>Node layer (used for cities)</DD> <DD>Default: <em>2</em></DD> <DT><b>acolumn</b>=<em>string</em></DT> <DD>Arcs' cost column (for both directions)</DD> <DT><b>ccats</b>=<em>range</em></DT> <DD>Category values</DD> <DD>Categories of points ('cities') on nodes (layer is specified by nlayer)</DD> </DL> <h2>DESCRIPTION</h2> <em>v.net.salesman</em> calculates the optimal route to visit nodes on a vector network. <h2>EXAMPLE</h2> Traveling salesman for 6 digitized nodes (Spearfish): <div class="code"><pre> g.copy vect=roads,myroads v.db.addcol myroads col="cost double precision" # define traveling costs as inverse of speed limit: v.db.update myroads col=cost val=1/50 v.db.update myroads col=cost val=1/75 where="label='interstate'" v.db.update myroads col=cost val=1/5 where="label='unimproved road'" v.db.update myroads col=cost val=1/25 where="label='light-duty road, improved surface'" v.db.select myroads # we have 6 locations to visit on our trip echo "1|601653.5|4922869.2|a 2|608284|4923776.6|b 3|601845|4914981.9|c 4|596270|4917456.3|d 5|593330.8|4924096.6|e 6|598005.5|4921439.2|f" | v.in.ascii cat=1 x=2 y=3 out=centers col="cat integer, \ east double precision, north double precision, label varchar(43)" v.db.select centers v.category centers op=report # type count min max # point 6 1 6 #create lines map connecting points to network (on layer 2) v.net myroads points=centers out=myroads_net op=connect thresh=500 v.category myroads_net op=report # Layer / table: 1 / myroads_net # type count min max # line 837 1 5 # # Layer: 2 # type count min max # point 6 1 5 # The network is now prepared. g.region vect=myroads_net d.mon x0 d.vect myroads_net d.vect -c centers icon=basic/triangle d.font verdana d.vect centers col=red disp=attr attrcol=label lsize=12 # due to the costs (?, TODO), the result looks like a Steiner tree: # v.net.salesman myroads_net acol=cost ccats=1-6 out=mysalesman # run without traveling costs v.net.salesman myroads_net ccats=1-6 out=mysalesman d.vect mysalesman col=green width=2 d.vect centers col=red disp=attr attrcol=label lsize=12 </pre></div> <img src="vnetsalesman.png" alt="v.net.salesman example" border="1"> <h2>SEE ALSO</h2> <em><a HREF="d.path.html">d.path</a></em>, <em><a HREF="v.net.html">v.net</a></em>, <em><a HREF="v.net.alloc.html">v.net.alloc</a></em>, <em><a HREF="v.net.iso.html">v.net.iso</a></em>, <em><a HREF="v.net.path.html">v.net.path</a></em>, <em><a HREF="v.net.steiner.html">v.net.steiner</a></em> <h2>AUTHOR</h2> Radim Blazek, ITC-Irst, Trento, Italy<br> Documentation: Markus Neteler <p><i>Last changed: $Date: 2007-08-03 14:21:50 +0200 (Fri, 03 Aug 2007) $</i> <HR> <P><a href="index.html">Main index</a> - <a href="vector.html">vector index</a> - <a href="full_index.html">Full index</a></P> <P>© 2003-2008 <a href="http://grass.osgeo.org">GRASS Development Team</a></p> </body> </html>