The Steiner traveling salesman problem with online advanced edge blockages. (June 2016)

• Record Type: Journal Article
• Authors: Zhang, Huili; Tong, Weitian; Xu, Yinfeng; Lin, Guohui
• Is Part Of: Computers & operations research. Volume 70(2016)
• Page Start: 26
• Page End: 38
• Publication Date: 2016-06
• Subjects: Traveling salesman problem -- Steiner TSP -- Advanced edge blockage -- Online algorithm -- Competitive ratio; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.12.013
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The package delivery in an urban road network is formulated as an online Steiner traveling salesman problem, where the driver ( i.e. the salesman) receives road ( i.e. edge) blockage messages when he is at a certain distance to the respective blocked edges. Such road blockages are referred to as advanced information. With these online advanced road blockages, the driver wishes to deliver all the packages to their respective customers and returns back to the service depot through a shortest route. During the entire delivery process, there will be at most k road blockages, and they are non-recoverable. When the driver knows about road blockages at a distance α OPT, where α ∈ [ 0, 1 ] is referred to as the forecasting ratio and OPT denotes the length of the offline shortest route, we first prove that max { ( 1 − 2 α ) k + 1, 1 } is a lower bound on the competitive ratio. We then present a polynomial time online algorithm with a competitive ratio very close to this lower bound. Computational results show that our algorithm is efficient and produces near optimal solutions. Similar results for a variation, in which the driver does not need to return to the service depot, are also achieved. Abstract : Highlights: The sTSP with online advanced edge blockages is formulated from an application. Lower bounds on the competitive ratio are proved. An efficient routing algorithm with proven performance is proposed. Extensive computational experiments show both the efficiency and the effectiveness.