How Do Dynamic Events Change the Fitness Landscape of Traveling Salesman Problems?

Traveling Salesman Problem (TSP) is a combinatorial optimization problem, serving as basis for many real-world applications (e.g., transportation planning, circuit board design, and DNA sequencing). In TSP, it is common to encounter some dynamic events, for example, traffic jam and roadworks in transportation planning. To deal with such Dynamic TSP (DTSP) scenarios, numerous techniques have been designed over decades. In this paper, we take a different perspective to study DTSP. Instead of focusing only on algorithm design for DTSP, we investigate how dynamic events in DTSP affect its fitness landscape (e.g., the location of local optimal solutions and the ruggedness level of search space). We consider three dynamic events, including node addition, node deletion and weight changes, and analyze how they affect the TSP with respect to the overall landscape structure and solution optimality. Experimental results show that the weight change event has great effect on the problem’s fitness landscape, introducing more local optima and reducing the basin of attraction for the global optimum. This may suggest that search algorithms need to have stronger exploration capability when handling weight change dynamic events. Furthermore, our experimental studies also demonstrate that the dynamic solution adaptation strategy on the original global optimum is effective for tracking the new optimum after dynamic changes.