In this paper, an improvement strategy is proposed for solving a determination problem of the optimal distribution network configuration (minimum distribution loss network configuration). To achieve the purpose, characteristics of the network configuration optimization problems are clarified by applying an exact determination method previously proposed to typical problems. Second, those characteristics are used to evaluate the performance of Tabu Search (TS), which is the most popular local search-based metaheuristics, when applied to the problems. Finally, TS algorithm is improved. Numerical simulations are carried out for a real scale complicated network model in order to verify the validity of improved TS.