ट्रैवलिंग सेल्समैन समस्या की उत्पत्ति स्पष्ट नहीं है। 1832 से यात्रा करने वाले सेल्समैन के लिए एक पुस्तिका में समस्या का उल्लेख है और इसमें जर्मनी और स्विटज़रलैंड के उदाहरण दौरे शामिल हैं, लेकिन इसमें कोई गणितीय उपचार नहीं है।


विलियम रोवन हैमिल्टन
टीएसपी को गणितीय रूप से 19वीं शताब्दी में आयरिश गणितज्ञ विलियम रोवन हैमिल्टन और ब्रिटिश गणितज्ञ थॉमस किर्कमैन द्वारा तैयार किया गया था। हैमिल्टन का इकोसियन गेम हैमिल्टनियन चक्र खोजने पर आधारित एक मनोरंजक पहेली थी। ऐसा प्रतीत होता है कि टीएसपी के सामान्य रूप का अध्ययन पहली बार 1930 के दशक के दौरान वियना और हार्वर्ड में गणितज्ञों द्वारा किया गया था, विशेष रूप से कार्ल मेन्जर द्वारा, जो समस्या को परिभाषित करते हैं, स्पष्ट जानवर-बल एल्गोरिथ्म पर विचार करते हैं, और निकटतम की गैर-इष्टतमता का निरीक्षण करते हैं। पड़ोसी अनुमानी:

हम संदेशवाहक समस्या से निरूपित करते हैं (चूँकि व्यवहार में यह प्रश्न प्रत्येक डाकिया द्वारा हल किया जाना चाहिए, वैसे भी कई यात्रियों द्वारा भी), बहुत से बिंदुओं के लिए, जिनकी जोड़ीदार दूरियाँ ज्ञात हैं, बिंदुओं को जोड़ने वाला सबसे छोटा मार्ग खोजने का कार्य। निःसंदेह, यह समस्या सीमित रूप से अनेक परीक्षणों द्वारा हल की जा सकती है। ऐसे नियम ज्ञात नहीं हैं जो परीक्षणों की संख्या को दिए गए बिंदुओं के क्रमपरिवर्तन की संख्या से नीचे धकेल देंगे। यह नियम कि किसी को पहले शुरुआती बिंदु से निकटतम बिंदु तक जाना चाहिए, फिर उसके निकटतम बिंदु तक जाना चाहिए, आदि, सामान्य तौर पर सबसे छोटा मार्ग नहीं देता है।

गणितीय रूप से इस पर पहली बार 1930 के दशक में मेरिल एम. फ्लड द्वारा विचार किया गया था जो स्कूल बस रूटिंग समस्या को हल करना चाह रहे थे। प्रिंसटन विश्वविद्यालय में हस्लर व्हिटनी ने इस समस्या में रुचि पैदा की, जिसे उन्होंने "48 राज्यों की समस्या" कहा। "ट्रैवलिंग सेल्समैन समस्या" वाक्यांश का उपयोग करने वाला सबसे पहला प्रकाशन जूलिया रॉबिन्सन की 1949 रैंड कॉर्पोरेशन रिपोर्ट थी, "हैमिल्टनियन गेम पर (एक ट्रैवलिंग सेल्समैन समस्या)।"

1950 और 1960 के दशक में, सांता मोनिका में RAND कॉर्पोरेशन द्वारा समस्या को हल करने में उठाए गए कदमों के लिए पुरस्कार की पेशकश के बाद यह समस्या यूरोप और संयुक्त राज्य अमेरिका में वैज्ञानिक हलकों में तेजी से लोकप्रिय हो गई। रैंड कॉर्पोरेशन के जॉर्ज डेंटज़िग, डेलबर्ट रे फुलकर्सन और सेल्मर एम. जॉनसन द्वारा उल्लेखनीय योगदान दिया गया, जिन्होंने समस्या को एक पूर्णांक रैखिक कार्यक्रम के रूप में व्यक्त किया और इसके समाधान के लिए कटिंग प्लेन विधि विकसित की। उन्होंने वह लिखा जो इस विषय पर मौलिक पेपर माना जाता है जिसमें इन नए तरीकों से उन्होंने एक दौरे का निर्माण करके 49 शहरों के साथ एक उदाहरण को इष्टतमता से हल किया और साबित किया कि कोई अन्य दौरा छोटा नहीं हो सकता है। हालाँकि, डैंटज़िग, फुलकर्सन और जॉनसन ने अनुमान लगाया कि निकट इष्टतम समाधान दिए जाने पर हम थोड़ी संख्या में अतिरिक्त असमानताएँ (कटौती) जोड़कर इष्टतमता खोजने या इष्टतमता साबित करने में सक्षम हो सकते हैं। उन्होंने इस विचार का उपयोग स्ट्रिंग मॉडल का उपयोग करके अपनी प्रारंभिक 49 शहर की समस्या को हल करने के लिए किया। उन्होंने पाया कि 49 शहरों की समस्या के समाधान के लिए उन्हें केवल 26 कटौती की आवश्यकता है। हालाँकि इस पेपर ने टीएसपी समस्याओं के लिए एक एल्गोरिथम दृष्टिकोण नहीं दिया, लेकिन इसके भीतर मौजूद विचार टीएसपी के लिए बाद में सटीक समाधान विधियों को बनाने के लिए अपरिहार्य थे, हालांकि इन कटों को बनाने में एक एल्गोरिथम दृष्टिकोण खोजने में 15 साल लगेंगे। प्लेन विधियों को काटने के साथ-साथ, डेंटज़िग, फुलकर्सन और जॉनसन ने शायद पहली बार शाखा और बाउंड एल्गोरिदम का उपयोग किया।

1959 में, जिलियन बियर्डवुड, जे.एच. हॉल्टन और जॉन हैमरस्ले ने कैम्ब्रिज फिलॉसॉफिकल सोसाइटी की पत्रिका में "द शॉर्टेस्ट पाथ थ्रू मैनी पॉइंट्स" शीर्षक से एक लेख प्रकाशित किया। बियर्डवुड-हाल्टन-हैमरस्ले प्रमेय ट्रैवलिंग सेल्समैन समस्या का व्यावहारिक समाधान प्रदान करता है। लेखकों ने एक सेल्समैन के लिए सबसे छोटे मार्ग की लंबाई निर्धारित करने के लिए एक एसिम्प्टोटिक फॉर्मूला निकाला, जो घर या कार्यालय से शुरू होता है और शुरुआत में लौटने से पहले निश्चित संख्या में स्थानों का दौरा करता है।

अगले दशकों में, गणित, कंप्यूटर विज्ञान, रसायन विज्ञान, भौतिकी और अन्य विज्ञान के कई शोधकर्ताओं द्वारा इस समस्या का अध्ययन किया गया। हालाँकि, 1960 के दशक में, एक नया दृष्टिकोण बनाया गया था, कि इष्टतम समाधान खोजने के बजाय एक ऐसा समाधान तैयार किया जाएगा जिसकी लंबाई इष्टतम लंबाई के गुणक द्वारा सीमित हो, और ऐसा करने से समस्या के लिए निचली सीमाएं पैदा होंगी; फिर इन निचली सीमाओं का उपयोग शाखा और बाउंड दृष्टिकोण के साथ किया जाएगा। ऐसा करने का एक तरीका ग्राफ़ का एक न्यूनतम स्पैनिंग ट्री बनाना और फिर उसके सभी किनारों को दोगुना करना था, जिससे यह सीमा उत्पन्न होती है कि एक इष्टतम दौरे की लंबाई न्यूनतम स्पैनिंग ट्री के वजन से अधिकतम दोगुनी होती है।

1976 में, क्रिस्टोफ़ाइड्स और सेरड्यूकोव ने एक-दूसरे से स्वतंत्र रूप से इस दिशा में बड़ी प्रगति की: क्रिस्टोफ़ाइड्स-सेरड्यूकोव एल्गोरिथ्म एक समाधान देता है, जो सबसे खराब स्थिति में, इष्टतम समाधान से अधिकतम 1.5 गुना लंबा है। चूंकि एल्गोरिदम सरल और त्वरित था, कई लोगों को उम्मीद थी कि यह लगभग इष्टतम समाधान विधि का मार्ग प्रशस्त करेगा। हालाँकि, सुधार की यह आशा तुरंत पूरी नहीं हुई, और क्रिस्टोफ़ाइड्स-सेरड्यूकोव 2011 तक सबसे खराब स्थिति वाली विधि बनी रही, जब "ग्राफ़िकल" टीएसपी के सबसेट के लिए एक (बहुत) थोड़ा बेहतर सन्निकटन एल्गोरिदम विकसित किया गया था। 2020 में इस छोटे से सुधार को पूर्ण (मीट्रिक) टीएसपी तक बढ़ा दिया गया।

रिचर्ड एम. कार्प ने 1972 में दिखाया कि हैमिल्टनियन चक्र समस्या एनपी-पूर्ण थी, जिसका तात्पर्य टीएसपी की एनपी-कठोरता से है। इसने इष्टतम पर्यटन खोजने की स्पष्ट कम्प्यूटेशनल कठिनाई के लिए गणितीय स्पष्टीकरण प्रदान किया।

1970 और 1980 के दशक के उत्तरार्ध में बड़ी प्रगति हुई, जब ग्रोट्सचेल, पैडबर्ग, रिनाल्डी और अन्य लोग कटिंग प्लेन और शाखा और बाउंड का उपयोग करके 2,392 शहरों तक के उदाहरणों को सटीक रूप से हल करने में कामयाब रहे।

1990 के दशक में, Applegate, Bixby, Chvátal, और Cook ने Concorde प्रोग्राम विकसित किया जिसका उपयोग हाल के कई रिकॉर्ड समाधानों में किया गया है। गेरहार्ड रीनेल्ट ने 1991 में टीएसपीएलआईबी प्रकाशित किया, जो अलग-अलग कठिनाई के बेंचमार्क उदाहरणों का एक संग्रह है, जिसका उपयोग परिणामों की तुलना करने के लिए कई शोध समूहों द्वारा किया गया है। 2006 में, कुक और अन्य ने माइक्रोचिप लेआउट समस्या द्वारा दिए गए 85,900-शहर के उदाहरण के माध्यम से एक इष्टतम दौरे की गणना की, जो वर्तमान में सबसे बड़ा हल किया गया TSPLIB उदाहरण है। लाखों शहरों के कई अन्य उदाहरणों के लिए, ऐसे समाधान ढूंढे जा सकते हैं जो इष्टतम दौरे के 2-3% के भीतर होने की गारंटी देते हैं।
* 19वीं सदी - आयरिश गणितज्ञ विलियम रोवन हैमिल्टन और ब्रिटिश गणितज्ञ थॉमस किर्कमैन द्वारा पहली बार गणितीय रूप से तैयार किया गया।
* 1930 के दशक - सबसे पहले वियना और हार्वर्ड में गणितज्ञों द्वारा अध्ययन किया गया, विशेष रूप से कार्ल मेन्जर और मेरिल एम. फ्लड द्वारा, जो स्कूल बस रूटिंग समस्या को हल करना चाह रहे थे।
* 1959 - जिलियन बियर्डवुड, जे.एच. हॉल्टन और जॉन हैमरस्ले ने कैम्ब्रिज फिलॉसॉफिकल सोसाइटी की पत्रिका में "द शॉर्टेस्ट पाथ थ्रू मैनी पॉइंट्स" शीर्षक से एक लेख प्रकाशित किया, जिसने पहला व्यावहारिक समाधान प्रदान किया।
* 1960 का दशक - नया दृष्टिकोण बनाया गया, जो एक ऐसा समाधान तैयार करता है जिसकी लंबाई इष्टतम लंबाई के गुणक से सिद्ध होती है।
* 1972 - रिचर्ड एम. कार्प ने दिखाया कि हैमिल्टनियन चक्र समस्या एनपी-पूर्ण थी, जिसका तात्पर्य ट्रैवलिंग सेल्समैन समस्या की एनपी-कठोरता से है।
* 1976 - क्रिस्टोफ़ाइड्स और सेरड्यूकोव ने स्वतंत्र रूप से नए एल्गोरिदम का आविष्कार किया, जो एक ऐसा समाधान देता है जो सबसे खराब स्थिति में इष्टतम समाधान से अधिकतम 1.5 गुना लंबा होता है।
* 1990 के दशक - Applegate, Bixby, Chvátal, और Cook ने Concorde प्रोग्राम विकसित किया जिसका उपयोग हाल के कई रिकॉर्ड समाधानों में किया गया है।
* 1991 - गेरहार्ड रीनेल्ट ने टीएसपीएलआईबी प्रकाशित किया, जो अलग-अलग कठिनाई के बेंचमार्क उदाहरणों का एक संग्रह है, जिसका उपयोग परिणामों की तुलना करने के लिए कई शोध समूहों द्वारा किया गया है।
* 2006 - कुक और अन्य ने माइक्रोचिप लेआउट समस्या द्वारा दिए गए 85,900-शहर के उदाहरण के माध्यम से एक इष्टतम दौरे की गणना की, जो वर्तमान में सबसे बड़ा हल किया गया टीएसपीएलआईबी उदाहरण है।
* 2011 - "ग्राफ़िकल" ट्रैवलिंग सेल्समैन समस्या के सबसेट के लिए थोड़ा बेहतर सन्निकटन एल्गोरिदम विकसित किया गया है।
* 2020 - "ग्राफ़िकल" के सबसेट के लिए विकसित थोड़ा बेहतर सन्निकटन एल्गोरिथ्म को पूर्ण ट्रैवलिंग सेल्समैन समस्या को कवर करने के लिए बढ़ाया गया है।
ट्रैवलिंग सेल्समैन समस्या की उत्पत्ति स्पष्ट नहीं है। 1832 से यात्रा करने वाले सेल्समैन के लिए एक पुस्तिका में समस्या का उल्लेख है और इसमें जर्मनी और स्विटज़रलैंड के उदाहरण दौरे शामिल हैं, लेकिन इसमें कोई गणितीय उपचार नहीं है।


विलियम रोवन हैमिल्टन
टीएसपी को गणितीय रूप से 19वीं शताब्दी में आयरिश गणितज्ञ विलियम रोवन हैमिल्टन और ब्रिटिश गणितज्ञ थॉमस किर्कमैन द्वारा तैयार किया गया था। हैमिल्टन का इकोसियन गेम हैमिल्टनियन चक्र खोजने पर आधारित एक मनोरंजक पहेली थी। ऐसा प्रतीत होता है कि टीएसपी के सामान्य रूप का अध्ययन पहली बार 1930 के दशक के दौरान वियना और हार्वर्ड में गणितज्ञों द्वारा किया गया था, विशेष रूप से कार्ल मेन्जर द्वारा, जो समस्या को परिभाषित करते हैं, स्पष्ट जानवर-बल एल्गोरिथ्म पर विचार करते हैं, और निकटतम की गैर-इष्टतमता का निरीक्षण करते हैं। पड़ोसी अनुमानी:

हम संदेशवाहक समस्या से निरूपित करते हैं (चूँकि व्यवहार में यह प्रश्न प्रत्येक डाकिया द्वारा हल किया जाना चाहिए, वैसे भी कई यात्रियों द्वारा भी), बहुत से बिंदुओं के लिए, जिनकी जोड़ीदार दूरियाँ ज्ञात हैं, बिंदुओं को जोड़ने वाला सबसे छोटा मार्ग खोजने का कार्य। निःसंदेह, यह समस्या सीमित रूप से अनेक परीक्षणों द्वारा हल की जा सकती है। ऐसे नियम ज्ञात नहीं हैं जो परीक्षणों की संख्या को दिए गए बिंदुओं के क्रमपरिवर्तन की संख्या से नीचे धकेल देंगे। यह नियम कि किसी को पहले शुरुआती बिंदु से निकटतम बिंदु तक जाना चाहिए, फिर उसके निकटतम बिंदु तक जाना चाहिए, आदि, सामान्य तौर पर सबसे छोटा मार्ग नहीं देता है।

गणितीय रूप से इस पर पहली बार 1930 के दशक में मेरिल एम. फ्लड द्वारा विचार किया गया था जो स्कूल बस रूटिंग समस्या को हल करना चाह रहे थे। प्रिंसटन विश्वविद्यालय में हस्लर व्हिटनी ने इस समस्या में रुचि पैदा की, जिसे उन्होंने "48 राज्यों की समस्या" कहा। "ट्रैवलिंग सेल्समैन समस्या" वाक्यांश का उपयोग करने वाला सबसे पहला प्रकाशन जूलिया रॉबिन्सन की 1949 रैंड कॉर्पोरेशन रिपोर्ट थी, "हैमिल्टनियन गेम पर (एक ट्रैवलिंग सेल्समैन समस्या)।"

1950 और 1960 के दशक में, सांता मोनिका में RAND कॉर्पोरेशन द्वारा समस्या को हल करने में उठाए गए कदमों के लिए पुरस्कार की पेशकश के बाद यह समस्या यूरोप और संयुक्त राज्य अमेरिका में वैज्ञानिक हलकों में तेजी से लोकप्रिय हो गई। रैंड कॉर्पोरेशन के जॉर्ज डेंटज़िग, डेलबर्ट रे फुलकर्सन और सेल्मर एम. जॉनसन द्वारा उल्लेखनीय योगदान दिया गया, जिन्होंने समस्या को एक पूर्णांक रैखिक कार्यक्रम के रूप में व्यक्त किया और इसके समाधान के लिए कटिंग प्लेन विधि विकसित की। उन्होंने वह लिखा जो इस विषय पर मौलिक पेपर माना जाता है जिसमें इन नए तरीकों से उन्होंने एक दौरे का निर्माण करके 49 शहरों के साथ एक उदाहरण को इष्टतमता से हल किया और साबित किया कि कोई अन्य दौरा छोटा नहीं हो सकता है। हालाँकि, डैंटज़िग, फुलकर्सन और जॉनसन ने अनुमान लगाया कि निकट इष्टतम समाधान दिए जाने पर हम थोड़ी संख्या में अतिरिक्त असमानताएँ (कटौती) जोड़कर इष्टतमता खोजने या इष्टतमता साबित करने में सक्षम हो सकते हैं। उन्होंने इस विचार का उपयोग स्ट्रिंग मॉडल का उपयोग करके अपनी प्रारंभिक 49 शहर की समस्या को हल करने के लिए किया। उन्होंने पाया कि 49 शहरों की समस्या के समाधान के लिए उन्हें केवल 26 कटौती की आवश्यकता है। हालाँकि इस पेपर ने टीएसपी समस्याओं के लिए एक एल्गोरिथम दृष्टिकोण नहीं दिया, लेकिन इसके भीतर मौजूद विचार टीएसपी के लिए बाद में सटीक समाधान विधियों को बनाने के लिए अपरिहार्य थे, हालांकि इन कटों को बनाने में एक एल्गोरिथम दृष्टिकोण खोजने में 15 साल लगेंगे। प्लेन विधियों को काटने के साथ-साथ, डेंटज़िग, फुलकर्सन और जॉनसन ने शायद पहली बार शाखा और बाउंड एल्गोरिदम का उपयोग किया।

1959 में, जिलियन बियर्डवुड, जे.एच. हॉल्टन और जॉन हैमरस्ले ने कैम्ब्रिज फिलॉसॉफिकल सोसाइटी की पत्रिका में "द शॉर्टेस्ट पाथ थ्रू मैनी पॉइंट्स" शीर्षक से एक लेख प्रकाशित किया। बियर्डवुड-हाल्टन-हैमरस्ले प्रमेय ट्रैवलिंग सेल्समैन समस्या का व्यावहारिक समाधान प्रदान करता है। लेखकों ने एक सेल्समैन के लिए सबसे छोटे मार्ग की लंबाई निर्धारित करने के लिए एक एसिम्प्टोटिक फॉर्मूला निकाला, जो घर या कार्यालय से शुरू होता है और शुरुआत में लौटने से पहले निश्चित संख्या में स्थानों का दौरा करता है।

अगले दशकों में, गणित, कंप्यूटर विज्ञान, रसायन विज्ञान, भौतिकी और अन्य विज्ञान के कई शोधकर्ताओं द्वारा इस समस्या का अध्ययन किया गया। हालाँकि, 1960 के दशक में, एक नया दृष्टिकोण बनाया गया था, कि इष्टतम समाधान खोजने के बजाय एक ऐसा समाधान तैयार किया जाएगा जिसकी लंबाई इष्टतम लंबाई के गुणक द्वारा सीमित हो, और ऐसा करने से समस्या के लिए निचली सीमाएं पैदा होंगी; फिर इन निचली सीमाओं का उपयोग शाखा और बाउंड दृष्टिकोण के साथ किया जाएगा। ऐसा करने का एक तरीका ग्राफ़ का एक न्यूनतम स्पैनिंग ट्री बनाना और फिर उसके सभी किनारों को दोगुना करना था, जिससे यह सीमा उत्पन्न होती है कि एक इष्टतम दौरे की लंबाई न्यूनतम स्पैनिंग ट्री के वजन से अधिकतम दोगुनी होती है।

1976 में, क्रिस्टोफ़ाइड्स और सेरड्यूकोव ने एक-दूसरे से स्वतंत्र रूप से इस दिशा में बड़ी प्रगति की: क्रिस्टोफ़ाइड्स-सेरड्यूकोव एल्गोरिथ्म एक समाधान देता है, जो सबसे खराब स्थिति में, इष्टतम समाधान से अधिकतम 1.5 गुना लंबा है। चूंकि एल्गोरिदम सरल और त्वरित था, कई लोगों को उम्मीद थी कि यह लगभग इष्टतम समाधान विधि का मार्ग प्रशस्त करेगा। हालाँकि, सुधार की यह आशा तुरंत पूरी नहीं हुई, और क्रिस्टोफ़ाइड्स-सेरड्यूकोव 2011 तक सबसे खराब स्थिति वाली विधि बनी रही, जब "ग्राफ़िकल" टीएसपी के सबसेट के लिए एक (बहुत) थोड़ा बेहतर सन्निकटन एल्गोरिदम विकसित किया गया था। 2020 में इस छोटे से सुधार को पूर्ण (मीट्रिक) टीएसपी तक बढ़ा दिया गया।

रिचर्ड एम. कार्प ने 1972 में दिखाया कि हैमिल्टनियन चक्र समस्या एनपी-पूर्ण थी, जिसका तात्पर्य टीएसपी की एनपी-कठोरता से है। इसने इष्टतम पर्यटन खोजने की स्पष्ट कम्प्यूटेशनल कठिनाई के लिए गणितीय स्पष्टीकरण प्रदान किया।

1970 और 1980 के दशक के उत्तरार्ध में बड़ी प्रगति हुई, जब ग्रोट्सचेल, पैडबर्ग, रिनाल्डी और अन्य लोग कटिंग प्लेन और शाखा और बाउंड का उपयोग करके 2,392 शहरों तक के उदाहरणों को सटीक रूप से हल करने में कामयाब रहे।

1990 के दशक में, Applegate, Bixby, Chvátal, और Cook ने Concorde प्रोग्राम विकसित किया जिसका उपयोग हाल के कई रिकॉर्ड समाधानों में किया गया है। गेरहार्ड रीनेल्ट ने 1991 में टीएसपीएलआईबी प्रकाशित किया, जो अलग-अलग कठिनाई के बेंचमार्क उदाहरणों का एक संग्रह है, जिसका उपयोग परिणामों की तुलना करने के लिए कई शोध समूहों द्वारा किया गया है। 2006 में, कुक और अन्य ने माइक्रोचिप लेआउट समस्या द्वारा दिए गए 85,900-शहर के उदाहरण के माध्यम से एक इष्टतम दौरे की गणना की, जो वर्तमान में सबसे बड़ा हल किया गया TSPLIB उदाहरण है। लाखों शहरों के कई अन्य उदाहरणों के लिए, ऐसे समाधान ढूंढे जा सकते हैं जो इष्टतम दौरे के 2-3% के भीतर होने की गारंटी देते हैं।