SOLVING THE TRAVELLING SALESMAN PROBLEM WITH TIME WINDOWS BY LAGRANGEAN RELAXATION

This article presents a Lagrangean Relaxation-based methodology to solve the Travelling Salesman Problem with Time Windows. The Lagrangean function exploits the structure of the problem. The proposed method, which elaborates on the Subgradient Optimization, presents a simple heuristics aimed to improve algorithm's convergence on the optimal solution. Furthermore, if the optimal solution is not found in a reasonable number of iterations, this method is able to provide a feasible solution while guaranteeing a tight gap between the primal and the optimal cost.