Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals

Urmila Pyakurel, Shiva Prakash Gupta, Durga Prasad Khanal and Tanka Nath Dhamala

International Journal of Mathematics and Mathematical Sciences, 2020, vol. 2020, 1-13

Abstract:

The multicommodity flow problem arises when several different commodities are transshipped from specific supply nodes to the corresponding demand nodes through the arcs of an underlying capacity network. The maximum flow over time problem concerns to maximize the sum of commodity flows in a given time horizon. It becomes the earliest arrival flow problem if it maximizes the flow at each time step. The earliest arrival transshipment problem is the one that satisfies specified supplies and demands. These flow over time problems are computationally hard. By reverting the orientation of lanes towards the demand nodes, the outbound lane capacities can be increased. We introduce a partial lane reversal approach in the class of multicommodity flow problems. Moreover, a polynomial-time algorithm for the maximum static flow problem and pseudopolynomial algorithms for the earliest arrival transshipment and maximum dynamic flow problems are presented. Also, an approximation solution to the latter problem is obtained in polynomial-time.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2020/2676378.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2020/2676378.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:2676378

DOI: 10.1155/2020/2676378

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().