TSP v1.1-6

0

Monthly downloads

0th

Percentile

Traveling Salesperson Problem (TSP)

Basic infrastructure and some algorithms for the traveling salesperson problem (also traveling salesman problem; TSP). The package provides some simple algorithms and an interface to the Concorde TSP solver and its implementation of the Chained-Lin-Kernighan heuristic. The code for Concorde itself is not included in the package and has to be obtained separately.

Readme

TSP - Traveling Salesperson Problem - R package

CRAN version CRAN RStudio mirror downloads Travis-CI Build Status AppVeyor Build Status

This package provides the basic infrastructure and some algorithms for the traveling salesman problems (symmetric, asymmetric and Euclidean TSPs). The package provides some simple algorithms and an interface to the Concorde TSP solver and its implementation of the Chained-Lin-Kernighan heuristic.

Installation

Stable CRAN version: install from within R with

install.packages("TSP")

Current development version: Download package from AppVeyor or install from GitHub (needs devtools).

library("devtools")
install_github("mhahsler/TSP")

Usage

Load a data set with 312 cities (USA and Canada) and create a TSP object.

R> library("TSP")
R> data("USCA312")

R> tsp <- TSP(USCA312)
R> tsp
object of class 'TSP'
312 cities (distance   'euclidean')

Find a tour using the default heuristic.

tour <- solve_TSP(tsp)
tour
object of class 'TOUR' 
result of method 'arbitrary_insertion+two_opt' for 312 cities
tour length: 40621

An online example application of TSP can be found on shinyapps.

References

Functions in TSP

Name Description
TSP Class TSP -- Symmetric traveling salesperson problem
USCA USCA312/USCA50 -- 312/50 cities in the US and Canada
cut_tour Cut a tour to form a path
ETSP Class ETSP -- Euclidean traveling salesperson problem
insert_dummy Insert dummy cities into a distance matrix
reformulate_ATSP_as_TSP Reformulate a ATSP as a symmetric TSP
ATSP Class ATSP -- Asymmetric traveling salesperson problem
Concorde Using the Concorde TSP Solver
TOUR Class TOUR -- Solution to a traveling salesperson problem
TSPLIB Read and write TSPLIB files
tour_length Calculate the length of a tour
solve_TSP TSP solver interface
No Results!

Vignettes of TSP

Name
TSP.Rnw
TSP.bib
overview.odg
overview.pdf
No Results!

Last month downloads

Details

Type Package
Date 2018-04-29
Classification/ACM G.1.6, G.2.1, G.4
URL http://lyle.smu.edu/IDA/seriation
BugReports https://github.com/mhahsler/TSP
License GPL-3
Copyright All code is Copyright (C) Michael Hahsler and Kurt Hornik.
NeedsCompilation yes
Packaged 2018-04-30 14:07:23 UTC; hahsler
Repository CRAN
Date/Publication 2018-04-30 16:43:02 UTC

Include our badge in your README

[![Rdoc](http://www.rdocumentation.org/badges/version/TSP)](http://www.rdocumentation.org/packages/TSP)