The solution of the vehicle routing problem with an alternate by determining centers location based on clusterization algorithms

Abstract

The article considers the problem of vehicle routing with several centers and with an alternate with two type objects, the peculiarity of which is the lack of initial information about the location of the centers. The problem is to find the centers coordinates and determine the order of visiting objects in order to minimize the total length of the route. The mathematical model of the problem with different types of variables and an algorithm for solving the problem are proposed. Its main idea is to cluster objects to find the centers coordinate and then determine the order in which the clusters are visited. The article discusses two clustering algorithms: k-means and an approach based on the use of ant strategies. Objects of the center type are proposed to be placed at the centers of mass of the resulting clusters. Next, we propose the method for specifying the distances matrix between clusters, which allows us to move on to solving the traveling salesman problem to form the desired route. In conclusion, an analysis of the clustering algorithms was carried out and conclusions were drawn on the feasibility of their use within the framework of the problem. The algorithm proposed in the article is also compared with the exact solution method. The effectiveness of the centers location searching procedure was assessed.