期刊名称：International Journal of Mathematics and Mathematical Sciences
印刷版ISSN：0161-1712
电子版ISSN：1687-0425
出版年度：2020
卷号：2020
页码：1-13
DOI：10.1155/2020/2676378
出版社：Hindawi Publishing Corporation
摘要：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.
