Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
From MaRDI portal
Publication:2884495
DOI10.1287/ijoc.13.1.56.9748zbMath1238.90126OpenAlexW1968492936MaRDI QIDQ2884495
Publication date: 30 May 2012
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/18ffceab6a1d42a1af46b852d35bf4c0c0c89463
Programming involving graphs or networks (90C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Dynamic programming (90C39)
Related Items (32)
Job shop scheduling with setup times, deadlines and precedence constraints ⋮ A granular local search matheuristic for a heterogeneous fleet vehicle routing problem with stochastic travel times ⋮ An exact algorithm with linear complexity for a problem of visiting megalopolises ⋮ Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ Large multiple neighborhood search for the soft-clustered vehicle-routing problem ⋮ Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem ⋮ A general variable neighborhood search for the traveling salesman problem with time windows under various objectives ⋮ Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems ⋮ Upper bounds on ATSP neighborhood size. ⋮ Heuristics for vehicle routing problems: sequence or set optimization? ⋮ Dominance guarantees for above-average solutions ⋮ A branch and bound method for the job-shop problem with sequence-dependent setup times ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ A variable iterated greedy algorithm for the traveling salesman problem with time windows ⋮ Large multiple neighborhood search for the clustered vehicle-routing problem ⋮ Solution of real-world postman problems ⋮ Further extension of the TSP assign neighborhood ⋮ A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem ⋮ Beam-ACO for the travelling salesman problem with time windows ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Single-machine scheduling with release times, deadlines, setup times, and rejection ⋮ Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows ⋮ New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows ⋮ Repeat inspection planning using dynamic programming ⋮ Fast local search algorithms for the handicapped persons transportation problem ⋮ Four-point conditions for the TSP: the complete complexity classification ⋮ A new ILP-based refinement heuristic for vehicle routing problems ⋮ Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version
This page was built for publication: Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
