This paper presents a heuristic algorithm to solve the Traveling Salesman Problem with Time-Dependent Costs, an interesting generalization of the Traveling Salesman Problem with Time Windows in which the cost and the travel time of each arc are time-dependent so that the problem fits more accurately real routing problems involving visits or pick-up or delivery of goods inside a big city, for example taking into account traffic jams during peak hours. This heuristic is a classical two-phase procedure: in the first phase it looks for a feasible solution and in the second one it tries to improve that feasible solution.

In order to check its efficiency, this heuristic has been tested on a set of 118 instances with up to 29 customers for which we know the solution given by an exact procedure on a discretized version of the instances. The average deviation of our results with respect to the solutions of the exact algorithm was 1.74% and in 51.69% of the instances both values were the same. Moreover, the heuristic gave a feasible solution in few seconds for 22 instances where the exact procedure did not find any.

traveling salesman, time windows, time-dependence, heuristic.