Programa para resolver el problema del viajante.
El Concorde TSP Solver es un programa para resolver el problema del viajante . Fue escrito por David Applegate , Robert E. Bixby , Vašek Chvátal y William J. Cook , en ANSI C , y está disponible gratuitamente para uso académico.
Concorde se ha aplicado a problemas de mapeo genético , [1] predicción de funciones proteicas , [2] rutas de vehículos , [3] conversión de imágenes de mapas de bits en dibujos de líneas continuas, [4] programación de movimientos de barcos para estudios sísmicos, [5] y en estudiar las propiedades de escala de problemas de optimización combinatoria. [6]
Según Mulder y Wunsch (2003), Concorde “es ampliamente considerado como el solucionador de TSP más rápido, para instancias grandes, que existe actualmente”. En 2001, el Concorde ganó un premio de 5.000 florines de CMG por resolver un problema de rutas de vehículos que la empresa había planteado en 1996. [7]
Concorde requiere un solucionador de programación lineal y solo admite QSopt [8] y CPLEX 8.0.
Notas
- ^ Hitte y col. (2003).
- ^ Johnson y Liu (2006).
- ^ Applegate y col. (2002).
- ^ Bosch y Herman (2004).
- ^ Gutin y col. (2005)
- ^ Aldous y Percus (2003).
- ^ Rutas de vehículos Whizzkids '96, del sitio web de Concorde, consultado el 26 de agosto de 2008.
- ^ "Solucionador de programación lineal QSopt". Universidad de Waterloo . Consultado el 28 de octubre de 2023 .
Referencias
- Aldous, David; Percus, Allon G. (2003), "Escalado y universalidad en la optimización combinatoria de longitud continua", Proc. Nacional. Acad. Ciencia. EE. UU. , 100 (20): 11211–11215, arXiv : cond-mat/0301035 , Bibcode : 2003PNAS..10011211A, doi : 10.1073/pnas.1635191100 , PMC 208736 , PMID 14504403.
- Applegate, David; Cocinero, William; Guión, Sanjeeb; Rohe, André (2002), "Solución de un problema de rutas de vehículos mínimo-máximo", INFORMS Journal on Computing , 14 (2): 132–143, doi :10.1287/ijoc.14.2.132.118.
- Bosch, Robert; Herman, Adrianne (2004), "Dibujos de líneas continuas a través del problema del viajante" (PDF) , Operations Research Letters , 32 (4): 302–303, doi :10.1016/j.orl.2003.10.001.
- Gutin, Gregorio; Jakubowicz, Helmut; Ronen, Shuki; Zverovitch, Alexei (2005), "Problema de los buques sísmicos" (PDF) , Comunicaciones en DQM , 8 : 13–20.
- Hitte, C.; Lorentzen, TD; Guyón, R.; Kim, L.; Cadieu, E.; Parker, HG; Quiñon, P.; Lowe, JK; et al. (2003), "Comparación de MultiMap y TSP/CONCORDE para construir mapas híbridos de radiación", Journal of Heredity , 94 (1): 9–13, doi : 10.1093/jhered/esg012 , PMID 12692156.
- Johnson, Olin; Liu, Jing (2006), "Un enfoque de vendedor ambulante para predecir funciones de proteínas", Código fuente para biología y medicina , 1 : 3, doi : 10.1186/1751-0473-1-3 , PMC 1636333 , PMID 17147783.
- Mulder, Samuel A.; Wunsch, Donald C., II (2003), "Solución del problema del vendedor ambulante de millones de ciudades mediante agrupación de divide y vencerás con redes neuronales de resonancia adaptativa", Neural Networks , 16 (5–6): 827–832, doi :10.1016/S0893- 6080(03)00130-8, PMID 12850040
{{citation}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ).
enlaces externos
