Home » Software » GRASS GIS: raster, vector, and imagery analysis » Vector Operations » Traveling Salesman Approach to Visiting Data-loggers

# Traveling Salesman Approach to Visiting Data-loggers

Dec 20, 2008 metroadmin**Premise:**

Several data-loggers in steep terrain; how can we visit all of them in the most efficient manner such that we traverse the least cumulative slope gradient? In a sense this is a traveling salesman style problem, with travel costs defined by slope gradient. The `v.net.salesman` module in GRASS can be used to compute the optimal route between data-loggers, given: 1) a network of lines connecting all points to be visited and 2) transferal of slope cost information to the network. An example approach is listed below. Note that due to a bug in `v.net.salesman`, we need to use one extra step-- details below.

**Approach:**

- generate a delaunay network between points
- densify the line segments along the network (v.split)
- convert the network to a 3D, by sampling a DEM along vertices (v.drape)
- save the slope of each line segment on the network to its attribute table (v.to.db)
- use the squared slope as the travel cost
- re-connect the new attribute table from the 3D map, to the original 2D map (v.db.connect)
- connect data-logger points to delaunay network (v.net)
- solve the traveling salesman problem (v.net.salesman)

**Room for Improvement:**

- generate a cost surface using a combination of slope map and known walkable trails / roads
- add support for lines to v.what.rast -- this would allow us to sample a more realistic cost surface, generated with r.cost
- fix v.net.salesman so that it can use 3D input maps

**mplementation in GRASS:**

### Links:

Spatial Clustering of Point Data: Spearfish Example

Vector Operations

## Software

- General Purpose Programming with Scripting Languages
- LaTeX Tips and Tricks
- PostGIS: Spatially enabled Relational Database Sytem
- PROJ: forward and reverse geographic projections
- GDAL and OGR: geodata conversion and re-projection tools
- R: advanced statistical package
- GRASS GIS: raster, vector, and imagery analysis
- Generic Mapping Tools: high quality map production