A Speculative Verification and Expert Repair Framework for Dynamic Vehicle Routing

लास्ट-माइल डिलीवरी सिस्टम एक ऐसी दुनिया में काम करते हैं जो शायद ही कभी स्थिर रहती है। जब ट्रक पहले से ही चल रहे होते हैं, तब भी ऑर्डर आते रहते हैं, ट्रैफिक की स्थितियाँ बदल जाती हैं, और डिलीवरी का समय अक्सर बहुत कम होता है। इस वातावरण में, एक स्थिर योजना—जो दिन की शुरुआत में एक बार गणना की गई हो—शायद ही कभी पर्याप्त होती है। इसके बजाय, डिस्पैचरों को अपनी योजनाओं को लगातार अपडेट करना पड़ता है, मौजूदा रूटों में नए स्टॉप जोड़ना पड़ता है या ग्राहक के रद्द करने या वाहन के खराब होने पर उन्हें फिर से व्यवस्थित करना पड़ता है। इस निरंतर पुन: अनुकूलन (re-optimize) की आवश्यकता एक कठिन कम्प्यूटेशनल चुनौती पैदा करती है: सिस्टम को कुछ ही सेकंड में स्टॉप का एक नया, वैध क्रम खोजना होता है। यदि कंप्यूटर सोचने में बहुत अधिक समय लेता है, तो डिलीवरी का समय समाप्त हो जाता है, या ड्राइवर खाली बैठा रह जाता है। यदि कंप्यूटर एक ऐसा नया रूट सुझाता है जो नियमों का उल्लंघन करता है—जैसे कि एक ट्रक बहुत अधिक वजन ले रहा है या बहुत देर से पहुँच रहा है—तो पूरी योजना ढह जाती है, और सिस्टम को फिर से शुरू करना पड़ता है। लक्ष्य केवल सबसे छोटा रास्ता खोजना नहीं है, बल्कि तुरंत एक काम करने योग्य रास्ता खना है।

हुबेई यूनिवर्सिटी ऑफ ऑटोमोटिव टेक्नोलॉजी के शोधकर्ताओं ने इस समस्या के लिए एक नया दृष्टिकोण विकसित किया है, जो इन पलक झपकते ही लिए जाने वाले निर्णयों को अधिक विश्वसनीय बनाने के लिए आर्टिफिशियल इंटेलिजेंस की दुनिया से एक रणनीति उधार लेता है। वे अपने सिस्टम को SRI-ECR-balanced कहते हैं। हर बार जब एक नया ऑर्डर आता है, तो शून्य से एक आदर्श रूट की गणना करने के बजाय, यह सिस्टम एक कुशल संपादक की तरह काम करता है जो कुछ वाक्य लिखता है, त्रुटियों के लिए उनकी जाँच करता है, अच्छे हिस्सों को रखता है, और तुरंत खराब हिस्सों को ठीक कर देता है। यह विधि, जिसे 'स्पेक्युलेटिव एक्जीक्यूशन' (speculative execution) कहा जाता है, सिस्टम को एक साथ कई भविष्य के स्टॉप प्रस्तावित करने, यह सत्यापित करने कि कौन से सुरक्षित हैं, और बाकी को हटाने की अनुमति देती है इससे पहले कि वे कोई समस्या पैदा करें। ऐसा करके, सिस्टम पारंपरिक तरीकों की तुलना में संघर्षों (conflicts) से बहुत तेज़ी से उबर सकता है, जिससे यह सुनिश्चित होता है कि स्थिति ज़मीनी स्तर पर तेज़ी से बदलने पर भी डिलीवरी योजना व्यवहार्य बनी रहे।

इस नए फ्रेमवर्क का मूल 'ड्राफ्टिंग, वेरिफिकेशन और रिपेयर' का चक्र है। जब एक नया ऑर्डर आता है, तो एक "ड्राफ्ट जनरेटर" ट्रक के रूट में जोड़ने के लिए ग्राहकों का एक छोटा क्रम प्रस्तावित करता है। अतीत में, सिस्टम शायद एक बार में केवल एक ग्राहक को जोड़ने का प्रयास करते थे, जो धीमा था, या वे एक साथ ग्राहकों की एक लंबी सूची जोड़ने का प्रयास करते थे, जिससे अक्सर गलतियाँ होती थीं। यह नया सिस्टम एक संतुलन बनाता है: यह स्टॉप का एक छोटा समूह प्रस्तावित करता है, शायद एक बार में पाँच। एक अलग "वेरिफायर" (verifier) फिर इस समूह की सड़क के नियमों के विरुद्ध जाँच करता है, जैसे कि ट्रक की वजन सीमा और ग्राहक का समय अंतराल। सिस्टम प्रस्तावित समूह के उस सबसे लंबे हिस्से को स्वीकार करता है जो नियमों के अनुकूल है और बाकी को तुरंत हटा देता है। यदि प्रस्तावित समूह के पहले तीन स्टॉप ठीक हैं लेकिन चौथा ट्रक के लिए बहुत भारी है, तो सिस्टम पहले तीन को रखता है और चौथे को वापस (roll back) कर देता है। यह पूरे प्लान को नहीं फेंकता; यह केवल उस हिस्से को हटाता है जिसने नियमों को तोड़ा है।

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

इस प्रक्रिया को वास्तविक समय के उपयोग के लिए पर्याप्त तेज़ बनाने के लिए, सिस्टम 'रूट-प्रिफिक्स कैश' (route-prefix cache) नामक एक प्रकार की मेमोरी का भी उपयोग करता है। एक गतिशील वातावरण में, ट्रक के रूट का अधिकांश हिस्सा एक क्षण से दूसरे क्षण तक समान रहता है; केवल रूट का अंत बदलता है। पारंपरिक सिस्टम अक्सर हर छोटे बदलाव के लिए पूरी यात्रा की पुन: गणना करते हैं, जिससे यात्रा के उन हिस्सों पर समय बर्बाद होता है जो बदले नहीं हैं। यह नया सिस्टम उन हिस्सों के लिए गणनाओं को याद रखता है जो पहले से ही पुष्ट हैं। जब इसे एक नया स्टॉप चेक करने की आवश्यकता होती है, तो यह केवल नए हिस्से की गणना करता है, शेष के लिए संग्रहीत डेटा का पुन: उपयोग करता है। इस सरल ट्रिक ने सिस्टम को संभावित रूटों का मूल्यांकन करने में तीन गुना से अधिक तेज़ बना दिया। 100 ग्राहकों के एक मानक सेट पर परीक्षण में, इस कैशिंग ने सिस्टम को शून्य से शुरू करने की तुलना में 3.12 गुना तेज़ी से रूटों का मूल्यांकन करने में सक्षम बनाया। 200 ग्राहकों के बड़े परीक्षण में, गति में सुधार 3.08 गुना था।

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

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

शोधकर्ताओं ने यह दावा नहीं किया कि उनका सिस्टम एक स्थिर दुनिया में सबसे छोटा रास्ता खोजने के लिए सबसे अच्छा है जहाँ समय कोई कारक नहीं है। उन्होंने स्पष्ट रूप से कहा कि उन समस्याओं के लिए जहाँ एकमात्र लक्ष्य दूरी को कम करना है और कंप्यूटर के पास सोचने के लिए कई सेकंड हैं, पारंपरिक सॉल्वर अभी भी जीतते हैं। इस नए फ्रेमवर्क का मूल्य विशेष रूप से गतिशील डिस्पैच की अराजक, समय-दबाव वाली दुनिया में है। इन परिदृश्यों में, एक संघर्ष से तुरंत उबरने की क्षमता और एक वैध योजना बनाए रखना, दूरी में मामूली सुधार करने से कहीं अधिक महत्वपूर्ण है। सिस्टम ने सबसे तनावपूर्ण परीक्षण परिदृश्यों में 100% ग्राहकों की सेवा करके और शून्य अस्वीकृत ऑर्डर के साथ अपनी योग्यता सिद्ध की, जबकि प्रतिक्रिया समय को लाइव डिस्पैच सेंटर के लिए उपयोगी बनाए रखा।

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

अंततः, यह कार्य इस बारे में हमारी सोच में आए बदलाव को प्रदर्शित करता है कि रूटिंग समस्याओं को कैसे हल किया जाए। कंप्यूटर को एक कैलकुलेटर के रूप में देखने के बजाय जो कि एक एकल सर्वश्रेष्ठ उत्तर खोजने के लिए बाध्य है, शोधकर्ताओं ने इसे एक निर्णय लेने वाले (decision-maker) के रूप में देखा जिसे जल्दी से एक अच्छा उत्तर खोजना चाहिए। आधुनिक आर्टिफिशियल इंटेलिजेंस के स्पेक्युलेटिव पैटर्न—ड्राफ्टिंग, वेरिफिकेशन और कैशिंग—को अपनाकर, सिस्टम अनिश्चितता के बीच गति और विश्वसनीयता के साथ डायनेमिक डिलीवरी को नेविगेट कर सकता है। निष्कर्ष बताते हैं कि कई वास्तविक दुनिया के लॉजिस्टिक्स चुनौतियों के लिए, तुरंत अनुकूलित होने की क्षमता ही एक सफल सिस्टम का असली पैमाना है, भले ही इसका अर्थ यह हो कि रूट गणितीय रूप से पूर्ण नहीं हैं। सिस्टम यह वादा नहीं करता कि वह हर बार सबसे छोटा रास्ता खोज लेगा या सभी देरी को समाप्त कर देगा, लेकिन यह वादा करता है कि जब एक नया ऑर्डर आएगा, तो एक योजना लगभग तुरंत तैयार होगी, जिससे डिलीवरी नेटवर्क के पहिए घूमते रहेंगे।