v.net.salesman.opt

Creates a cycle connecting given nodes (Traveling salesman problem).

Note that TSP is NP-hard, heuristic algorithm is used by this module and created cycle may be suboptimal

v.net.salesman.opt [-g] input=name output=name [type=string [,string,...]] [alayer=string] [nlayer=string] [afcolumn=string] [abcolumn=string] [sequence=name] ccats=range [method=string] [--overwrite] [--verbose] [--quiet] [--qq] [--ui]

Example:

v.net.salesman.opt input=name output=name ccats=range

grass.script.run_command("v.net.salesman.opt", input, output, type="line,boundary", alayer="1", nlayer="2", afcolumn=None, abcolumn=None, sequence=None, ccats, method=None, flags=None, overwrite=False, verbose=False, quiet=False, superquiet=False)

Example:

gs.run_command("v.net.salesman.opt", input="name", output="name", ccats="range")

Parameters

Command linePython (grass.script)

input=name [required]
    Name of input vector map
    Or data source for direct OGR access
output=name [required]
    Name for output vector map
type=string [,string,...]
    Arc type
    Allowed values: line, boundary
    Default: line,boundary
alayer=string
    Layer number or name
    Arc layer
    Default: 1
nlayer=string
    Layer number or name
    Node layer (used for cities)
    Default: 2
afcolumn=string
    Arc forward/both direction(s) cost column (number)
abcolumn=string
    EXPERIMENTAL: Arc backward direction cost column (number)
sequence=name
    Name for output file holding node sequence ("-" for stdout)
ccats=range [required]
    Category values
    Categories of points ('cities') on nodes (layer is specified by nlayer)
method=string
    Optimization method
    Allowed values: bs, ga
    bs: bootstrapping
    ga: genetic algorithm
-g
    Use geodesic calculation for longitude-latitude locations
--overwrite
    Allow output files to overwrite existing files
--help
    Print usage summary
--verbose
    Verbose module output
--quiet
    Quiet module output
--qq
    Very quiet module output
--ui
    Force launching GUI dialog

input : str, required
    Name of input vector map
    Or data source for direct OGR access
    Used as: input, vector, name
output : str, required
    Name for output vector map
    Used as: output, vector, name
type : str | list[str], optional
    Arc type
    Allowed values: line, boundary
    Default: line,boundary
alayer : str, optional
    Layer number or name
    Arc layer
    Used as: input, layer
    Default: 1
nlayer : str, optional
    Layer number or name
    Node layer (used for cities)
    Used as: input, layer
    Default: 2
afcolumn : str, optional
    Arc forward/both direction(s) cost column (number)
abcolumn : str, optional
    EXPERIMENTAL: Arc backward direction cost column (number)
sequence : str, optional
    Name for output file holding node sequence ("-" for stdout)
    Used as: output, file, name
ccats : str, required
    Category values
    Categories of points ('cities') on nodes (layer is specified by nlayer)
    Used as: input, cats, range
method : str, optional
    Optimization method
    Allowed values: bs, ga
    bs: bootstrapping
    ga: genetic algorithm
flags : str, optional
    Allowed values: g
    g
        Use geodesic calculation for longitude-latitude locations
overwrite: bool, optional
    Allow output files to overwrite existing files
    Default: False
verbose: bool, optional
    Verbose module output
    Default: False
quiet: bool, optional
    Quiet module output
    Default: False
superquiet: bool, optional
    Very quiet module output
    Default: False

DESCRIPTION

v.net.salesman.opt estimates the optimal route to visit nodes on a vector network and optionally tries to improve the result.

Costs may be either line lengths, or attributes saved in a database table. These attribute values are taken as costs of whole segments, not as costs to traverse a length unit (e.g. meter) of the segment. For example, if the speed limit is 100 km / h, the cost to traverse a 10 km long road segment must be calculated as length / speed = 10 km / (100 km/h) = 0.1 h. Supported are cost assignments for arcs, and also different costs for both directions of a vector line. For areas, costs will be calculated along boundary lines.

The input vector needs to be prepared with v.net operation=connect in order to connect points representing center nodes to the network.

Points specified by category must be exactly on network nodes, and the input vector map needs to be prepared with v.net operation=connect.

Optimization

For less than 10 nodes, the initial result is usually very close to the shortest possible tour and further optimization will have no effect.

v.net.salesman.opt uses the same heuristics like v.net.salesman.opt to find a good tour which is not necessarily the optimal tour. The tour can be optimized with two methods: bootstrapping and genetic algorithm (GA). The bootstrapping method removes a subtour from the tour and reinserts the nodes resulting in a shorter tour. This is applied on intermediate tours and the final tour.

The genetic algorithm first creates several initial tours. From these tours nearly identical toursare eliminated. The remaining tours are recombined to create new, better tours. All tours are now mutated. The sequence of Selection, Recombination, Mutation is repeated until there is no better solution. Finally, the best tour is optimized with bootstrapping.

NOTES

Arcs can be closed using cost = -1.

EXAMPLE

Visiting all 167 schools (North Carolina):

# North Carolina

# prepare network by connecting schools to streets
v.net -c input=streets_wake points=schools_wake output=streets_schools \
  operation=connect alayer=1 nlayer=2 thresh=1000

# verify data preparation
v.category in=streets_schools op=report
# type       count        min        max
# point          6          1          6

# find the shortest path
v.net.salesman.opt in=streets_schools ccats=1-167 out=schools_tour

# Resulting tour length: 551551.662

# find the shortest path, optimize with genetic algorithm
v.net.salesman.opt in=streets_schools ccats=1-167 out=schools_tour_ga method=ga

# Resulting tour length: 521191.083
# The original tour was 5.8% longer

# find the shortest path, optimize with bootstrapping
v.net.salesman.opt in=streets_schools ccats=1-167 out=schools_tour_bs method=bs

# Resulting tour length: 510693.965
# The original tour was 8.0% longer

AUTHORS

Radim Blazek, ITC-Irst, Trento, Italy
Markus Metz
Documentation: Markus Neteler, Markus Metz

SOURCE CODE

Available at: v.net.salesman.opt source code (history)
Latest change: Thursday Feb 20 13:02:26 2025 in commit 53de819