Free Access

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

Edward K. Baker
Edward K. Baker
University of Miami, Coral Gables, Florida
Search for more papers by this author

Edward K. Baker

University of Miami, Coral Gables, Florida

Search for more papers by this author

Published Online:1 Oct 1983https://doi.org/10.1287/opre.31.5.938

Cited by
- Beware of the classical benchmark instances for the Traveling Salesman Problem with Time Windows
  Computers & Operations Research, Vol. 191
- Expressivity limits in quantum walk-based optimization
  17 February 2026 | Physical Review A, Vol. 113, No. 2
- Linear programming for UAVs search path planning in livestock health monitoring
  Computers and Electronics in Agriculture, Vol. 240
- Learning implicit multiple time windows in the Traveling Salesman Problem
  Transportation Research Procedia, Vol. 82
- An intensification-driven search algorithm for the family traveling salesman problem with incompatibility constraints
  Knowledge-Based Systems, Vol. 302
- A Cooperative Scheduling Based on Deep Reinforcement Learning for Multi-Agricultural Machines in Emergencies
  17 May 2024 | Agriculture, Vol. 14, No. 5
- A general variable neighborhood search for the traveling salesman problem with time windows under various objectives
  Discrete Applied Mathematics, Vol. 346
- Machine learning-enhanced aircraft landing scheduling under uncertainties
  Transportation Research Part C: Emerging Technologies, Vol. 158
- Integrating driver behavior into last-mile delivery routing: Combining machine learning and optimization in a hybrid decision support framework
  European Journal of Operational Research, Vol. 311, No. 1
- The bus sightseeing problem
  7 June 2022 | International Transactions in Operational Research, Vol. 30, No. 6
- Iterated Maximum Large Neighborhood Search for the Traveling Salesman Problem with Time Windows and its Time-dependent Version
  Computers & Operations Research, Vol. 150
- Learning to Solve Multiple-TSP With Time Window and Rejections via Deep Reinforcement Learning
  IEEE Transactions on Intelligent Transportation Systems, Vol. 24, No. 1
- Random Forest Regression Model AugmenteD With KL Algorithm (RFRKL) To Minimize Power In FSM Synthesis
- Unconstrained binary models of the travelling salesman problem variants for quantum optimization
  22 January 2022 | Quantum Information Processing, Vol. 21, No. 2
- Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
  22 November 2021 | Sustainability, Vol. 13, No. 22
- Optimizing quality of experience in Tourist Traveling Problem with Time Windows
- Solving two-stage stochastic route-planning problem in milliseconds via end-to-end deep learning
  14 February 2021 | Complex & Intelligent Systems, Vol. 7, No. 3
- Looking for Charizard: applying the orienteering problem to location-based games
  31 July 2019 | The Visual Computer, Vol. 37, No. 1
- A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs
  EURO Journal on Computational Optimization, Vol. 9
- Deep Reinforcement Learning for Traveling Salesman Problem with Time Windows and Rejections
- Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows
  Duc Minh Vu,
  Mike Hewitt,
  Natashia Boland,
  Martin Savelsbergh
  8 August 2019 | Transportation Science, Vol. 54, No. 3
- Electric Vehicle Tour Planning Considering Range Anxiety
  2 May 2020 | Sustainability, Vol. 12, No. 9
- Coordinated Production and Delivery Operations With Parallel Machines and Multiple Vehicles
  IEEE Access, Vol. 8
- Perspectives on integer programming for time-dependent models
  10 May 2019 | TOP, Vol. 27, No. 2
- Solving the single crane scheduling problem at rail transshipment yards
  Discrete Applied Mathematics, Vol. 264
- On Designing Near-Optimum Paths on Weighted Regions for an Intelligent Vehicle
  4 June 2018 | International Journal of Intelligent Transportation Systems Research, Vol. 17, No. 2
- Fuzzy System and Time Window Applied to Traffic Service Network Problems under a Multi-Demand Random Network
  13 May 2019 | Electronics, Vol. 8, No. 5
- Optimization of vehicle routing problem with fatigue driving based on genetic algorithm
  9 October 2018
- Where's Pikachu: Route Optimization in Location-Based Games
- A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling
  Anirudh Subramanyam,
  Chrysanthos E. Gounaris
  17 April 2017 | Transportation Science, Vol. 52, No. 2
- A hybrid heuristic procedure for the Windy Rural Postman Problem with Zigzag Time Windows
  Computers & Operations Research, Vol. 88
- An improved ant colony optimization for green multi-depot vehicle routing problem with time windows
- Dynamic Programming for the Minimum Tour Duration Problem
  Christian Tilk,
  Stefan Irnich
  25 March 2016 | Transportation Science, Vol. 51, No. 2
- A traveling salesman problem with pickups and deliveries, time windows and draft limits: Case study from chemical shipping
  Computers & Operations Research, Vol. 77
- A Bi-criteria Ant Colony Optimization for Minimizing Fuel Consumption and Cost of The Traveling Salesman Problem With Time Windows
  Procedia Computer Science, Vol. 112
- Trajectory recommendation for task accomplishment in crowdsourcing – a model to favour different actors
  7 June 2016 | Journal of Location Based Services, Vol. 10, No. 2
- Solving the Routing Problems with Time Windows
  5 February 2016
- Heuristics for Task Recommendation in Spatiotemporal Crowdsourcing Systems
  11 December 2015
- Opportunistic Trajectory Recommendation for Task Accomplishment in Crowdsourcing Systems
  23 April 2015
- Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows
  Procedia Economics and Finance, Vol. 26
- Mission Design of a Team of Service Robots
- Pricing routines for vehicle routing with time windows on road networks
  Computers & Operations Research, Vol. 51
- A variable iterated greedy algorithm for the traveling salesman problem with time windows
  Information Sciences, Vol. 279
- On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines
  Theoretical Computer Science, Vol. 540-541
- Efficient Constraint Handling in Electromagnetism-Like Algorithm for Traveling Salesman Problem with Time Windows
  The Scientific World Journal, Vol. 2014
- Mission Planning of Mobile Robots and Manipulators for Service Applications
- New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times
  7 August 2013 | Optimization, Vol. 62, No. 10
- The travelling salesman problem with time windows: Adapting algorithms from travel-time to makespan optimization
  Applied Soft Computing, Vol. 13, No. 9
- Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling
  Computers & Operations Research, Vol. 40, No. 7
- Algorithm and knowledge engineering for the TSPTW problem
- An Incremental Online Heuristic For Evaluating The Feasibility Of The M-VRPTWAR
  20 December 2012
- Ant colony optimisation with random selection for block transportation scheduling with heterogeneous transporters in a shipyard
  International Journal of Production Research, Vol. 50, No. 24
- New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows
  Roberto Baldacci,
  Aristide Mingozzi,
  Roberto Roberti,
  17 May 2011 | INFORMS Journal on Computing, Vol. 24, No. 3
- A discrete artificial bee colony algorithm for the traveling salesman problem with time windows
- INTEGRATING PATH PLANNING, ROUTING, AND SCHEDULING FOR LOGISTICS OPERATIONS IN MANUFACTURING FACILITIES
  Cybernetics and Systems, Vol. 43, No. 3
- A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows
  Sanjeeb Dash,
  Oktay Günlük,
  Andrea Lodi,
  Andrea Tramontani,
  29 December 2010 | INFORMS Journal on Computing, Vol. 24, No. 1
- Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
- Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows
- Mission Planning of Mobile Robots and Manipulators for Service Applications
- Computational study of neighborhood operator performance on the Traveling Salesman Problem with Time Windows in neighborhood search based frameworks (RTS, VNS)
- Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows
- Mission design for a group of autonomous guided vehicles
  Robotics and Autonomous Systems, Vol. 59, No. 1
- The Delivery Man Problem with time windows
  Discrete Optimization, Vol. 7, No. 4
- An ant colony system approach for fuzzy traveling salesman problem with time windows
  10 March 2010 | The International Journal of Advanced Manufacturing Technology, Vol. 50, No. 9-12
- Beam-ACO for the travelling salesman problem with time windows
  Computers & Operations Research, Vol. 37, No. 9
- Transporter scheduling based on a network flow model under a dynamic block transportation environment1
- Vehicle scheduling in 2D shop floor environments
  Industrial Robot: An International Journal, Vol. 36, No. 2
- Ant colony system for job shop scheduling with time windows
  15 September 2007 | The International Journal of Advanced Manufacturing Technology, Vol. 39, No. 1-2
- Modeling Time-Constraints in Construction Operations through Simulation
  Journal of Construction Engineering and Management, Vol. 134, No. 7
- Probabilistic Traveling Salesman Problem with Deadlines
  Ann M. Campbell,
  Barrett W. Thomas,
  1 February 2008 | Transportation Science, Vol. 42, No. 1
- Integer Programming Models of Bookmobile Routing
- Transporter Scheduling under Dynamic Block Transportation Environment
- Locating a cycle in a transportation or a telecommunications network
  2 May 2007 | Networks, Vol. 50, No. 1
- A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows
  Jeffrey W. Ohlmann,
  Barrett W. Thomas,
  1 February 2007 | INFORMS Journal on Computing, Vol. 19, No. 1
- Problema do carteiro chinês: escolha de métodos de solução e análise de tempos computacionais
  Production, Vol. 16, No. 3
- Particle Swarm Optimization for Preemptive Scheduling under Break and Resource-Constraints
  Journal of Construction Engineering and Management, Vol. 132, No. 3
- Consideration of break in modeling of construction processes
  Engineering, Construction and Architectural Management, Vol. 12, No. 4
- The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations
  Mathematical and Computer Modelling, Vol. 41, No. 8-9
- Measuring Spatial Separation: Distance, Time, Routing, and Accessibility
- Time analysis for planning a path in a time-window network
  21 December 2017 | Journal of the Operational Research Society, Vol. 54, No. 8
- Shipping problems with body clock constraints
  Computers & Operations Research, Vol. 30, No. 7
- Minimization of travel time and weighted number of stops in a traffic-light network
  European Journal of Operational Research, Vol. 144, No. 3
- A Hybrid Exact Algorithm for the TSPTW
  Filippo Focacci,
  Andrea Lodi,
  Michela Milano,
  1 November 2002 | INFORMS Journal on Computing, Vol. 14, No. 4
- Time-constrained Chinese postman problems
  Computers & Mathematics with Applications, Vol. 44, No. 3-4
- Better approximation ratios for the single‐vehicle scheduling problems on line‐shaped networks
  31 May 2002 | Networks, Vol. 39, No. 4
- Formulating the steel scheduling problem as a TSPTW
- Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
  Egon Balas,
  Neil Simonetti,
  1 February 2001 | INFORMS Journal on Computing, Vol. 13, No. 1
- Non-Static Network Optimization Problems: A Survey
- A polyhedral study of the asymmetric traveling salesman problem with time windows
  1 January 2000 | Networks, Vol. 36, No. 2
- A travelling salesman problem with allocation, time window and precedence constraints — an application to ship scheduling
  24 August 2006 | International Transactions in Operational Research, Vol. 7, No. 3
- A New Heuristic for the Traveling Salesman Problem with Time Windows
  Roberto Wolfler Calvo,
  1 February 2000 | Transportation Science, Vol. 34, No. 1
- Production management practice in a developing country: a case study
  24 August 2006 | International Transactions in Operational Research, Vol. 6, No. 6
- O problema do seqüenciamento da produção em uma indústria química: avaliação de uma aplicação real
  Gestão & Produção, Vol. 6, No. 1
- A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows
  Michel Gendreau,
  Alain Hertz,
  Gilbert Laporte,
  Mihnea Stan,
  1 June 1998 | Operations Research, Vol. 46, No. 3
- Case study: improving industrial competitiveness: a TSP approach
  Logistics Information Management, Vol. 11, No. 3
- An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows
  Gilles Pesant,
  Michel Gendreau,
  Jean-Yves Potvin,
  Jean-Marc Rousseau,
  1 February 1998 | Transportation Science, Vol. 32, No. 1
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems
- Vehicle scheduling on a tree with release and handling times
  Annals of Operations Research, Vol. 69, No. 0
- Solving the Traveling-Salesman Problem with Time Windows Using Tabu Search
  13 September 2016 | IIE Transactions, Vol. 28, No. 8
- Implementation of a linear time algorithm for certain generalized traveling salesman problems
  3 June 2005
- Routing problems: A bibliography
  Annals of Operations Research, Vol. 61, No. 1
- Shuffling heuristics for the storage location assignment in an AS/RS
  26 April 2007 | International Journal of Production Research, Vol. 33, No. 6
- A Survey of Intelligent Scheduling Systems
- Chapter 2 Time constrained routing and scheduling
- A stochastic scheduling problem issued from iron and steel industry : Some results
  23 June 2005
- A two‐commodity flow formulation for the traveling salesman and the makespan problems with time windows
  11 October 2006 | Networks, Vol. 23, No. 7
- Vehicle scheduling on a tree with release and handling times
  1 June 2005
- Signal routing with temporal constraints
- Signal Routing With Temporal Constraints
- Auswahl von theoriebezogenen Veröffentlichungen
- GENETIC ALGORITHMS FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS
- Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de l'art
  29 March 2011 | RAIRO - Operations Research, Vol. 24, No. 3
- Models and algorithms for a two-stage production process
  16 May 2007 | Production Planning & Control, Vol. 1, No. 1
- Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints
  American Journal of Mathematical and Management Sciences, Vol. 6, No. 3-4
- An algorithm for the traveling salesman problem with pickup and delivery customers
  European Journal of Operational Research, Vol. 22, No. 3
- Future directions in logistics research
  Transportation Research Part A: General, Vol. 19, No. 5-6

Volume 31, Issue 5

September-October 1983

Pages 803-971

Article Information

Metrics

Information

Published Online:October 01, 1983

Cite as

Edward K. Baker, (1983) Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem. Operations Research 31(5):938-945.

https://doi.org/10.1287/opre.31.5.938

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

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

Volume 31, Issue 5

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News