The Steiner traveling salesman problem with online advanced edge blockages

DOI10.1016/j.cor.2015.12.013zbMath1391.90626OpenAlexW2204163060MaRDI QIDQ1651622

Weitian Tong, Guo-Hui Lin, Yin-Feng Xu, Hui-Li Zhang

Publication date: 12 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2015.12.013

zbMATH Keywords

competitive ratiotraveling salesman problemonline algorithmSteiner TSPadvanced edge blockage

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27)

Related Items (7)

Online machine minimization with lookahead ⋮ Online routing and searching on graphs with blocked edges ⋮ An online optimization approach for post-disaster relief distribution with online blocked edges ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem ⋮ An integer linear programming model for efficient scheduling of UGV tasks in precision agriculture under human supervision

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Compact formulations of the Steiner traveling salesman problem and related problems
• The Steiner traveling salesman problem with online edge blockages
• Shortest paths without a map
• Design and control of warehouse order picking: a literature review
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• A cutting plane procedure for the travelling salesman problem on road networks
• A fast algorithm for Steiner trees
• On the solutions of stochastic traveling salesman problems
• Stochastic vehicle routing
• A review of dynamic vehicle routing problems
• The \(k\)-Canadian travelers problem with communication
• The covering Canadian traveller problem
• Routing and Scheduling on a Shoreline with Release Times
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Online Vehicle Routing Problems: A Survey
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• A Preference Order Dynamic Program for a Stochastic Traveling Salesman Problem
• Special cases of traveling salesman and repairman problems with time windows
• A fundamental problem in vehicle routing
• Algorithms for the on-line travelling salesman

This page was built for publication: The Steiner traveling salesman problem with online advanced edge blockages