Concorde TSP Solver
Concorde TSP Solver är ett program för att lösa problemet med resande säljare . Den skrevs av David Applegate , Robert E. Bixby , Vašek Chvátal och William J. Cook, i ANSI C , och är fritt tillgänglig för akademiskt bruk.
Concorde har tillämpats på problem med genkartläggning , förutsägelse av proteinfunktioner , fordonsdirigering , konvertering av bitmappsbilder till kontinuerliga linjeritningar, schemaläggning av fartygsrörelser för seismiska undersökningar och vid studier av skalningsegenskaperna hos kombinatoriska optimeringsproblem.
Enligt Mulder & Wunsch (2003) betraktas Concorde allmänt som den snabbaste TSP-lösaren, för stora instanser som för närvarande finns. År 2001 vann Concorde ett pris på 5 000 gulden från CMG för att lösa ett fordonsdirigeringsproblem som företaget hade ställt till 1996.
Anteckningar
- Aldous, David; Percus, Allon G. (2003), "Skalning och universalitet i kombinatorisk optimering av kontinuerlig längd", Proc. Natl. Acad. Sci. USA , 100 (20): 11211–11215, arXiv : cond-mat/0301035 , Bibcode : 2003PNAS..10011211A , doi : 10.1073 /pnas.1635191120 , 4001191120 , 400 3 PM .
- 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 travelling 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 .
- Hitte, C.; Lorentzen, TD; Guyon, R.; Kim, L.; Cadieu, E.; Parker, HG; Quignon, P.; Lowe, JK; et al. (2003), "Comparison of MultiMap and TSP/CONCORDE for constructing radiation hybrid maps", Journal of Heredity , 94 (1): 9–13, doi : 10.1093/jhered/esg012 , PMID 12692156 .
- 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 , PMC 1636333 , PMID 17147783 .
- 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 , PMID 12850040 .