Title :
On polynomial-approximated solutions to the film copy deliverer problem
Author :
Zhang, Lei ; Zheng, Weimin
Author_Institution :
Sch. of Econ. & Manage., Tsinghua Univ., Beijing, China
Abstract :
First, a heuristic is developed to solve a feasible solution to an instance of the extended traveling salesman problem (the ETSP), proposed by Zhang and Zheng (1994), which is in fact a relaxation of the film copy deliverer problem (the FDP) defined by Cheng, Zhang, and Mitsuo (1993). Secondly the approximated condition of the ETSP is given, and it is that any edge of the underlying graph of the ETSP is satisfied with the triangle inequality which means that one of the three edges in a weighted graph is equal to or less than the sum of the left edges. Then the worst-case performance of that heuristic is analyzed. Finally some numerical examples are given
Keywords :
approximation theory; computational complexity; graph theory; polynomials; travelling salesman problems; extended traveling salesman problem; film copy deliverer problem; polynomial-approximated solutions; triangle inequality; underlying graph; worst-case performance; Algorithm design and analysis; Constraint optimization; Dynamic programming; Heuristic algorithms; Matrix decomposition; Motion pictures; Performance analysis; Polynomials; Routing; Traveling salesman problems;
Conference_Titel :
Systems, Man, and Cybernetics, 1996., IEEE International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7803-3280-6
DOI :
10.1109/ICSMC.1996.565340
