Finding the global optimal solution in Dynamic multiple TSPTW with data-driven ACO

Dynamic Travelling Salesman Problem (D-TSP) is a classic dynamic optimization problem (DOP), which aims to maintain the optimal route with every change of the graph. D-TSP often greedily pursues the current optimum after each change efficiently and does not lead to the global optimum. This paper proposes a new model, Data-driven Ant Colony Optimization (D-ACO), to solve the problem by considering the historical data. We assume that some patterns can be observed from the historical data and apply these patterns to route planning. In D-ACO, artificial ants independently make up virtual vertices by sampling the data while exploring the graph. Furthermore, they remove virtual vertices after their exploration. Accumulated pheromone on the original graph carries the latent features of the actual data, which indicates the best route after the change. The experimental results on real datasets show that D-ACO can effectively identify the patterns in the historical data and outperform state-of-art models.