The Multiple Traveling Salesman Problem with Backup Coverage

We consider a variant of the classical Multiple Traveling Salesmen Problem in which the distance between any two vehicles is never greater than a fixed distance D. This new feature allows salesmen to help each other timely if an emergency happens, with an estimated backup response time related to D. To achieve this goal, a spatial and temporal synchronization is required, and it incorporates routes interdependence difficulties to be overcomed. A Genetic Algorithm and a Local Search Genetic Algorithm that embodies a Variable Neighborhood Descent procedure are proposed to solve this problem. Computational results are reported on modified benchmark instances taken from TSPLIB in order to exhibit prospects of the proposed algorithms. Through an analysis of results, the highly effective performance of our proposed Local Search Genetic Algorithm is shown in comparison to the classical Genetic Algorithm.