Maximum and Quickest Interval-valued FlowsOver Time

Flows over time generalize standard network flows by introducing an element of time. The specific characteristic of these kinds of network flows are transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Road and air traffic control, production systems, communication networks (e.g. the internet) and financial flows are the problems arising in this issue. While in most of network flow problems, capacities are given constant, stochastic or Fuzzy numbers, in this paper we suppose that capacities and consequently flows on arcs fall within specific ranges expressed as compact intervals. This vagueness in capacities and flows could arise in a number of ways: 1) when determining the exact capacity quantities is hard and there may happen errors in determining them which intervals reflect the measurement errors; 2) when it is impossible or even it is not needed to produce neither a distribution nor fuzzy functions but capacities and flows lie within specific ranges, or vary in time within these ranges. Our contribution in this paper is producing maximum flow and quickest s-t flow algorithms to network flows over time with interval-valuedcapacities.

کلیدواژه ها:

Maximum flows over time ، Transit times ، Interval-valued capacities