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.9748zbMATH Open1238.90126OpenAlexW1968492936MaRDI QIDQ2884495FDOQ2884495
Authors: E. Balas, Neil Simonetti 
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
Recommendations
- A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
- Implementation of a linear time algorithm for certain generalized traveling salesman problems
- An integer programming approach for the time-dependent TSP
- New dynamic programming algorithms for the resource constrained elementary shortest path problem
- New complexity results for time-constrained dynamical optimal path problems
- Linear Time Constructions of Some $$d$$-Restriction Problems
- New approximation algorithms for \((1,2)\)-TSP
- On a linear-programming, combinatorial approach to the traveling-salesman problem
- scientific article; zbMATH DE number 4189104
- Approximating the regular graphic TSP in near linear time
Programming involving graphs or networks (90C35) Dynamic programming (90C39) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Cited In (37)
- New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP
- A comprehensive survey on the generalized traveling salesman problem
- Beam-ACO for the travelling salesman problem with time windows
- Solution of real-world postman problems
- Heuristics for vehicle routing problems: sequence or set optimization?
- Fast local search algorithms for the handicapped persons transportation problem
- Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version
- 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
- A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem
- Further extension of the TSP assign neighborhood
- Upper bounds on ATSP neighborhood size.
- A general variable neighborhood search for the traveling salesman problem with time windows under various objectives
- Reliable production process design problem: compact MILP model and ALNS-based primal heuristic
- New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem
- Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP
- Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
- Implementation of a linear time algorithm for certain generalized traveling salesman problems
- Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
- Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows
- Large multiple neighborhood search for the clustered vehicle-routing problem
- Repeat inspection planning using dynamic programming
- Job shop scheduling with setup times, deadlines and precedence constraints
- Algorithms for automatic ranking of participants and tasks in an anonymized contest
- A new ILP-based refinement heuristic for vehicle routing problems
- 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
- A branch and bound method for the job-shop problem with sequence-dependent setup times
- A TSP (1,2) application arising in cable assembly shops
- Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
- An exact algorithm with linear complexity for a problem of visiting megalopolises
- Dominance guarantees for above-average solutions
- A granular local search matheuristic for a heterogeneous fleet vehicle routing problem with stochastic travel times
- A variable iterated greedy algorithm for the traveling salesman problem with time windows
- Four-point conditions for the TSP: the complete complexity classification
This page was built for publication: Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884495)
