A cooperative approach between metaheuristic and branch-and-price for the team orienteering problem with time windows

The team orienteering problem with time windows (TOPTW) is a well studied routing problem. In this paper, a cooperative algorithm is proposed. It collaborates metaheuristic and branch-and-price. A restricted master problem and subproblem are defined. It uses a heuristic to obtain an integral solution for the restricted master problem and a metaheuristic to generate new columns for the subproblem. Experimental study shows that this algorithm can find new better solutions for several instances in short time, which supports the effectiveness of the cooperative mechanism between metaheuristic and branch-and-price.