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à 2<unk>3% 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ò.