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

作者：李玲玉,张昆

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

发文机构：华东师范大学地理信息科学教育部重点实验室

关键词：旅行商问题分枝定界算法QGIS插件精确解travelling salesman problembranch and boundQGIS pluginexact solution

分类号： P208[天文地球—地图制图学与地理信息工程]