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

袁志

Chinese

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-09-04

- 旅行商问题的一种高效近似算法及其排考应用
- An Efficient Approach for Small-scale TSP and its Application in Examination Timetabling
- 微电子学与计算机 2018年35卷第1期页码：56-60
- 作者机构：
  
  广州大学机构华软软件学院,广东,广州,510990
- 作者简介：
- 基金信息：
  
  广东省教育厅2015重大平台和科研项目 2015KTSCX177
- DOI：
  中图分类号：
- 纸质出版：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

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种用于极低压boost系统的高效率电荷泵

AlN/GaN混合缓冲层双异质结p-GaN HEMT直流特性仿真

一种基于特征上下文理解与切片分析的肺结核检测算法

基于MSS-YOLO-MPHands融合架构的装配手部动作识别研究

基于区块链的AI生成内容溯源框架设计研究