Кластерный метод решения множественной задачи коммивояжера с несколькими депо

Филимонов А.Б., Нгуен Т.К.

Ключевые слова: множественная задача коммивояжера, наличие нескольких депо, условия устранения подмаршрутов Миллера-Такера-Землина, целочисленное линейное программирование, геопространственная кластеризация.

Аннотация. Рассматривается множественная задача коммивояжера (МЗК). Дается математическая формализация задачи коммивояжера с одним депо. Данная задача формализуется как задача целочисленного линейного программирования. Приводятся условия устранения подмаршрутов Миллера-Такера-Землина. Предлагается метод решения МЗК с несколькими депо. Метод включает два этапа: на первом осуществляется геопространственная кластеризация множества всех городов, которые должны посетить продавцы. Предполагается, что города в каждом кластере объезжаются продавцами из одного депо. На втором этапе для каждого кластера осуществляется выбор депо и решается соответствующая МЗК с этим (т.е. единственным) депо.

Method for solving the multiple traveling salesman problem with several depots

Filimonov A.B., Nguyen Т.К.

Keywords: the multiple traveling salesman problem, a multiple depot, Miller-Tucker-Zemlin subtour elimination constraints, integer programming formulation, spatial clustering, K-means algorithm.

Abstract. We consider the multiple traveling salesman problem (MTSP). A mathematical formalization of the traveling salesman problem with one depot is given. This problem is formalized as an integer linear programming problem. Conditions for eliminating Miller-Tucker-Zemlin subroutes are reduced. A method for solving the MTSP with several depots is proposed. The method includes two stages: the first one involves geospatial clustering of the set of all cities that sellers must visit. It is assumed that the cities of each cluster are served by sellers from one depot. At the second stage, a depot is selected for each cluster and the corresponding MTSP with this (that’s the only one) depot is solved.