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

YUAN Zhi

Chinese

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-09-04

- An Efficient Approach for Small-scale TSP and its Application in Examination Timetabling
- Vol. 35, Issue 1, Pages: 56-60(2018)
- 作者机构：
  
  广州大学机构华软软件学院,广东,广州,510990
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2018
- 稿件说明：
移动端阅览
袁志. 旅行商问题的一种高效近似算法及其排考应用[J]. 微电子学与计算机, 2018, 35(1): 56-60.

YUAN Zhi. An Efficient Approach for Small-scale TSP and its Application in Examination Timetabling[J]. 2018, 35(1): 56-60.
袁志. 旅行商问题的一种高效近似算法及其排考应用[J]. 微电子学与计算机, 2018, 35(1): 56-60. DOI：

YUAN Zhi. An Efficient Approach for Small-scale TSP and its Application in Examination Timetabling[J]. 2018, 35(1): 56-60. DOI：

摘要

要为解决现实应用中的类似于小规模旅行商问题的组合优化问题

提出了一种新的近似算法——群体竞争搜索算法(PCS).使用了一种新的局部搜索算子2e/1p-opt

并按照"搜索-选优-变异-搜索"的迭代策略设计了群体竞争搜索算法.与CLK算法进行了比较

对于280城市以下的旅行商问题

在计算速度和计算结果两方面都有较好表现.将高校排考中的场次排序优化问题转化为TSP并用算法求解

能在1秒内得到大幅改进的结果.

Abstract

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.

关键词

Keywords

references

Martin O C, Otto S W, Felten E W. Large-step markov chains for the traveling salesman problem[J]. Complex Systems, 1991, 5(3): 299-326. DOI: 299

Schaert A. A survey of automated timetabling[J]. Artificial Intelligence Review, 1999, 13(2): 87-127. DOI: 87

李红婵, 朱颢东. 采用十进制免疫遗传算法求解高校排课问题. [J]. 系统工程理论与实践, 2012, 32(9): 2031-2036. DOI: 2031

崔丽. 高校学分制环境下排考问题的改进图算法[J]. 计算机系统应用, 2015, 24(3): 220-225. DOI: 220

程毕芸, 鲁海燕, 徐向平, 等. 求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J]. 计算机应用, 2016, 36(1): 138-142. DOI: 138

蔡木生. 高校自动排考算法的设计与实现[J]. 计算机工程与应, 2010, 46(24): 69-72. DOI: 69

邹鹏, 周哲, 江贺, 等. 球旅行商问题的局部循环搜索算法的运行时间和性能分布分析[J]. 计算机学报, 2008, 29(1): 92-99. DOI: 92

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Design of ultra-low power real-time clock circuits

Research on assembly action recognition based on MSS-YOLO-MPHands fusion architecture

Monte carlo analysis of V-layout trench SiC neutron detector

Implementation and verification of a dual-chain power gating strategy for low power design

Research on the design of blockchain-based AI-generated content traceability framework

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰