Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints

DOI10.1287/OPRE.45.3.365zbMATH Open0893.90167OpenAlexW2038970683MaRDI QIDQ4367231FDOQ4367231

Authors: Aristide Mingozzi, Salvatore Ricciardelli, Lucio Bianco 

Publication date: 16 August 1998

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.45.3.365

Recommendations

• Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming
• Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
• Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
• THE PRECEDENCE CONSTRAINED TRAVELING SALESMAN PROBLEM

zbMATH Keywords

traveling salesmanstate space relaxationHamiltonian tourbounding functionstime window and precedence constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Cited In (34)

• New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP
• Call-based dynamic programming for the precedence constrained line traveling salesman
• Nodal aggregation of resource constraints in a shortest path problem
• Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version
• Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
• An exact constraint logic programming algorithm for the traveling salesman problem with time windows
• 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
• Network-based approximate linear programming for discrete optimization
• Shipping problems with body clock constraints.
• On the effect of precedence constraints on computational complexity of dynamic programming method for routing problems
• The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem
• Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• A hybrid algorithm for the vehicle routing problem with AND/OR precedence constraints and time windows
• An efficient genetic algorithm for the traveling salesman problem with precedence constraints
• Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows
• A traveling salesman problem with pickups and deliveries, time windows and draft limits: case study from chemical shipping
• Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin-Marsten bounding
• An enhanced branch-and-bound algorithm for the talent scheduling problem
• Scheduling tasks on moving executors to minimise the maximum lateness
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• Exact and heuristic algorithms for routing AGV on path with precedence constraints
• Title not available (Why is that?)
• The delivery man problem with time windows
• Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
• The time-dependent capacitated profitable tour problem with time windows and precedence constraints
• Single-vehicle scheduling with time window constraints
• New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• A tabu search algorithm for scheduling a single robot in a job-shop environment
• Deep policy dynamic programming for vehicle routing problems
• The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach
• The vehicle routing problem with floating targets: formulation and solution approaches

This page was built for publication: Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints

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