The complexity of the travelling repairman problem
RAIRO-Theor. Inf. Appl., 20 1 (1986) 79-87
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
(2024)
https://doi.org/10.2139/ssrn.4690805
Scalable policies for the dynamic traveling multi-maintainer problem with alerts
Peter Verleijsdonk, Willem van Jaarsveld and Stella KapodistriaEuropean Journal of Operational Research 319 (1) 121 (2024)
https://doi.org/10.1016/j.ejor.2024.05.049
Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem
Moïse Blanchard, Alexandre Jacquillat and Patrick JailletMathematics of Operations Research 49 (2) 1169 (2024)
https://doi.org/10.1287/moor.2021.0286
Vehicle routing for connected service areas - a versatile approach covering single, hierarchical, and bi-criteria objectives
Stefan BockEuropean Journal of Operational Research 313 (3) 905 (2024)
https://doi.org/10.1016/j.ejor.2023.08.051
Frontiers in Operations: Waiting Experience in Open-Shop Service Networks: Improvements via Flow Analytics and Automation
Manlu Chen, Opher Baron, Avishai Mandelbaum, Jianfu Wang, Galit B. Yom-Tov and Nadir ArberManufacturing & Service Operations Management 26 (4) 1211 (2024)
https://doi.org/10.1287/msom.2022.0590
A survey on the Traveling Salesman Problem and its variants in a warehousing context
Stefan Bock, Stefan Bomsdorf, Nils Boysen and Michael SchneiderEuropean Journal of Operational Research (2024)
https://doi.org/10.1016/j.ejor.2024.04.014
443 (2023)
https://doi.org/10.1007/978-3-031-24907-5_53
A Novel Bias-TSP Algorithm for Maritime Patrol
Geraldo Mulato de Lima Filho, Angelo Passaro, Guilherme Moura Delfino and Herman MonsuurIEEE Access 11 28190 (2023)
https://doi.org/10.1109/ACCESS.2023.3252013
5645 (2023)
https://doi.org/10.1109/ICRA48891.2023.10160473
Policies for the dynamic traveling maintainer problem with alerts
Paulo da Costa, Peter Verleijsdonk, Simon Voorberg, et al.European Journal of Operational Research 305 (3) 1141 (2023)
https://doi.org/10.1016/j.ejor.2022.06.044
Waiting Experience in Open-Shop Service Networks: Improvements via Flow Analytics & Automation
Manlu Chen, Opher Baron, Avishai Mandelbaum, Jianfu Wang, Galit Yom-Tov and Nadir ArberSSRN Electronic Journal (2022)
https://doi.org/10.2139/ssrn.4018744
Intensification-driven local search for the traveling repairman problem with profits
Jintong Ren, Jin-Kao Hao, Feng Wu and Zhang-Hua FuExpert Systems with Applications 202 117072 (2022)
https://doi.org/10.1016/j.eswa.2022.117072
Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND
Miroslav Kulich and Libor PřeučilInternational Transactions in Operational Research 29 (2) 805 (2022)
https://doi.org/10.1111/itor.12794
A constant-factor approximation for directed latency in quasi-polynomial time
Zachary Friggstad and Chaitanya SwamyJournal of Computer and System Sciences 126 44 (2022)
https://doi.org/10.1016/j.jcss.2021.12.001
The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing Problem
Mauro Henrique Mulati, Ricardo Fukasawa and Flávio Keidi MiyazawaDiscrete Optimization 45 100710 (2022)
https://doi.org/10.1016/j.disopt.2022.100710
Proceedings of the Sixteenth International Conference on Management Science and Engineering Management – Volume 1
Gozde Onder Uzun, Berna Dengiz, Imdat Kara and Oya Ekin KarasanLecture Notes on Data Engineering and Communications Technologies, Proceedings of the Sixteenth International Conference on Management Science and Engineering Management – Volume 1 144 506 (2022)
https://doi.org/10.1007/978-3-031-10388-9_37
Improving a state‐of‐the‐art heuristic for the minimum latency problem with data mining
Ítalo Santana, Alexandre Plastino and Isabel RossetiInternational Transactions in Operational Research 29 (2) 959 (2022)
https://doi.org/10.1111/itor.12774
A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones
M.E. Bruni, S. Khodaparasti and M. Moshref-JavadiComputers & Operations Research 145 105845 (2022)
https://doi.org/10.1016/j.cor.2022.105845
An online optimization approach for post-disaster relief distribution with online blocked edges
Vahid Akbari and Davood ShiriComputers & Operations Research 137 105533 (2022)
https://doi.org/10.1016/j.cor.2021.105533
Exact and Approximation Algorithms for the Expanding Search Problem
Ben Hermans, Roel Leus and Jannik MatuschkeINFORMS Journal on Computing 34 (1) 281 (2022)
https://doi.org/10.1287/ijoc.2020.1047
13728 690 (2022)
https://doi.org/10.1007/978-3-031-22695-3_48
1156 (2021)
https://doi.org/10.1109/IV48863.2021.9576002
Weighted online minimum latency problem with edge uncertainty
Vahid Akbari and Davood ShiriEuropean Journal of Operational Research 295 (1) 51 (2021)
https://doi.org/10.1016/j.ejor.2021.02.038
A Systematic Framework for Maintenance Scheduling and Routing for Off-Shore Wind Farms by Minimizing Predictive Production Loss
Jianshe Feng, Haoshu Cai, Zongchang Liu, et al.E3S Web of Conferences 233 01063 (2021)
https://doi.org/10.1051/e3sconf/202123301063
New formulations for the traveling repairman problem with time windows
Gözde Önder Uzun and İmdat KaraExpert Systems with Applications 176 114863 (2021)
https://doi.org/10.1016/j.eswa.2021.114863
Tight Bounds for Online TSP on the Line
Antje Bjelde, Jan Hackfeld, Yann Disser, et al.ACM Transactions on Algorithms 17 (1) 1 (2021)
https://doi.org/10.1145/3422362
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
René SittersSIAM Journal on Computing 50 (5) 1580 (2021)
https://doi.org/10.1137/19M126918X
Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem
Noura Smiti, Mohamed Mahjoub Dhiaf, Bassem Jarboui and Saïd HanafiInternational Transactions in Operational Research 27 (1) 651 (2020)
https://doi.org/10.1111/itor.12513
Optimally solving a versatile Traveling Salesman Problem on tree networks with soft due dates and multiple congestion scenarios
Stefan BockEuropean Journal of Operational Research 283 (3) 863 (2020)
https://doi.org/10.1016/j.ejor.2019.11.058
Solving the traveling repairman problem with profits: A Novel variable neighborhood search approach
Jun Pei, Nenad Mladenović, Dragan Urošević, Jack Brimberg and Xinbao LiuInformation Sciences 507 108 (2020)
https://doi.org/10.1016/j.ins.2019.08.017
Approximation algorithms for the a priori traveling repairman
Fatemeh Navidi, Inge Li Gørtz and Viswanath NagarajanOperations Research Letters 48 (5) 599 (2020)
https://doi.org/10.1016/j.orl.2020.07.009
Modeling emergency response operations: A theory building survey
J.P. Minas, N.C. Simpson and Z.Y. TachevaComputers & Operations Research 119 104921 (2020)
https://doi.org/10.1016/j.cor.2020.104921
Combining Traveling Salesman and Traveling Repairman Problems: A multi-objective approach based on multiple scenarios
Stefan Bock and Kathrin KlamrothComputers & Operations Research 112 104766 (2019)
https://doi.org/10.1016/j.cor.2019.104766
A bi-objective study of the minimum latency problem
N. A. Arellano-Arriaga, J. Molina, S. E. Schaeffer, A. M. Álvarez-Socarrás and I. A. Martínez-SalazarJournal of Heuristics 25 (3) 431 (2019)
https://doi.org/10.1007/s10732-019-09405-0
Apply the quantum particle swarm optimization for the K-traveling repairman problem
Sirine Jmal, Boukthir Haddar and Habib ChabchoubSoft Computing 23 (23) 12547 (2019)
https://doi.org/10.1007/s00500-019-03805-x
Minimizing the average searching time for an object within a graph
Ron Teller, Moshe Zofi and Moshe KaspiComputational Optimization and Applications 74 (2) 517 (2019)
https://doi.org/10.1007/s10589-019-00121-w
Online minimum latency problem with edge uncertainty
Huili Zhang, Weitian Tong, Guohui Lin and Yinfeng XuEuropean Journal of Operational Research 273 (2) 418 (2019)
https://doi.org/10.1016/j.ejor.2018.08.017
On Analyzing Cost Allocation Problems: Cooperation Building Structures and Order Problem Representations
John Kleppe, Peter Borm, Ruud Hendrickx and Hans ReijnierseInternational Game Theory Review 20 (04) 1850007 (2018)
https://doi.org/10.1142/S021919891850007X
Scheduling last-mile deliveries with truck-based autonomous robots
Nils Boysen, Stefan Schwerdfeger and Felix WeidingerEuropean Journal of Operational Research 271 (3) 1085 (2018)
https://doi.org/10.1016/j.ejor.2018.05.058
A branch-and-price algorithm for the Minimum Latency Problem
Teobaldo Bulhões, Ruslan Sadykov and Eduardo UchoaComputers & Operations Research 93 66 (2018)
https://doi.org/10.1016/j.cor.2018.01.016
Multiple searchers searching for a randomly distributed immobile target on a unit network
Songtao Li and Simin HuangNetworks 71 (1) 60 (2018)
https://doi.org/10.1002/net.21793
The Chinese Postman Problem with Load-Dependent Costs
Ángel Corberán, Güneş Erdoğan, Gilbert Laporte, Isaac Plana and José M. SanchisTransportation Science 52 (2) 370 (2018)
https://doi.org/10.1287/trsc.2017.0774
1 (2017)
https://doi.org/10.1109/ECMR.2017.8098696
Smart Cities
Nancy A. Arellano-Arriaga, Ada M. Álvarez-Socarrás and Iris A. Martínez-SalazarLecture Notes in Computer Science, Smart Cities 10268 11 (2017)
https://doi.org/10.1007/978-3-319-59513-9_2
The customer-centric, multi-commodity vehicle routing problem with split delivery
Mohammad Moshref-Javadi and Seokcheon LeeExpert Systems with Applications 56 335 (2016)
https://doi.org/10.1016/j.eswa.2016.03.030
A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem
Ricardo Fukasawa, Qie He and Yongjia SongTransportation Science 50 (1) 23 (2016)
https://doi.org/10.1287/trsc.2015.0593
Finding optimal tour schedules on transportation paths under extended time window constraints
Stefan BockJournal of Scheduling 19 (5) 527 (2016)
https://doi.org/10.1007/s10951-016-0481-1
A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem
Samuel Nucamendi-Guillén, Iris Martínez-Salazar, Francisco Angel-Bello and J Marcos Moreno-VegaJournal of the Operational Research Society 67 (8) 1121 (2016)
https://doi.org/10.1057/jors.2015.113
Solving the traveling repairman problem on a line with general processing times and deadlines
Stefan BockEuropean Journal of Operational Research 244 (3) 690 (2015)
https://doi.org/10.1016/j.ejor.2015.02.009
Extended Warranties, Maintenance Service and Lease Contracts
D. N. P. Murthy and Nat JackSpringer Series in Reliability Engineering, Extended Warranties, Maintenance Service and Lease Contracts 311 (2014)
https://doi.org/10.1007/978-1-4471-6440-1_11
(2014)
https://doi.org/10.1002/9781118445112.stat04184
Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints
Zhixing Luo, Hu Qin and Andrew LimEuropean Journal of Operational Research 234 (1) 49 (2014)
https://doi.org/10.1016/j.ejor.2013.09.014
Dynamic ng-Path Relaxation for the Delivery Man Problem
Roberto Roberti and Aristide MingozziTransportation Science 48 (3) 413 (2014)
https://doi.org/10.1287/trsc.2013.0474
A vehicle routing problem with multiple overlapped batches
Mingzhu Yu and Xiangtong QiTransportation Research Part E: Logistics and Transportation Review 61 40 (2014)
https://doi.org/10.1016/j.tre.2013.10.004
Vehicle routing problems with regular objective functions on a path
Wei Yu and Zhaohui LiuNaval Research Logistics (NRL) 61 (1) 34 (2014)
https://doi.org/10.1002/nav.21564
535 (2013)
https://doi.org/10.1109/ICAdLT.2013.6568515
Physical search problems with probabilistic knowledge
Noam Hazon, Yonatan Aumann, Sarit Kraus and David SarneArtificial Intelligence 196 26 (2013)
https://doi.org/10.1016/j.artint.2012.12.003
Sequence-dependent scheduling with order deliveries
B.M.T. Lin, P.Y. Yin and Y.S. LiuApplied Mathematics and Computation 222 58 (2013)
https://doi.org/10.1016/j.amc.2013.06.087
Heuristics for the traveling repairman problem with profits
T. Dewilde, D. Cattrysse, S. Coene, F.C.R. Spieksma and P. VansteenwegenComputers & Operations Research 40 (7) 1700 (2013)
https://doi.org/10.1016/j.cor.2013.01.003
Asymmetric Traveling Salesman Path and Directed Latency Problems
Zachary Friggstad, Mohammad R. Salavatipour and Zoya SvitkinaSIAM Journal on Computing 42 (4) 1596 (2013)
https://doi.org/10.1137/100797357
Emergency path restoration problems
Igor AverbakhDiscrete Optimization 9 (1) 58 (2012)
https://doi.org/10.1016/j.disopt.2012.01.001
The role of centrality in ambulance dispatching
Seokcheon LeeDecision Support Systems 54 (1) 282 (2012)
https://doi.org/10.1016/j.dss.2012.05.036
The flowtime network construction problem
Igor Averbakh and Jordi PereiraIIE Transactions 44 (8) 681 (2012)
https://doi.org/10.1080/0740817X.2011.636792
Routing open shop and flow shop scheduling problems
Wei Yu, Zhaohui Liu, Leiyang Wang and Tijun FanEuropean Journal of Operational Research 213 (1) 24 (2011)
https://doi.org/10.1016/j.ejor.2011.02.028
Algorithms and Computation
Wei Yu and Guochuan ZhangLecture Notes in Computer Science, Algorithms and Computation 7074 30 (2011)
https://doi.org/10.1007/978-3-642-25591-5_5
Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem
Amir Salehipour, Kenneth Sörensen, Peter Goos and Olli Bräysy4OR 9 (2) 189 (2011)
https://doi.org/10.1007/s10288-011-0153-0
Single-vehicle scheduling problems with release and service times on a line
Wei Yu and Zhaohui LiuNetworks 57 (2) 128 (2011)
https://doi.org/10.1002/net.20393
Computing and Combinatorics
Axel Simroth and Alexander SouzaLecture Notes in Computer Science, Computing and Combinatorics 5609 168 (2009)
https://doi.org/10.1007/978-3-642-02882-3_18
5780 (2009)
https://doi.org/10.1109/CDC.2009.5399521
Vehicle routing problems on a line-shaped network with release time constraints
Wei Yu and Zhaohui LiuOperations Research Letters 37 (2) 85 (2009)
https://doi.org/10.1016/j.orl.2008.10.006
Handbook of Maintenance Management and Engineering
D. N. P. Murthy and Nat JackHandbook of Maintenance Management and Engineering 461 (2009)
https://doi.org/10.1007/978-1-84882-472-0_18
On the power of lookahead in on-line server routing problems
Luca Allulli, Giorgio Ausiello, Vincenzo Bonifaci and Luigi LauraTheoretical Computer Science 408 (2-3) 116 (2008)
https://doi.org/10.1016/j.tcs.2008.08.003
A new formulation for the Traveling Deliveryman Problem
Isabel Méndez-Díaz, Paula Zabala and Abilio LucenaDiscrete Applied Mathematics 156 (17) 3223 (2008)
https://doi.org/10.1016/j.dam.2008.05.009
Open problems around exact algorithms
Gerhard J. WoegingerDiscrete Applied Mathematics 156 (3) 397 (2008)
https://doi.org/10.1016/j.dam.2007.03.023
Profit-based latency problems on the line
Sofie Coene and Frits C.R. SpieksmaOperations Research Letters 36 (3) 333 (2008)
https://doi.org/10.1016/j.orl.2007.11.001
Profit-Based Latency Problems on the Line
Sofie Coene and Frits SpieksmaSSRN Electronic Journal (2008)
https://doi.org/10.2139/ssrn.1290504
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Viswanath Nagarajan and R. RaviLecture Notes in Computer Science, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques 5171 193 (2008)
https://doi.org/10.1007/978-3-540-85363-3_16
A Faster, Better Approximation Algorithm for the Minimum Latency Problem
Aaron Archer, Asaf Levin and David P. WilliamsonSIAM Journal on Computing 37 (5) 1472 (2008)
https://doi.org/10.1137/07068151X
(2007)
https://doi.org/10.1002/9780470061572.eqr133
Theory and Applications of Models of Computation
Giorgio Ausiello, Luca Allulli, Vincenzo Bonifaci and Luigi LauraLecture Notes in Computer Science, Theory and Applications of Models of Computation 3959 1 (2006)
https://doi.org/10.1007/11750321_1
Warranty Management and Product Manufacture
Springer Series in Reliability Engineering, Warranty Management and Product Manufacture 217 (2006)https://doi.org/10.1007/1-84628-258-6_11
Machine scheduling with deliveries to multiple customer locations
Chung-Lun Li, George Vairaktarakis and Chung-Yee LeeEuropean Journal of Operational Research 164 (1) 39 (2005)
https://doi.org/10.1016/j.ejor.2003.11.022
Computer-Aided Complexity Classification of Dial-a-Ride Problems
Willem E. de Paepe, Jan Karel Lenstra, Jiri Sgall, René A. Sitters and Leen StougieINFORMS Journal on Computing 16 (2) 120 (2004)
https://doi.org/10.1287/ijoc.1030.0052
Exact algorithms for the minimum latency problem
Bang Ye Wu, Zheng-Nan Huang and Fu-Jie ZhanInformation Processing Letters 92 (6) 303 (2004)
https://doi.org/10.1016/j.ipl.2004.09.009
36 (2003)
https://doi.org/10.1109/SFCS.2003.1238179
Approximation Schemes for Minimum Latency Problems
Sanjeev Arora and George KarakostasSIAM Journal on Computing 32 (5) 1317 (2003)
https://doi.org/10.1137/S0097539701399654
News from the online traveling repairman
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen and Leen StougieTheoretical Computer Science 295 (1-3) 279 (2003)
https://doi.org/10.1016/S0304-3975(02)00409-7
Complexity of decision-theoretic troubleshooting
Marta VomlelováInternational Journal of Intelligent Systems 18 (2) 267 (2003)
https://doi.org/10.1002/int.10087
Integer Programming and Combinatorial Optimization
René SittersLecture Notes in Computer Science, Integer Programming and Combinatorial Optimization 2337 230 (2002)
https://doi.org/10.1007/3-540-47867-1_17
A note on the traveling repairman problem
Alfredo García, Pedro Jodrá and Javier TejelNetworks 40 (1) 27 (2002)
https://doi.org/10.1002/net.10031
Computing and Combinatorics
Yaw-Ling LinLecture Notes in Computer Science, Computing and Combinatorics 2387 525 (2002)
https://doi.org/10.1007/3-540-45655-4_56
Mathematical Foundations of Computer Science 2001
Sven O. Krumke, Willem E. de Paepe, Diana Poensgen and Leen StougieLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2001 2136 487 (2001)
https://doi.org/10.1007/3-540-44683-4_43
Integer Programming and Combinatorial Optimization
Clifford Stein and David P. Wagner*Lecture Notes in Computer Science, Integer Programming and Combinatorial Optimization 2081 406 (2001)
https://doi.org/10.1007/3-540-45535-3_32
Algorithms and Complexity
Giorgio Ausiello, Stefano Leonardi and Alberto Marchetti-SpaccamelaLecture Notes in Computer Science, Algorithms and Complexity 1767 1 (2000)
https://doi.org/10.1007/3-540-46521-9_1
Polynomial time algorithms for some minimum latency problems
Bang Ye WuInformation Processing Letters 75 (5) 225 (2000)
https://doi.org/10.1016/S0020-0190(00)00102-2
An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
Xin He and Zhi-Zhong ChenSIAM Journal on Computing 29 (1) 65 (1999)
https://doi.org/10.1137/S0097539797322255
688 (1999)
https://doi.org/10.1145/301250.301432
Operations Research in Transportation Systems
Alexander S. BelenkyApplied Optimization, Operations Research in Transportation Systems 20 91 (1998)
https://doi.org/10.1007/978-1-4757-6075-0_3
171 (1998)
https://doi.org/10.1109/HIPC.1998.737986
An improved approximation ratio for the minimum latency problem
Michel Goemans and Jon KleinbergMathematical Programming 82 (1-2) 111 (1998)
https://doi.org/10.1007/BF01585867