Heterogeneous Multi-commodity Network Flows over Time
- Publisher:
- Springer International Publishing
- Publication Type:
- Chapter
- Citation:
- Computer Science – Theory and Applications, 2022, 13296 LNCS, pp. 238-255
- Issue Date:
- 2022-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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 introduced by Fleischer and Skutella (SIAM J. Comput., 2007).
Please use this identifier to cite or link to this item: