Splitting a Giant Tour using Integer Linear Programming

In this paper, we propose a polynomial way for optimally partitioning a giant tour using integer linear programming. The obtained model is extended to the mTSP with limited visits per tour. A hybridization of the variable neighborhood search (VNS) heuristic with these mathematical models is also presented. Computational experiments are conducted using a conventional solver to illustrate the performance of some of these split-based models as well as their hybridization with VNS.