TSP मार्ग अनुकूलक

ट्रैवलिंग सेल्समैन समस्या (TSP) क्या है?

TSP पूछता है: स्थानों का एक सेट और उनके बीच की दूरियाँ दी गई हैं, प्रत्येक स्थान को ठीक एक बार विज़िट करके शुरुआती बिंदु पर लौटने का सबसे छोटा संभव मार्ग क्या है?

TSP NP-कठिन है। व्यावहारिक समाधान ह्यूरिस्टिक पर निर्भर करते हैं: निकटतम पड़ोसी (तेज़, इष्टतम से ~25% अधिक), Clarke-Wright, और मेटा-ह्यूरिस्टिक।

TSP लास्ट-माइल डिलीवरी, फील्ड सर्विस, PCB ड्रिलिंग और गोदाम पिक पथ में लागू होता है।

Formula: लक्ष्य: min Σ d(route[i], route[i+1]) निकटतम पड़ोसी: निकटतम अविज़िटेड स्थान पर जाएं बचत: s(i,j) = d(डिपो,i) + d(डिपो,j) − d(i,j)

गणना उदाहरण

डिपो (0,0) पर, 4 पड़ाव (3,4), (6,1), (8,5), (2,7)। निकटतम पड़ोसी: (3,4) d=5.0, फिर (2,7) d=3.2, फिर (8,5) d=6.3, फिर (6,1) d=4.5, वापसी d=6.1। कुल = 25.04 (पूर्णांकित खंडों का योग 25.1)। चार पड़ावों पर यही सबसे छोटा मार्ग है — 24 में से कोई क्रम छोटा नहीं — और savings विधि भी वही 25.04 देती है।

इस कैलकुलेटर का उपयोग कब करें

• एक डिलीवरी डिस्पैचर 10-30 ग्राहक स्थानों पर जाने वाले एकल ड्राइवर के लिए दैनिक मार्ग की योजना बना रहा है
• एक फील्ड सर्विस मैनेजर सर्विस कॉल के बीच यात्रा समय न्यूनतम करने के लिए तकनीशियन मार्गों का अनुकूलन कर रहा है
• एक वेयरहाउस इंजीनियर कई गलियारा स्थानों से गुज़रते हुए इष्टतम पिक पाथ डिज़ाइन कर रहा है
• एक सेल्स रिप्रेज़ेंटेटिव न्यूनतम ड्राइविंग दूरी के साथ क्लाइंट से मिलने के लिए बहु-शहर यात्रा की योजना बना रहा है

बचने योग्य सामान्य गलतियाँ

• यह मानना कि निकटतम-पड़ोसी समाधान इष्टतम है — यह एक ग्रीडी ह्यूरिस्टिक है जो इष्टतम मार्ग से 20-25% ऊपर हो सकता है; हमेशा कई एल्गोरिदम आज़माएं और तुलना करें
• सड़क-आधारित रूटिंग के लिए सीधी-रेखा (यूक्लिडियन) दूरी का उपयोग करना — सड़क नेटवर्क के कारण वास्तविक ड्राइविंग दूरी 20-40% अधिक हो सकती है; सड़क रूटिंग के लिए, उपलब्ध होने पर वास्तविक दूरी का उपयोग करें
• डिपो वापसी यात्रा शामिल करना भूलना — TSP के लिए शुरुआती बिंदु पर लौटना आवश्यक है; वापसी छोड़ने से कुल मार्ग दूरी कम आंकी जाती है
• ऐसी समस्याओं पर TSP लागू करना जो वास्तव में VRP हैं — यदि आपके पास क्षमता प्रतिबंध, समय खिड़कियां या कई वाहन हैं, तो बेहतर परिणामों के लिए VRP टूल का उपयोग करें

परिणामों की व्याख्या कैसे करें

• Nearest Neighbor और Clarke-Wright परिणामों की तुलना करें: यदि वे काफी भिन्न हैं, तो समस्या में अधिक उन्नत विधियों के साथ और अनुकूलन की गुंजाइश है
• मिलीसेकंड में गणना समय आपकी समस्या के आकार के लिए रीयल-टाइम री-रूटिंग संभव है या नहीं इसका आकलन करने में मदद करता है
• मार्ग मानचित्र विज़ुअलाइज़ेशन स्पष्ट अक्षमताओं जैसे क्रॉसिंग मार्ग या अनावश्यक बैकट्रैकिंग की पहचान करने में मदद करता है जो ह्यूरिस्टिक उत्पन्न कर सकते हैं

संबंधित मानक और संदर्भ

• Nearest Neighbor और Clarke-Wright savings (1964) — इस उपकरण में बेंचमार्क की गई रचनात्मक ह्यूरिस्टिक्स
• Lin-Kernighan स्थानीय खोज — उच्च-गुणवत्ता वाले TSP टूर के लिए वास्तविक संदर्भ ह्यूरिस्टिक
• TSPLIB — TSP सॉल्वर गुणवत्ता की तुलना के लिए उपयोग की जाने वाली मानक सार्वजनिक बेंचमार्क लाइब्रेरी

अक्सर पूछे जाने वाले प्रश्न

कौन सा एल्गोरिदम उपयोग करें?

15 से कम स्टॉप: निकटतम पड़ोसी। 15-50: Clarke-Wright + 2-opt। 50+: मेटा-ह्यूरिस्टिक या Google OR-Tools।

TSP वास्तविक डिलीवरी रूटिंग से कैसे भिन्न है?

वास्तविक रूटिंग में टाइम विंडो, वाहन क्षमता, ट्रैफ़िक और बहु-वाहन जुड़ते हैं। TSP नींव है लेकिन व्यावहारिक सॉफ़्टवेयर इन बाधाओं को जोड़ता है।