Remodeling the film copy deliverer problem
Lei Zhang, Weimin Zheng · 2002
We remodel the film copy deliverer problem (FDP) as: 1 film copy is to be shown. Starting from a base cinema, vertex 1, the deliverer must bring it to the i-th cinema, vertex i, c/sub i/ times, c/sub i/ being usually a distinct, predetermined integer and i/spl isin/{1,2,...,r}, and then return vertex 1 so that the total distance of the tour is minimized and vertex i is visited exactly c/sub 1/ times, but not continuously. Besides the TSP, the FDP extends the k-traveling salesman problem, a variant of the TSP, into its special case for all c/sub 1/=1 but c/sub 1/=k. Since the TSP is NP-complete class, the FDP is NP-hard. Bellmore et al. (1968) developed an heuristic for the FDP. Its basic idea is that the input FDP is decomposed into several TSPs of maybe different size and their best tours are found, then the best tour is constructed on basis of these TSP tours. Many computing techniques are used, so it not only might be too complex to code a routine solving an FDP, but also seems not easy to find the optimal tour for the FDP even of small scale size. On the other hand, for the original FDP, even though each c/sub i/ is one, we do not always keep the FDP to its "trivial" case. That is why we herein must redefine the FDP by replacing "at least" with "exactly". It is convenient to search those with best worst-case guarantee performance of the heuristics for the FDP. We build a general search architecture. It is reduced into a TSP such that all techniques known are possibly applied to it. We are mainly interested in discussing 1-approximate heuristics for the FDP.>