Updating Network Flows Given Multiple,Heterogeneous Arc Attribute Changes |
| |
Authors: | Elise Miller-Hooks Hao Tang Zhiying Chen |
| |
Institution: | (1) Department of Civil & Environmental Engineering, University of Maryland, 1173 Glenn Martin Hall, College Park, MD 20742, USA;(2) Operations Research Group, FedEx Express Corporation, Memphis, Tennessee |
| |
Abstract: | A dual ascent reoptimization technique is proposed for updating optimal flows for the minimum cost network flow problem (MCNFP)
given any number of simultaneous, heterogeneous changes to the network attributes (i.e. supply at nodes, arc costs and arc
capacities) and the optimal solutions to the prior primal and dual problems. Significant savings in computation time can be
achieved through the use of reoptimization in place of solving a new MCNFP from scratch as each new problem instance (i.e.
set of network attribute updates) arises. The proposed technique can be implemented with polynomial worst-case computational
complexity. Extensive numerical experiments were designed and conducted to assess the computational benefits of employing
the proposed reoptimization technique as compared with solution from scratch using comparable classic implementations of the
original algorithms. This work was motivated by the need for the real-time provision of evacuation instructions to people
seeking quick egress from a large sensor-equipped building that has come under attack by natural or terrorist forces, but
has broad applicability. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|