Network Reconfiguration with Orientation-Dependent Transit Times
| Autor: | Urmila Pyakurel, Hari Nandan Nath, Tanka Nath Dhamala |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
021103 operations research Network construction Article Subject 0211 other engineering and technologies Transit time 02 engineering and technology Network reconfiguration Orientation (graph theory) Arc (geometry) Mathematics (miscellaneous) Flow (mathematics) Strongly polynomial 0202 electrical engineering electronic engineering information engineering QA1-939 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | International Journal of Mathematics and Mathematical Sciences, Vol 2021 (2021) |
| ISSN: | 0161-1712 |
| DOI: | 10.1155/2021/6613622 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|