TY - JOUR
T1 - The Steiner traveling salesman problem with online advanced edge blockages
AU - Zhang, Huili
AU - Tong, Weitian
AU - Xu, Yinfeng
AU - Lin, Guohui
N1 - Publisher Copyright:
© 2015 Elsevier Ltd. All rights reserved.
PY - 2016/6
Y1 - 2016/6
N2 - 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.
AB - 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.
KW - Advanced edge blockage
KW - Competitive ratio
KW - Online algorithm
KW - Steiner TSP
KW - Traveling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=84954451033&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2015.12.013
DO - 10.1016/j.cor.2015.12.013
M3 - Article
AN - SCOPUS:84954451033
SN - 0305-0548
VL - 70
SP - 26
EP - 38
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -