Film-copy deliverer problem using genetic algorithms

Film-copy Deliverer Problem (short for the FDP) can be regarded as a new extension of traveling salesman problem. It has been proven that FDP is a NP hard problem and several heuristic algorithms have been reported. In this paper, we develop an implementation of genetic algorithms to solve this problem. A deliverer tour can be represented as a walk on a graph, which is a natural coding scheme. A subtour preservation crossover is proposed in order to maintain building blocks in the offspring in much the same manner as Holland described. Mutation is designed with local search techniques intending to generate the improved offspring. The proposed procedure is tested on randomly generated problems and the results show that genetic algorithms can be a promising way for this problem.