Special cases of traveling salesman and repairman problems with time windows. (English) Zbl 0819.90124

Tsitsiklis, John N.

Networks 22, No. 3, 263-282 (1992).

Summary: Consider a complete directed graph in which each arc has a given length. There is a set of jobs, each job \(i\) located at some node of the graph, with an associated processing time \(h_ i\), and whose execution has to start within a prespecified time window \([r_ i, d_ i]\). 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\). Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times \(r_ i\) are 0, and (c) all of the deadlines \(d_ i\) are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP-completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time \(t\), the number of jobs that can be executed at that time is bounded.

MSC:

90C35	Programming involving graphs or networks
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

time windows; traveling salesman; traveling repairman; complete directed graph; NP-completeness

References:

[1]	Afrati, Theor. Info. Appl. 20 pp 79– (1986)
[2]	Bruno, SIAM J. Comput. 7 (1978)
[3]	, , and , Vehicle routing with time windows: Optimization and approximation. Vehicle Routing: Methods and Studies ( and , Eds.). Elsevier, Amsterdam (1988) 65–84.
[4]	Desrosiers, R.A.I.R.O. Recherche Operationelle 17 pp 357– (1983)
[5]	Desrosiers, Am. J. Math. Management Sci. 6 pp 301– (1986)
[6]	Garey, SIAM J. Comput. 6 pp 416– (1977)
[7]	and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979). · Zbl 0411.68039
[8]	Held, J. SIAM 10 pp 196– (1962)
[9]	, , and , Ed., The Traveling Salesman Problem. Wiley, New York (1985). · Zbl 0563.90075
[10]	Lenstra, Ann. Discrete Math. 1 pp 343– (1977)
[11]	Monma, Operations Res. 37 pp 798– (1989)
[12]	Psaraftis, Management Sci. 36 pp 212– (1990)
[13]	Savelsbergh, Ann. Operations Res. 4 pp 285– (1985)
[14]	Smith, Naval Res. Logistics Q. 3 pp 59– (1956)
[15]	Solomon, Transportation Sci. 22 pp 1– (1988)