THE TIME-DEPENDENT TRAVELING SALESMAN PROBLEM

This study addresses the Traveling Salesman Problem with varying travel costs over the planning horizon, aiming to model the effects of traffic congestion at different times of day. Two mixed-integer linear programming models, strengthened by valid inequalities, are presented. These solution approaches are evaluated and compared on a set of instances derived from real traffic data, reflecting the dynamics encountered in large urban centers. Computational experiments were conducted using a heuristic initial solution and were carried out both with and without valid inequalities. The results show that, in a congestion-aware context, both formulations yield similar average solutions in terms of total travel time. However, with respect to the lower bounds, one approach achieved an improvement of almost 11% over the other.