A Constructive Method Based on Dynamic Solution Space for Travelling Salesman Problem
Xiaoxin Bai, LuLi LuLi, Hanqian Wu · 2023
Neural combinatorial optimization (NCO) has emerged as a promising field to solve the combinatorial optimization problem (COP) as automatically learning the solvers less relying on domain-specific expert knowledge. Constructive Method (ConsM) is the most widely used approach in NCO for solving various COPs and their variations. However, few literature elucidates the underlying principles of ConsM, hindering further optimization. In this paper, we analyze the efficiency principle of ConsM for COPs from the perspective of discrete solution space and summarize its design principles. These principles can serve as guidelines for designing novel constructive policy. Based on these principles, we reviewed the existing ConsM models and identified that the design of existing decoder introduced certain noises, which negatively impacted the policy performance. Therefore, we designed a novel decoder in line with the aforementioned principles. Notably, our method can be applied to all ConsM models and yielded significant improvements compared to the original. We evaluated our method on Traveling Salesman Problem(TSP) and the experimental results verified the effectiveness and efficiency of our method, supporting our analysis of ConsM. In particular, we reduced the average optimality gap from 1.16% to 0.62% for TSP100 compared to Sym-NCOs, keeping the hyperparameters constant.