Quickest Multi-Commodity Flow Over Time with Partial Lane Reversals

Abstract

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.