स्वार्म इंटेलिजेंस और इवोल्यूशनरी कंप्यूटेशन का अंतर्राष्ट्रीय जर्नल

अमूर्त

कॉम्बिनेटोरियल ऑप्टिमाइजेशन के लिए एक प्रतिरक्षात्मक एल्गोरिथ्म: केस स्टडी के रूप में ईंधन वितरण समस्या

पावोन एम*, कोस्टान्ज़ा जे और क्यूटेलो वी

सार रूटिंग समस्याएँ शास्त्रीय संयोजन अनुकूलन कार्य हैं जो कई औद्योगिक और वास्तविक दुनिया के परिदृश्यों में बहुत अधिक प्रयोज्यता पाते हैं। रूटिंग समस्या का एक चुनौतीपूर्ण रूप ईंधन वितरण समस्या (FDP) है जिसका सामना एक परिवहन कंपनी को अपने दैनिक संचालन में करना पड़ता है। एक परिवहन ईंधन कंपनी की मुख्य गतिविधि अपने सभी स्टोर, यानी पेट्रोल स्टेशनों को भौगोलिक मानचित्र के साथ फिर से भरना है, जिसका लक्ष्य इसकी समग्र लागत को कम करना है। इस शोध कार्य में हम FDP को हल करने के लिए प्रतिरक्षा प्रणाली के रूपक पर आधारित एक हाइब्रिड हेयुरिस्टिक प्रस्तुत करते हैं, जो मूल रूप से ग्राहकों की कई प्राप्त मांगों को पूरा करने के लिए कंपनी के वाहनों की एक निश्चित संख्या के लिए यथासंभव छोटे मार्गों का एक सेट खोजने के लिए कहता है। विशेष रूप से, प्रस्तुत प्रतिरक्षात्मक एल्गोरिथ्म क्लोनल चयन सिद्धांत से प्रेरणा लेता है, जिसकी प्रमुख विशेषताएं क्लोनिंग, हाइपर-म्यूटेशन और एजिंग ऑपरेटर हैं। इस तरह के एल्गोरिदम की विशेषता यह भी है कि इसमें (i) डेप्थ फर्स्ट सर्च (DFS) एल्गोरिदम पर आधारित एक नियतात्मक दृष्टिकोण है - जिसका उपयोग वाहन को एक शीर्ष निर्दिष्ट करने की योजना में किया जाता है - और (ii) पड़ोस की खोज के आधार पर एक स्थानीय खोज ऑपरेटर। एल्गोरिदम का परीक्षण एक वास्तविक डेटा इंस्टेंस पर किया गया है, जिसमें 82 कोने हैं, और 25 अन्य कृत्रिम अलग-अलग इंस्टेंस हैं, जिन्हें DIMACS ग्राफ कलरिंग बेंचमार्क से लिया गया है। इस कार्य में प्रस्तुत प्रायोगिक परिणाम, न केवल विकसित एल्गोरिदम की मजबूती और दक्षता को साबित करते हैं, बल्कि स्थानीय खोज की अच्छाई और DFS एल्गोरिदम पर आधारित दृष्टिकोण को भी दर्शाते हैं। दोनों पद्धतियाँ एल्गोरिदम को जटिल खोज स्थान का बेहतर ढंग से पता लगाने में मदद करती हैं।