A HEURISTIC FOR THE MULTIPLE TOUR MAXIMUM COLLECTION PROBLEM

The multiple tour maximum collection problem (MTMCP) consists of deter mining the m optimal time constrained tours which visit a subset of we ighted nodes in a graph such that the total weight collected from the subset of nodes is maximized. In this paper, a heuristic for the MTMCP is developed. The results of computational testing reveal that the he uristic has three very attractive features. First, the heuristic will always produce a feasible solution if one exists. Second, the heuristi c produces very good solutions. In most cases where the exact solution is known, it produces the optimal solution. And finally, the heuristi c has the ability to handle large problems in a very short amount of c omputation time.