Programa para resolver el problema del viajante de comercio
El Concorde TSP Solver es un programa para resolver el problema del viajante de comercio . 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] enrutamiento de vehículos , [3] conversión de imágenes de mapa de bits a dibujos de líneas continuas, [4] programación de movimientos de barcos para estudios sísmicos, [5] y en el estudio de las propiedades de escala de problemas de optimización combinatoria. [6]
Según Mulder y Wunsch (2003), Concorde “está ampliamente considerado como el solucionador de TSP más rápido, para instancias grandes, que existe actualmente”. En 2001, Concorde ganó un premio de 5000 florines de CMG por resolver un problema de enrutamiento 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 otros (2003).
- ^ Johnson y Liu (2006).
- ^ Applegate y otros (2002).
- ^ Bosch y Herman (2004).
- ^ Gutin y otros (2005)
- ^ Aldous y Percus (2003).
- ^ Ruta de vehículos de Whizzkids '96, del sitio web de Concorde, recuperado 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), "Escalamiento y universalidad en la optimización combinatoria de longitud continua", Proc. Natl. Acad. Sci. USA , 100 (20): 11211–11215, arXiv : cond-mat/0301035 , Bibcode :2003PNAS..10011211A, doi : 10.1073/pnas.1635191100 , PMC 208736 , PMID 14504403.
- Applegate, David; Cook, William; Dash, Sanjeeb; Rohe, André (2002), "Solución de un problema de enrutamiento de vehículos con valores mínimo y 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 de comercio" (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), "Problema de los buques sísmicos" (PDF) , Comunicaciones en DQM , 8 : 13–20.
- Hitte, C.; Lorentzen, TD; Guyon, R.; Kim, L.; Cadieu, E.; Parker, HG; Quignon, P.; Lowe, JK; et al. (2003), "Comparación de MultiMap y TSP/CONCORDE para la construcción de 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 las funciones de las proteínas", 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), "Solución del problema del viajante de comercio en una ciudad de un millón mediante la 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}}: CS1 maint: varios nombres: lista de autores ( enlace ).
Enlaces externos
