\input zb-basic
\input zb-ioport
\iteman{io-port 04131978}
\itemau{Kindervater, G.A.P.; Lenstra, J.K.; Savelsbergh, M.W.P.}
\itemti{Parallel local search for the time-constrained traveling salesman problem.}
\itemso{Twenty-five years of operations research in the Netherlands, Pap. Dedicated to Gijs de Leve, CWI Tracts 70, 61-75 (1989).}
\itemab
[For the entire collection see Zbl 0682.00019.] The problem considered is the so called time-constrained travelling salesman problem where each city has to be visited within a given time interval. Due to the presence of time windows there are feasible and unfeasible tours. This complexifies the standard local search strategy in which a given cycle is improved by changing k edges up to proving its k- optimality. A search strategy is proposed which finds a k-optimal tour in a PRAM model in O(log n) time using O(n/log n) processors.
\itemrv{N.I.Yanev}
\itemcc{}
\itemut{parallel processing; time-constrained travelling salesman; time windows; k-optimality}
\itemli{}
\end