The complexity of the travelling repairman problem
From MaRDI portal
Publication:3709900
DOI10.1051/ita/1986200100791zbMath0585.68057OpenAlexW80909727MaRDI QIDQ3709900
Foto N. Afrati, Nadia Papakostantinou, Christos H. Papadimitriou, George Papageorgiou, Stavros S. Cosmandakis
Publication date: 1986
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92248
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)
Related Items
A constant-factor approximation for directed latency in quasi-polynomial time ⋮ A note on the traveling repairman problem ⋮ Exact algorithms for the minimum latency problem ⋮ Polynomial time algorithms for some minimum latency problems ⋮ Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Solving the traveling repairman problem on a line with general processing times and deadlines ⋮ Integrated production and logistics planning: contract manufacturing and choice of air/surface transportation ⋮ A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones ⋮ Heuristics for the traveling repairman problem with profits ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ Scheduling last-mile deliveries with truck-based autonomous robots ⋮ Finding optimal tour schedules on transportation paths under extended time window constraints ⋮ Routing problems: A bibliography ⋮ On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis ⋮ On the existence of schedules that are near-optimal for both makespan and total weighted completion time ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ Approximation algorithms for the a priori traveling repairman ⋮ Modeling emergency response operations: a theory building survey ⋮ An online optimization approach for post-disaster relief distribution with online blocked edges ⋮ Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem ⋮ Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND ⋮ Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining ⋮ News from the online traveling repairman. ⋮ Routing open shop and flow shop scheduling problems ⋮ Emergency path restoration problems ⋮ Product warranty logistics: issues and challenges. ⋮ The Directed Minimum Latency Problem ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ Profit-based latency problems on the line ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ A truck and drones model for last-mile delivery: a mathematical model and heuristic approach ⋮ Open problems around exact algorithms ⋮ On the power of lookahead in on-line server routing problems ⋮ Solving the traveling repairman problem with profits: a novel variable neighborhood search approach ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ Minimizing the average searching time for an object within a graph ⋮ Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem ⋮ Machine scheduling with deliveries to multiple customer locations ⋮ Complexity of decision-theoretic troubleshooting ⋮ The A priori traveling repairman problem ⋮ A new formulation for the traveling deliveryman problem ⋮ Optimally solving a versatile traveling salesman problem on tree networks with soft due dates and multiple congestion scenarios ⋮ Single-vehicle scheduling problems with release and service times on a line ⋮ Vehicle routing problems on a line-shaped network with release time constraints ⋮ An Improved Online Algorithm for the Traveling Repairperson Problem on a Line ⋮ An improved approximation ratio for the minimum latency problem ⋮ Combining traveling salesman and traveling repairman problems: a multi-objective approach based on multiple scenarios ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Policies for the dynamic traveling maintainer problem with alerts ⋮ On Analyzing Cost Allocation Problems: Cooperation Building Structures and Order Problem Representations
Cites Work
