A note on the traveling repairman problem

DOI10.1002/net.10031zbMath1027.90104OpenAlexW2031458380MaRDI QIDQ4785216

Pedro Jodrá, Alfredo Daniel Garcia, F. Javier Tejel

Publication date: 17 December 2002

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10031

zbMATH Keywords

computational complexitydynamic programmingminimum latency problemtraveling repairman problemMonge matrices

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Dynamic programming (90C39)

Related Items (18)

Exact algorithms for the minimum latency problem ⋮ Solving the traveling repairman problem on a line with general processing times and deadlines ⋮ Maintenance scheduling of geographically distributed assets with prognostics information ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ Finding optimal tour schedules on transportation paths under extended time window constraints ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach ⋮ A simple and effective metaheuristic for the minimum latency problem ⋮ Minimizing total weighted latency in home healthcare routing and scheduling with patient prioritization ⋮ Variable neighborhood search based algorithms to solve a rich \(k\)-travelling repairmen problem ⋮ Profit-based latency problems on the line ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem ⋮ Single-vehicle scheduling problems with release and service times on a line ⋮ Vehicle routing problems on a line-shaped network with release time constraints ⋮ Vehicle scheduling with combinable delivery and pickup operations ⋮ 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

Cites Work

• An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
• A linear-time algorithm for concave one-dimensional dynamic programming
• The delivery man problem on a tree network
• The complexity of the travelling repairman problem
• The concave least-weight subsequence problem revisited
• Special cases of traveling salesman and repairman problems with time windows
• Improved Algorithms for Economic Lot Size Problems
• Sales‐delivery man problems on treelike networks
• On-line dynamic programming with applications to the prediction of RNA secondary structure

This page was built for publication: A note on the traveling repairman problem