Concorde TSP Solver: diferència entre les revisions
Contingut suprimit Contingut afegit
| Línia 6: | Línia 6: | ||
{{Reflist}} |
{{Reflist}} |
||
== |
==Bibliografia== |
||
{{refbegin|2}} |
|||
*{{citation |
|||
| last1 = Aldous | first1 = David |
|||
| last2 = Percus | first2 = Allon G. |
|||
| doi = 10.1073/pnas.1635191100 |
|||
| issue = 20 |
|||
| journal = PROC. Nat. Acad. Sci. USA |
|||
| pages = 11211–11215 |
|||
| title = Scaling and universality in continuous length combinatorial optimization |
|||
| volume = 100 |
|||
| year = 2003 |
|||
| pmid = 14504403 |
|||
| pmc = 208736| bibcode = 2003PNAS..10011211A |
|||
}}. |
|||
*{{citation |
|||
| last1 = Applegate | first1 = David |
|||
| last2 = Cook | first2 = William |
|||
| last3 = Dash | first3 = Sanjeeb |
|||
| last4 = Rohe | first4 = André |
|||
| doi = 10.1287/ijoc.14.2.132.118 |
|||
| issue = 2 |
|||
| journal = INFORMS Journal on Computing |
|||
| pages = 132–143 |
|||
| title = Solution of a min-max vehicle routing problem |
|||
| volume = 14 |
|||
| year = 2002}}. |
|||
*{{citation |
|||
| last1 = Bosch | first1 = Robert |
|||
| last2 = Herman | first2 = Adrianne |
|||
| doi = 10.1016/j.orl.2003.10.001 |
|||
| issue = 4 |
|||
| journal = Operations Research Letters |
|||
| pages = 302–303 |
|||
| title = Continuous line drawings via the traveling salesman problem |
|||
| url = http://www.oberlin.edu/math/faculty/bosch/cld.pdf |
|||
| volume = 32 |
|||
| year = 2004}}. |
|||
*{{citation |
|||
| last1 = Gutin | first1 = Gregory |
|||
| last2 = Jakubowicz | first2 = Helmut |
|||
| last3 = Ronen | first3 = Shuki |
|||
| last4 = Zverovitch | first4 = Alexei |
|||
| journal = Communications in DQM |
|||
| pages = 13–20 |
|||
| title = Seismic vessel problem |
|||
| url = http://www.cs.rhul.ac.uk/home/gutin/paperstsp/svp5.pdf |
|||
| volume = 8 |
|||
| year = 2005}}. |
|||
*{{citation |
|||
| last1 = Hahsler | first1 = Michael |
|||
| last2 = Hornik | first2 = Kurt |
|||
| issue = 2 |
|||
| journal = Journal of Statistical Software |
|||
| pages = 1–21 |
|||
| title = TSP – Infrastructure for the Traveling Salesperson Problem |
|||
| url = http://www.jstatsoft.org/v23/i02 |
|||
| volume = 23 |
|||
| year = 2007}}. |
|||
*{{citation |
|||
| last1 = Hitte | first1 = C. |
|||
| last2 = Lorentzen | first2 = T. D. |
|||
| last3 = Guyon | first3 = R. |
|||
| last4 = Kim | first4 = L. |
|||
| last5 = Cadieu | first5 = E. |
|||
| last6 = Parker | first6 = H. G. |
|||
| last7 = Quignon | first7 = P. |
|||
| last8 = Lowe | first8 = J. K. |
|||
| last9 = Gelfenbeyn | first9 = B. |
|||
| last10 = Andre |
|||
| first10 = C |
|||
| last11 = Ostrander |
|||
| first11 = E. A. |
|||
| last12 = Galibert |
|||
| first12 = F |
|||
| doi = 10.1093/jhered/esg012 |
|||
| issue = 1 |
|||
| journal = Journal of Heredity |
|||
| pages = 9–13 |
|||
| title = Comparison of MultiMap and TSP/CONCORDE for constructing radiation hybrid maps |
|||
| volume = 94 |
|||
| year = 2003 |
|||
| pmid = 12692156| display-authors = 8 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Johnson | first1 = Olin |
|||
| last2 = Liu | first2 = Jing |
|||
| doi = 10.1186/1751-0473-1-3 |
|||
| journal = Source Code for Biology and Medicine |
|||
| page = 3 |
|||
| title = A traveling salesman approach for predicting protein functions |
|||
| volume = 1 |
|||
| year = 2006 |
|||
| pmid = 17147783 |
|||
| pmc = 1636333}}. |
|||
*{{citation |
|||
| last1 = Mulder | first1 = Samuel A. |
|||
| last2 = Wunsch | first2 = Donald C., II |
|||
| doi = 10.1016/S0893-6080(03)00130-8 |
|||
| issue = 5–6 |
|||
| journal = Neural Networks |
|||
| pages = 827–832 |
|||
| title = Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks |
|||
| volume = 16 |
|||
| year = 2003 |
|||
| pmid = 12850040}}. |
|||
{{refend}} |
|||
== Enllaços externs == |
== Enllaços externs == |
||
Revisió del 15:06, 16 juny 2015
El Concorde TSP Solver és un programa per solucionar el problema del viatjant de comerç. Va ser escrit per David Applegate, Robert E. Bixby, Vašek Chvátal, i William J. Cuiner, en ANSI C, i es troba lliurement disponible per ús acadèmic.
Concorde ha estat aplicat a problemes de mapatge de gens, predicció de funció de la proteïna, encaminament de vehicles, conversió d'imatges vectorials a dibuixos de línia contínua, planificació de moviments de vaixell per estudis sísmics, i estudi de propietats d'escalatge de problemes d'optimització combinatòria.[1][2][3][4][5][6]
Notes
Bibliografia
- 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 et al. (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", Operations Research Letters 32 (4): 302–303, doi:10.1016/j.orl.2003.10.001, <http://www.oberlin.edu/math/faculty/bosch/cld.pdf>.
- Gutin, Gregory; Jakubowicz, Helmut & Ronen, Shuki et al. (2005), "Seismic vessel problem", Communications in DQM 8: 13–20, <http://www.cs.rhul.ac.uk/home/gutin/paperstsp/svp5.pdf>.
- Hahsler, Michael & Hornik, Kurt (2007), "TSP – Infrastructure for the Traveling Salesperson Problem", Journal of Statistical Software 23 (2): 1–21, <http://www.jstatsoft.org/v23/i02>.
- Hitte, C.; Lorentzen, T. D. & Guyon, R. 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.
- 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.
- 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.
Enllaços externs
- Lloc web del Concorde (anglès)
- Online access to Concorde solver a Argonne National Laboratories (anglès)