क्षमता युक्त आवरण विक्रेता समस्याओं के लिए सटीक एल्गोरिदम और हीयूरिस्टिक्स

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