Heterogeneous Multi-commodity Network Flows over Time

摘要: In the 1950’s, Ford and Fulkerson introduced dynamic flows by incorporating the notion of time into the network flow model (Oper. Res., 1958). In this paper, motivated by real-world applications including route planning and evacuations, we extend the framework of multi-commodity dynamic flows to the heterogeneous commodity setting by allowing different transit times for different commodities along the same edge.We first show how to construct the time-expanded networks, a classical technique in dynamic flows, in the heterogeneous setting. Based on this construction, we give a pseudopolynomial-time algorithm for the quickest flow problem when there are two heterogeneous commodities. We then present a fully polynomial-time approximation scheme when the nodes have storage for any number of heterogeneous commodities. The algorithm is based on the condensed time-expanded network technique …