Algorithms for solving the Profitable Tour Problem with Time Windows

The Profitable Tour Problem with Time Windows (PTPTW) is known to be NP-Hard and arises in a variety of logistics applications. In this thesis, we aim at exploiting the technique of Reduced Cost Variable Fixing (RCVF) to speed up the processing required by the Mixed Integer Linear Programming solver to optimize this problem. We developed an iterative RCVF procedure to find the needed primal bound, and we also verified the best possible results of our RCVF approach. The dual bounds needed by RCVF were obtained with Dynamic Programming and State Space Relaxation. Through an extensive experimentation we also verified the performances of our algorithms. The performances of the iterative RCVF approach were not always better than the ones of the basic model solution. However, we could observe that, with adequate lower bounds, RCVF can still be very effective.