फिरत्या विक्रेत्याची समस्या हा संशोधन क्षेत्रातील एक महत्त्वाचा प्रश्न आहे. या प्रश्नाच्या नावामागे विक्रीच्या कामाशी संबंधित असलेल्या एखाद्या माणसाला अनेक गावांना भेट द्यायची असेल तर त्यासाठीचा प्रवास त्याला कमीत कमी वेळात कसा करता येईल ही संकल्पना आहे.
या प्रश्नाचे विधान असे : आकृतीमध्ये दाखविल्याप्रमाणे 1 या ठिकाणापासून सुरुवात करून 2 ते 5 या ठिकाणांना फक्त एकदाच भेट देऊन शेवटी पुन्हा एकदा सुरुवातीच्या ठिकाणी, म्हणजे 1 या अंकाच्या ठिकाणी परत यायचे आहे. या प्रवासासाठी 1 – 2 – 4 – 5 – 3 – 1 किंवा याच प्रकारे आपण 1 – 5 – 2 – 3 – 4 – 1 किंवा अशाच अन्य मार्गांचा वापर करता येऊ शकतो.
वरील प्रकारच्या उदाहरणांमध्ये कोणत्याही ठिकाणापासून दुसर्‍या कोणत्याही ठिकाणापर्यंत जाता येईल असे गृहीत धरलेले असते. म्हणजेच 1 या ठिकाणापासून थेट 2 किंवा 3 किंवा 4 किंवा 5 या ठिकाणापर्यंत जाता येऊ शकते. तसेच 2 या ठिकाणापासूनसुद्धा इतर कोणत्याही ठिकाणापर्यंत थेट जाता येते. उदाहरणात रस्ते एकदम सरळ दाखवलेले असले तरी प्रत्यक्षात ते वेडेवाकडे असू शकतात.
असे अनेक पर्याय उपलब्ध असताना त्यातील सगळ्यात योग्य पर्याय कोणता हे ठरवण्यासाठी “फिरत्या विक्रेत्याची समस्या” या प्रश्नाची मदत होते. वरील उदाहरणामध्ये अंकांऐवजी गावे आहेत असे आपण मानले तर एका गावाहून दुसऱ्या, दुसऱ्या गावाहून तिसर्‍या, असे करत करत विक्रेता शेवटी मूळ गावी परतायला हवा. तसेच वाटेतील प्रत्येक गावाला त्याने एकदाच भेट द्यायला हवी. या अटीमुळे याचा आलेख सिद्धांत (Graph Theory) या संकल्पनेशीही संबंध आहे. कमीत कमी वेळात पोहोचविणारा मार्ग ठरविणे हा या प्रश्नामागील मूळ उद्देश आहे. त्यासाठी मुळात एका ठिकाणापासून दुसऱ्या ठिकाणापर्यंत जाण्यासाठीचे अंतर किती हे माहीत असणे आवश्यक आहे. ही माहिती नमुन्यादाखल खाली दिलेल्या तक्त्याप्रमाणे आहे असे समजू.
या तक्त्यामध्ये पहिल्या ओळीतील पहिल्या स्तंभात शून्य हा अंक आहे. याचा अर्थ असा : 1 या ठिकाणापासून 1 या ठिकाणापर्यंत जाणे म्हणजे आहे तिथेच थांबणे असल्यामुळे त्यासाठीचे अंतर शून्य आहे; ठिकाण 1 व 2 मधील अंतर 10; ठिकाण 1 व 3 मधील अंतर 8; ठिकाण 2 व 4 मधील अंतर 5; ठिकाण 4 व 5 मधील अंतर 6 इत्यादी
या माहितीच्या आधारे 1 या ठिकाणापासून सुरुवात करून उरलेल्या प्रत्येक ठिकाणाला बरोबर एकदाच भेट देऊन शेवटी पुन्हा 1 या आपल्या मूळ ठिकाणी येण्यासाठी विक्रेता कमीत कमी प्रवास कसा करेल हे शोधावे लागते. उदाहरणार्थ वर उल्लेख केलेल्या 1 – 2 – 4 – 5 – 3 – 1 या मार्गानुसार प्रवास केला तर विक्रेत्याला 10 + 5 + 6 + 9 + 8 = 38 (ठिकाणांमधील अंतरांची बेरीज) इतके फिरावे लागेल. याऐवजी विक्रेत्याने 1 – 5 – 2 – 3 – 4 – 1 असा प्रवास केला तर त्याला 7 + 6 + 10 + 8 + 9 = 40 इतके अंतर जावे लागेल. म्हणजेच पहिल्या पर्यायापेक्षा हे अंतर जास्त आहे. म्हणूनच या दुसऱ्या पर्यायापेक्षा पहिल्या पर्यायाला प्राधान्य दिले जाईल. अर्थातच अशा प्रकारे तक्त्यातील इतरही सर्व पर्याय तपासून पहावे लागतील आणि त्यांतील सर्वांत कमी अंतराचा; म्हणजेच सगळ्यात कमी वेळ घेणारा आणि सगळ्यात कमी खर्चिक पर्याय कोणता आहे हे तपासावे लागेल. त्यातून मिळणारा अपेक्षित पर्याय हे या प्रश्नाचे उत्तर असेल.
‘ट्रॅव्हलिंग सेल्समन प्रॉब्लेम’ इथे संपत नाही. या उदाहरणामध्ये 1 या ठिकाणापासूनच सुरुवात करायची असे गृहीत धरलेले आहे. प्रत्यक्षात मात्र सुरुवात 1 या ठिकाणाऐवजी 2, 3, 4 किंवा 5 यांपैकी कोणत्याही ठिकाणाहून होऊ शकेल असे गृहीत धरून सर्वांत प्रभावी मार्ग कोणता याचाही शोध घेणे अपेक्षित असते.
एखाद्या कारखान्यामध्ये कच्च्या मालावर प्रक्रिया होत असताना नेमक्या कोणत्या क्रमाने प्रक्रिया करायची हे ठरविण्यासाठी ‘ट्रॅव्हलिंग सेल्समन प्रॉब्लेम’चा उपयोग होऊ शकतो. अनेक कामांची यादी समोर असताना, सुरुवात कोणत्या कामाने करावयाची व पुढे हा क्रम कसा ठेवायचा हे ठरविण्यासाठी या प्रश्नाची मदत होऊ शकते. हा प्रश्न सोडवण्यासाठी आलेख सिद्धांताऐवजी पूर्णांक रेषीय कार्यक्रमण (Integer Linear Programming) या पद्धतीचा देखील उपयोग करता येतो.
इ.स. 1800 च्या दशकात डब्ल्यू. आर. हॅमिल्टन (W. R. Hamilton) या आयरिश तसेच थॉमस किर्कमन (Thomas Kirkman) या गणितज्ज्ञांनी या प्रश्नाची गणिती संकल्पना प्रथम मांडली. अनेक सुधारणांनंतर 1960 च्या दशकात 49 शहरांचा प्रवास सर्वांत कमी वेळात करण्यासाठीचा मार्ग या संकल्पनेच्या आधारे ठरविण्यात आला. 2006 मध्ये संगणकाच्या मदतीने शहरांचा हा आकडा 85,900 वर गेला. आता कृत्रिम बुद्धिमत्तेच्या संकल्पनेचा वापर करून हा प्रश्न अधिक वेगाने आणि प्रभावीपणे सोडवणे शक्य झाले आहे.
संदर्भ :
- 50 Mathematical Ideas You Really Need to Know: Tony Crilly (Quercus)
- Advanced Operations Research Lecture by Prof G Srinivasan of IIT, Madras
- Encyclopedia of Operations Research and Management Science: Centennial Edition: Edited by Saul I Gass and Carl M Harris (Kluwer Academic Publishers)
- https://en.wikipedia.org/wiki/Travelling_salesman_problem#Description
समीक्षक : डॉ. व. ग. टिकेकर
