Searching the Hyper-heuristic for the Traveling Salesman Problem with Time Windows by Genetic Programming

Abstract

This paper focuses on the solving constrained traveling salesman problem with time windows indirectly by finding useful hyper-heuristic via genetic programming. Resulting hyper-heuristic represents calculation of city priority along the traveling salesman path. The influences of different city properties (position in the Cartesian coordinate space, sum of distances to then nearest cities, polar angle from the beginning of the coordinate system, etc.), math functions (addition, subtraction, division, sine, cosine, tangent) and penalty functions are tested. Trigonometric functions have no positive influence, best results are achieved with Cartesian coordinates and sum of distances to the nearest cities. Polar angle gives more diverse solutions. Resulting hyperheuristics are good on training sets. When they are tested on another datasets, they find relatively short paths, but there are problems with respecting constraints in the form of time windows.