Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding
From MaRDI portal
Publication:5865336
DOI10.1080/10556788.2020.1817447zbMath1489.90163OpenAlexW3085334717MaRDI QIDQ5865336
Yaroslav Salii, Andrey S. Sheka
Publication date: 13 June 2022
Published in: Optimization Methods and Software (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/10556788.2020.1817447
dynamic programmingparallelismtravelling salesmanprecedence constraintssequential ordering problembrand-and-bound
Partial orders, general (06A06) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Dynamic programming (90C39)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
- Load-dependent and precedence-based models for pickup and delivery problems
- Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm
- On a bottleneck routing problem
- On the complexity of dynamic programming for sequencing problems with precedence constraints
- A heuristic manipulation technique for the sequential ordering problem
- An algorithm for the traveling salesman problem with pickup and delivery customers
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- An inexact algorithm for the sequential ordering problem
- Counting linear extensions
- On estimating the number of order ideals in partial orders, with some applications
- The Min-Max Spanning Tree Problem and some extensions
- A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
- Arborescence optimization problems solvable by Edmonds' algorithm
- The traveling salesman problem and its variations
- An improved ant colony system for the sequential ordering problem
- Hybrid optimization methods for time-dependent sequencing problems
- An algebraic framework for minimum spanning tree problems
- The precedence-constrained asymmetric traveling salesman polytope
- The time dependent traveling salesman problem: polyhedra and algorithm
- Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
- On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs
- Scheduling inbound and outbound trucks at cross docking terminals
- New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- A Scheme of Independent Calculations in a Precedence Constrained Routing Problem
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- A Model of "Nonadditive" Routing Problem Where the Costs Depend on the Set of Pending Tasks
- TSPLIB—A Traveling Salesman Problem Library
- Branch-and-Bound Strategies for Dynamic Programming
- Feature Article—Reporting Computational Experiments with Parallel Algorithms: Issues, Measures, and Experts' Opinions
- Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming
- Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
- Multivalued Decision Diagrams for Sequencing Problems
- An Experimental Investigation and Comparative Evaluation of Production Line Balancing Techniques
