Research Article Open Access

Quickest Multi-Commodity Flow Over Time with Partial Lane Reversals

Tanka Nath Dhamala1, Shiva Prakash Gupta1, Durga Prasad Khanal1 and Urmila Pyakurel1
  • 1 Tribhuvan University, Nepal
Journal of Mathematics and Statistics
Volume 16 No. 1, 2020, 198-211

DOI: https://doi.org/10.3844/jmssp.2020.198.211

Submitted On: 21 May 2020 Published On: 2 October 2020

How to Cite: Dhamala, T. N., Gupta, S. P., Khanal, D. P. & Pyakurel, U. (2020). Quickest Multi-Commodity Flow Over Time with Partial Lane Reversals. Journal of Mathematics and Statistics, 16(1), 198-211. https://doi.org/10.3844/jmssp.2020.198.211

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.

  • 376 Views
  • 106 Downloads
  • 0 Citations

Download

Keywords

  • Network Flow
  • Multi-Commodity
  • Quickest Flow
  • Lane Reversals
  • Length Bounded
  • ∆-Condensed