 Kí ni ìtàn ìṣòro àwọn oníṣòwò arìnrìn-àjò láti àwọn ọdún wọnyí wá nínú àkọsílẹ tó ṣe ṣókí?Context:Àwọn ohun tó fa ìṣòro àwọn oníṣòwò arìnrìn-àjò kò tíì ṣe kedere. Ìwé atọka kan tí wọn ṣe fún àwọn oníṣòwò arìnrìn-àjò láti ọdún 1832 mẹnu kan ìṣòro náà, ó sì ní àwọn ìrìn àjò àjò àfiṣàpẹẹrẹ ní Jámánì àti Switzerland nínú, àmọ kò ní ìtumọ ìṣirò kankan.   William Rowan Hamilton Onímọ ìṣirò ọmọ ilẹ Ireland náà William Rowan Hamilton àti onímọ ìṣirò ọmọ ilẹ Gẹẹsì náà Thomas Kirkman ló gbé ìlànà TSP kalẹ ní ọrúndún kọkàndínlógún. Ìdárayá tí Hamilton ṣe ni eré ìdárayá tí ó dá lórí wíwá àyíká Hamiltonian. Fọọmu gbogbogbo ti TSP dabi ẹni pe o ti kọkọ kẹkọọ nipasẹ awọn onimọ-jinlẹ lakoko awọn ọdun 1930 ni Vienna ati ni Harvard, ni pataki nipasẹ Karl Menger, ẹniti o ṣalaye iṣoro naa, ṣe akiyesi algorithm ti o han gbangba ti brute-force, o si ṣe akiyesi aiṣe ti heuristic aladugbo to sunmọ julọ:  A n tọka nipa iṣoro ifiranṣẹ niwọn igba ti o jẹ pe ni iṣe ibeere yii yẹ ki o yanju nipasẹ ọkọ ifiweranṣẹ kọọkan, ni eyikeyi idiyele tun nipasẹ ọpọlọpọ awọn arinrin-ajo iṣẹ-ṣiṣe lati wa, fun ọpọlọpọ awọn aaye ti a mọ awọn ijinna lẹẹmeji, ọna ti o kuru julọ ti o sopọ awọn aaye naa. Àmọ ṣá o, a lè yanjú ìṣòro yìí nípa ṣíṣe ọpọlọpọ àyẹwò. A kò mọ àwọn ìlànà tí yóò mú kí iye àwọn ìdánwò dín kù sí iye àwọn àtúnṣe tí ó wà fún àwọn ibi tí a fún. Òfin tó sọ pé kéèyàn kọkọ lọ láti ibi tó ti bẹrẹ lọ sí ibi tó sún mọ ọn jù lọ, lẹyìn náà lọ sí ibi tó sún mọ ọn jù lọ, àti bẹẹ bẹẹ lọ, kì í sábà jẹ kéèyàn rí ọnà tó kúrú jù lọ.  Ó kọkọ jẹ ọkan nínú àwọn ìlànà ìṣirò tí Merrill M. Flood ṣe ní àwọn ọdún 1930 nígbà tó ń wá ojútùú sí ọrọ bí wọn ṣe ń darí ọkọ akẹkọọ. Hassler Whitney tó wà ní Yunifásítì Princeton bẹrẹ sí í nífẹẹ sí ìṣòro yìí, ó pè é ní ìṣòro ìpínlẹ méjìdínláàádọta. Ìwé àkọkọ tó lo gbólóhùn náà ìṣòro oníṣòwò arìnrìn-àjò ni ìròyìn RAND Corporation ti 1949 tí Julia Robinson ṣe, On the Hamiltonian game a traveling salesman problem   Ní àwọn ọdún 1950 àti 1960, ìṣòro náà di èyí tí ó gbajúmọ sí i nínú àwọn ẹka sáyẹǹsì ní Yúróòpù àti Orílẹ-èdè Amẹríkà lẹyìn tí ilé-iṣẹ RAND Corporation ní Santa Monica fúnni ní èrè fún àwọn ìgbésẹ tí a gbé láti yanjú ìṣòro náà. Àwọn olùkópa pàtàkì ni George Dantzig, Delbert Ray Fulkerson àti Selmer M. Johnson láti ilé-iṣẹ RAND, tí wọn sọ ìṣòro náà gẹgẹ bí ètò ìsọrí tí ó jẹ odidi kan tí wọn sì dá ọnà gígùn gé fún ìdáhùn rẹ. Wọn kọ ohun tí wọn kà sí ìwé tí ó ṣe pàtàkì jùlọ lórí ọrọ náà nínú èyí tí wọn fi àwọn ọnà tuntun yìí yanjú ọràn kan pẹlú ìlú 49 sí ibi tí ó dára jùlọ nípa kíkọ ìrìn àjò kan àti fífi hàn pé kò sí ìrìn àjò mìíràn tó lè kúrú. Dantzig, Fulkerson and Johnson, sibẹsibẹ, ro pe fun ojutu ti o sunmọ ti o dara julọ a le ni anfani lati wa iṣapeye tabi fi idi iṣapeye mulẹ nipa fifi nọmba kekere ti awọn aiṣedede afikun awọn gige. Wọn lo èrò yìí láti yanjú ìṣòro ìlú 49 tí wọn kọkọ ṣe nípa lílo àwòkọṣe ìlà. Wọn rí i pé ìkúrú mẹrìndínlọgbọn péré ni wọn nílò láti yanjú ìṣòro ìlú mọkàndínláàádọta tí wọn ní. Lakoko ti iwe yii ko funni ni ọna algorithmic si awọn iṣoro TSP, awọn imọran ti o wa ninu rẹ jẹ dandan lati ṣẹda nigbamii awọn ọna ojutu deede fun TSP, botilẹjẹpe yoo gba ọdun 15 lati wa ọna algorithmic ni ṣiṣẹda awọn gige wọnyi. Yàtọ sí àwọn ọnà tí wọn fi ń gé òpó, Dantzig, Fulkerson àti Johnson tún lo àwọn ọnà tí wọn fi ń ṣe ẹka àti àlàfo fún ìgbà àkọkọ.  Ní ọdún 1959, Jillian Beardwood, J.H. Halton àti John Hammersley tẹ àpilẹkọ kan jáde tí àkọlé rẹ jẹ The Shortest Path Through Many Points nínú ìwé ìròyìn ti Cambridge Philosophical Society. Ìlànà Beardwood, Halton àti Hammersley pèsè ojútùú tó wúlò sí ìṣòro oníṣòwò arìnrìn-àjò. Àwọn òǹkọwé náà lo ìlànà kan láti mọ bí ọnà tó ṣe ṣókí jù lọ tí oníṣòwò kan lè gbà láti ilé kan tàbí ọfíìsì kan ṣe máa gùn tó, kó tó pa dà síbi tó ti bẹrẹ.  Láwọn ọdún tó tẹ lé e, ọpọ àwọn olùṣèwádìí nínú ìmọ ìṣirò, ìmọ kọǹpútà, ìmọ kẹmíkà, ìmọ nípa ohun alààyè àti àwọn ìmọ sáyẹǹsì míì ló kẹkọọ nípa ìṣòro yìí. Ní àwọn ọdún 1960, bí ó tilẹ rí bẹẹ, wọn dá ọnà tuntun kan, tí dípò wíwá ojútùú tí ó dára jùlọ yóò mú ojútùú kan jáde tí gígùn rẹ jẹ èyí tí ó mọ ní ààlà pẹlú ọpọlọpọ gígùn tí ó dára jùlọ, àti ní ṣíṣe bẹẹ yóò dá àwọn ààlà ìsàlẹ fún ìṣòro náà; àwọn ààlà ìsàlẹ wọnyí ni a ó lò pẹlú ẹka àti àwọn ọnà tí ó mọ. Ọna kan lati ṣe eyi ni lati ṣẹda igi ti o kere ju ti graph ati lẹhinna ilọpo meji gbogbo awọn eti rẹ, eyiti o ṣe agbejade opin pe gigun irin-ajo ti o dara julọ jẹ julọ ni ilọpo meji ti iwuwo ti igi ti o kere ju.  Ní ọdún 1976, Christofides àti Serdyukov ṣe ìtẹsíwájú ńlá ní ọnà yìí: ìlànà Christofides-Serdyukov mú ìdáhùn kan jáde tí, nínú ọràn tó burú jùlọ, ó ju ìdáhùn tí ó dára jù lọ lọ ní ìlọpo méjì àti ààbọ. Níwọn bó ti jẹ pé ìlànà ìṣirò náà rọrùn, ó sì yára, ọpọ èèyàn ló nírètí pé ó máa jẹ kí àwọn èèyàn lè rí ojútùú tó dára jù lọ. Sibẹsibẹ, ireti yii fun ilọsiwaju ko ṣe lẹsẹkẹsẹ, ati pe Christofides-Serdyukov wa ni ọna pẹlu iṣẹlẹ ti o buru julọ julọ titi di ọdun 2011, nigbati a ṣe agbekalẹ algorithm isunmọ ti o ni ilọsiwaju diẹ pupọ fun apakan ti awọn aworan TSPs. Ni ọdun 2020 ilọsiwaju kekere yii ni a gbooro si TSP metric TSP ni kikun.  Richard M. Karp fi han ni 1972 pe iṣoro iyika Hamiltonian jẹ NP-pupọ, eyiti o tumọ si lile NP ti TSP. Èyí fúnni ní àlàyé ìṣirò fún ìṣòro tí ó hàn gbangba-gbàǹgbà nínú wíwá àwọn ìrìn-àjò tí ó dára jùlọ.  Ìlọsíwájú ńlá ni a ṣe ní òpin àwọn ọdún 1970 àti 1980, nígbà tí Grötschel, Padberg, Rinaldi àti àwọn mìíràn ṣàṣeyọrí láti yanjú àwọn ọràn pẹlú àwọn ìlú 2,392, nípa lílo àwọn ọkọ òfuurufú tí wọn ń gé àti ẹka àti ìlà.  Ni awọn ọdun 1990, Applegate, Bixby, Chvátal, ati Cook ṣe agbekalẹ eto Concorde ti a ti lo ni ọpọlọpọ awọn iṣeduro igbasilẹ to ṣẹṣẹ. Gerhard Reinelt ṣe atẹjade TSPLIB ni ọdun 1991, akojọpọ awọn iṣẹlẹ itọkasi ti o yatọ si iṣoro, eyiti o ti lo nipasẹ ọpọlọpọ awọn ẹgbẹ iwadi fun afiwe awọn abajade. Ni ọdun 2006, Cook ati awọn miiran ṣe iṣiro irin-ajo ti o dara julọ nipasẹ apẹẹrẹ ilu 85,900 ti a fun nipasẹ iṣoro iṣeto microchip, lọwọlọwọ apẹẹrẹ TSPLIB ti o tobi julọ ti o yanju. Fún ọpọlọpọ àwọn ọràn mìíràn pẹlú ọkẹ àìmọye àwọn ìlú, a lè rí àwọn ojútùú tí ó dájú pé ó wà ní ààlà 23 ti ìrìn àjò tí ó dára jùlọ. :  Ọrúndún kọkàndínlógún - àwọn onímọ ìṣirò ọmọ ilẹ Ireland, William Rowan Hamilton àti onímọ ìṣirò ọmọ ilẹ Gẹẹsì, Thomas Kirkman, ló kọ ọ lọnà ìṣirò fún ìgbà àkọkọ  1930s - Àwọn onímọ ìṣirò ní Vienna àti ní Harvard kọkọ kẹkọọ nípa rẹ, pàápàá jùlọ Karl Menger àti Merill M. Flood tí ó ń wá ojútùú sí ọrọ bí wọn ṣe ń darí ọkọ akẹkọọ.  1959 - Jillian Beardwood, J.H. Halton àti John Hammersley tẹ àpilẹkọ kan jáde tí àkọlé rẹ jẹ The Shortest Path Through Many Points nínú ìwé ìròyìn ti Cambridge Philosophical Society, èyí tí ó pèsè ojútùú tí ó wúlò àkọkọ.  1960s - ọna tuntun ni a ṣẹda, eyiti o ṣe agbekalẹ ojutu kan ti gigun rẹ jẹ eyiti o ni idiwọn nipasẹ ọpọlọpọ ti gigun ti o dara julọ.  1972 - Richard M. Karp fi hàn wípé ìṣòro àyíká Hamiltonian jẹ NP-kúnrẹrẹ, èyí tí ó túmọ sí NP-ìmújútó ìṣòro oníṣòwò arìnrìn-àjò.  1976 - Christofides ati Serdyukov ṣe agbekalẹ alugoridimu tuntun, eyi ti o funni ni ojutu ti o buru julọ ni o kere ju awọn akoko 1.5 ju ojutu ti o dara julọ lọ.  1990s - Applegate, Bixby, Chvátal, àti Cook gbé ètò Concorde tí a ti lò nínú ọpọ àwọn àtúnṣe àkọsílẹ tí ó ṣẹṣẹ ṣe.  1991 - Gerhard Reinelt tẹ TSPLIB, àkójọpọ àwọn àpẹẹrẹ ìfiwéra tí ó yàtọ síra, èyí tí ọpọ àwùjọ ìwádìí ti lò láti fi àbájáde wéra  2006 - Cook ati awọn miiran ṣe iṣiro irin-ajo ti o dara julọ nipasẹ apẹẹrẹ ilu 85,900 ti a fun nipasẹ iṣoro iṣeto microchip, lọwọlọwọ apẹẹrẹ TSPLIB ti o tobi julọ ti o yanju.  2011 - A ṣe atunṣe algorithm ti o sunmọ diẹ fun ipin ti awọn aworan iṣoro oniṣowo irin-ajo.  2020 - A ṣe àtúnṣe díẹ sí àtòjọ àtòjọ tí a ṣe fún àwùjọ àwòrán-àwòrán láti bo gbogbo ìṣòro oníṣòwò arìnrìn-àjò. 