An Optimal Algorithm for the Traveling Salesman Problem with Time Windows

DOI10.1287/opre.43.2.367zbMath0837.90036OpenAlexW2109405343MaRDI QIDQ4849335

Eric Gelinas, Jacques Desrosiers, Yvan Dumas, Marius M. Solomon

Publication date: 25 September 1995

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

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

zbMATH Keywords

traveling salesman problem with time windowselimination tests

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Dynamic programming (90C39)

Related Items (69)

Simultaneous lotsizing and scheduling problems: a classification and review of models ⋮ Finding \(K\) shortest looping paths in a traffic-light network ⋮ Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows ⋮ An enhanced branch-and-bound algorithm for the talent scheduling problem ⋮ Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ Scheduled penalty variable neighborhood search ⋮ Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices ⋮ What are the worst cases in constrained last-in-first-out pick-up and delivery problems? ⋮ A traveling salesman problem with pickups and deliveries, time windows and draft limits: case study from chemical shipping ⋮ History-dependent scheduling: models and algorithms for scheduling with general precedence and sequence dependence ⋮ Routing problems: A bibliography ⋮ Deep policy dynamic programming for vehicle routing problems ⋮ Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ Branch-and-check approaches for the tourist trip design problem with rich constraints ⋮ The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach ⋮ Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery ⋮ Traveling salesman problem with clustering ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ A solution approach for multi‐trip vehicle routing problems with time windows, fleet sizing, and depot location ⋮ The intermittent travelling salesman problem ⋮ Exact and anytime approach for solving the time dependent traveling salesman problem with time windows ⋮ Solving the single crane scheduling problem at rail transshipment yards ⋮ The first AI4TSP competition: learning to solve stochastic routing problems ⋮ Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures ⋮ Local search with annealing-like restarts to solve the VRPTW ⋮ A general variable neighborhood search for the traveling salesman problem with time windows under various objectives ⋮ Integrating driver behavior into last-mile delivery routing: combining machine learning and optimization in a hybrid decision support framework ⋮ A general VNS heuristic for the traveling salesman problem with time windows ⋮ The delivery man problem with time windows ⋮ Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows ⋮ Shipping problems with body clock constraints. ⋮ The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches ⋮ Improved Peel-and-Bound: Methods for Generating Dual Bounds with Multivalued Decision Diagrams ⋮ A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for routing problems with time windows ⋮ 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 ⋮ Hybrid optimization methods for time-dependent sequencing problems ⋮ Multi-objective optimisation models for the travelling salesman problem with horizontal cooperation ⋮ Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines ⋮ An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation ⋮ Restricted dynamic programming: a flexible framework for solving realistic VRPs ⋮ Ship scheduling with soft time windows: An optimisation based approach ⋮ The first \(K\) shortest unique-arc walks in a traffic-light network ⋮ Scheduling tasks on moving executors to minimise the maximum lateness ⋮ Solving the traveling salesman problem with time windows through dynamically generated time-expanded networks ⋮ New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times ⋮ Beam-ACO for the travelling salesman problem with time windows ⋮ Capacitated lot sizing and sequence dependent setup scheduling: An iterative approach for integration ⋮ A polyhedral study of the asymmetric traveling salesman problem with time windows ⋮ Finding \(K\) shortest looping paths with waiting time in a time--window network ⋮ Dynamic programming based metaheuristics for the dial-a-ride problem ⋮ Optimizing Time Slot Allocation in Single Operator Home Delivery Problems ⋮ A metaheuristic for the delivery man 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 ⋮ Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the travelling salesman problem with time windows ⋮ A stochastic dynamic traveling salesman problem with hard time windows ⋮ The rural postman problem with deadline classes ⋮ Combining traveling salesman and traveling repairman problems: a multi-objective approach based on multiple scenarios ⋮ A soft dynamic programming approach for on-line aircraft 4D-trajectory optimization ⋮ Single-vehicle scheduling with time window constraints ⋮ An ant colony system approach for variants of the traveling salesman problem with time windows ⋮ Unconstrained binary models of the travelling salesman problem variants for quantum optimization ⋮ Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version ⋮ Compact formulations of the Steiner traveling salesman problem and related problems ⋮ Minimization of travel time and weighted number of stops in a traffic-light network ⋮ Improving the filtering of branch-and-bound MDD solver ⋮ A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs

This page was built for publication: An Optimal Algorithm for the Traveling Salesman Problem with Time Windows