शाखा और मूल्य एल्गोरिथम

Sep 03 2020

क्या शाखा और मूल्य न्यूनतम-अधिकतम उद्देश्य फ़ंक्शन के साथ एक रूटिंग समस्या के लिए एक अच्छा समाधान दृष्टिकोण हो सकता है? उदाहरण के लिए, वीआरपी में किसी भी वाहन मार्ग की अधिकतम लंबाई को कम करना।

साहित्य में, मैंने कभी नहीं देखा कि यह समाधान दृष्टिकोण इस तरह की समस्या को हल करने के लिए उपयोग किया जाता है। जहां तक मुझे पता है, इस दृष्टिकोण का उपयोग कुल लागत को कम करने वाले वीआरपी को हल करने के लिए किया जाता है।

जवाब

9 dhasson Sep 03 2020 at 09:08

एक अच्छा या बुरा दृष्टिकोण कई कारकों पर निर्भर करेगा, उदाहरण के लिए:

उदाहरणों का आकार
समय एक समाधान खोजने के लिए उपलब्ध है (यह वाहन रूटिंग अनुप्रयोगों में एक महत्वपूर्ण मामला है)
संगणन शक्ति
किस क्वालिटी का सॉल्यूशन क्वालिटी काफी अच्छा है

यू, नागराजन और शेन के इस काम को संगतता बाधाओं के साथ न्यूनतम मेकएप वीआरपी पर देखें , क्योंकि यह एक ऐसी ही समस्या है जिसका अध्ययन मेक-अप वीआरपी वेरिएंट को हल करने के लिए एक दृष्टिकोण के रूप में शाखा-और-मूल्य का उपयोग करने से पहले किया गया है। इसने काफी अच्छा काम किया। ध्यान दें कि उनके मामले में, उन्होंने B & P निष्पादन समय में तेजी लाने के लिए एक सन्निकटन एल्गोरिथम तैयार किया है।

मैं निम्नलिखित प्रयोग का सुझाव देता हूं:

पहला कदम: वीआरपी में मेकपैन मिनिमाइजेशन के संबंध में आपके पिछले सवाल @ रॉबट्रैट के जवाब के बाद :

चलो $d_i$ ग्राहक की मांग हो $i\in N$, चलो $V=\{1,\dots,K\}$ वाहनों का सेट हो, और जाने दो $P$ स्तंभों का समूह हो, जहां प्रत्येक कॉलम चाप चर के साथ डिपो से शुरू होने वाले एक संभव उपसर्ग से मेल खाता हो $x_{i,j}$ और नोड चर $y_i$। चलो$z$Makepan हो। गुरु समस्या खत्म$z$ तथा $\lambda$कोष्ठक में दोहरे चर के साथ निम्नानुसार है: \ start {align} & \ {text {छोटा} और z \\ & \ text {अधीन} & z - \ sum_ {p \ _ P} \ बाएँ (\ sum_ {i, j) में } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {के लिए$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ _ in V} \ sum_ {p \ _ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text \ { $i\in N$} && (\ text {$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {के लिए $v\in V$} && (\ text {$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {के लिए $v\in V$ तथा $p\in P$} \ अंत {संरेखित}

स्तंभ निर्माण उपप्रकार खत्म हो गया $x$ तथा $y$ प्रत्येक के लिए $v\in V$ के बाद कम लागत को कम करने के लिए है $\lambda^p_v$। वह है, न्यूनतम$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ का विषय है $(x,y)$ डिपो से शुरू होने वाले एक घटिया उप-प्रकार का निर्माण, के साथ $\sum_i d_i y_i \le L$, कहां है $L$ प्रत्येक वाहन की क्षमता है।

जैसा कि वहाँ कहा गया है, उपप्रकार को प्राथमिक सबसे छोटे पथ के रूप में सुधारा जा सकता है: डिपो को एक स्रोत और एक सिंक में विभाजित करें, और नोड वज़न को आर्क्स में ले जाएँ: $\pi_v c_{i,j}−\alpha_i$ चाप के वजन के लिए $(i,j)$ प्राथमिक कम से कम पथ उपप्रकार में।

दूसरा: उपरोक्त विधि को लागू करें। मैं अनुशंसा करता हूं कि वीआरपीवाई का उपयोग करने की कोशिश करें, जैसा कि यहां कुइफजे ने सुझाव दिया है । इस तरह आपको स्क्रैच से सभी शाखा और मूल्य संचालन को लागू नहीं करना पड़ेगा। विस्तृत कदम:

परियोजना के प्रलेखन पर एक नज़र डालें।
GitHub में कोड देखें।
एक कांटा बनाएं या प्रोजेक्ट को .zip के रूप में डाउनलोड करें, जैसे कि आप स्थानीय रूप से परिवर्तन कर सकते हैं।
उपप्रबंध के बारे में कोड को संशोधित करें , जैसे कि डिपो विभाजित है जैसा कि ऊपर बताया गया था।
प्रयोगों को चलाएं, आप यहां और यहां जैसे प्रलेखन से उदाहरण उदाहरणों का पालन कर सकते हैं ।
आइए जानते हैं कि इसने कैसे काम किया। और अपने काम में वीआरपीवाई और उसके डेवलपर्स को स्वीकार करना याद रखें (यह एक परियोजना रिपोर्ट, थीसिस, प्रकाशन, आदि), साथ ही संशोधनों के संबंध में पुस्तकालय के लाइसेंस पर शर्तों का सम्मान करना है।

5 Kuifje Nov 11 2020 at 01:09

VRPy (v0.3.0) अब इस विकल्प का समर्थन करता है: आपको बस इतना करना है कि ऑब्जेक्ट को तत्काल करते समय minimize_global_spanविकल्प सेट करें :TrueVehicleRoutingProblem

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

बेशक, आपका ग्राफ $G$ पहली जगह में अच्छी तरह से परिभाषित किया जाना है।

@RobPratt द्वारा प्रस्तावित सूत्रीकरण लागू किया गया है। यदि आप कुछ खिलौना समस्याओं के साथ आसपास खेलते हैं, तो आप देखेंगे कि फॉर्म्युला शास्त्रीय (मेकप के बिना) की तुलना में कमजोर है। यह देखना आसान है कि बाधा$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ _ V में$} $$ इसके लिए जिम्मेदार है।