基于可控K-means算法的任務均衡多旅行商問題求解

金明

中國電子科技集團公司第二十八研究所 江蘇 南京 210007

引言

m個旅行商從中心城市出發，遍歷n個城市，每一個城市被且只被一個旅行商訪問一次，最終返回中心城市，求解總路程最小的劃分及遍歷順序，這是經典的多旅行商問題（mTSP）。當m=1時，該問題退化為單旅行商問題（TSP）。現實中很多問題可以簡化為mTSP問題，比如無人機搜索覆蓋、物資配送、不合格品控制等[1]，因此該問題的求解具有重要意義，但mTSP是一個典型的NP難問題，精確計算方法具有指數級復雜度，只能用于求解小規模問題。mTSP問題一般包含兩個優化目標，總路程最小及任務分配均衡，這兩個目標并不是一致的，一般無法使這兩個目標同時達到最優，通常任務均衡多旅行商問題求解更具現實意義[3-4]。

在求解mTSP問題時可以通過聚類提升算法性能[5]，常用的聚類算法包括K-means算法、高斯混合聚類算法、密度聚類算法、層次聚類算法[6]。通過K-means聚類實現子集劃分[7]，聚類能夠把距離相近的點劃分成一個子集，各個子集之間互不交叉，仿真實驗表明該方法能夠獲取更短的總路徑，但文獻中并未考慮任務均衡實現方法。K-means聚類的結果與數據分布密切相關，因此無法確保聚類結果的均衡性，本文在K-means聚類的基礎上，基于簇中心距離最近原則，實現了可控K-means聚類，可用于任務均衡mTSP問題求解。

1 數學建模

于是任務均衡mTSp優化目標函數可以描述為：

其中：

表示第k個旅行商機動總距離，約束條件為[3]：

如果需要實現路線最短，只需把優化目標函數從式（3）改為：

如果同時考慮兩個因素的影響可以把優化目標函數修改為：

我們把mTSP分解為兩個問題，一是如何把n個城市劃分為m個不相交的子集，二是對每一個子集如何求解TSP，單個TSP可用經典的啟發式算法求解。劃分后的m個子集需滿足式（11）。

2 可控K-means聚類算法

2.1 初始劃分

假設要求的聚類中各個簇的元素數量為ni，并滿足：

2.2 沖突消解

3 任務均衡算法

3.1 算法初始化

3.2 快速迭代

最后，使用TSP算法獲取m個最小距離，計算并比較值，直到不再變大。

3.3 精細化搜索

然后，使用可控K-means聚類，獲得指定元素數量的劃分。之后，使用TSP算法獲取m個最小距離，并計算值。

最后，如果 值比前一次迭代的值大，則繼續迭代，否則返回前一次迭代結果，并結束迭代。

4 算法推廣及應用

4.1 起點各異mTSP

對于m個旅行商起始城市各異問題，可以根據距離最近原則，把m個城市的聚類簇劃分給m個旅行商，假設第i個旅行商的起始點設為，構建距離矩陣，矩陣中的元素表示第i個旅行商從城市出發到城市聚類簇中最短的距離，迭代取矩陣中的元素最小值，從而確定該旅行商和城市聚類簇之間的關系，然后刪除矩陣最小值對應的行和列，如此重復，直到確定所有旅行商和聚類簇之間的對應關系。

4.2 多人巡檢問題

我們還可以把多旅行商問題進行進一步推廣成多人巡檢問題，m個巡檢人員需訪問n個站點，每個站點除了站點間機動需要時間，站點巡檢也需要時間，此時優化目標從距離均衡變為時間均衡。假設每一個旅行商的機動速度一致，都為，且每一個點位都需要一定的巡檢時間，第i個點位的巡檢時間設為，此時需要把任務分配給m個巡檢人員，需要使各個巡檢人員任務完成時間相對均衡。此時只需把算法中的的替換為即可，定義如下。

5 結束語

多旅行商問題總路程最小、任務分配均衡的兩個優化目標彼此相關，但又不完全一致，本文通過K-means聚類，把距離相近的城市劃為一類，可有效減少機動距離。同時針對常規聚類算法簇內元素數量不可控的問題，提出了可控K-means聚類算法。該算法基于簇中心距離最近原則進行聚類，通過消解沖突方法，獲得指定元素數量的簇劃分。該算法可用于任務均衡mTSP及其推廣問題的求解。