On approximating a geometric prize-collecting traveling salesman problem with time windows. (English) Zbl 1066.90098

Bar-Yehuda, Reuven; Even, Guy; Shahar, Shimon

J. Algorithms 55, No. 1, 76-92 (2005).

Summary: We study a scheduling problem in which jobs have locations. For example, consider a repairman that is supposed to visit customers at their homes. Each customer is given a time window during which the repairman is allowed to arrive. The goal is to find a schedule that visits as many homes as possible. We refer to this problem as the prize-collecting traveling salesman problem with time windows (TW-TSP).
We consider two versions of TW-TSP. In the first version, jobs are located on a line, have release times and deadlines but no processing times. We present a geometric interpretation of TW-TSP on a line that generalizes the longest monotone subsequence problem. We present an \(O(\log n)\) approximation algorithm for this case, where \(n\) denotes the number of jobs. This algorithm can be extended to deal with non-unit job profits.
The second version deals with a general case of asymmetric distances between locations. We define a density parameter that, loosely speaking, bounds the number of zig-zags between locations within a time window. We present a dynamic programming algorithm that finds a tour that visits at least OPT/density locations during their time windows. This algorithm can be extended to deal with non-unit job profits and processing times.

MSC:

90C27	Combinatorial optimization
90B35	Deterministic scheduling theory in operations research
90C39	Dynamic programming

Keywords:

scheduling problem; traveling salesman; locations; dynamic programming algorithm