🤖 AI

An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

यह शोध पत्र एक उन्नत लार्ज नेबरहुड सर्च पद्धति प्रस्तावित करता है जो इनकम्पैटिबल कस्टमर्स वाले कैपेसिटेटेड फैसिलिटी लोकेशन प्रॉब्लम को हल करने के लिए मौजूदा अत्याधुनिक मेटाह्यूरिस्टिक्स से बेहतर प्रदर्शन करने हेतु हाइब्रिड डिस्ट्रॉय ऑपरेटर्स को एक सटीक रिपेयर सॉल्वर के साथ जोड़ता है, जिससे सभी बेंचमार्क इंस्टेंसों के लिए नए सर्वश्रेष्ठ समाधान प्राप्त हुए हैं।

मूल लेखक: Ida Gjergji, Lucas Kletzander, Nysret Musliu, Andrea Schaerf

प्रकाशित 2026-05-28

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ida Gjergji, Lucas Kletzander, Nysret Musliu, Andrea Schaerf

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल डिलीवरी कंपनी के मैनेजर हैं। आपके पास ग्राहकों की एक सूची है जिन्हें पैकेज चाहिए, और संभावित गोदामों (warehouses) की एक सूची है जहाँ आप उन पैकेजों को स्टोर कर सकते हैं। आपका लक्ष्य सरल है: सही गोदाम खोलना और सही पैकेज सही लोगों तक पहुँचाना ताकि आप ओपनिंग कॉस्ट और शिपिंग फीस पर कम से कम पैसा खर्च करें।

यह क्लासिक "फैसिलिटी लोकेशन प्रॉब्लम" है। लेकिन इस विशिष्ट शोध पत्र में, लेखक इसमें एक पेचीदा मोड़ जोड़ते हैं: ग्राहक असंगति (Customer Incompatibility)।

ट्विस्ट: पड़ोस में "दुश्मनी"

कल्पना कीजिए कि आपके कुछ ग्राहक प्रतिद्वंद्वी कंपनियाँ हैं (जैसे दो प्रतिस्पर्धी सोडा ब्रांड) या वे खतरनाक सामग्री का रख-रखाव कर रहे हैं जिसे मिलाया नहीं जा सकता। आप इन "दुश्मन" ग्राहकों को एक ही गोदाम में नहीं रख सकते। यदि आप ऐसा करते हैं, तो यह एक आपदा होगी। यह एक जटिलता की परत जोड़ता है जो पूर्ण समाधान खोजना अविश्वसनीय रूप से कठिन बना देती है, जैसे कि एक विशाल, बदलते हुए जिग्सॉ पहेली को हल करने की कोशिश करना जहाँ कुछ टुकड़े एक-दूसरे से चुंबकीय रूप से प्रतिकर्षित होते हैं।

समाधान: "बिग नेबरहुड" सर्च

लेखक इस पहेली को हल करने का एक नया तरीका प्रस्तावित करते हैं जिसे लार्ज नेबरहुड सर्च (LNS) कहा जाता है। इसे समझने के लिए, कल्पना करें कि आप एक लिविंग रूम में फर्नीचर को फिर से व्यवस्थित करने की कोशिश कर रहे हैं ताकि वह बेहतर दिखे।

"डिस्ट्रॉय" चरण (गड़बड़ी करने वाला):
एक बार में एक कुर्सी हिलाने के बजाय, एल्गोरिदम कमरे का एक पूरा हिस्सा लेता है—मान लीजिए सोफा, कालीन और कॉफी टेबल—और उन्हें दरवाजे के बाहर फेंक देता है। शोध पत्र की भाषा में, यह डिस्ट्रॉय ऑपरेटर (Destroy Operator) है। उन्होंने यह चुनने के लिए तीन विशेष तरीके विकसित किए कि कौन सा "फर्नीचर" (ग्राहक और गोदाम) हटाया जाएगा:
- चीपेस्ट फैसिलिटीज (Cheapest Facilities): उन गोदामों को चुनना जिनका उपयोग करने की लागत वर्तमान में सबसे अधिक है।
- हाइब्रिड कस्टमर्स (Hybrid Customers): सबसे महंगे ग्राहकों को चुनने और उनके लिए नए बेहतरीन स्थान खोजने का एक चतुर मिश्रण।
- रैंडम (Random): बस हलचल पैदा करने के लिए एक रैंडम समूह को उठा लेना।
"रिपेयर" चरण (विशेष वास्तुकार):
अब आपके पास एक बिखरा हुआ कमरा है जिसके बीच में एक खाली जगह है। आप केवल अंदाज़ा लगाकर फर्नीचर को वापस नहीं रखते। इसके बजाय, आप केवल उस विशिष्ट छेद के लिए एक सुपर-स्मार्ट आर्किटेक्ट (एक सटीक गणितीय सॉल्वर जिसे Gurobi कहा जाता है) को बुलाते हैं। आर्किटेक्ट यह पता लगाता है कि उन विशिष्ट वस्तुओं को पूरी तरह से फिट करने के लिए, "दुश्मन" नियमों का सम्मान करते हुए, उन्हें फिर से व्यवस्थित करने का सबसे अच्छा तरीका क्या है। यह रिपेयर ऑपरेटर (Repair Operator) है।
लूप (The Loop):
कंप्यूटर इस प्रक्रिया को हजारों बार दोहराता है: समाधान के एक हिस्से को तोड़ें, उस विशिष्ट हिस्से को ठीक करने के लिए विशेषज्ञ को बुलाएं, और देखें कि क्या पूरा कमरा पहले से बेहतर दिखता है। यदि यह बेहतर है, तो बदलाव को स्वीकार करें। यदि नहीं, तो अगली बार तोड़ने के लिए अगला हिस्सा चुनें।

यह शोध पत्र क्यों विशेष है

लेखकों ने केवल यह मशीन नहीं बनाई; उन्होंने इसे एक रेस कार की तरह ट्यून किया है।

स्टार्टिंग लाइन: उन्होंने महसूस किया कि एक अच्छा शुरुआती प्लान मायने रखता है। उन्होंने पहले "कमरे" को सेट करने के विभिन्न तरीकों का परीक्षण किया और पाया कि एक विशिष्ट 'ग्रीडी स्ट्रैटेजी' के साथ शुरुआत करने से उन्हें बढ़त मिली।
स्वीकृति के नियम (Rules of Acceptance): उन्होंने इस बात के नियमों को भी बदला कि एक नए अरेंजमेंट को कब स्वीकार किया जाए। उन्होंने तय किया कि कभी-कभी "बराबर" के अरेंजमेंट्स को भी स्वीकार किया जा सकता है (न कि केवल बेहतर वाले)। यह एल्गोरिदम को "लोकल ट्रैप्स" (स्थानीय जाल) से बचने में मदद करता है—ऐसी स्थितियाँ जहाँ कमरा अच्छा दिखता है, लेकिन वास्तव में वह एक कोने में फंसा हुआ है और बिना किसी बड़े बदलाव के बेहतर नहीं हो सकता।
परिणाम: उन्होंने अपने तरीके का परीक्षण डेटा के दो विशाल सेटों पर किया (कुछ में 3,000 गोदाम और 8,000 ग्राहक तक थे)। परिणाम प्रभावशाली थे: उनके तरीके ने सभी पिछले "स्टेट-ऑफ-द-आर्ट" तरीकों को पछाड़ दिया। वास्तव में, उन्होंने जितने भी टेस्ट केस आजमाए, उनमें से हर एक के लिए, उन्होंने एक नया सर्वश्रेष्ठ समाधान खोजा, जिससे पहले से ज्ञात अन्य चीजों की तुलना में पैसा बचा।

निचोड़ (The Bottom Line)

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

तकनीकी सारांश: असंगत ग्राहकों वाले क्षमतायुक्त सुविधा स्थान समस्या के लिए एक उन्नत लार्ज नेबरहुड सर्च दृष्टिकोण

समस्या की परिभाषा
यह शोध पत्र असंगत ग्राहकों वाली मल्टी-सोर्स कैपेसिटेटेड फैसिलिटी लोकेशन प्रॉब्लम (MS-CFLP-CI) को संबोधित करता है। यह संस्करण क्लासिक MS-CFLP का विस्तार है, जो असंगत ग्राहक युग्मों ( $I$ ) के एक सेट को पेश करता है जिन्हें एक ही सुविधा द्वारा सेवा नहीं दी जा सकती है। इस समस्या में यह निर्धारित करना शामिल है कि किन सुविधाओं को खोला जाए (खुलने की लागत $f_j$ वहन करते हुए) और ग्राहकों की मांग ( $d_i$ ) को खुली सुविधाओं के बीच कैसे वितरित किया जाए (शिपिंग लागत $c_{ij}$ वहन करते हुए) ताकि कुल लागत को कम किया जा सके। समाधान को सुविधा क्षमता बाधाओं ( $s_j$ ) को संतुष्ट करना चाहिए, ग्राहक की मांग को पूरी तरह से पूरा करना चाहिए, और यह सुनिश्चित करना चाहिए कि कोई भी दो असंगत ग्राहक एक ही सुविधा साझा न करें। असंगतता बाधाओं की उपस्थिति उप-समस्या (subproblem) को खोजने में NP-hard बना देती है कि खुली सुविधाओं से इष्टतम आपूर्ति कैसे प्राप्त की जाए, भले ही खुली सुविधाओं का सेट निश्चित हो।

कार्यप्रणाली
लेखक MS-CFLP-CI को हल करने के लिए एक लार्ज नेबरहुड सर्च (LNS) फ्रेमवर्क का प्रस्ताव करते हैं। इस दृष्टिकोण का मुख्य भाग वर्तमान समाधान के एक हिस्से को पुनरावर्ती रूप से नष्ट करना (destroy) और फिर उसे एक सटीक मिक्स्ड इंटीजर प्रोग्रामिंग (MIP) सॉल्वर (Gurobi) का उपयोग करके सुधारना (repair) है।

समाधान का प्रतिनिधित्व: समाधानों को शिप की गई मात्रा के मैट्रिक्स के रूप में दर्शाया जाता है, जिसे खुली/बंद सुविधाओं और असाइन किए गए ग्राहकों को ट्रैक करने वाले सहायक डेटा स्ट्रक्चर द्वारा समर्थित किया जाता है।
प्रारंभिक समाधान: एक ह्यूरिस्टिक वर्तमान समाधान बनाने के लिए सुविधाओं को खोलने की लागत के आधार पर क्रमबद्ध करता है, कुल मांग को पूरा करने के लिए पर्याप्त सुविधाएं चुनता है, और असंगतता बाधाओं को संभालने के लिए अतिरिक्त सुविधाओं की एक विशिष्ट संख्या ( $k=5$ ) जोड़ता है। ग्राहकों को एक समान रणनीति के आधार पर असाइन किया जाता है।
डिस्ट्रॉय ऑपरेटर्स (Destroy Operators): पेपर में असंगतता बाधाओं के लिए विशेष रूप से डिज़ाइन किए गए तीन नवीन डिस्ट्रॉय ऑपरेटर्स पेश किए गए हैं:
1. चीपेस्ट फैसिलिटीज (CF): एक रैंडम सुविधा और उसके ग्राहकों का चयन करता है, और फिर अन्य खुली सुविधाओं की पहचान करता है जो उस विशिष्ट ग्राहक समूह के लिए सबसे कम औसत शिपिंग लागत प्रदान करती हैं।
2. हाइब्रिड कस्टमर्स (HC): दो रणनीतियों का एक पुनर्संयोजन है। यह एक रैंडम सुविधा और उसके ग्राहकों का चयन करता है, और फिर "चीपेस्ट कस्टमर्स" (वे जिनका शिपिंग खर्च कम है) और "एक्सपेंसिव कस्टमर्स" (वे जिनका शिपिंग खर्च अधिक है) की पहचान करता है। इसके बाद यह उन अतिरिक्त सुविधाओं का चयन करता है जो इन विशिष्ट ग्राहक उप-समूहों के लिए सर्वोत्तम सेवा प्रदान करती हैं।
3. क्लोज्ड फैसिलिटीज (Closed Facilities): नई सुविधाओं को खोलने की खोज करने के लिए रैंडम बंद सुविधाओं और न्यूनतम लागत माप ( $Q_g$ ) वाले स्थानों को उप-समस्या में शामिल किया गया है।
रिपेयर ऑपरेटर (Repair Operator): नष्ट किए गए तत्वों द्वारा परिभाषित उप-समस्या को Gurobi का उपयोग करके सटीक रूप से हल किया जाता है। कम्प्यूटेशनल समय को प्रबंधित करने के लिए, रिपेयर चरण में एक बाधा शामिल है जो नए खोले जाने वाले सुविधाओं की संख्या को उप-समस्या में शामिल वर्तमान सुविधाओं से अधिकतम दो अधिक तक सीमित करती है। अभिसरण (convergence) को तेज करने के लिए सॉल्वर को एक कटऑफ मान (वर्तमान उप-समस्या लागत) प्रदान किया जाता है।
कॉन्फ़िगरेशन और ट्यूनिंग: लेखक फीचर-आधारित पैरामीटर ट्यूनिंग के लिए irace टूल का उपयोग करते हैं, जिसमें इंस्टेंस स्केल के आधार पर (विशेष रूप से $\le 700$ और $> 700$ सुविधाओं वाले इंस्टेंस के बीच अंतर करते हुए) उप-समस्या आकार ( $\nu$ ) जैसे मापदंडों को समायोजित किया जाता है। अंतिम एल्गोरिदम, जिसे $LNS_{init,accept}$ कहा जाता है, प्रस्तावित डिस्ट्रॉय ऑपरेटर्स को एक बेहतर प्रारंभिक समाधान ह्यूरिस्टिक और एक स्वीकृति मानदंड (acceptance criterion) के साथ जोड़ता है जो समान लागत वाले समाधानों को स्वीकार करने की अनुमति देता है, जिससे लोकल ऑप्टिमा से बाहर निकलने में मदद मिलती है।

मुख्य योगदान

नवीन एल्गोरिद्मिक फ्रेमवर्क: यह MS-CFLP-CI समस्या के लिए लार्ज नेबरहुड सर्च का पहला अनुप्रयोग है।
विशेषज्ञ संचालित (Specialized Operators): डिस्ट्रॉय ऑपरेटर्स (CF और HC) का डिज़ाइन जो स्पष्ट रूप से असंगतता बाधाओं को ध्यान में रखता है, जो मानक फैसिलिटी लोकेशन ह्यूरिस्टिक्स से आगे बढ़ता है।
हाइब्रिड सटीक/ह्यूरिस्टिक रिपेयर: रिपेयर चरण के भीतर एक सटीक MIP सॉल्वर का एकीकरण, जिसे समाधान की गुणवत्ता और रनटाइम के बीच संतुलन बनाने के लिए विशिष्ट बाधाओं के साथ अनुकूलित किया गया है।
गहन विश्लेषण: व्यक्तिगत घटकों (आरंभीकरण, स्वीकृति मानदंड, एडेप्टिव वेट्स) के प्रभाव का मूल्यांकन करने के लिए एक व्यापक एब्लेशन अध्ययन और सांख्यिकीय विश्लेषण (Friedman और Nemenyi परीक्षणों का उपयोग करके) किया गया है।
व्यापक बेंचमार्किंग: 3,000 सुविधाओं और 8,000 ग्राहकों तक के दो बड़े पैमाने के डेटासेट (wlp और cflp-ci) पर मूल्यांकन।

प्रायोगिक परिणाम
प्रस्तावित $LNS_{init,accept}$ विधि का परीक्षण अत्याधुनिक मेटा-ह्यूरिस्टिक्स के विरुद्ध किया गया था, जिनमें MineReduce-आधारित मल्टी-स्टार्ट इटरेटेड लोकल सर्च (MR-MS-ILS), GRASP, परम्यूटेशन-कोडेड इवोल्यूशनरी एल्गोरिदम (PcEA), मल्टी-स्टार्ट ग्रीडी (MG), और सिम्युलेटेड एनीलिंग (SA) शामिल हैं।

प्रदर्शन: प्रस्तावित विधि ने दो अलग-अलग समय सीमाओं ( $10\sqrt{m}$ और $m$ सेकंड) के तहत दोनों डेटासेट पर सभी मौजूदा तरीकों से काफी बेहतर प्रदर्शन किया।
नए सर्वश्रेष्ठ समाधान: इस दृष्टिकोण ने दोनों डेटासेट के सभी 80 इंस्टेंस के लिए नए सर्वश्रेष्ठ समाधान खोजे।
सांख्यिकीय महत्व: सांख्यिकीय परीक्षणों ने पुष्टि की कि पिछले सर्वश्रेष्ठ तरीके (SA) पर सुधार सांख्यिकीय रूप से महत्वपूर्ण है।
स्केलेबिलिटी: जबकि सटीक सॉल्वर (Gurobi/CPLEX) उचित समय के भीतर केवल 150 सुविधाओं तक के इंस्टेंस को ही इष्टतम रूप से हल कर सके, LNS दृष्टिकोण ने 3,000 सुविधाओं तक के इंस्टेंस को प्रभावी ढंग से संभाला।
गैप में कमी: wlp डेटासेट के लिए, विधि ने ज्ञात सर्वश्रेष्ठ समाधानों पर -0.68% से -1.84% तक का गैप सुधार हासिल किया। cflp-ci डेटासेट के लिए, सुधार -0.46% से -2.09% के बीच रहा।

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

ट्विस्ट: पड़ोस में "दुश्मनी"

समाधान: "बिग नेबरहुड" सर्च

यह शोध पत्र क्यों विशेष है

निचोड़ (The Bottom Line)

इसी तरह के और पेपर