Multi-Commodity Dynamic Flow Problems With Intermediate Storage and Varying Transit Times

Abstract

Network flow problems, with single or multiple commodity, are commonly used to transship the objects from the source to the destination. In single commodity flow problem, objects are considered to be uniform and are send from a source to a sink (in case of multiple source-sink, it can be reduced to single source-sink by assigning virtual source and sink) whereas in multi-commodity flow problem, different commodities are transshipped from respective sources to corresponding sinks. Similarly, flow with intermediate storage is a network flow problem in which flow from the source is not only sent to the sink but also at appropriate intermediate shelters so that total flow out from the source is maximized. On the other hand, contraflow is very well known and commonly used technique of flow increment in two-way network topology in which oppositely directed anti-parallel arcs are reversed towards the destination. As an extension of the flow with intermediate storage in multi-commodity flow (MCF), we solve the maximum static MCF problem in polynomial time and maximum dynamic MCF problem in pseudo-polynomial time. For the polynomial time approximation, we present priority based maximum dynamic MCF which can be useful in disaster management. Similarly, we provide the approximate solutions to maximum and quickest MCF problems by sharing the capacity in bundle (common) arcs using proportional capacity sharing technique in polynomial time and flow-dependent capacity sharing technique in pseudo-polynomial time. We also discuss the polynomial time approximations of inflow-dependent quickest MCF problem with partial contraflow configuration using length bound and ∆-condense approaches. Besides the different applications of network flow models, our main concern is to relate our problems to the evacuation scenarios. So, we consider source/s as the danger zone/s, sink/s as the safe zone/s and intermediate shelters comparatively safer than the source/s. As single commodity flow problem is a special case of multi-commodity flow problem, we solve the single commodity maximum dynamic flow (MDF) and earliest arrival flow (EAF) problems with intermediate storage in general network and series-parallel network, respectively, by using temporal repetition of the flow in polynomial time complexity. Similarly, to solve the contraflow problem with asymmetric transit times in anti-parallel arcs, we introduce anti-parallel path decomposition technique. For the implementation of temporally repeated solution to MDF with intermediate storage and anti-parallel path decomposition to asymmetric contraflow network, we apply our solution strategies to the real road network of Kathmandu, Nepal as the case illustrations. For the sequential development of the thesis, we start with single commodity flow problem and turn to the multiple commodity case. Abstract network flow concerns with shifting of the flow not in node-arc form but in element-path form in which paths must satisfy the switching property. We incorporate the flow with intermediate storage in abstract network and solve the static, lexicographic static and dynamic flow problems in polynomial time complexity. It helps to eliminate the congestion by diverting the flow in non-crossing sides and storing the excess flow at intermediate shelters (elements). To improve the flow in abstract network, we propose the partial switching technique and solve maximum and quickest flow problems in polynomial time. The facility allocation problem is another important area of network flow problem whose objective is to maximize the flow transmission along with placement of the facilities at appropriate locations. We give the bi-level formulation of the problem in which upper level problem searches an appropriate location for the placement of the facility and lower level problem finds the optimal solution of maximum flow problem. A naive approach and KarushKuhn-Tucker (KKT) transformation with big-M constant and ϵ bound method are solution approaches used to solve the problem.

Keywords: Intermediate storage, asymmetric contraflow, anti-parallel path decomposition, multi-commodity, commodity priority, proportional and flow-dependent capacity sharing, facility allocation . सामान्यतया कमोडिटीहरू (एकल वा बहु-कमोडिटी) लाई स्रोतबाट गन्तव्यमा पठाउनको लागि प्रयोग गरिने सञ्जाल (Network) संग सम्बन्धित प्रवाह समस्याहरू लाई सञ्जाल प्रवाह भनिन्छ। एकल कमोडिटी प्रवाह समस्यामा कमोडिटीहरूलाई समान मानिन्छ र एक स्रोतबाट गन्तव्यमा पठाइन्छ (बहु स्रोत-गन्तव्यको अवस्थामा यसलाई भर्चुअल स्रोत र गन्तव्य प्रदान गरेर एकल स्रोत-गन्तव्यमा घटाउन सकिन्छ) जबकि बहु-कमोडिटी प्रवाह समस्यामा विभिन्न कमोडिटीहरू सम्बन्धित स्रोतहरूबाट सम्बन्धित गन्तव्यहरूमा पठाइन्छ। त्यसै गरी, मध्यवर्ती भण्डारणसहितको प्रवाह एक सञ्जाल प्रवाह समस्या हो जसमा स्रोतबाट प्रवाहित कमोडिटीहरू गन्तव्यमा मात्र नभइ उपयुक्त मध्यवर्ती आश्रयहरूमा पनि पठाइन्छ ताकि स्रोतबाट कुल प्रवाह अधिकतम होस। अर्कोतर्फ, कन्ट्राफ्लो दुई-तर्फी सञ्जालमा प्रवाह वृद्धिको लागी प्रयोग हुने विधि हो जसमा विपरीत दिशाका समानान्तर आर्कहरू गन्तव्यतर्फ उल्टाइन्छ। बहु-कमोडिटी प्रवाह (Multi-commodity flow) मा मध्यवर्ती भण्डारणको साथ प्रवाहको विस्तारको रूपमा हामी पोलिनोमीयल (Polynomial) समयमा अधिकतम स्थिर (Maximum static) बहु-कमोडिटी प्रवाह समस्या र सुडो-पोलिनोमीयल (Pseudo-polynomial) समयमा अधिकतम गतिशील (Maximum dynamic) बहु-कमोडिटी प्रवाह समस्या समाधान गर्छौं। पोलिनोमीयल समय अनुमानको लागि हामी प्राथमिकतामा आधारित अधिकतम गतिशील बहु-कमोडिटी प्रवाह प्रस्तुत गर्दछौं जुन विपद् व्यवस्थापनमा उपयोगी हुन सक्छ। त्यसैगरी, हामी पोलिनोमीयल समयमा समानुपातिक क्षमता साझेदारी प्रविधि र सुडो-पोलिनोमीयल समयमा प्रवाह-निर्भर क्षमता साझेदारी विधि प्रयोग गरेर बन्डल (साझा) आर्कहरूमा क्षमता साझेदारी गरेर अधिकतम (Maximum) र द्रुत (Quickest) बहु-कमोडिटी प्रवाह समस्याहरूको समाधान प्रदान गर्दछौं। हामी Length bound र Delta-condensed विधिहरू प्रयोग गरेर आंशिक कन्ट्राफ्लोको साथ प्रवाह-निर्भर द्रुत बहु-कमोडिटी प्रवाह समस्याको पोलिनोमीयल समयमा समाधान गर्छौं। सञ्जाल प्रवाह मोडेलहरूको विभिन्न अनुप्रयोगहरू बाहेक हाम्रो मुख्य लक्ष्य भनेको हाम्रा समस्याहरूलाई विपद् व्यवस्थापन परिदृश्यहरूसँग सम्बन्धित गर्नु हो। त्यसकारण हामी स्रोत/हरूलाई खतरा क्षेत्र/हरू, गन्तव्य/हरूलाई सुरक्षित क्षेत्र/हरू र मध्यवर्ती आश्रयहरूलाई स्रोत/हरू भन्दा तुलनात्मक रूपमा सुरक्षित मान्दछौं। एकल कमोडिटी प्रवाह समस्या बहु-कमोडिटी प्रवाह समस्या को एक विशेष परिस्थिति हो। हामी एकल कमोडिटी अधिकतम गतिशील प्रवाह (Maximum Dynamic Flow (MDF)) र प्रारम्भिक आगमन प्रवाह (Earliest arrival flow (EAF)) समस्याहरू क्रमशः सामान्य सञ्जाल र श्रृंखला-समानान्तर (Series-parallel) सञ्जालमा मध्यवर्ती भण्डारणको साथ पोलिनोमीयल समयमा प्रवाहको पुनरावृत्ति (Temporally repeated) प्रयोग गर्दै समाधान गर्छौं। त्यसैगरी, विपरीत-समानान्तर आर्कहरूमा सममित (Asymmetric) ट्रान्जिट समयहरूसँग कन्ट्राफ्लो समस्या समाधान गर्न हामी विपरीत-समानान्तर पथ गठन (Anti-parallel path decomposition) प्रविधिको विकास गर्छौं। मध्यवर्ती भण्डारण सहितको अस्थायी पुनरावृत्ति सममित र कन्ट्राफ्लो सञ्जालमा विपरीत-समानान्तर पथ गठन विधि प्रयोग गर्दै MDF को मामला अध्ययन दृष्टान्त (Case illustration) को लागि हाम्रो समाधान रणनीतिलाई काठमाडौंको सडक सञ्जालमा लागू गर्छौं। शोध प्रबन्धको क्रमिक विकासको लागि, हामी एकल कमोडिटी प्रवाह समस्याबाट सुरु गर्छौं र बहु-कमोडिटी मामलामा फर्कन्छौं। नोड-आर्क रुपमा नभई पथहरूले स्विच गर्ने गुण सहित एलिमेन्ट-पथ रुपमा कमोडिटी प्रवाह लाई अमूर्त (Abstract) सञ्जाल प्रवाह भनिन्छ। हामी अमूर्त (Abstract) सञ्जालमा मध्यवर्ती भण्डारणको साथ प्रवाहलाई पोलिनोमीयल समयमा स्थिर (Static), लेकशीकोग्राफिक स्थिर (Lexicographic static) र गतिशील (Dynamic) प्रवाह समस्याहरू समाधान गर्छौं। यसले गैर-क्रसिङ पक्षहरूमा पथहरूलाई मोड्दै र मध्यवर्ती आश्रयहरू (एलिमेन्टहरू) मा अतिरिक्त प्रवाह भण्डारण गरेर भीड हटाउन मद्दत गर्दछ। अमूर्त सञ्जालमा प्रवाह सुधार गर्न हामी आंशिक स्विचिंग (Partial switching) विधि प्रस्ताव गर्दछौं र पोलिनोमीयल समयमा अधिकतम र द्रुत प्रवाह समस्याहरू समाधान गर्दछौं। सुविधा बाँडफाँड (Facility allocation) समस्या सञ्जाल प्रवाह समस्याको अर्को महत्त्वपूर्ण क्षेत्र हो जसको उद्देश्य उपयुक्त स्थानहरूमा सुविधाहरूको प्रतिस्थापनसँगै प्रवाह प्रसारणलाई अधिकतम बनाउनु हो। हामी समस्याको द्वि-स्तरीय सूत्र दिन्छौं जसमा माथिल्लो तहले सुविधाको स्थानको लागि उपयुक्त स्थान खोज्छ र तल्लो तहले अधिकतम प्रवाह समस्याको इष्टतम समाधान फेला पार्छ। Big-M र epsilon-Bound विधिको साथ Karush-Kuhn-Tucker (KKT) रूपान्तरण समस्या समाधान गर्न प्रयोग गरिने समाधान उपायहरू हुन्।