A matheuristic for the traveling salesman problem with positional consistency constraints

Abstract

We propose a matheuristic for the traveling salesman problem with positional consistency constraints, where we seek to generate a set of routes with minimum total cost, in which the nodes visited in more than one route (consistent nodes) must occupy the same relative position in all routes. The matheuristic is an iterated local search based algorithm that uses a restricted version of the problem under study, where the positions of consistent nodes are fixed, to significantly improve the quality of local optima found by the local search. Computational results show that, for instances with 48–171 nodes and 5 or 10 routes, the matheuristic can obtain, in short computational times, significantly better solutions than an exact method in 10 hours, obtaining optimal or near-optimal solutions for instances where the optimal solution is known.