Mathematics and Computer Science, Volume 2

22Flow Dynamics in Continuous-Time with Average Arc Capacities

Badri Prasad Pangeni^1⋆ and Tanka Nath Dhamala²

¹Tribhuvan University, Prithvi Narayan Campus, Pokhara, Nepal

²Tribhuvan University, Central Department of Mathematics, Kathmandu, Nepal

Abstract

The dynamics of network flows are influenced by transit time along the arcs, unlike the static cases. A continuous-time model depicts the actual scenario of many transshipment problems. Here, we introduce the average arc problem (AAP) in a continuous-time model which widely occurs in our daily life. In AAP, the flow value which is total of the flow at every time step/instant (in discrete/continuous time respectively) of the arc has an upper bound as the flow capacity of that arc. When the time-expanded network is structured, AAP violates the capacity constraint. This failure of extension of the arc problem (AP) to the AAP of the problem leads to formulating a linear programming of it. In AP, at every instant of time, flow can be sent up to the capacity of that arc, as in the traditional dynamic network flows. To get feasible flow, a transformation and reduction algorithm is also presented.

Keywords: Dynamic network flows, continuous-time model, complexity, linear programming

22.1 Introduction

Consider the water supply network of a city, the traffic network of a highway connecting two cities, or the communication network between two places. In these type of network flows, the capacity of the arc in every time step in discrete ...