Solution of the Large-Scale Traveling Salesman Problem in the Context of the Complany's Logistics Strategy

Abstract

This paper describes an approach based on reducing the large traveling salesman problem to a set of simpler ones. A solution algorithm is presented with a detailed illustration and a description of the logic behind the steps. The algorithm allows for repeated visits to cities, which is acceptable for practical purposes, since the primary objective is to find a route of minimal overall length, visiting each city at least once. A novel feature is the consideration of intra- and inter-cluster connections by recalculating the matrix of pairwise shortest distances between settlements. The initial network of settlements is then divided into clusters. Within each cluster, an optimal route is found that passes through all its nodes without returning to the starting node. The shortest route linking the clusters is then found. Taking this factor into account more clearly “separates” pairs of settlements in the resulting cluster structure, which facilitates obtaining high-quality solutions.