求解动态TSP问题的化学反应算法研究

Research on Chemical Reaction Algorithm for Solving Dynamic TSP Problem

旅行商问题(TSP)是经典的NP难问题,节点可变的TSP问题被称为动态旅行商问题(DTSP)。通过研究化学反应算法(CRA),并对CRA算法并行化实现,能够解决DTSP问题。实验结果表明,CRA算法能够有效地处理快速变化的DTSP问题,且性能不亚于其它元启发式算法。

The Traveling Salesman Problem(TSP)is a classic NP-hard problem.The node-changing TSP problem is called Dynamic Traveling Salesman Problem(DTSP).By studying the chemical reaction algorithm(CRA)and parallelizing the CRA algorithm,the DTSP can be solved.The experimental results show that the CRA algorithm can effectively deal with the rapidly changing DTSP problem and its performance is no less than other meta-heuristic algorithms.