Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals
Joint Authors
Pyakurel, Urmila
Gupta, Shiva Prakash
Khanal, Durga Prasad
Dhamala, Tanka Nath
Source
International Journal of Mathematics and Mathematical Sciences
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-10-31
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Pyakurel, Urmila& Gupta, Shiva Prakash& Khanal, Durga Prasad& Dhamala, Tanka Nath. 2020. Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals. International Journal of Mathematics and Mathematical Sciences،Vol. 2020, no. 2020, pp.1-13.
https://search.emarefa.net/detail/BIM-1172630
Modern Language Association (MLA)
Pyakurel, Urmila…[et al.]. Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals. International Journal of Mathematics and Mathematical Sciences No. 2020 (2020), pp.1-13.
https://search.emarefa.net/detail/BIM-1172630
American Medical Association (AMA)
Pyakurel, Urmila& Gupta, Shiva Prakash& Khanal, Durga Prasad& Dhamala, Tanka Nath. Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals. International Journal of Mathematics and Mathematical Sciences. 2020. Vol. 2020, no. 2020, pp.1-13.
https://search.emarefa.net/detail/BIM-1172630
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1172630