Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs

详细信息    查看全文

• 作者：Yingjie Xia ; ^a ; ^{xiayingjie@zju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Mingzhe Zhu^b ; Qianping Gu^b ; Luming Zhang^c ; Xuelong Li^d
• 关键词：Branch decomposition ; Intelligent transportation system ; Sphere-cut decomposition ; Steiner travelling salesman problem ; Vehicle routing
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 December 2016
• 年：2016
• 卷：374
• 期：Complete
• 页码：164-178
• 全文大小：2666 K

文摘

The Steiner travelling salesman problem (STSP) is an important issue in intelligent transportation systems and has various practical applications, such as travelling and parcel delivery. In this study, we consider the STSP in real-world road maps, i.e., given a road map with a set of service points or intersections, selection of the representative vertices of a graph G to determine a closed route so a vehicle can visit each service point at least once with the minimum cost. It has been theoretically proved that the STSP and its ancestor, travelling salesman problem, are NP-hard. However, it has been empirically demonstrated that they can be solved efficiently on planar graphs with small branchwidths. Therefore, we propose a branch decomposition-based extraction algorithm for the STSP in planar graphs. Our algorithm can solve the STSP in a planar graph G with a time complexity of 2^O(bw(G))n^O(1), where bw(G)$\mathrm{bw}\left(G\right)$ is the branchwidth of G. In the case of planar graphs with a small branchwidth, our algorithm performs efficiently. We evaluated our algorithm by applying it to real-world urban road maps, which demonstrated the suitability of our method for real-world applications.