摘要
通过分析已有的最近插入法,提出了一种基于参考点的相邻插入法(RPBNI)及其改进策略(I-RPBNI),用于求解旅行商问题(TSP),时间性能分别为O(n2)和O(n3);进而提出了结合模拟退火算法和I-RPBNI的两阶段方法.通过典型算例的数值仿真,验证了所提出算法的有效性、高效性和鲁棒性.
By analyzing the existing nearest insertion method, a kind of reference point based near insertion approach (RPBNI) and its improvement version (I-RPBNI) with O(n2) and O(n3) polynomial time performances are proposed respectively to solve traveling salesman problem (TSP). An effective two-stage approach combining simulated annealing with I-RPBNI is proposed. Numerical simulations based on typical benchmarks demonstrate the effectiveness, efficiency and robustness of the proposed approach.
出处
《控制与决策》
EI
CSCD
北大核心
2004年第7期831-833,837,共4页
Control and Decision
基金
国家自然科学基金资助项目(60204008
60374060)
国家973计划项目(2002CB312200).
关键词
旅行商问题
参考点
相邻插入法
模拟退火
Computer simulation
Robustness (control systems)
Simulated annealing
