Solving Prize-Collecting Traveling Salesman Problem with Time Windows by Chaotic Neural Network

摘要

This paper presents an artificial neural network algorithm for prize-collecting traveling salesman problem with time windows, which is often encountered when scheduling color-coating coils in cold rolling production or slabs in hot rolling mill. The objective is to find a subset sequence from all cities such that the sum of traveling cost and penalty cost of city unvisited is minimized. To deal with this problem, we construct mathematical model and the corresponding network formulation. Chaotic neurodynamic is introduced and designed to obtain the solution of the problem, and the workload reduction strategy is proposed to speed up the solving procedure. To verify the efficiency of the proposed method, we compare it with ordinary Hopfield neural network by performing experiment on the problem instances randomly generated. The results clearly indicate that the proposed method is effective and efficient for given size of problems with respect to solution quality and computation time.