Initialization methods for the TSP with Time Windows using Variable Neighborhood Search

Abstract

This paper presents a General Variable Search heuristic, trying to discover initial, feasible solution for the Travelling Salesman Problem with Time Windows. More specifically, we provide all relevant information regarding TSP-TW, Variable Neighborhood Search (VNS) and initialization methods, then we quote all related work in the direction on solving this NP-HARD problem, and at last we propose our new implementation for generating initial, feasible solution for the TSP-TW. We are thoroughly focused on the behavior of our main algorithm to different random-based or sorting-based initialization procedures of our main implemented algorithm. At last, we show experimentally that in some cases, the use of a sorting function as an initialization function in this algorithm did not work and never returned a feasible solution in some cases.