Quickest Multi-Commodity Flow Over Time with Partial Lane Reversals
- 1 Tribhuvan University, Nepal
Copyright: © 2020 Tanka Nath Dhamala, Shiva Prakash Gupta, Durga Prasad Khanal and Urmila Pyakurel. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Routing of more than one different commodity from speciﬁc origin nodes to the corresponding destination nodes through the arcs of an underlying network respecting the capacity constraints is one of the main problems in operational research. Among them, the quickest multi-commodity ﬂow problem concerns with minimization of time taken to complete this process. The general multi-commodity and quickest multi-commodity ﬂow problems are computationally hard. By ﬂipping the orientation of lanes towards the demand nodes, the outbound lane capacities are increases. We introduce lane reversals in the quickest multi-commodity ﬂow problem and present two approximation algorithms, one polynomial-time with the help of length-bounded ﬂow and another FPTAS by using ∆-condensed time-expanded graph. Both algorithms prevent reversing arc capacities that are not required by the optimal ﬂows that may be of interest for other purposes.
- 376 Views
- 106 Downloads
- 0 Citations
- Network Flow
- Quickest Flow
- Lane Reversals
- Length Bounded