A Novel Neighborhood Generation Method for Heuristics and Application to Traveling Salesman Problem

摘要

This paper presents a novel neighbor generation mechanism for heuristic algorithms in which a permutation solution representation is utilized. The mechanism, called cantor-set based (CB) method, is inspired by the recursive algorithm which is used to construct a famous fractal shape, namely a cantor set. CB method was embedded into the classical local search (LS) algorithm to show its advantage of escaping from local optima providing big jumps in the landscape. CB method benefits from the self-similarity aspect of the fractal shapes to generate neighbor solutions. Several variations of the CB method were designed to find the most effective variation on the classical traveling salesman problem (TSP). To make comparisons, swap and insertion mechanisms were also embedded into LS separately for solving the TSP. Finally, the methods were compared using a set of benchmark problems with varying city sizes. The computational tests exhibit that CB method gives better results than swap and insertion mechanisms in terms of effectiveness.