On the computational complexity of the probabilistic traveling salesman problem with deadlines

DOI10.1016/J.TCS.2013.11.028MaRDI QIDQ2453174zbMATH OpenOpenAlexFDO

Authors Dennis Weyland

Publication date 6 June 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.11.028

zbMATH Keywords

computational complexityinapproximabilitystochastic combinatorial optimizationstochastic vehicle routing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06) Stochastic network models in operations research (90B15) Combinatorial optimization (90C27)

Recommendations

• Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
• Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
• Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines
• The parameterized approximability of TSP with deadlines
• Further results on the probabilistic traveling salesman problem

Cites work

• A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers
• Aggregation for the probabilistic traveling salesman problem
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers
• An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands
• Computational complexity of stochastic programming problems
• Estimation-based local search for stochastic combinatorial optimization using delta evaluations: a case study on the probabilistic traveling salesman problem
• Estimation-based metaheuristics for the probabilistic traveling salesman problem
• Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
• Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
• scientific article; zbMATH DE number 4047423 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• Introduction to Stochastic Programming
• Lagrangian Relaxation Methods for Solving the Minimum Fleet Size Multiple Traveling Salesman Problem with Time Windows
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• Reducibility among combinatorial problems
• Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines
• Solving the vehicle routing problem with stochastic demands using the cross-entropy method
• Stochastic vehicle routing
• Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem
• The knapsack problem: A survey
• Vehicle Routing with Time Windows

Cited in

(8)

• The probabilistic orienteering problem
• A structured view on weighted counting with relations to counting, quantum computation and applications
• The parameterized approximability of TSP with deadlines
• Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
• Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
• scientific article; zbMATH DE number 1486639 (Why is no real title available?)
• Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines
• Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete

This page was built for publication: On the computational complexity of the probabilistic traveling salesman problem with deadlines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453174)