A self-convergent algorithm for the asymmetric traveling salesman problem based on feedback adjustment mechanism
基于反馈校正原理的非对称旅行商问题的自收敛优化算法

A novel algorithmic framework based on the feedback adjustment mechanism is proposed to solve the asym-metric traveling salesman problem(ATSP).The main idea of the algorithm is to continuously exclude arcs not belonging to the optimal solution,using the dual information of the relaxed ATSP problem.The initial arc-set is regarded as the "reference input";the lower-bound solver and the upper-bound solver are treated as the"controlled plant";the al-gorithm for excluding arcs not belonging to the optimal solution is considered the "feedback controller",to which the feedback input is the difference of the outputs from the "controlled plant".During the process of iterations,with the gap between the lower-bound and the upper-bound is reduced gradually,the cardinality of the excluding arcs will be aug-mented which guarantees the algorithm of self-convergence to the optimal solution.This work integrates the mathematical programming and the heuristic method,the superiority of which over an isolated single method is shown theoretically and illustrated computationally,demonstrating the efficiency.