Trade-off between Complexity and Performance in TSPTW: Evaluation of Algorithms for Distance Minimization and Makespan

The Traveling Salesman with Time Windows Problem is critical in logistics, where time constraints are critical. This paper comparatively analyzes three approaches: greedy algorithm, VND refinement, and GVNS meta-heuristics, applied to asymmetric benchmark instances for total distance minimization and makespan, with a limit of 1000 iterations or 300 seconds of execution. The results indicate that the effectiveness of the methods is significantly influenced by the objective function. The greedy algorithm stood out in the minimization of makespan (reaching 71.4% of the best known solutions), while GVNS stood out in total distance (69.4%). It is concluded that GVNS is competitive against algorithms consolidated in the literature, such as Beam-ACO, validating the use of variable neighborhoods in the optimization of logistics costs.