The m-Steiner Traveling Salesman Problem with online edge blockages

Henan Liu (), Huili Zhang () and Yi Xu ()
Additional contact information
Henan Liu: Xi’an Jiaotong University
Huili Zhang: Xi’an Jiaotong University
Yi Xu: Xi’an University of Technology

Journal of Combinatorial Optimization, 2021, vol. 41, issue 4, No 5, 844-860

Abstract: Abstract We consider the online multiple Steiner Traveling Salesman Problem based on the background of the delivery of packages in an urban traffic network. In this problem, given an edge-weighted undirected graph $$G = (V, E)$$ G = ( V , E ) , a subset $$D\subset V$$ D ⊂ V of customer vertices, and m salesmen. For each edge in E, the weight w(e) is associated with the traversal time or the cost of the edge. The aim is to find m closed tours that visit each vertex of D at least once. We formulate the traffic congestion with k non-recoverable blocked edges revealed to the salesmen in real-time, meaning that the salesmen know about a blocked edge whenever it occurs. For the version to minimize the maximum cost of m salesmen (minmax mSTSP), we prove a lower bound and propose the ForestTraversal algorithm. The corresponding competitive ratio is proved to be linear with k. For the version to minimize the total cost of m salesmen (minsum mSTSP), we also propose a lower bound and the Retrace algorithm, where the competitive ratio of the algorithm is proved to be linear with k.

Keywords: m-Steiner Traveling Salesman Problem; Canadian Traveler Problem; Traffic Blockage; Competitive Ratio (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00720-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:4:d:10.1007_s10878-021-00720-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00720-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().