旅行商问题的一种高效近似算法及其排考应用  

An Efficient Approach for Small-scale TSP and its Application in Examination Timetabling

作　　者：袁志[1] 

机构地区：[1]广州大学华软软件学院,广东广州510990

出　　处：《微电子学与计算机》2018年第1期56-60,共5页Microelectronics & Computer

基　　金：广东省教育厅2015重大平台和科研项目(2015KTSCX177)

摘　　要：要为解决现实应用中的类似于小规模旅行商问题的组合优化问题,提出了一种新的近似算法——群体竞争搜索算法(PCS).使用了一种新的局部搜索算子2e/1p-opt,并按照"搜索-选优-变异-搜索"的迭代策略设计了群体竞争搜索算法.与CLK算法进行了比较,对于280城市以下的旅行商问题,在计算速度和计算结果两方面都有较好表现.将高校排考中的场次排序优化问题转化为TSP并用算法求解,能在1秒内得到大幅改进的结果.To solve the practical combinatorial optimization problem similar to small-scale 1 ~1~, an emclem algorithm named Population Competitive Search（PCS） is presented. A new local search operator named 2e/lp-opt is used, and t algorithm is designed based on the iterative strategy of ＂search-select-mutate-search＂. Compared with CLK on TSP instances witch city numbers not more than 280, PCS has better performance in speed and results. PCS is applied for examination timetabling and achieves greatly improved results in 1 second.

关 键 词：旅行商问题 局部搜索 群体进化算法 排考 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]