Uma heurística eficiente para problemas do caixeiro viajante com janelas de tempo

Abstract

This study introduces a heuristic approach for the Traveling Salesman Problem with Time Windows (TSPTW) and the Traveling Salesman Problem with Time Windows and Makespan Minimization (TSPTW-M). The implemented heuristic is based on GRASP, ILS, and RVND techniques. Furthermore, it employs an effective technique for evaluating the constraints of time windows, using specific structures for the concatenation of subsequences, with amortized O(1) complexity. Various experiments were conducted using instance sets from the literature, revealing that this methodology demonstrates performance comparable to existing methods in the literature for TSPTW and TSPTW-M and exhibits notable improvements in some TSPTW instances.