Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals
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 ti...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2020/2676378 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547722050142208 |
|---|---|
| author | Urmila Pyakurel Shiva Prakash Gupta Durga Prasad Khanal Tanka Nath Dhamala |
| author_facet | Urmila Pyakurel Shiva Prakash Gupta Durga Prasad Khanal Tanka Nath Dhamala |
| author_sort | Urmila Pyakurel |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-9d60daf0a5154f79b0a40c1ffee845a5 |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-9d60daf0a5154f79b0a40c1ffee845a52025-02-03T06:43:42ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252020-01-01202010.1155/2020/26763782676378Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane ReversalsUrmila Pyakurel0Shiva Prakash Gupta1Durga Prasad Khanal2Tanka Nath Dhamala3Central Department of Mathematics, Tribhuvan University, P.O. Box 13143, Kathmandu, NepalTribhuvan University, Tri-Chandra Multiple Campus, Kathmandu, NepalTribhuvan University, Saraswati Multiple Campus, Kathmandu, NepalCentral Department of Mathematics, Tribhuvan University, P.O. Box 13143, Kathmandu, NepalThe 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.http://dx.doi.org/10.1155/2020/2676378 |
| spellingShingle | Urmila Pyakurel Shiva Prakash Gupta Durga Prasad Khanal Tanka Nath Dhamala Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals International Journal of Mathematics and Mathematical Sciences |
| title | Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals |
| title_full | Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals |
| title_fullStr | Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals |
| title_full_unstemmed | Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals |
| title_short | Efficient Algorithms on Multicommodity Flow over Time Problems with Partial Lane Reversals |
| title_sort | efficient algorithms on multicommodity flow over time problems with partial lane reversals |
| url | http://dx.doi.org/10.1155/2020/2676378 |
| work_keys_str_mv | AT urmilapyakurel efficientalgorithmsonmulticommodityflowovertimeproblemswithpartiallanereversals AT shivaprakashgupta efficientalgorithmsonmulticommodityflowovertimeproblemswithpartiallanereversals AT durgaprasadkhanal efficientalgorithmsonmulticommodityflowovertimeproblemswithpartiallanereversals AT tankanathdhamala efficientalgorithmsonmulticommodityflowovertimeproblemswithpartiallanereversals |