用分枝定界算法求解旅行商問題的插件開發

作者：李玲玉,張昆

摘要：針對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[天文地球—地圖制圖學與地理信息工程]