基于多旅行商問題模型解決工作量均衡的任務(wù)規(guī)劃問題應(yīng)用研究

摘 要：針對常見的工作量均衡的任務(wù)規(guī)劃問題，基于MTSP（多旅行商問題）模型，利用遺傳算法，通過設(shè)置平均分隔點確保各保障組工作量均衡，構(gòu)建3種適應(yīng)度函數(shù)論證總路徑長度和各保障組路徑差的控制方法，比較2種選擇方法確定遺傳迭代過程，采取3種變異方式豐富種群多樣性；最后利用Python語言編寫程序，有效解決基于TSP（旅行商問題）、不同起點的MTSP、相同起點的MTSP模型的3類任務(wù)規(guī)劃問題，具有較強的實踐性和可操作性。

關(guān)鍵詞：TSP；MTSP；遺傳算法；任務(wù)規(guī)劃；工作量均衡；Python

中圖分類號：TP18 文獻標識碼：A 文章編號：2095-1302（2024）07-00-06

0 引 言

多旅行商問題（Multiple Traveling Salesman Problem， MTSP）由傳統(tǒng)旅行商問題（Traveling Salesman Problem， TSP）延伸而來，即有m個旅行商分別拜訪n個城市，每個城市只能拜訪一次，最后回到出發(fā)城市，求所有旅行商的最短總路徑之和[1]。MTSP是一個典型的組合優(yōu)化難題，屬于NP問題[2]，在日常生活中有著廣泛的應(yīng)用，如物流配送、電路板線路設(shè)計以及無人機路徑規(guī)劃等。文獻[3]提出一種多染色體遺傳算法解決多旅行商問題，文獻[4]提出基于遺傳算法的多旅行商問題的優(yōu)化，文獻[5]提出求解多旅行商問題的改進分組遺傳算法等。保障領(lǐng)域的任務(wù)規(guī)劃問題，可參照MTSP建立模型，即有m個保障組，要為n個需求點提供保障服務(wù)（如物資前送、人員搶救、裝備搶修等），需要合理規(guī)劃保障路徑，使得總保障路徑最短，且各保障組工作量相對均衡，以提高保障時效。文獻[6]提出求解工作量平衡多旅行商問題的改進遺傳算法，文獻[7]提出工作量平衡的多旅行商問題及其求解方法，均提供了很好的參考。本文在此基礎(chǔ)上，利用遺傳算法研究解決MTSP，進而解決保障任務(wù)規(guī)劃問題，并利用Python語言設(shè)計程序，為保障任務(wù)規(guī)劃提供直觀顯示功能。

1 問題描述

1.1 問題特點

工作量均衡的保障任務(wù)規(guī)劃問題存在以下特點：

（1）各保障組獨立行動，互不干擾。

（2）各需求點只經(jīng)過1次即可，防止重復(fù)保障。

（3）各保障組承擔工作量相近的任務(wù)。這里所說的工作量不僅要考慮各保障組之間的路徑長度差距，更要考慮各保障組所承擔的工作量差距。因為保障組到達需求點后還要進行保障行動，所需時間甚至可能超過路上機動時間。所以，比起各保障組路上機動的路徑均衡，各保障組實施保障的對象（需求點）數(shù)量均衡更為重要。

（4）各保障組所處的位置不確定，有可能從同一個地點出發(fā)，也有可能從不同地點出發(fā)。

（5）各保障組最終要回到原位置進行調(diào)整，即保障路徑是環(huán)狀。

根據(jù)以上特點，工作量均衡的保障任務(wù)規(guī)劃問題的制約因素較多，需要綜合考慮，確定合理的算法。

1.2 問題建模

根據(jù)上述問題特點，構(gòu)建以下模型。

定義變量：m表示保障組數(shù)量；n表示需求點數(shù)量；lij表示需求點i與需求點j之間的距離；nk、nk'表示第k個和第k'個

保障組經(jīng)過的需求點數(shù)量；dk表示第k個保障組執(zhí)行保障任務(wù)的路徑總長度；xl代表第l個需求點被經(jīng)過的次數(shù)。則有：

以Z表示m個保障組保障路徑總長度，則目標函數(shù)為：

約束條件為：

2 遺傳算法設(shè)計

遺傳算法（Genetic Algorithm， GA）是Holland教授于20世紀60年代提出的[8]，它主要借用了生物進化中“物競天擇，適者生存”的自然機理，通過選擇、遺傳和變異等機制，模擬自然進化過程來求解復(fù)雜問題。從某種程度上說遺傳算法是對生物進化過程進行的數(shù)學(xué)仿真。與自然界類似，遺傳算法從代表問題可能潛在解集的一個種群（population）開始，將擇優(yōu)與隨機信息結(jié)合起來并逐步迭代，在每一代中通過一定的規(guī)則，使用上代中適應(yīng)性最好的個體（individual）來形成新的種群，如此重復(fù)，直到滿足指定條件為止。

2.1 染色體編碼

染色體編碼采用十進制一段式編碼方式，數(shù)字代表需求點序號，每一個個體有n個基因（由n個需求點序號隨機排列組成）。假設(shè)有n個需求點需要m個保障組提供保障，則需設(shè)置m-1個分隔點，將此個體分為m個染色體片段，形成m個保障路徑。為確保各保障組保障的需求點數(shù)量均衡，設(shè)置分隔點時應(yīng)考慮均等劃分染色體，故分隔點應(yīng)設(shè)置在、、…、處（結(jié)果四舍五入）。以圖1所示個體染色體為例，假設(shè)n=17，m=3，根據(jù)染色體劃分原則，需要在第5個、第11個基因處設(shè)置2個分隔點。由圖1可知，第1個保障組按照“13-2-5-11-0”的順序?qū)?個需求點進行保障，第2個保障組按照“16-9-14-15-1-4”的順序?qū)?個需求點進行保障，第3個保障組按照“8-7-10-3-12-6”的順序?qū)?個需求點進行保障，各保障組保障的需求點數(shù)量最大差值為1。

2.2 初始化種群

種群是由P個個體集合而成。每一個個體就是一個包含n個基因的染色體（長度為n的包含0～n的隨機序列），等待m個保障組提供保障。具體來說，每個個體中，m個保障組從出發(fā)地（個體第一個基因或每個分隔點后第一個基因）起始，依次到達下一個需求點，直到最后一個需求點（下一個分隔點前一個基因或個體最后一個基因），而后返回出發(fā)地，路徑軌跡就是m個沒有重復(fù)經(jīng)歷的環(huán)，包含了所有需求點。種群初始化的意義就是隨機生成P個個體，后續(xù)從P個個體中選擇優(yōu)秀個體。

2.3 適應(yīng)度函數(shù)

遺傳算法的核心思想就是“優(yōu)勝劣汰”，所以如何“擇優(yōu)”就成為解決問題的關(guān)鍵?，F(xiàn)在有P個個體，這些個體都是隨機生成的，評價個體效果的好壞需要有一個衡量指標，據(jù)此才能進行選擇。這里引入適應(yīng)度函數(shù)F（x）作為衡量個體好壞的指標，以此作為下一步選擇的依據(jù)。對于MTSP來說，適應(yīng)度函數(shù)與距離密切相關(guān)，個體的好壞取決于該個體總路徑長度Zp?？偮窂皆介L，個體越“壞”；總路徑越短，個體越“好”。在確定適應(yīng)度函數(shù)時，要合理計算并利用Zp值，以此來控制個體中各保障組之間的路徑長度差距。需要注意的是，為了確保各個保障組獨立行動、互不干擾，在個體染色體被分隔后，對每一段染色體進行判斷，如該段染色體包含2個及以上保障組，便將該段染色體形成的保障路徑長度設(shè)為無窮大，則相應(yīng)的Zp也為無窮大，迫使該個體在下一步的選擇中被淘汰。這里采取3種方法構(gòu)建F（x），而后擇優(yōu)選用。

2.3.1 不控制各保障路徑長度距離

個體總路徑長度為個體中各保障組路徑長度的總和，適應(yīng)度函數(shù)為個體總路徑長度，即，F(xiàn)1（xp）=Zp。這種情況僅控制個體總路徑長度，未考慮個體中各保障路徑長度差距。

2.3.2 通過為Zp賦值無窮大控制保障路徑長度差距

如個體中最長保障路徑與最短保障路徑差值大于閾值a（可設(shè)為20%），則相應(yīng)的Zp賦值為無窮大，適應(yīng)度函數(shù)仍為個體總路徑長度，即，F(xiàn)2（xp）=Zp。這種情況以控制個體中各保障路徑長度差距為先決條件，而后控制個體總路徑長度。

2.3.3 通過重新設(shè)定F（x）控制保障路徑長度差距

綜合個體總路徑長度和路徑差值總和兩個優(yōu)化目標[9]，引入兩個新參數(shù)，調(diào)整系數(shù)k和路徑差值總和Sp，。構(gòu)建的F3（xp）為與Zp和Sp線性相關(guān)的函數(shù)，即綜合考慮個體總路徑長度和路徑差值總和的影響，此時F3（xp）=k·Zp+（1-k）·Sp。這種方法可同時控制個體總路徑長度和個體中各保障組路徑長度差距。

利用Python語言編寫程序進行比較，設(shè)置P=80，m=3，n=50，k=0.8，需求點坐標x、y值均為0～4 000范圍內(nèi)的隨機值，區(qū)分3種方法連續(xù)運行100次進行統(tǒng)計，分別得到平均個體總路徑長度Z1、Z2、Z3，平均個體最長保障組路徑與最短保障組路徑差值C1、C2、C3，平均達到最優(yōu)值的迭代次數(shù)I1、I2、I3。程序運行結(jié)果如圖2～圖4所示。

從程序運行結(jié)果來看，第1種方法：Z1=27 921，C1=27.43%，I1=2 743；第2種方法：Z2=29 419，C2=15.75%，I2=2 950；第3種方法：Z3=28 923，C3=14.87%，I3=2 708。

通過分析，第1種方法中，C1得不到有效控制，個別數(shù)值甚至到達92%；第2種方法中，雖然C2被嚴格控制在20%以下，但個體總路徑長度Z2的控制效果不好，迭代次數(shù)I2也偏高；第3種方法中Z3介于其他兩種方法之間，C3、I3均是3種方法中最小的。綜合衡量，選取F3（xp）作為適應(yīng)度函數(shù)。

2.4 選擇

有了適應(yīng)度函數(shù)，就可以評價個體的好壞，便可從種群中將優(yōu)秀的個體選擇出來進行遺傳，得到更好的后代個體，并由此不斷進化，一代代傳承收斂，種群中的某個個體達到了優(yōu)秀的極限，便是最優(yōu)解。當然，遺傳算法的特點決定了通過逐代優(yōu)化求得的最優(yōu)解可以不斷逼近全局最優(yōu)解，但不一定是全局最優(yōu)解。在選擇操作上，比較常用的方法是輪盤賭選擇。輪盤賭選擇法是根據(jù)個體的適應(yīng)度值計算個體被選擇的概率，通過輪盤賭的形式隨機選擇P個個體構(gòu)成子代種群。這種選擇策略使得適應(yīng)度值越好的個體被選擇的概率越大。因此，在求解最大化問題的時候，可以直接采用適應(yīng)度值來進行選擇；但是在求解最小化問題的時候，必須對問題的適應(yīng)度函數(shù)進行變換，將最小化問題轉(zhuǎn)化為最大化問題進行處理（如采用倒數(shù)）。假設(shè)每個個體的適應(yīng)度值為F（xp），取倒數(shù)后進行歸一化處理，便得到該個體被選擇的概率qp，即。顯然，個體越優(yōu)秀，被重復(fù)選擇的概率就越大，如圖5所示。

從種群中按照輪盤賭的方式選出P個個體，差的個體被淘汰，其他個體形成下一代種群，此時便完成了1輪選擇，實現(xiàn)1輪“優(yōu)勝劣汰”。設(shè)置P=80，m=3，n=30，迭代次數(shù)為10 000次。程序運行結(jié)果如圖6所示。

前面在定義適應(yīng)度函數(shù)時，為了實現(xiàn)各保障組獨立行動，人為將不符合要求的個體Zp賦值為無窮大，影響了后面的收斂速度。從實驗結(jié)果可以看出，采取輪盤賭的方法進行選擇，在迭代次數(shù)為10 000次時，路徑規(guī)劃的結(jié)果仍不是最優(yōu)解（路徑規(guī)劃不合理且存在交叉路線），且迭代過程收斂不穩(wěn)定，迭代了9 000余次才達到局部最優(yōu)，時效性比較差。

為了提高迭代效率，在每一輪選擇時，需盡快將優(yōu)秀個體選出，進行單親遺傳[10]，加快迭代過程，故而采取錦標賽選擇法進行“優(yōu)勝劣汰”。在錦標賽選擇中，從種群中采樣e個個體，然后從e個個體中選擇獲勝者（最優(yōu)個體）放入下一代種群中；同時，獲勝者作為父代，通過不同的方式進行變異，得到其他e-1個個體，一起放入下一代種群中。這樣最差的個體永遠得不到傳承，而最優(yōu)個體始終都能保留，避免了最優(yōu)個體被淘汰，加速了收斂。

按照輪盤賭選擇方式的相同參數(shù)進行錦標賽選擇法實驗，程序運行結(jié)果如圖7所示。

從實驗結(jié)果可以看出，采取錦標賽的方法進行選擇，迭代到近2 000次時便得到了最優(yōu)解，且最優(yōu)解比輪盤賭的最優(yōu)解降低了23%，達到了效果優(yōu)、收斂快的目標。因此，在子代種群選擇方式上，采取錦標賽選擇方法。

2.5 變異

在后代的生長過程中，它們的染色體會發(fā)生一些變化，這個過程稱之為“變異”，正是因為變異，種群才會存在多樣性。針對選擇出的優(yōu)秀父代，采取3種方式進行變異操作，生成變異后代。

2.5.1 翻轉(zhuǎn)

隨機生成2個分隔點，對分隔點之間的基因進行翻轉(zhuǎn)操作，生成第1個變異后代。以2.1節(jié)中個體染色體為例，翻轉(zhuǎn)操作如圖8所示。

2.5.2 交換

隨機選中2個基因進行交換，生成第2個變異后代。以2.1節(jié)中個體染色體為例，交換操作如圖9所示。

2.5.3 遷移

將隨機選中的染色體片段向左遷移1位，生成第3個變異后代。以2.1節(jié)中個體染色體為例，遷移操作如圖10所示。在任務(wù)規(guī)劃問題的遺傳算法中，首先從包括P個個體的種群中順序選出4個個體，從4個個體中選出最優(yōu)的個體作為父代，在此基礎(chǔ)上采取上述3種變異操作生成后代，將生成的3個變異后代與原來的1個父代一起放入下一代種群中；然后繼續(xù)從父代種群中順序選擇4個個體，重復(fù)選擇、變異操作，直至產(chǎn)生一個包括P個個體的新種群。如此迭代，直至進化出最優(yōu)個體。

3 程序?qū)崿F(xiàn)

程序流程如圖11所示。

3.1 讀取信息

從Excel表格中讀取保障組、需求點數(shù)量及坐標，便于操作者錄入原始數(shù)據(jù)。如進行1個保障組保障n個需求點任務(wù)規(guī)劃（TSP），錄入保障點信息時僅錄入1個保障組，其余均為需求點；如進行不同點位的m個保障組保障n個需求點任務(wù)規(guī)劃（起點不同的MTSP），錄入保障點信息時錄入m個保障組和n個需求點；如進行相同點位的m個保障組保障n個需求點任務(wù)規(guī)劃（起點相同的MTSP），錄入保障點信息時錄入m個保障組和n個需求點，m個保障組坐標要錄入相同坐標。

3.2 生成分隔點

根據(jù)保障組數(shù)量m、需求點數(shù)量n（n包含m）生成個體分隔點序號，分隔點應(yīng)設(shè)置在、、…、處（結(jié)果四舍五入）。

3.3 初始化種群

生成P個長度為n（包含0～n）的隨機序列作為初始種群，種群數(shù)量P設(shè)為80。

3.4 進入迭代循環(huán)

經(jīng)過反復(fù)實驗論證，因任務(wù)規(guī)劃量不同，循環(huán)次數(shù)不宜取固定值，設(shè)為n的120倍較為合適，既可保證有充分的循環(huán)次數(shù)尋找最優(yōu)解，又可避免陷入無效循環(huán)，提高規(guī)劃效率。

（1）適應(yīng)度計算。適應(yīng)度函數(shù)為：F（xp）=k·Zp+（1-k）·Sp，

首先將個體按照分隔點序號隔開，形成m個片段（m個保障路徑），每個片段末尾添加該片段的第一個序號，形成閉合回路，也就是環(huán)形路徑。接下來計算每個保障路徑長度及各保障組之間的路徑差值，分別匯總計算Zp、Sp，進而計算出F（xp）。在計算每個保障路徑長度時，如該路徑經(jīng)過了2個及以上保障組點位，則將此保障路徑長度設(shè)為10100，相應(yīng)的Zp、Sp、F（xp）也均為超常值，在后續(xù)選擇中被剔除。關(guān)于k值的選擇，可設(shè)為0～1之間的任意小數(shù)，k值越小，F(xiàn)（xp）越側(cè)重于控制各保障組之間的路徑差距；k值越大，F(xiàn)（xp）越側(cè)重于控制個體的總路徑長度。事實上，保障任務(wù)規(guī)劃的最終目的是更快地完成保障任務(wù)，而不是刻意強調(diào)各保障組之間的路徑平衡。因此，根據(jù)多次實驗論證，k值取0.8較為適宜。

（2）選擇。從包含80個個體的種群中按順序選出4個個體，從4個個體中選出最優(yōu)的個體作為父代進行后續(xù)變異操作。每個種群共計進行20次選擇。

（3）變異。分別采取翻轉(zhuǎn)、交換和遷移對優(yōu)秀父代進行操作，產(chǎn)生3個變異后代。

（4）生成新種群。將1個父代個體和3個變異后代收集起來，重復(fù)20次操作，完成原種群的選擇和變異，生成新的包含80個個體的種群。

（5）生成優(yōu)秀個體集。每輪迭代都將種群中最優(yōu)的個體信息單獨收集，形成優(yōu)秀個體集。

3.5 結(jié)果顯示

當120n次迭代完成后，從優(yōu)秀個體集中選擇最優(yōu)個體，利用PLT庫函數(shù)顯示最后的路徑規(guī)劃結(jié)果及迭代次數(shù)、總路徑長度等信息，如圖12～圖14所示。

4 結(jié) 語

本文基于多旅行商問題（MTSP）模型，利用遺傳算法研究解決保障任務(wù)規(guī)劃問題，通過Python語言編寫程序，實現(xiàn)了工作量均衡的任務(wù)規(guī)劃問題的直觀顯示。但是本文研究的模型過于理想化，未能考慮到任務(wù)優(yōu)先級、地形影響系數(shù)等因素，需要在下一步研究中不斷完善，以期更加符合實際需要。

參考文獻

[1]張碩航，郭改枝.多旅行商模型及其應(yīng)用研究綜述[J].計算機科學(xué)與探索，2022，16（7）：1516-1528.

[2]周輝仁，唐萬生，魏穎輝.基于GA的最小旅行時間的多旅行商問題研究[J].計算機應(yīng)用研究，2009，26（7）：2526-2529.

[3]葉多福，劉剛，何兵.一種多染色體遺傳算法解決多旅行商問題

[J].系統(tǒng)仿真學(xué)報，2019，31（1）：36-42.

[4]束東來.基于遺傳算法的多旅行商問題的優(yōu)化[D].安慶：安慶師范大學(xué)，2018.

[5]王勇臻，陳燕，于瑩瑩.求解多旅行商問題的改進分組遺傳算法

[J].電子與信息學(xué)報，2017，39（1）：198-205.

[6]胡士娟，魯海燕，黃洋，等.求解工作量平衡多旅行商問題的改進遺傳算法[J].計算機工程與應(yīng)用，2019，55（17）：150-155.

[7]劉偉民，李蘇劍，鄭愛云，等.考慮工作量平衡的多旅行商問題及其求解[J].計算機工程與應(yīng)用，2010，46（15）：47-50.

[8]王海龍，周輝仁，魏穎輝.基于遺傳算法的一類多旅行商問題研究[J].計算機應(yīng)用，2009，29（1）：119-122.

[9]孫冰，王川，楊強，等.面向多起點均衡多旅行商問題的進化算法[J].計算機工程與設(shè)計，2023，44（7）：2030-2038.

[10]朱紅瑞，譚代倫.改進快速單親遺傳算法解均衡多旅行商問題

[J].六盤水師范學(xué)院學(xué)報，2022，34（3）：96-105.