DSpace Collection:
https://elibrary.tucl.edu.np/handle/123456789/131
2024-03-29T17:52:23ZMulti-Commodity Dynamic Flow Problems With Intermediate Storage and Varying Transit Times
https://elibrary.tucl.edu.np/handle/123456789/22018
Title: Multi-Commodity Dynamic Flow Problems With Intermediate Storage and Varying Transit Times
Authors: Khanal, Durga Prasad
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) रूपान्तरण समस्या समाधान गर्न प्रयोग गरिने समाधान उपायहरू हुन्।2023-09-01T00:00:00ZSome Sequence Spaces and Matrix Transformation with Vedic Relations
https://elibrary.tucl.edu.np/handle/123456789/20075
Title: Some Sequence Spaces and Matrix Transformation with Vedic Relations
Authors: Ray, Suresh
Abstract: Available with full text2021-01-01T00:00:00Z“A Study of Topological Structures of Linear Spaces of Generalized Sequences
https://elibrary.tucl.edu.np/handle/123456789/19226
Title: “A Study of Topological Structures of Linear Spaces of Generalized Sequences
Authors: Ghimire, Jhavi Lal
Abstract: This dissertation deals with the sequence spaces and applications. The various topological and algebraic properties of different sequence spaces defined by Orlicz function have been studied. We introduce and study the sequence spaces that are the generalization of classical sequence spaces of null, convergent, and bounded type. We introduce and study a class c_0 (M,(X,||.||),(a,) ̅α ̅ ) of vector valued difference sequences of null type with the help of Orlicz function. It is the generalization of classical null sequence space. We prove some linear structures and prove some inclusion and equality relations in terms of different parameters a ̅ and α ̅. In the similar fashion, we study the sequence space of bounded type l_∞ (M,(X,||.||),(a,) ̅α ̅ ) of normed space valued difference sequences using Orlicz function M. The containment relations on different parameters are established. The class l_∞ (M,X,(Y,||.||) of Banach space Y - valued functions is introduced as the generalization of bounded complex sequences. The different topological structures have been studied when topologized it with the suitable natural norm. The difference sequence spaces W_0 (∆,f),W(∆,f) and W_∞ (∆,f) defined by non-negative Φ-function on R are introduced and studied their different topological properties endowed by paranormed structure on these spaces. Infinite series and sequences played important role in the development of Calculus and other branches of mathematics. But the mathematicians were facing the problems of calculating the limits of infinite sequences and series, in particular with those having divergent in behaviour. Then the mathematicians developed the various types of convergence to assign a limit in some sense to divergent sequences and series. We also introduce and investigate sequence spaces defined by ideal convergence and Orlicz function in 2-normed space. The theory of sequence space and frame theory are interconnected as frame theory makes the use of sequence space. The sequence spaces are used as the vector spaces in frame theory. Some of the application of frame theory that makes the use of sequence spaces are image processing, signal processing, error correction, data compression etc. The atomic decomposition in a non-locally convex Banach space is defined and discussed its existence. It is also proved that if a p-Banach space has an atomic decomposition then the space is isomorphic to its associated p-Banach sequence space. The necessary and sufficient condition for an atomic decomposition in p-Banach space is given. Certain properties associated with Schauder frames in Banach space have been defined and studied.2023-02-01T00:00:00ZRegularity of 2D Surface Quai-Geostrophic (SQG) Equations
https://elibrary.tucl.edu.np/handle/123456789/19112
Title: Regularity of 2D Surface Quai-Geostrophic (SQG) Equations
Authors: Shrestha, Pawan
Abstract: In this research, we delve into three distinct topics within the realm of nonlinear fluid dynamics, namely the generalized Korteweg-de Vries (KdV)-type equation, the regularity of solutions in the $2$D Surface Quasi-Geostrophic (SQG) equation, and the behavior of water waves under indefinite boundary constraints.
Firstly, we undertake an analytical and numerical examination of the following generalized KdV-type equation ut+aux+2buux+cuxxx- duxx=0, u(x,0)=u0(x) where a, b, c, d are real parameters.
Our study involves allowing the coefficients a, b, c , and d to approach zero in the limiting sense, while contrasting the outcomes with the scenario in which each coefficient is precisely zero. By analyzing this nonlinear partial differential equation in one dimension, we trace the impact of the nonlinear term on the solution. Furthermore, we extend our findings to a two-dimensional equation with structures comparable to those in the 2D SQG equation.
Secondly, we focus on the regularity of solutions in the following 2D SQG equation
where κ ≥ 0 and α > 0 are parameters,
conducting a thorough analysis that addresses a notable gap in analytical and numerical research. The SQG equation exhibits numerous characteristics similar to the 3D Euler equation and the Navier-Stokes equation, with the regularity of the latter being recognized as one of the Clay Institute of Mathematics' millennium problems. To bridge this gap, we concentrate on various aspects of the SQG equation, exploring both inviscid and dissipative instances. In the dissipative case, we categorize the instances as subcritical, critical, and supercritical. Analytical solutions have recently been derived for the subcritical and critical scenarios, while the question of regularity in the supercritical case remains unresolved. Our research focuses on numerical calculations of the inviscid and supercritical SQG equations, with particular attention to the proximity of level curves, the L2 norm, and the expansion of the quantity. We meticulously examine the nature of the solution, particularly in the region where α =.
Finally, we turn our attention to the study of the following water waves
where u is the velocity, P is the pressure, and g is the acceleration due to gravity,
which are typically modeled using Euler equations with unit density. We address an outstanding open problem concerning the existence of closed orbits for water waves under indefinite boundary constraints. Our investigation begins with a discussion of advancements in water wave structure under finite bottom conditions. We then shift our focus to the behavior of water waves at the kinematic barrier of infinite depth. By employing the Crandall-Rabinowitz theorem to construct water wave profiles for scenarios with zero and2023-02-01T00:00:00Z