TY  - JOUR
AU  - Dhamala, Tanka Nath 
AU  - Gupta, Shiva Prakash 
AU  - Khanal, Durga Prasad 
AU  - Pyakurel, Urmila 
PY  - 2020
TI  - Quickest Multi-Commodity Flow Over Time with Partial Lane Reversals
JF  - Journal of Mathematics and Statistics
VL  - 16
IS  - 1
DO  - 10.3844/jmssp.2020.198.211
UR  - https://thescipub.com/abstract/jmssp.2020.198.211
AB  - Routing of more than one different commodity from specific 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 flow problem concerns with minimization of time taken to complete this process. The general multi-commodity and quickest multi-commodity flow problems are computationally hard. By flipping the orientation of lanes towards the demand nodes, the outbound lane capacities are increases. We introduce lane reversals in the quickest multi-commodity flow problem and present two approximation algorithms, one polynomial-time with the help of length-bounded flow and another FPTAS by using ∆-condensed time-expanded graph. Both algorithms prevent reversing arc capacities that are not required by the optimal flows that may be of interest for other purposes.