A Survey on Models of Flows over Time with Flow Dependent Transit Times

Abstract

Ford and Fulkerson introduce the maximum dynamic flow problems with fixed transit times on the arcs and developed the first well known algorithm that sends maximum flow from the source to the sink by augmenting along s-t paths and prove the maximum amount of flow is equal to the total capacity of the arcs in minimum cut. In flows over time with fixed transit time on the arc, the time it takes to traverse an arc does not depend on the current flow situation on the arc. But in real situation, the flow units travelling on the same arc at the same time do not necessarily experience the same pace, i.e., flow units are in general not entering and leaving an arc in the same order. In this paper, we discuss the time expanded graph for load-dependent and inflow[1]dependent transit times. We also discuss the discrete and continuous time flow, earliest arrival flow and quickest transhipment problem.