Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

कल्पना कीजिए कि वाहनों का एक बेड़ा समय के विरुद्ध दौड़ लगा रहा है ताकि बिखरे हुए स्थानों के संग्रह का दौरा किया जा सके, जिनमें से प्रत्येक से अलग पुरस्कार मिलता है। लक्ष्य सरल है: समय समाप्त होने से पहले अधिक से अधिक मूल्य एकत्र करना। लेकिन दुनिया कोई स्प्रेडशीट नहीं है। किसी स्थान पर कार्य पूरा करने में लगने वाला समय अनिश्चित होता है; हवा का एक अचानक झोंका ड्रोन को विलंबित कर सकता है, या अशांत समुद्र नाव को धीमा कर सकता है। इसके अलावा, प्रत्येक स्थान केवल समय की एक विशिष्ट अवधि के लिए उपलब्ध होता है। यदि कोई वाहन बहुत जल्दी पहुँच जाता है, तो उसे प्रतीक्षा करनी होगी; यदि वह बहुत देर से पहुँचता है, तो अवसर हमेशा के लिए हाथ से निकल जाएगा। यह 'टाइम विंडो' के साथ टीम ओरिएंटियरिंग समस्या (team orienteering problem with time windows) के रूप में जानी जाने वाली एक जटिल लॉजिस्टिक चुनौती का सार है। वास्तविक दुनिया में, यह परिदृश्य तब सामने आता है जब अग्निशामक जंगल की आग को नियंत्रित करने की कोशिश करते हैं, तेल रिसाव नियंत्रण दल तट से टकराने से पहले चिकनाई को रोकने की दौड़ लगाते हैं, या चिकित्सा टीमों को महत्वपूर्ण समय सीमा के भीतर रोगियों से मिलना होता है। कठिनाई यह है कि वर्तमान कार्य में कितना समय लगेगा, यह जाने बिना और हर सेकंड पूरे प्लान को फिर से कैलकुलेट करने की विलासिता के बिना, तुरंत अगला कदम उठाना।

वर्षों तक, शोधकर्ताओं ने कंप्यूटर को सरल निर्णय नियम विकसित करने की शिक्षा देकर इसे हल करने का प्रयास किया है। ये नियम एक ट्रैफिक कंट्रोलर की तरह कार्य करते हैं, जो वर्तमान स्थिति को देखते हैं और तुरंत तय करते हैं कि अगले किस ग्राहक के पास जाना है। अब तक की सबसे सफल विधि, जिसे NS-GP के रूपas जाना जाता है, ग्यारह बुनियादी विशेषताओं (जैसे कि ग्राहक कितनी दूर है या कितना समय बचा है) के एक निश्चित सेट पर निर्भर करती है। प्रभावी होने के बावजूद, इस दृष्टिकोण की एक सीमा है। यह दुनिया का वर्णन करने के लिए एक सीमित शब्दावली का उपयोग करता है, ठीक वैसे ही जैसे केवल सौ शब्दों का उपयोग करके एक उपन्यास लिखने की कोशिश करना। ब्राजील के विश्वविद्यालयों में ऑगस्टो मेंडोंसा और उनकी टीम के नेतृत्व वाले इन शोधकर्ताओं ने एक साहसिक प्रश्न पूछा: क्या होगा यदि कंप्यूटर एक विशेषज्ञ योजनाकार (expert planner) को ऑफलाइन समस्या सुलझाते हुए देखकर एक समृद्ध शब्दावली सीख सके? वे यह देखना चाहते थे कि क्या वे उच्च-गुणवत्ता वाले समाधानों के छिपे हुए तर्क को निकाल सकते हैं और उन अंतर्दionों को सरल, पठनीय नियमों में बदल सकते हैं जो वास्तविक समय में काम करते हैं।

टीम ने SI-GP नामक एक नई विधि विकसित की, जिसका अर्थ है 'सॉल्वर-इन्फॉर्म्ड जेनेटिक प्रोग्रामिंग' (Solver-Informed Genetic Programming)। यह प्रक्रिया कंप्यूटर के अनुमान से नहीं, बल्कि कंप्यूटर के देखने से शुरू होती है। सबसे पहले, शोधकर्ताओं ने चालीस अलग-अलग परीक्षण समस्याओं के लिए सर्वोत्तम संभव मार्ग खोजने के लिए शक्तिशाली, उच्च-गति वाले सॉल्वरों का उपयोग किया, यह मानते हुए कि सब कुछ पूरी तरह से सही होगा। फिर उन्होंने इन आदर्श मार्गों को एक सिम्युलेटेड दुनिया में फिर से खेला जहाँ रैंडम देरी होती है, ठीक वैसे ही जैसे वास्तविकता में होता है। आदर्श योजनाओं की तुलना वास्तविक घटनाओं से करके, टीम ने उन विशिष्ट ऑपरेशनों की पहचान की जो आदर्श योजनाओं ने किए लेकिन मानक नियमों ने मिस कर दिए। उदाहरण के लिए, उन्होंने देखा कि सर्वोत्तम योजनाएं अक्सर कई कदम आगे देखती थीं कि कितने पुरस्कार प्राप्त करने योग्य शेष रहेंगे, या वे वर्तमान निर्णय के लिए प्रतिबद्ध होने के जोखिम की गणना करती थीं कि इससे भविष्य के अवसर खोने का क्या खतरा है।

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

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

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

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