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

To solve the practical combinatorial optimization problem similar to small-scale TSP, an efficient algorithm named Population Competitive Search(PCS) is presented. A new local search operator named 2e/1p-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.