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

金明

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

引言

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

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

1 數(shù)學(xué)建模

于是任務(wù)均衡mTSp優(yōu)化目標(biāo)函數(shù)可以描述為：

其中：

表示第k個(gè)旅行商機(jī)動(dòng)總距離，約束條件為[3]：

如果需要實(shí)現(xiàn)路線最短，只需把優(yōu)化目標(biāo)函數(shù)從式（3）改為：

如果同時(shí)考慮兩個(gè)因素的影響可以把優(yōu)化目標(biāo)函數(shù)修改為：

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

2 可控K-means聚類算法

2.1 初始劃分

假設(shè)要求的聚類中各個(gè)簇的元素?cái)?shù)量為ni，并滿足：

2.2 沖突消解

3 任務(wù)均衡算法

3.1 算法初始化

3.2 快速迭代

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

3.3 精細(xì)化搜索

然后，使用可控K-means聚類，獲得指定元素?cái)?shù)量的劃分。之后，使用TSP算法獲取m個(gè)最小距離，并計(jì)算值。

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

4 算法推廣及應(yīng)用

4.1 起點(diǎn)各異mTSP

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

4.2 多人巡檢問題

我們還可以把多旅行商問題進(jìn)行進(jìn)一步推廣成多人巡檢問題，m個(gè)巡檢人員需訪問n個(gè)站點(diǎn)，每個(gè)站點(diǎn)除了站點(diǎn)間機(jī)動(dòng)需要時(shí)間，站點(diǎn)巡檢也需要時(shí)間，此時(shí)優(yōu)化目標(biāo)從距離均衡變?yōu)闀r(shí)間均衡。假設(shè)每一個(gè)旅行商的機(jī)動(dòng)速度一致，都為，且每一個(gè)點(diǎn)位都需要一定的巡檢時(shí)間，第i個(gè)點(diǎn)位的巡檢時(shí)間設(shè)為，此時(shí)需要把任務(wù)分配給m個(gè)巡檢人員，需要使各個(gè)巡檢人員任務(wù)完成時(shí)間相對均衡。此時(shí)只需把算法中的的替換為即可，定義如下。

5 結(jié)束語

多旅行商問題總路程最小、任務(wù)分配均衡的兩個(gè)優(yōu)化目標(biāo)彼此相關(guān)，但又不完全一致，本文通過K-means聚類，把距離相近的城市劃為一類，可有效減少機(jī)動(dòng)距離。同時(shí)針對常規(guī)聚類算法簇內(nèi)元素?cái)?shù)量不可控的問題，提出了可控K-means聚類算法。該算法基于簇中心距離最近原則進(jìn)行聚類，通過消解沖突方法，獲得指定元素?cái)?shù)量的簇劃分。該算法可用于任務(wù)均衡mTSP及其推廣問題的求解。