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

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

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

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2024）07-00-06

0 引 言

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

1 問(wèn)題描述

1.1 問(wèn)題特點(diǎn)

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

（1）各保障組獨(dú)立行動(dòng)，互不干擾。

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

（3）各保障組承擔(dān)工作量相近的任務(wù)。這里所說(shuō)的工作量不僅要考慮各保障組之間的路徑長(zhǎng)度差距，更要考慮各保障組所承擔(dān)的工作量差距。因?yàn)楸Ｕ辖M到達(dá)需求點(diǎn)后還要進(jìn)行保障行動(dòng)，所需時(shí)間甚至可能超過(guò)路上機(jī)動(dòng)時(shí)間。所以，比起各保障組路上機(jī)動(dòng)的路徑均衡，各保障組實(shí)施保障的對(duì)象（需求點(diǎn)）數(shù)量均衡更為重要。

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

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

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

1.2 問(wèn)題建模

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

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

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

以Z表示m個(gè)保障組保障路徑總長(zhǎng)度，則目標(biāo)函數(shù)為：

約束條件為：

2 遺傳算法設(shè)計(jì)

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

2.1 染色體編碼

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

2.2 初始化種群

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

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

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

2.3.1 不控制各保障路徑長(zhǎng)度距離

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

2.3.2 通過(guò)為Zp賦值無(wú)窮大控制保障路徑長(zhǎng)度差距

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

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

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

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

從程序運(yùn)行結(jié)果來(lái)看，第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。

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

2.4 選擇

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

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

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

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

按照輪盤(pán)賭選擇方式的相同參數(shù)進(jìn)行錦標(biāo)賽選擇法實(shí)驗(yàn)，程序運(yùn)行結(jié)果如圖7所示。

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

2.5 變異

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

2.5.1 翻轉(zhuǎn)

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

2.5.2 交換

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

2.5.3 遷移

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

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

程序流程如圖11所示。

3.1 讀取信息

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

3.2 生成分隔點(diǎn)

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

3.3 初始化種群

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

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

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

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

首先將個(gè)體按照分隔點(diǎn)序號(hào)隔開(kāi)，形成m個(gè)片段（m個(gè)保障路徑），每個(gè)片段末尾添加該片段的第一個(gè)序號(hào)，形成閉合回路，也就是環(huán)形路徑。接下來(lái)計(jì)算每個(gè)保障路徑長(zhǎng)度及各保障組之間的路徑差值，分別匯總計(jì)算Zp、Sp，進(jìn)而計(jì)算出F（xp）。在計(jì)算每個(gè)保障路徑長(zhǎng)度時(shí)，如該路徑經(jīng)過(guò)了2個(gè)及以上保障組點(diǎn)位，則將此保障路徑長(zhǎng)度設(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è)重于控制個(gè)體的總路徑長(zhǎng)度。事實(shí)上，保障任務(wù)規(guī)劃的最終目的是更快地完成保障任務(wù)，而不是刻意強(qiáng)調(diào)各保障組之間的路徑平衡。因此，根據(jù)多次實(shí)驗(yàn)論證，k值取0.8較為適宜。

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

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

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

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

3.5 結(jié)果顯示

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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