On solving maximum and quickest interval-valued flows over time

摘要

Network flows over time (also called Dynamic Network Flows) are considered as generalized form of standard (static) networks by adding an element of time. The factor of transit time on the arcs which specify the amount of time it takes for one unit of the flows to pass through a particular arc, make these networks different to traditional form of networks. While in most of network flow problems, transit times and capacities are given constant, stochastic or Fuzzy numbers, in this paper we suppose that transit times, capacities and consequently flows on arcs fall within specific ranges expressed as compact intervals. This vagueness in transit times, capacities and flows could arise in a number of ways: 1) when determining the exact capacity or transit time 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 transit times, capacities and flows lie within specific ranges, or vary in time within these ranges. While determining the exact time for traveling in specific path in network transportation system is extremely difficult or almost impossible, determination of interval which can describe the range of required time for travelling in the network would be easy and fully operational. Our contribution in this paper is producing maximum flow and quickest s-t flow algorithms, first to network flows over time with interval-valued capacities and then to T-length bounded network flows over time with interval-valued transit times and capacities.