Attestation committee
Accreditation committee
Expert committee
Dispositions, instructions
Normative acts
MANPOWER TRAINING
Nomenclature
Institutions
Scientific councils
Seminars
Theses		 Scientific advisers
Scientists
Doctoral students
Postdoctoral students
CNAA logo

 română | русский | english


Optimal flows in dynamic networks and algorithms for their finding


Author: Fonoberova Maria
Degree:doctor of physics and mathematics
Speciality: 01.01.09 - Mathematical cybernetics and operation research
Year:2008
Scientific adviser: Dumitru Lozovanu
doctor habilitat, professor, Moldova State University
Institution: Institute of Mathematics and Computer Science
Scientific council: DH 30-01.01.09-27.03.08
Moldova State University

Status

The thesis was presented on the 25 January, 2008
Approved by NCAA on the 28 February, 2008

Abstract

Adobe PDF document – 0.41 Mb / in romanian

Thesis

CZU 519.1

Adobe PDF document 0.97 Mb / in english
90 pages

Keywords

network flows, dynamic networks, minimum cost flow, maximum flow, multicommodity flows, time-expanded network method

Summary

The PhD thesis is addressed to the research topic concerned with the elaboration of methods and algorithms for determining optimal single-commodity and multicommodity flows in dynamic networks. This direction of research is the natural development of the theory of static flows and has a large application for investigation and solving a wide range of practical problems.

In the PhD thesis two basic problems related to determining optimal flows in dynamic networks are investigated: the minimum cost flow problem and the maximum flow problem. In the dynamic networks for these problems the flow passes arcs in time and costs on arcs are nonlinear and dependent on time and flow. The considered problems are studied on dynamic networks when all parameters of networks depend on time. These problems generalize the classical flow problems on static networks and extend some known dynamic optimization models on networks. It is assumed that the capacity function and the demand-supply function depend on time and the cost function on arcs depends on time and flow. In general, for the case of multicommodity problems it is considered that transit times on arcs depend on the sort of commodity entering them. In addition, it is investigated the dynamic model with transit time functions that depend on the amount of flow and the entering time-moment of flow in the arc. Efficient algorithms for solving the considered problems based on dynamic programming and time-expanded network method are proposed and grounded. Multicriterial versions of the mentioned problems are formulated and investigated on the basis of the concept of cooperative and noncooperative games. Approaches and methods for finding optimal solutions in the sense of Pareto and Nash for the multicriterial problems are discussed. It is described the relationship between the optimal control problem on network and the minimum cost flow problem on network with concave cost functions on arcs. In Visual Studio 2005 it is elaborated software for construction time-expanded and reduced time-expanded networks for single-commodity and multicommodity dynamic networks for the considered problems.

The PhD thesis is written in the English language.

Summary


CHAPTER 1. Static Flow Models and Determining Optimal Flows in Networks
  • 1.1. Static Flows: Definitions and Some Properties
    • 1.1.1. Single-Commodity Flow
    • 1.1.2. Multicommodity Flow
  • 1.2. The Maximum Flow Problem
  • 1.3. The Minimum Cost Flow Problem
    • 1.3.1. The Linear Case
    • 1.3.2. The Non-Linear Case
  • 1.4. The Minimum Cost Multicommodity Flow Problem
    • 1.4.1. The Continuously Differentiable and Convex Objective Function
    • 1.4.2. The Separable Objective Function

CHAPTER 2. Single-Commodity Dynamic Flow Problems and the Time-Expanded Network Method for their Solving
  • 2.1. The Minimum Cost Dynamic Flow Problem
  • 2.2. The Method for Solving the Minimum Cost Dynamic Flow Problem
  • 2.3. The Dynamic Model with Flow Storage at Nodes
  • 2.4. The Dynamic Model with Flow Storage at Nodes and Integral Constant Demand-Supply Functions
  • 2.5. The Algorithm
  • 2.6. Approaches for Solving the Minimum Cost Dynamic Flow Problems with Different Types of Cost Functions on Arcs and Some Generalizations
  • 2.7. Determining the Minimum Cost Flows in Dynamic Networks with Transit Time Functions that Depend on Flow and Time
  • 2.8. The Algorithm for Solving the Maximum Flow Problem on Dynamic Network

CHAPTER 3. Multicommodity Dynamic Flow Problems and Algorithms for their Solving
  • 3.1. The Minimum Cost Multicommodity Flow Problem on Dynamic Network
  • 3.2. The Method for Solving the Minimum Cost Multicommodity Dynamic Flow Problem
    • 3.2.1. The Dynamic Network with Different Transit Times on an Arc for Different Commodities
    • 3.2.2. The Dynamic Network with Separable Cost Functions and without Restrictions on Mutual Capacities of Arcs
    • 3.2.3. The Dynamic Network with Common Transit Times on an Arc for Different Commodities
  • 3.3. The Algorithm
  • 3.4. Examples
  • 3.5. Some Generalizations
  • 3.6. Construction of the Time-Expanded Network for Acyclic Graphs
  • 3.7. The Minimum Cost Multicommodity Dynamic Flow Problem with Transit Time Functions that Depend on Flow and Time
  • 3.8. The Algorithm for Solving the Maximum Multicommodity Dynamic Flow Problem

CHAPTER 4. Optimal Dynamic Flows in Decision Making Systems
  • 4.1. Game-Theoretic Approach for Solving Multiobjective Multicommodity Flow Problems on Networks
    • 4.1.1. Pareto-Nash Equilibria for Multiobjective Games
    • 4.1.2. The Multiobjective Multicommodity Flow Models
    • 4.1.3. Comments
  • 4.2. The Minimum Cost Dynamic Flow Problems without Restrictions on Arc Capacities
    • 4.2.1. The Minimum Cost Flow Problems with Cost Functions that Do Not Depend on Flow and the Network Synthesis Problems
    • 4.2.2. The Minimum Cost Flow Problems with Concave Cost Functions on Arcs and the Optimal Control Problems on Networks