Two-Stage Routing of Transport Using Geospatial Clustering

One of the urgent and key problems of the transport industry is considered. This is the problem of planning the routes of vehicles. The given problem can be described and formalized as the Traveling Salesman Problem (TSP) for many applications.This problem consists in finding of the optimal route for a traveling salesman passing through the indicated cities at least once and with returning to the source city. In general, when planning such routes, it is necessary to solve the multiple traveling salesman problem (MTSP), which allows for more than one traveling salesman and more than one depot, their base point, where routes begin and end. As a combinatorial optimization problem, MTSP belongs to the class of NP-hard problems. This article presents a heuristic method for its solving on the basis of geospatial clusterization of the initial set of cities. First, an MTSP with a single depot is considered. A two-index mathematical formalization of this problem is given and the Miller-Tucker-Zemlin method is described. It reduced to the problem of integer linear programming. Metaheuristic methods for solving MTSP are discussed. A more complex problem an MTSP with several depots is being considered. A comprehensive two-stage method for solving this problem is described — the CFRS ("Cluster First — Route Second") method, which allows reducing it to the MTSP family with a single depot. Here, at the first stage, geospatial clustering of cities is carried out, for which it is possible to use various clustering methods, including the K-means method. At the second stage, for each built cluster, a depot is selected for its maintenance and routes are built to bypass all cities in this cluster. The clustering methodology is discussed as an effective tool for solving MTSP.A numerical example of aviation logistics is given — the routing of flights of UAV group.