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

摘要：

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

关键词：旅行商问题、分枝定界算法、QGIS插件、精确解

所属期刊栏目：45

分类号：P208(一般性问题)

资助基金：上海市自然科学基金项目19ZR1459700

在线出版日期：2020-12-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：185-190