A Solution Space Decomposition Method to Find the Best K Fixed-Charge Network Designs

Abstract

The fixed-charge network design problem (NDP) selects a subset of candidate links with a minimal cost. To enrich decision making in real-world applications, the KNDP aims to find the best K designs as alternative selections. As far as we know, this problem has not been addressed in previous studies. The NDP model includes design and routing variables, where design variables dominate the routing variables. Based on design variables, we develop a solution space decomposition method to find the best K fixed-charge network designs. At iteration k, we divide the current solution space into several subspaces. Each subspace produces a standard NDP instance and generates a candidate network design. By comparing the objective values of all candidate designs, we can obtain the $k+1\mathrm{th}$ optimal design. Numerical experiments are conducted in three transportation networks to demonstrate the effectiveness and efficiency of the proposed method. The central processing unit (CPU) running time grows linearly with the value of K, showing that the proposed method has good properties.