{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:19:00Z","timestamp":1773796740493,"version":"3.50.1"},"reference-count":15,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5276,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,5]]},"abstract":"Abstract<\/jats:title>Consider a complete directed graph in which each arc has a given length. There is a set of jobs, each job i<\/jats:italic> located at some node of the graph, with an associated processing time h<\/jats:italic>i<\/jats:italic><\/jats:sub>, and whose execution has to start within a presepecified time window [r<\/jats:italic>i<\/jats:italic><\/jats:sub>, d<\/jats:italic>i<\/jats:italic><\/jats:sub>]. We have a single server that can move on the arcs of the graph, at unit speed, and that has to execute all of the jobs within their respective time windows. We consider the following two problems: (a) minimize the time by which all jobs are executed (traveling salesman problem) and (b) minimize the sum of the waiting times of the jobs (traveling repairman problem). We focus on the following two special cases: (a) The jobs are located on a line and (b) the number of nodes of the graph is bounded by some integer constant B<\/jats:italic>. Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times r<\/jats:italic>i<\/jats:italic><\/jats:sub> are 0, and (c) all of the deadlines d<\/jats:italic>i<\/jats:italic><\/jats:sub> are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP\u2010completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time t<\/jats:italic>, the number of jobs that can be executed at that time is bounded.<\/jats:p>","DOI":"10.1002\/net.3230220305","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:22:12Z","timestamp":1178972532000},"page":"263-282","source":"Crossref","is-referenced-by-count":185,"title":["Special cases of traveling salesman and repairman problems with time windows"],"prefix":"10.1002","volume":"22","author":[{"given":"John N.","family":"Tsitsiklis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"issue":"1","key":"e_1_2_1_2_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1051\/ita\/1986200100791","article-title":"The complexity of the traveling repairman problem","volume":"20","author":"Afrati F.","year":"1986","journal-title":"Theor. Info. Appl."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207031"},{"key":"e_1_2_1_4_2","first-page":"65","volume-title":"Vehicle Routing: Methods and Studies","author":"Desrochers M.","year":"1988"},{"issue":"4","key":"e_1_2_1_5_2","first-page":"357","article-title":"Plus court chemin avec contraintes d'horaires","volume":"17","author":"Desrosiers J.","year":"1983","journal-title":"R.A.I.R.O. Recherche Operationelle"},{"issue":"3","key":"e_1_2_1_6_2","first-page":"301","article-title":"A dynamic programming solution of the large\u2010scale single\u2010vehicle dial\u2010a\u2010ride problem with time windows","volume":"6","author":"Desrosiers J.","year":"1986","journal-title":"Am. J. Math. Management Sci."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206029"},{"key":"e_1_2_1_8_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"issue":"1","key":"e_1_2_1_9_2","first-page":"196","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held M.","year":"1962","journal-title":"J. SIAM"},{"key":"e_1_2_1_10_2","volume-title":"The Traveling Salesman Problem","author":"Lawler E. L.","year":"1985"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70743-X"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.5.798"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.36.2.212"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02022044"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030106"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.22.1.1"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220305","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T08:50:03Z","timestamp":1698051003000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["10.1002\/net.3230220305"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220305","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}