The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling

DOI10.1287/opre.26.1.86zbMath0371.90066MaRDI QIDQ4147830

Maurice Queyranne, Jean-Claude Picard

Publication date: 1978

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

Full work available at URL: https://publications.polymtl.ca/6094/1/EP-R-77-12_Picard.pdf

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C35: Extremal problems in graph theory

90C90: Applications of mathematical programming

90B35: Deterministic scheduling theory in operations research

Related Items

Two-machine flowshop scheduling to minimize total tardiness, Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times, Looking ahead with the pilot method, A controlled search simulated annealing method for the single machine weighted tardiness problem, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, A new formulation for the traveling deliveryman problem, Dynamic programming and decomposition approaches for the single machine total tardiness problem, Real-time scheduling of an automated manufacturing center, Convergent duality for the traveling salesman problem, An analytical comparison of different formulations of the travelling salesman problem, A time indexed formulation of non-preemptive single machine scheduling problems, A tool-change scheduling model for machining centres, A survey of algorithms for the single machine total weighted tardiness scheduling problem, One machine scheduling to minimize expected mean tardiness. II, Scheduling in a sequence dependent setup environment with genetic search, A classification of formulations for the (time-dependent) traveling salesman problem, Solving the continuous flow-shop scheduling problem by metaheuristics., A dynamic vehicle routing problem with time-dependent travel times, Some concepts of stability analysis in combinatorial optimization, Using short-term memory to minimize the weighted number of late jobs on a single machine., A decomposition algorithm for the single machine total tardiness problem, Vehicle dispatching with time-dependent travel times, Improving the performance of enumerative search methods. I: Exploiting structure and intelligence, A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times, Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times, Reformulation by discretization: application to economic lot sizing, Minimizing total tardiness in a scheduling problem with a learning effect, Formulations and exact algorithms for the vehicle routing problem with time windows, A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times, A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Time-dependent travelling salesman problem., On the capacitated concentrator location problem: a reformulation by discretization, Optimierung des Schülerverkehrs durch gemischt ganzzahlige Programmierung