用分枝定界算法求解旅行商问题的插件开发

• 作者: 张昆 李玲玉
• 来源期刊: 测绘科学
• 学科: 地球科学
• 关键词: 旅行商问题 分枝定界算法 QGIS插件 精确解
• 年，卷（期）: 2020,（11）
• 所属期刊栏目: 地图学与地理信息
• 页码范围: 185-190
• 页数: 6页
• 分类号: P208
• 语种: 中文
• DOI: 10.16251/j.cnki.1009-2307.2020.11.026

摘要

针对GIS软件中采用启发式算法求解旅行商问题(TSP),还不具备求解TSP精确解的问题,以Python为开发语言,在PyQT5和QGIS Python API环境下,采用分枝定界算法开发了名为TSP Branch and Bound Solver的QGIS插件.插件基于广度优先与优先级队列技术实现分枝定界算法,同时采用最近邻居算法先求得一条回路作为初始解,加快了剪枝的进程.该插件在5 min内能解决的TSP规模为16个节点,优势在于能够获得TSP的精确解.对于规模不大的TSP问题,该插件具有实用价值,例如用于外卖配送,使快递员的配送路径最优.同时,由于QGIS是一款开源GIS软件,开发的插件也避开了版权问题的困扰,用户可以免费下载和使用该插件.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张昆		45	739	11.0	27.0
2	李玲玉		5	1	1.0	1.0