Multi-facility allocation in network flow models: A case study

Abstract

Optimizing network flow with facility allocation requires strategic placement and efficient traffic management. The considered model integrates the network flow model with location analysis. Allocation of facilities on arcs changes the capacity of the arcs, which reduces the optimality of the original network. The multi-facility allocation in the network flow model is the NP-hard problem. An acceptable solution to the k-FlowLoc problem can be obtained via an auxiliary graph H that incorporates facility-location compatibility constraints and maximum-flow computation. This transformation ensured a one-to-one correspondence between feasible allocations and maximum flows of value k in H. Optimization objectives are guided by cost functions on H's edges, significantly influencing facility placement quality. Computational results with different cost functions demonstrate that this approach provides a scalable alternative to exact solutions. The solution with a dataset of Asan, Kathmandu, Nepal, validates its practical applicability in real-world applications and motivates further exploration of a new cost function.