Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem

DOI10.1287/opre.31.5.938zbMath0549.90072OpenAlexW2093665022MaRDI QIDQ3342216

Edward Baker

Publication date: 1983

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

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

zbMATH Keywords

disjunctive graph modelComputational resultstime window constraintsbranch and bound solution procedurelongest path algorithmtime-constrained traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items (30)

Time-constrained Chinese postman problems ⋮ 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 ⋮ A hybrid heuristic procedure for the windy rural postman problem with zigzag time windows ⋮ A traveling salesman problem with pickups and deliveries, time windows and draft limits: case study from chemical shipping ⋮ Routing problems: A bibliography ⋮ Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints ⋮ The bus sightseeing problem ⋮ Solving the single crane scheduling problem at rail transshipment yards ⋮ A branch-and-bound approach for a vehicle routing problem with customer costs ⋮ 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 ⋮ The delivery man problem with time windows ⋮ Shipping problems with body clock constraints. ⋮ On the computational complexity of the probabilistic traveling salesman problem with deadlines ⋮ A variable iterated greedy algorithm for the traveling salesman problem with time windows ⋮ Implementation of a linear time algorithm for certain generalized traveling salesman problems ⋮ Perspectives on integer programming for time-dependent models ⋮ Shuffling heuristics for the storage location assignment in an AS/RS ⋮ 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 ⋮ A polyhedral study of the asymmetric 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 ⋮ 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 ⋮ An algorithm for the traveling salesman problem with pickup and delivery customers ⋮ The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations ⋮ Minimization of travel time and weighted number of stops in a traffic-light network ⋮ Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks

This page was built for publication: Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem