The minimum load coloring problem (MLCP) is an important NP-complete problem arising from wavelength division multiplexing (WDM), a technology used for building optical communication networks. The solutions to NP-complete problems grow exponentially as the size of the problems expands, so heuristic algorithms are often used to solve such problems. Analysis of research at home and abroad shows that among the existing heuristic algorithms for solving the MLCP, local search algorithms exhibit the best performance. This study proposes two optimization strategies to overcome the limitations of existing local search algorithms in data preprocessing and neighborhood space search. First, during data preprocessing, a one-degree vertex rule is proposed to reduce the size of data and thus reduce the search space of the MLCP. Second, in the search phase of the algorithm, a strategy termed two-stage best from multiple selections (TSBMS) is proposed to help local search algorithms efficiently select a high-quality neighborhood solution for neighborhood space with different sizes, which effectively improves the performance of local search algorithms for processing data of different sizes. This optimized local search algorithm is named IRLTS. Seventy-four classic test instances are adopted to validate the effectiveness of the IRLTS algorithm. Experimental results demonstrate that the IRLTS algorithm outperforms the three best local search algorithms on most test instances in terms of both optimal and average solutions. Furthermore, the effectiveness of the proposed strategy is validated through experiments, and the influence of key parameters on the IRLTS algorithm is analyzed.