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

DOI10.1287/opre.26.1.86zbMath0371.90066OpenAlexW2072136110MaRDI 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

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Applications of mathematical programming (90C90) Deterministic scheduling theory in operations research (90B35)

Related Items

An integer programming approach for the time-dependent TSP, One machine scheduling to minimize expected mean tardiness. II, Layered graph approaches for combinatorial optimization problems, A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine, An integrated approach for earthwork allocation, sequencing and routing, Scheduling in a sequence dependent setup environment with genetic search, Dynamic programming and decomposition approaches for the single machine total tardiness problem, Improving the performance of enumerative search methods. I: Exploiting structure and intelligence, The traveling salesman problem with time-dependent service times, Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem, Dealing with time in the multiple traveling salespersons problem with moving targets, Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations, An integer programming approach for the time-dependent traveling salesman problem with time windows, The traveling purchaser problem with time-dependent quantities, A branch-and-price algorithm for the minimum latency problem, Load-dependent and precedence-based models for pickup and delivery problems, Time-dependent routing problems: a review, Real-time scheduling of an automated manufacturing center, The arc-item-load and related formulations for the cumulative vehicle routing problem, Approximation algorithms for the a priori traveling repairman, On path ranking in time-dependent graphs, An online optimization approach for post-disaster relief distribution with online blocked edges, A simple and effective metaheuristic for the minimum latency problem, Routing multiple work teams to minimize latency in post-disaster road network restoration, A classification of formulations for the (time-dependent) traveling salesman problem, Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery, Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem, Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem, Minimizing total weighted latency in home healthcare routing and scheduling with patient prioritization, Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery, Tight lower bounds for the traveling salesman problem with draft limits, The Surgical Patient Routing Problem: A Central Planner Approach, The travelling salesman problem with positional consistency constraints: an application to healthcare services, A bi-criteria moving-target travelling salesman problem under uncertainty, A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem, Optimization of interception plan for rectilinearly moving targets, The delivery man problem with time windows, The time dependent traveling salesman problem: polyhedra and algorithm, A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times, Scheduling with time-dependent discrepancy times, Solving the continuous flow-shop scheduling problem by metaheuristics., Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem, A controlled search simulated annealing method for the single machine weighted tardiness problem, Two-machine flowshop scheduling to minimize total tardiness, Convergent duality for the traveling salesman problem, An analytical comparison of different formulations of the travelling salesman problem, Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times, Natural and extended formulations for the time-dependent traveling salesman problem, Minimizing latency in post-disaster road clearance operations, A comparison of algorithms for finding an efficient theme park tour, Reformulation by discretization: application to economic lot sizing, Minimizing total tardiness in a scheduling problem with a learning effect, Weighted online minimum latency problem with edge uncertainty, Arc flow formulations based on dynamic programming: theoretical foundations and applications, Formulations and exact algorithms for the vehicle routing problem with time windows, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows, Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems, A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times, A time indexed formulation of non-preemptive single machine scheduling problems, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Fitness landscape analysis for the no-wait flow-shop scheduling problem, Hybrid optimization methods for time-dependent sequencing problems, A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Time-dependent travelling salesman problem., Perspectives on integer programming for time-dependent models, An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem, Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times, Models for a traveling purchaser problem with additional side-constraints, On the capacitated concentrator location problem: a reformulation by discretization, A dynamic vehicle routing problem with time-dependent travel times, A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem, Almost sure asymptotic optimality for online routing and machine scheduling problems, A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints, A minmax regret version of the time-dependent shortest path problem, Facets and valid inequalities for the time-dependent travelling salesman problem, A new formulation for the traveling deliveryman problem, Models and algorithms for the traveling salesman problem with time-dependent service times, A tool-change scheduling model for machining centres, Some concepts of stability analysis in combinatorial optimization, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Using short-term memory to minimize the weighted number of late jobs on a single machine., A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Optimierung des Schülerverkehrs durch gemischt ganzzahlige Programmierung, Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints, An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem, A decomposition algorithm for the single machine total tardiness problem, An enhanced lower bound for the time-dependent travelling salesman problem, A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem, Vehicle dispatching with time-dependent travel times, Looking ahead with the pilot method