A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem
यह शोध पत्र ILS+SP को प्रस्तुत करता है, जो एक हाइब्रिड मेटाहेयुरिस्टिक है जो इटरटेड लोकल सर्च को सेट पार्टीशनिंग पोस्ट-ऑप्टिमाइज़ेशन के साथ संयोजित करता है, जो बड़े पैमाने के बेंचमार्क इंस्टेंस पर निकट-इष्टतम समाधान प्राप्त करके फैमिली कैपेसिटेटेड व्हीकल राउटिंग प्रॉब्लम को हल करने में मौजूदा अत्याधुनिक विधियों से काफी बेहतर प्रदर्शन करता है।
मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक डिलीवरी कंपनी के मैनेजर हैं। आपके पास समान ट्रकों का एक बेड़ा है, जो सभी एक केंद्रीय गोदाम से शुरू होते हैं। आपका काम विभिन्न ग्राहकों तक पैकेज पहुँचाना है।
लेकिन यहाँ एक ट्विस्ट है: आपके ग्राहक केवल व्यक्ति नहीं हैं; वे परिवारों में संगठित हैं। उदाहरण के लिए, "स्मिथ परिवार" के अलग-अलग सड़कों पर पाँच घर हैं, लेकिन आपका अनुबंध केवल उन पाँच में से दो घरों तक डिलीवरी करने की आवश्यकता रखता है। "गार्सिया परिवार" के तीन घर हैं, लेकिन आपको केवल एक पर जाने की आवश्यकता है।
यह फैमिली कैपेसिटेटेड व्हीकल राउटिंग प्रॉब्लम (F-CVRP) है। यह दो मुख्य नियमों के साथ एक विशाल पहेली है:
- द फैमिली रूल (परिवार का नियम): आपको प्रत्येक परिवार के लिए आवश्यक घरों की सटीक संख्या तक पहुँचना होगा, लेकिन आप यह चुन सकते हैं कि किन विशिष्ट घरों में जाना है।
- द ट्रक रूल (ट्रक का नियम): प्रत्येक ट्रक की एक वजन सीमा (क्षमता) होती है। आप उसे ओवरलोड नहीं कर सकते।
लक्ष्य सरल है: इन नियमों को पूरा करने के लिए अपने सभी ट्रकों को चलाने का सबसे सस्ता तरीका खोजें बिना ईंधन या समय समाप्त किए।
समस्या: इसे पूरी तरह से हल करना बहुत कठिन है
जैसे-जैसे परिवारों और घरों की संख्या बढ़ती है, संभावित मार्गों की संख्या इतनी विशाल हो जाती है कि दुनिया के सबसे तेज़ सुपरकंप्यूटरों को भी सटीक उत्तर खोजने में वर्षों लग जाएंगे। इसीलिए, लेखक ब्रूनो, डियागो और मार्कोस ने एक "स्मार्ट गेसर" (एक मेटाहेयुरिस्टिक) बनाया जो जल्दी से एक बहुत अच्छा उत्तर खोज सके।
वे अपने समाधान को ILS+SP कहते हैं। आइए इसे खाना पकाने के उदाहरण से समझते हैं।
रेसिपी: ILS+SP
1. "इटरेटेड लोकल सर्च" (ILS) – चखने वाला शेफ
कल्पना कीजिए कि एक शेफ सूप की रेसिपी को बेहतर बनाने की कोशिश कर रहा है।
- शुरुआत: शेफ एक बुनियादी सूप बनाता है (एक प्रारंभिक समाधान)।
- टेस्ट टेस्ट (लोकल सर्च): शेफ सूप को चखता है और इसमें छोटे बदलाव करता है: "शायद चुटकी भर नमक और डालूँ?" या "गाजर को आलू से बदल दूँ?" वे इन छोटे सुधारों को करने के लिए बदलाव करते रहते हैं।
- "सिमुलेटेड एनीलिंग" ट्विस्ट: कभी-कभी, एक बदलाव सूप के स्वाद को अस्थायी रूप से खराब कर देता है। एक सामान्य शेफ इसे तुरंत अस्वीकार कर देगा। लेकिन यह शेफ एक विशेष नियम (सिमुलेटेड एनीलिंग) का उपयोग करता है: यदि सूप केवल थोड़ा सा खराब है, तो वे इसे फिर भी स्वीकार कर सकते हैं। क्यों? क्योंकि कभी-कभी एक पूरी तरह से नया, अद्भुत स्वाद खोजने के लिए आपको सूप को थोड़ा "अजीब" बनाना पड़ता है। यह उन्हें उन "बुरे इलाकों" से बाहर निकलने में मदद करता है जहाँ वे एक औसत दर्जे की रेसिपी के साथ फंसे हुए हैं।
- झटका (परटर्बेशन/Perturbation): यदि शेफ छोटे सुधारों के एक लूप में फंस जाता है जो मदद नहीं कर रहे हैं, तो वह कुछ नाटकीय करता है: वह आधा सूप बाहर निकाल देता है और सामग्रियों के एक बिल्कुल नए संयोजन के साथ फिर से शुरू करता है। इसे "परटर्बेशन" कहा जाता है। यह उसे रसोई के बिल्कुल नए हिस्से में देखने के लिए मजबूर करता है।
लेखकों ने इस शेफ के टूलकिट में एक विशेष सामग्री जोड़ी है: MemberRelocate। चूंकि यह एक "फैमिली" समस्या है, इसलिए शेफ केवल सामग्री को नहीं बदलता; वे परिवार के सदस्यों को बदलते हैं। यदि वे स्मिथ के घर #1 पर जा रहे हैं, तो वे पूछ सकते हैं, "रुको, घर #2 अधिक पास है। चलिए घर #1 को घर #2 से बदलकर देखते हैं कि क्या इससे समय बचता है।"
2. "सेट पार्टीशनिंग" (SP) – मास्टर एडिटर
जब शेफ ने घंटों तक बदलाव करने, झटकने और चखने में बिता दिए हैं, तो उनके पास अलग-अलग सूप विविधताओं (मार्गों) की एक बड़ी नोटबुक होती है जिसे उन्होंने आजमाया है।
सेट पार्टीशनिंग चरण उस मास्टर एडिटर की तरह है जो उस पूरी नोटबुक को देखता है। एडिटर खाना नहीं बनाता; वे बस चुनते और छाँटते हैं। वे देखते हैं कि शेफ ने दिन के दौरान जो भी बेहतरीन "टुकड़े" (रूट्स) बनाए हैं, उन्हें कैसे जोड़ा जा सकता है और पूछते हैं: "यदि मैं सुबह 10:00 बजे के इस विशिष्ट मार्ग को दोपहर 2:00 बजे के उस मार्ग के साथ मिला दूँ, तो क्या मैं एक आदर्श भोजन बना सकता हूँ?"
यह अंतिम चरण सुनिश्चित करता है कि भले ही शेफ ने खाना पकाने की प्रक्रिया के दौरान पूर्ण संयोजन मिस कर दिया हो, एडिटर दिन के काम के सर्वोत्तम हिस्सों को गणितीय रूप से जोड़कर उसे ढूंढ लेता है।
परिणाम: क्या यह काम आया?
लेखकों ने अपने "ILS+SP" रेसिपी का परीक्षण दुनिया के वर्तमान सर्वश्रेष्ठ तरीकों के विरुद्ध किया।
- परीक्षण: उन्होंने 144 बड़े, कठिन पहेलियाँ (50 से अधिक ग्राहकों के साथ) इस्तेमाल कीं जिन्हें अन्य शोधकर्ताओं ने पहले ही हल करने की कोशिश की थी।
- स्कोर: उनकी विधि हर एक मामले में या तो जीत गई या बराबरी पर रही।
- सुधार: इस पेपर से पहले, सर्वश्रेष्ठ तरीके औसतन लगभग 1.84% दूर थे। लेखकों के तरीके ने उस अंतर को घटाकर 0.01% कर दिया। लॉजिस्टिक्स की दुनिया में, यह लक्ष्य से थोड़ा चूकने से लेकर लगभग हर बार सटीक निशाना लगाने जैसा है।
- गति: उन्होंने और भी बड़े पहेलियों (142 ग्राहकों तक) पर भी इसका परीक्षण किया। उनके तरीके ने औसतन लगभग 37 सेकंड में बेहतरीन समाधान खोज लिए।
सारांश
यह पेपर एक जटिल डिलीवरी रूटिंग समस्या को हल करने का एक नया, हाइब्रिड तरीका प्रस्तुत करता है जहाँ आपको परिवार के सदस्यों में से किसे चुनना है, यह तय करना होता है। एक "चखने वाले शेफ" को मिलाने के साथ जो स्मार्ट, कभी-कभी जोखिम भरे, छोटे बदलाव करता है, और एक "मास्टर एडिटर" के साथ जो दिन के काम के सर्वोत्तम हिस्सों को जोड़ता है, उन्होंने एक ऐसा उपकरण बनाया है जो इस विशिष्ट समस्या के लिए पहले से प्रकाशित किसी भी चीज़ की तुलना में तेज़ और अधिक सटीक है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।