Concorde TSP Solver: Difference between revisions
mNo edit summary |
it also avaible commercially. |
||
| Line 1: | Line 1: | ||
{{otheruses|Concorde (disambiguation)}} |
{{otheruses|Concorde (disambiguation)}} |
||
The '''Concorde TSP Solver''' is a program for solving the [[traveling salesman problem]]. It was written by David Applegate, Robert E. Bixby, [[Vašek Chvátal]], and William J. Cook, in [[ANSI C]], and is available for academic use. |
The '''Concorde TSP Solver''' is a program for solving the [[traveling salesman problem]]. It was written by David Applegate, Robert E. Bixby, [[Vašek Chvátal]], and William J. Cook, in [[ANSI C]], and is freely available for academic use. |
||
Concorde has been applied to problems of [[gene mapping]],<ref>{{harvtxt|Hitte|Lorentzen|Guyon|Kim|2003}}.</ref> protein function prediction,<ref>{{harvtxt|Johnson|Liu|2006}}.</ref> [[Vehicle routing problem|vehicle routing]],<ref>{{harvtxt|Applegate|Cook|Dash|Rohe|2002}}.</ref> conversion of bitmap images to continuous line drawings,<ref>{{harvtxt|Bosch|Herman|2004}}.</ref> scheduling ship movements for seismic surveys,<ref>{{harvtxt|Gutin|Jakubowicz|Ronen|Zverovitch|2005}}.</ref> and in studying the scaling properties of combinatorial optimization problems.<ref>{{harvtxt|Aldous|Percus|2003}}.</ref> |
Concorde has been applied to problems of [[gene mapping]],<ref>{{harvtxt|Hitte|Lorentzen|Guyon|Kim|2003}}.</ref> protein function prediction,<ref>{{harvtxt|Johnson|Liu|2006}}.</ref> [[Vehicle routing problem|vehicle routing]],<ref>{{harvtxt|Applegate|Cook|Dash|Rohe|2002}}.</ref> conversion of bitmap images to continuous line drawings,<ref>{{harvtxt|Bosch|Herman|2004}}.</ref> scheduling ship movements for seismic surveys,<ref>{{harvtxt|Gutin|Jakubowicz|Ronen|Zverovitch|2005}}.</ref> and in studying the scaling properties of combinatorial optimization problems.<ref>{{harvtxt|Aldous|Percus|2003}}.</ref> |
||
Revision as of 02:20, 3 May 2010
The Concorde TSP Solver is a program for solving the traveling salesman problem. It was written by David Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook, in ANSI C, and is freely available for academic use.
Concorde has been applied to problems of gene mapping,[1] protein function prediction,[2] vehicle routing,[3] conversion of bitmap images to continuous line drawings,[4] scheduling ship movements for seismic surveys,[5] and in studying the scaling properties of combinatorial optimization problems.[6]
Hahsler & Hornik (2007) review both heuristic and exact solutions to the TSP; they call Concorde “a state of the art implementation” and state that it is “one of the best exact TSP solvers currently available.” Mulder & Wunsch (2003) add that Concorde “is widely regarded as the fastest TSP solver, for large instances, currently in existence.” In 2001, Concorde won a 5000 Guilder prize from CMG for solving a vehicle routing problem the company had posed in 1996.[7]
Notes
- ^ Hitte et al. (2003).
- ^ Johnson & Liu (2006).
- ^ Applegate et al. (2002).
- ^ Bosch & Herman (2004).
- ^ Gutin et al. (2005).
- ^ Aldous & Percus (2003).
- ^ Whizzkids '96 vehicle routing, from the Concorde web site, retrieved August 26, 2008.
References
- Aldous, David; Percus, Allon G. (2003), "Scaling and universality in continuous length combinatorial optimization", PROC. Nat. Acad. Sci. USA, 100 (20): 11211–11215, doi:10.1073/pnas.1635191100
- Applegate, David; Cook, William; Dash, Sanjeeb; Rohe, André (2002), "Solution of a min-max vehicle routing problem", INFORMS Journal on Computing, 14 (2): 132–143, doi:10.1287/ijoc.14.2.132.118
- Bosch, Robert; Herman, Adrianne (2004), "Continuous line drawings via the traveling salesman problem" (PDF), Operations Research Letters, 32 (4): 302–303, doi:10.1016/j.orl.2003.10.001
- Gutin, Gregory; Jakubowicz, Helmut; Ronen, Shuki; Zverovitch, Alexei (2005), "Seismic vessel problem" (PDF), Communications in DQM, 8: 13–20
- Hahsler, Michael; Hornik, Kurt (2007), "TSP – Infrastructure for the Traveling Salesperson Problem", Journal of Statistical Software, 23 (2): 1–21
- Hitte, C.; Lorentzen, T. D.; Guyon, R.; Kim, L.; Cadieu, E.; Parker, H. G.; Quignon, P.; Lowe, J. K.; Gelfenbeyn, B.; Andre, C.; Ostrander, E. A.; Galibert, F. (2003), "Comparison of MultiMap and TSP/CONCORDE for constructing radiation hybrid maps", Journal of Heredity, 94 (1): 9–13, doi:10.1093/jhered/esg012
- Johnson, Olin; Liu, Jing (2006), "A traveling salesman approach for predicting protein functions", Source Code for Biology and Medicine, 1: 3, doi:10.1186/1751-0473-1-3
{{citation}}: CS1 maint: unflagged free DOI (link)
- Mulder, Samuel A.; Wunsch, Donald C., II (2003), "Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks", Neural Networks, 16 (5–6): 827–832, doi:10.1016/S0893-6080(03)00130-8
{{citation}}: CS1 maint: multiple names: authors list (link)