A heuristic for the multiple tour maximum collection problem

The multiple tour maximum collection problem (MTMCP) consists of determining the m optimal time constrained tours which visit a subset of weighted 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 heuristic has three very attractive features. First, the heuristic will always produce a feasible solution if one exists. Second, the heuristic produces very good solutions. In most cases where the exact solution is known, it produces the optimal solution. And finally, the heuristic has the ability to handle large problems in a very short amount of computation time.