Updating Network Flows Given Multiple, Heterogeneous Arc Attribute Changes

Updating Network Flows Given Multiple, Heterogeneous Arc Attribute Changes

0.00 Avg rating0 Votes
Article ID: iaor20108963
Volume: 9
Issue: 4
Start Page Number: 291
End Page Number: 309
Publication Date: Dec 2010
Journal: Journal of Mathematical Modelling and Algorithms
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.