Solving the traveling repairman problem on a line with general processing times and deadlines

Stefan Bock ()

European Journal of Operational Research, 2015, vol. 244, issue 3, 690-703

Abstract: This paper resolves the complexity status of the well-known Traveling Repairman Problem on a line (Line-TRP) with general processing times at the request locations and deadline restrictions. It has long remained an open research question whether an exact solution procedure with pseudo-polynomial running time can be developed for this version of the Traveling Repairman Problem that was known to be at least binary NP-hard. The presented proof of strong NP-completeness of the problem is provided by a reduction from 3-PARTITION. Since recent literature provides significant new results for further variants of the Line-TRP and the Line-TSP, a brief updated overview of the complexity status of the different variants is given. Another major contribution is that a practically applicable exact best-first search Branch&Bound approach that optimally solves instances of real-world size in reasonable time is proposed. By applying sophisticated dominance rules as well as lower bounds, the number of enumerated partial solutions is kept limited. The efficiency of the new approach and the applied instruments is validated by a computational study.

Keywords: Line-traveling repairman problem; Optimal schedules; Complexity analysis; Branch&Bound (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171500106X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:244:y:2015:i:3:p:690-703

DOI: 10.1016/j.ejor.2015.02.009

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().