The Concorde TSP Solver is a program for solving the
travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
. It was written by
David Applegate,
Robert E. Bixby,
Vašek Chvátal Vašek is both a Czech surname and masculine given name (diminutive of Václav). It may refer to: Surname
* Anton Vašek (1905–1946), Slovak Holocaust perpetrator
* Petr Vašek (born 1979), Czech footballer
* Radomír Vašek (born 1972), Czech te ...
, and
William J. Cook, in
ANSI C
ANSI C, ISO C, and Standard C are successive standards for the C programming language published by the American National Standards Institute (ANSI) and ISO/IEC JTC 1/SC 22/WG 14 of the International Organization for Standardization (ISO) and th ...
, and is freely available for academic use.
Concorde has been applied to problems of
gene mapping
Gene mapping describes the methods used to identify the locus of a gene and the distances between genes. Gene mapping can also describe the distances between different sites within a gene.
The essence of all genome mapping is to place a c ...
,
protein function prediction,
vehicle routing
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises t ...
, conversion of bitmap images to continuous line drawings, scheduling ship movements for seismic surveys, and in studying the scaling properties of combinatorial optimization problems.
According to , Concorde “is widely regarded as the fastest TSP solver, for large instances, currently in existence.” In 2001, Concorde won a 5000
guilder
Guilder is the English translation of the Dutch and German ''gulden'', originally shortened from Middle High German ''guldin pfenninc'' " gold penny". This was the term that became current in the southern and western parts of the Holy Roman Emp ...
prize from
CMG for solving a vehicle routing problem the company had posed in 1996.
Whizzkids '96 vehicle routing
from the Concorde web site, retrieved August 26, 2008.
Notes
References
*.
*.
*.
*.
*.
*.
*.
{{refend
External links
Concorde website
at Arizona State University
Travelling salesman problem
Mathematical optimization software