文章基本信息

标题：Network Reconfiguration with Orientation-Dependent Transit Times
本地全文：下载
作者：Hari Nandan Nath ; Urmila Pyakurel ; Tanka Nath Dhamala 等
期刊名称：International Journal of Mathematics and Mathematical Sciences
印刷版ISSN：0161-1712
电子版ISSN：1687-0425
出版年度：2021
卷号：2021
页码：1-11
DOI：10.1155/2021/6613622
出版社：Hindawi Publishing Corporation
摘要：Motivated by applications in evacuation planning, we consider a problem of optimizing flow with arc reversals in which the transit time depends on the orientation of the arc. In the considered problems, the transit time on an arc may change when it is reversed, contrary to the problems considered in the existing literature. Extending the existing idea of auxiliary network construction to allow asymmetric transit time on arcs, we present strongly polynomial time algorithms for solving single-source-single-sink maximum dynamic contraflow problem and quickest contraflow problem. The results are substantiated by a computational experiment in a Kathmandu road network. An algorithm to solve the corresponding earliest arrival contraflow problem with a pseudo-polynomial-time complexity is also presented. The partial contraflow approach for the corresponding problems has also been discussed.