Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

कल्पना कीजिए कि आप एक डिलीवरी ड्राइवर हैं जिसके पास जाने के लिए बहुत सारे स्टॉप्स वाला एक नक्शा है। आप हर स्टॉप पर ठीक एक बार जाना चाहते हैं और वापस घर आना चाहते हैं, लेकिन आप कम से कम गैस जलाना चाहते हैं। यह क्लासिक "ट्रैवलिंग सेल्सपर्सन प्रॉब्लम" (Traveling Salesperson Problem) है, एक ऐसी पहेली जिसने दशकों से गणितज्ञों और कंप्यूटर वैज्ञानिकों को उलझा रखा है। यह सिर्फ डिलीवरी ट्रकों के बारे में नहीं है; यह स्मार्ट वाहनों के रूटिंग से लेकर कंप्यूटर चिप पर डेटा को व्यवस्थित करने तक सब कुछ है। पेचीदा हिस्सा यह है कि जैसे-जैसे आप स्टॉप्स की संख्या बढ़ाते हैं, संभावित मार्गों की संख्या इतनी तेजी से बढ़ती है कि दुनिया के सबसे तेज़ कंप्यूटर भी इस भूलभुलैया में खो सकते हैं।

इसे हल करने के लिए, कंप्यूटर अक्सर "कन्स्ट्रेंट प्रोग्रामिंग" (Constraint Programming) नामक विधि का उपयोग करते हैं। इसे एक सुपर-स्मार्ट जासूस की तरह समझें जो केवल बेतरतीब ढंग से रास्तों का अनुमान नहीं लगाता। इसके बजाय, जासूस तुरंत असंभव या मूर्खतापूर्ण विकल्पों को हटाने के लिए नियमों (कन्स्ट्रेंट्स) की एक श्रृंखला निर्धारित करता है। उदाहरण के लिए, "आप एक ही शहर में दो बार नहीं जा सकते" या "आप एक ऐसा घेरा नहीं बना सकते जो यात्रा के बाकी हिस्से को छोड़ देता हो।" आमतौर पर, जब समस्या में एक सपाट मानचित्र पर दूरियां शामिल होती हैं (जिसे वैज्ञानिक "यूक्लिडियन" मामला कहते हैं), तो कंप्यूटर उस मानचित्र को संख्याओं की एक सामान्य सूची की तरह मानता है, यह नजरअंदाज करते हुए कि स्टॉप वास्तव में सीधी रेखाओं और कोणों वाले कागज के टुकड़े पर खींचे गए हैं। यह एक शहर में नेविगेट करने जैसा है जहाँ आप केवल सड़कों के नामों की सूची देख रहे हैं, बिना कभी नक्शे को देखे।

यह शोध पत्र एक सरल लेकिन शक्तिशाली प्रश्न पूछता है: क्या होगा अगर हम नक्शे को अनदेखा करना बंद कर दें? लेखकों, एलेसांद्रो बर्टाग्नोन और मार्को गावेली ने निर्णय लिया कि वे अपने कंप्यूटर जासूस के लिए नए "नियम" बनाएंगे जो वास्तव में ज्यामिति (geometry) को समझते हैं। उन्होंने विशेष एल्गोरिदम बनाए जो जानते हैं कि एक आदर्श, सबसे छोटे पथ में, सड़कें आकाश में "X" की तरह एक-दूसरे को नहीं काटनी चाहिए, और बिंदुओं के एक समूह का बाहरी किनारा एक व्यवस्थित, गोलाकार क्रम में जाना चाहिए। कंप्यूटर को समस्या के आकार को "देखने" के लिए सिखाकर, उन्होंने पहले की तुलना में बहुत तेज़ी से लाखों खराब अनुमानों को काटने का तरीका खोज निकाला। उन्होंने यह भी दिखाया कि उनके ज्यामितीय नुस्खे तब भी काम करते हैं जब समस्या अधिक जटिल हो जाती है, जैसे कि जब आपको शहरों के एक समूह में जाना होता है लेकिन आपको उनमें से केवल एक पर रुकना होता है।

शोध का मुख्य निष्कर्ष

इस कार्य का मुख्य निष्कर्ष यह है कि ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP) के विशिष्ट ज्यामितीय गुणों का उपयोग करके—विशेष रूप से इस तथ्य का कि एक सपाट तल पर सबसे छोटा पथ खुद को कभी नहीं काटता है और एक आकार के बाहरी किनारे का अनुसरण करता है—कंप्यूटर इन रूटिंग पहेलियों को काफी तेज़ी से हल कर सकते हैं। लेखकों ने इन नए नियमों को "कन्स्ट्रेंट लॉजिक प्रोग्रामिंग" (CLP) नामक एक प्रोग्रामिंग भाषा में लागू किया।

उन्होंने अपने नए "ज्यामितीय फ़िल्टरिंग" का परीक्षण मौजूदा सर्वोत्तम विधियों के साथ किया। परिणाम चौंकाने वाले थे: 100 बिंदुओं तक के रैंडम मैप्स के लिए, उनके नए दृष्टिकोण ने सबसे अच्छा समाधान खोजने में लगने वाले समय को औसतन लगभग 70% कम कर दिया। कंप्यूटर के "सोचने के चरणों" (सर्च नोड्स) के मामले में, उन्होंने काम को लगभग 59% से 75% तक कम कर दिया, जो उपयोग की गई विशिष्ट रणनीति पर निर्भर करता है। इसका मतलब है कि कंप्यूटर ने न केवल प्रति चरण तेज़ी से सोचा; बल्कि उत्तर खोजने के लिए उसे बहुत कम चरणों के बारे में सोचना पड़ा।

उन्होंने क्या खारिज किया और कैसे किया

यह शोध पत्र स्पष्ट रूप से यूक्लिडियन TSP (जहाँ दूरियाँ एक तल पर सीधी रेखाएँ हैं) को सामान्य TSP के समान मानने के मानक दृष्टिकोण के विरुद्ध तर्क देता है। सामान्य विधि प्रत्येक जोड़े के बीच की दूरी की गणना करना, संख्याओं की एक विशाल तालिका बनाना और फिर जेनेरिक नियम लागू करना है। लेखक दिखाते हैं कि यह "अंधा" दृष्टिकोण उस मूल्यवान जानकारी को अनदेखा करता है जो पहले से ही मौजूद है: बिंदुओं के निर्देशांक (coordinates)। वे प्रदर्शित करते हैं कि ज्यामिति को अनदेखा करने से सर्च स्पेस बहुत बड़ा हो जाता है और समाधान धीमा हो जाता है।

वे यह भी स्पष्ट करते हैं कि उनका तरीका क्या नहीं है। वे यह दावा नहीं करते कि उन्होंने TSP को पूरी तरह से हल कर लिया है या किसी ऐसे जादुई हथियार का निर्माण किया है जो रूटिंग समस्या के हर प्रकार पर काम करता है। उदाहरण के लिए, वे नोट करते हैं कि उनका "नो-क्रॉसिंग" (कोई क्रॉसिंग नहीं) नियम उन समस्याओं पर लागू नहीं होता जहाँ सड़कें क्रॉस होनी ही चाहिए, जैसे कि वन-वे स्ट्रीट या पुलों वाले वास्तविक दुनिया के सिटी ग्रिड में, या सख्त टाइम विंडो वाली समस्याओं में जहाँ एक लंबा रास्ता लेना आवश्यक हो सकता है। उनका काम विशेष रूप से "कम्प्लीट यूक्लिडियन इंस्टेंस" के लिए है जहाँ बिंदु एक सपाट तल पर होते हैं और क्रॉसिंग से बचा जा सकता है।

"नो-क्रॉसिंग" और "कॉन्वेक्स हल" का जादू

कंप्यूटर को स्मार्ट बनाने के लिए, लेखकों ने दो मुख्य ज्यामितीय अवधारणाएं पेश कीं:

1. नो-क्रॉसिंग नियम (The No-Crossing Rule): कल्पना कीजिए कि आप मेज पर डॉट्स को जोड़ने के लिए एक धागे से एक लूप बना रहे हैं। यदि आपका धागा खुद को काटता है, तो आप हमेशा एक छोटा लूप बना सकते हैं जो बिना क्रॉसिंग के होता है। लेखकों ने गणितीय रूप से सिद्ध किया कि इष्टतम (सबसे छोटा) पथ में क्रॉसिंग वाली रेखाएं नहीं होंगी। उन्होंने अपने कंप्यूटर प्रोग्राम में एक विशेष "फ़िल्टर" बनाया जो तुरंत किसी भी ऐसे मार्ग विकल्प को हटा देता है जो क्रॉसिंग का कारण बनता है। यह क्लब के एक बाउंसर की तरह है जो तुरंत किसी को गलत दरवाजे से प्रवेश करने की कोशिश करने पर बाहर निकाल देता है, जिससे बाउंसर को बाद में उसकी आईडी चेक करने की ज़रूरत नहीं पड़ती।

2. कॉन्वेक्स हल ऑर्डर (The Convex Hull Order): कल्पना कीजिए कि आप एक बोर्ड पर कीलों के समूह के चारों ओर एक रबर बैंड खींच रहे हैं। रबर बैंड जो आकार बनाता है उसे "कॉन्वेक्स हल" कहा जाता है। लेखकों ने दिखाया कि सबसे छोटे पथ में, इस रबर बैंड के बिल्कुल किनारे वाली कीलों को एक विशिष्ट क्रम (घड़ी की दिशा या घड़ी की विपरीत दिशा) में जाना चाहिए। उन्होंने ऐसे नियम बनाए जो कंप्यूटर को इस क्रम का सम्मान करने के लिए मजबूर करते हैं, जिससे वह किनारे पर आगे-पीछे ज़िगज़ैग करने वाले रास्तों की जाँच करने में समय बर्बाद करने से बच जाता है।

समूह समस्याओं में जादू का विस्तार

शोध पत्र एक कठिन संस्करण को भी संबोधित करता है जिसे "जनरलाइज्ड ट्रैवलिंग सेल्सपर्सन प्रॉब्लम" (GTSP) कहा जाता है। इस संस्करण में, हर एक शहर में जाने के बजाय, आपको "क्लस्टर्स" (समूहों) के एक सेट पर जाना होता है, लेकिन आपको प्रत्येक समूह में केवल एक शहर पर रुकना होता है। यह एक डिलीवरी ड्राइवर की तरह है जिसे तीन अलग-अलग मोहल्लों में पैकेज छोड़ने हैं लेकिन उसे प्रत्येक मोहल्ले में केवल एक घर पर जाना है।

लेखकों ने दिखाया कि उनके ज्यामितीय नियमों को इस कठिन समस्या के लिए भी अनुकूलित किया जा सकता है। उन्होंने क्लस्टर्स की ज्यामिति के आधार पर "पड़ोसियों" को परिभाषित किया और उसी नो-क्रॉसिंग और ऑर्डरिंग लॉजिक को लागू किया। क्लस्टर वाले मैप्स के लिए क्लस्टर्ड मैप्स में औसत समाधान समय में 76% तक और ग्रिड-नुमा मैप्स में 67% तक की कमी देखी गई।

निचोड़

लेखक सावधानीपूर्वक बताते हैं कि हालांकि उनकी विधि पिछले कन्स्ट्रेंट प्रोग्रामिंग तकनीकों की तुलना में एक बड़ा सुधार है, लेकिन यह अभी भी बुनियादी TSP के लिए दुनिया के सबसे शक्तिशाली विशेष सॉल्वर (जैसे कॉनकोर्ड - Concorde) जितनी तेज़ नहीं है। हालाँकि, वे विशेष रूप से उन जटिल "जनरलाइज्ड" संस्करणों को सफलतापूर्वक संभालते हैं जिन्हें लेखक हल कर रहे हैं।

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