曾坤，姜志俠，趙紅夢

（長春理工大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，長春 130022）

TSP（Traveling Salesman Problem）旅行商問題，又稱貨郎問題，是數(shù)學(xué)學(xué)科中的一個著名問題。TSP問題的數(shù)學(xué)模型在實際應(yīng)用中有著十分重要的作用，如物流配送、車輛路徑優(yōu)化、激光切割、機器人路徑規(guī)劃等［1-3］。TSP問題的具體描述為：旅行商拜訪指定城市，已知各個城市的位置坐標(biāo)，旅行商拜訪僅且拜訪每個城市一次，最終回到原來出發(fā)的城市，求旅行商經(jīng)過城市的最短路徑。此問題提出后，學(xué)者們相繼對其進行了研究，也取得了不少成就。其求解方法大致分為精確式算法和啟發(fā)式算法。精確式算法如窮舉、動態(tài)規(guī)劃、分支定界算法等，他們能夠求解較小規(guī)模的TSP問題最優(yōu)值，但是對于大規(guī)模TSP問題精確式算法求解所消耗的時間和計算資源往往是不能夠接受的。近年來，隨著啟發(fā)式算法的發(fā)展，如遺傳算法、粒子群算法、蟻群算法等，學(xué)者們將啟發(fā)式算法用于求解TSP問題。啟發(fā)式算法雖然不能像精確式算法那樣求解到全局最優(yōu)解，但是在能夠接受一定偏差的情況下，節(jié)約了大量的計算時間和計算資源。其中遺傳算法能夠跳出局部最優(yōu)，有著較強的隨機搜索全局最優(yōu)解的能力，利用交叉和變異可能產(chǎn)生出較目前更優(yōu)的解，同時還有較好的擴展性，易與其他算法進行結(jié)合，在TSP問題的應(yīng)用中也展現(xiàn)出了優(yōu)良特性。文獻［4］中，針對遺傳算法求解TSP問題過程中收斂速度慢甚至無法收斂的情形，改進了適應(yīng)度函數(shù)，以此增加個體區(qū)分度，對交叉算子采用淘汰機制，加快了算法的收斂能力。對50個城市點進行了求解，使得在較短時間內(nèi)求得了較優(yōu)解，但是該文獻中僅對小規(guī)模TSP問題進行了研究。當(dāng)城市規(guī)模較大時，自然分而治之的思想便產(chǎn)生了。鄭旭峰等人［5］提出了一種k-均值聚類蟻群算法優(yōu)化求解大規(guī)模TSP問題的方法，將大規(guī)模TSP問題聚類分組為小規(guī)模的子問題，然后用蟻群算法分別求解子問題，最后再將每個子問題合并，但是該算法對于小規(guī)模TSP問題求解精度較低，而大規(guī)模TSP問題的求解時間較多。李慶［6］等人分析了傳統(tǒng)遺傳算法的不足，傳統(tǒng)遺傳算法容易出現(xiàn)早熟、收斂速度慢、收斂結(jié)果不準確等問題。并對選擇、交叉、變異三個階段進行了優(yōu)化，在一定程度上避免了“早熟”現(xiàn)象的發(fā)生，加快了收斂速度。針對以上問題，結(jié)合聚類分組小規(guī)模求解速度快、遺傳算法較強的全局最優(yōu)解搜索能力以及分布式計算運算速度快的優(yōu)點，提出了一種改進的分布式并行遺傳算法求解大規(guī)模TSP問題的方法。首先對大規(guī)模TSP問題用k-均值聚類，然后對每個子問題用分布式并行遺傳算法進行求解。在大多數(shù)研究中，對遺傳算法的染色體初始化采用的是隨機初始化方法，其隨機初始化的解質(zhì)量差。因此用改進的貪心策略進行初始化，同時對遺傳算法的交叉、變異和選擇進行了改進，以此提高求解質(zhì)量，最后將求解的每個子問題利用Delaunay三角剖分進行合并，得到整條TSP路徑的解。

1 模型及算法原理

1.1 TSP問題模型

TSP問題是一個經(jīng)典的組合優(yōu)化問題。對于n個城市規(guī)模的TSP問題，其數(shù)學(xué)模型為［7］：

其中，Z表示TSP問題的目標(biāo)函數(shù)值；dij表示城市點i到城市點j的距離；xij為決策變量。如果城市點i到城市點j連通則xij的值為1，否則為0。n表示TSP問題的城市點個數(shù)。約束（1）和約束（2）表示任何一個城市點都只有兩個城市點相連，即旅行商從一個城市點進入該城市點，以及從該城市點出發(fā)達到另一個城市點。V={1,2,…,n}表示由城市點的序號組成的點集，Q表示點集V中任意元素個數(shù)大于2的真子集。|Q|表示點集Q的元素個數(shù)，約束（3）表示所有拜訪過的城市點組成僅且組成一個回路。xij取值為0～1的整型變量，并且i≠j，即每一個城市點不能與自身相連。

1.2 k-均值聚類算法

TSP問題屬于NP難問題，復(fù)雜度隨著城市數(shù)量的增加成指數(shù)增長，其精確式算法求解所帶來的時間成本往往是不能夠讓人接受的。因此采用分而治之的思想，將TSP問題用k-均值算法進行聚類分組，然后求每個子問題的解，最后將子問題進行合并。雖然分組優(yōu)化求解的最終結(jié)果不一定是原問題的最優(yōu)解，但是聚類分組能夠極大地降低求解時間和復(fù)雜度，在求解精度和求解時間之間起到了一個很好的均衡作用。k-均值聚類是一種無監(jiān)督算法，不需要數(shù)據(jù)集有標(biāo)簽。只需要輸入聚類的類別數(shù)k，然后根據(jù)歐式距離將數(shù)據(jù)集中離每個聚類中心較近的點分為k個類。其主要步驟為［8］：

（1）隨機選取k個點，作為聚類中心。

（2）計算數(shù)據(jù)集中每個點分別到聚類中心的距離，然后將該點分配到離聚類中心最近的聚類族中。

（3）更新聚類中心，利用族中所有點的均值作為每一個族新的聚類中心。

（4）重復(fù)上述步驟，直到聚類中心的位置趨于穩(wěn)定。

采用k-均值聚類算法對大規(guī)模TSP問題進行分組，經(jīng)過多次實驗發(fā)現(xiàn)每個子問題的規(guī)模為250個城市點時算法的各個性能較為均衡。對于規(guī)模300以下的數(shù)據(jù)集直接采用遺傳算法進行求解。對于規(guī)模大于300個城市點的數(shù)據(jù)集，進行聚類分組，將聚類分組的每個子問題分別用遺傳算法進行求解，得到子問題的優(yōu)化解，然后再進行合并。

1.3 改進的貪心策略初始化種群

貪心算法是一種逐步逼近最優(yōu)解的算法［9］。雖然貪心算法求到的解可能不是全局最優(yōu)，但是對于一些不能在多項式時間內(nèi)求到最優(yōu)求解的問題，貪心算法在一定程度上能夠靠近最優(yōu)解。本小節(jié)采用貪心策略對遺傳算法的種群進行初始化，貪心策略在執(zhí)行時每一步總是尋找當(dāng)前最優(yōu)，在一定程度上影響了初始種群的質(zhì)量。若僅考慮當(dāng)前最優(yōu)，在拜訪城市過程中，可能會出現(xiàn)四個城市兩條路徑相互交叉的情況，如圖6虛線框B處。由于在三角形中兩邊長度之和大于第三邊長度，其交叉的路徑會增加訪問的最終距離，因此對貪心策略進行改進。

改進的貪心策略初始化種群的具體思想為：隨機選擇一個城市作為初始城市點，然后尋找離該城市最近的城市點作為拜訪的下一個城市，對當(dāng)前兩個城市點連成的線段進行判斷是否與前面的路徑存在交叉，如果存在交叉則重新選擇一個城市作為下一個要拜訪的城市點。如果重復(fù)w次仍然找不到滿足要求的城市點，則接受這個交叉以該城市作為下一個要拜訪的城市點。依次重復(fù)上述步驟，直到全部拜訪完所有的城市點回到初始的城市點。判斷兩條線段是否交叉的步驟如下：設(shè)有四個城市點分別為，四個點組成的兩條線段為 p1p2，p3p4。

（1）判斷p1p2和p3p4組成的直線是否重合或平行，如果否，計算直線p1p2和直線p3p4的交點D(x ,y)。

（2）分別計算兩條線段的端點與交點的凸組合，求解系數(shù) λ1～λ4：

（3）如果0 ≤ λ1～λ4≤ 1，則線段 p1p2與線段p3p4相交。

1.4 分布式并行遺傳算法求解大規(guī)模TSP問題

遺傳算法由 Holland，John在 1975提出［10］，是一種模仿自然界中生物進化原理的啟發(fā)式算法。通過遺傳機制、自然進化和自然選擇搜索全局最優(yōu)解。遺傳算法具有十分強的全局最優(yōu)解搜索能力。同時遺傳算法具有非常好的可擴展性，易于與其他算法進行結(jié)合，以此提高求解的質(zhì)量。遺傳算法的一般步驟為編碼、種群初始化、選擇、交叉、變異。遺傳算法求解TSP問題的一般過程中，存在交叉變異后城市點出現(xiàn)重復(fù)和缺少現(xiàn)象。并且基于概率的交叉、變異和選擇方式存在很大的不確定性。本文對上述問題進行了改進，摒棄了傳統(tǒng)遺傳算法中基于概率的交叉、變異和選擇方式，讓種群依次順序進行交叉、就近策略進行變異，每一次交叉變異后進行局部最優(yōu)選擇子代，再對每一次選擇的局部最優(yōu)個體進行優(yōu)化。

編碼及種群初始化：編碼及種群初始化是遺傳算法中的一個重要環(huán)節(jié)，好的編碼和種群初始化策略能夠有效地提高初始解的質(zhì)量。根據(jù)TSP問題的性質(zhì)，采用符號編碼方法進行編碼，每一個城市對應(yīng)一個序號。如有5個城市，則序列3→2→5→1→4表示一條路徑。使用改進后的貪心策略進行種群初始化。

交叉：將種群中個體的染色體進行重組，得到的子代的基因可能優(yōu)于父代，是遺傳算法中獲取更優(yōu)個體的重要途徑。由路徑組成的染色體隨機選擇父代中的片段進行交叉，得到的子代路徑可能出現(xiàn)城市點重復(fù)或缺少的現(xiàn)象，或者可能會大量修改交叉片段之外的基因信息［11］。對傳統(tǒng)交叉方式進行改進，采用基因片段先刪除后插入策略，對n個個體的種群pop，進行n次循環(huán)，循環(huán)變量為i，父代f1=pop[i]依次從種群中順序選取，父代f2隨機選取異于f1的個體，讓整個種群的父代f1按順序進行交叉。隨機選擇兩個交叉點索引 i1和 i2（i1＜i2），記 f1和 f2中 i1的前一個點分別為p1和p2，取f1和f2交叉點之間的基因片段s1和s2，然后刪除在f1中的基因片段s2的點，在f1中查找點p2的下標(biāo)索引idx2，將基因片段s2插入到f1的idx2位置后面，從而得到子代child1。對p2做同樣的處理，刪除在f2中的基因片段s1的點，在f2中查找p1的下標(biāo)索引idx1，將基因片段s1插入到f2的idx1位置后面，得到子代child2。這樣的交叉方式，插入新基因前已經(jīng)在要插入的父代中刪除了新基因表示的城市點，保證了交叉的個體不會出現(xiàn)城市點缺失和重復(fù)。同時新基因插入點為原來個體中基因片段的前一個點，保證了新插入的基因片段與新個體的有效融合。

變異：經(jīng)過交叉后得到兩個子代child1和child2，將這四條染色體進行變異。常用的方法有隨機變異法，即隨機選擇兩個城市點，然后交換這兩個城市的位置。顯然對于兩個相距較遠的城市進行變異很難獲得更優(yōu)的解。因此本節(jié)對交換城市進行限制采用就近交叉機制，以此提高獲得更優(yōu)解的概率。首先對所有城市點的距離矩陣按列排序。隨機選擇變異點c1，在距離矩陣中檢索離c1最近的m個點，將c1刪除，然后將c1隨機插入m個點中的一個點后。

選擇：傳統(tǒng)遺傳算法中選擇操作是以某一概率（如輪盤賭）的形式從父代種群中選擇父代種群規(guī)模大小的個體組成新的種群，以便進行下一次的迭代。由于以概率的方式進行選擇，帶有很大的不確定性。如不能保證上一代最優(yōu)的個體能夠遺傳到下一代。不能保證種群的多樣性。提出了一種種群中所有個體按順序全部進行交叉、變異的局部最優(yōu)的選擇方法。對f1和f2進行交叉操作后得到child1和child2，將child1和child2兩條染色體進行變異，得到變異后的染色體mut1和mut2。分別計算這兩條染色體的適應(yīng)度值（以該條路徑的距離的倒數(shù)作為適應(yīng)度值）。比較這兩條染色體和父代f1的適應(yīng)度值，若有比f1適應(yīng)度值更大的個體，則將該個體替換父代f1，從而組成新的種群。

分布式并行運算：使用k-均值算法進行聚類分組后的每個子問題之間的計算不需要進行通信，耦合度低。對于分組后的子問題，每個子問題的交叉、變異之間互不影響，因此可以將大規(guī)模問題進行分組在多個節(jié)點上，分別計算子問題，達到分布式并行計算的目的，提高計算效率。利用改進的貪心策略初始化種群，由于每個子問題之間是獨立的，將分組后的子問題分配到不同的計算節(jié)點中同時進行交叉、變異以及適應(yīng)度值計算，每一個子問題經(jīng)過交叉變異后在子代和父代中選擇出最優(yōu)的個體，組成新的種群。然后進入下一輪迭代，重復(fù)上述步驟直到滿足終止條件，最終得到每一個子問題的解。

優(yōu)個體插入：在迭代多次后，適應(yīng)度值較低的個體優(yōu)化空間較大，能夠繼續(xù)進行更新，而種群整體的最優(yōu)適應(yīng)度值更新較慢。根據(jù)遺傳機制特點，在第t次迭代后，刪除種群中適應(yīng)度值較小的r個個體，將適應(yīng)度值最大的個體，隨機插入刪除后的種群中r次，繼續(xù)迭代。這樣增加了最優(yōu)個體與其他個體交叉、變異的幾率，更有機會產(chǎn)生更好的個體優(yōu)于當(dāng)前種群的最優(yōu)個體。

優(yōu)化：在遺傳算法中，經(jīng)過交叉變異選擇后的個體還有一些較多的優(yōu)化空間。如：（1）某一個城市點離其他城市點連接成的線段非常近，可以通過將該城市點插入到其中減小拜訪距離，如圖6虛線框A處；（2）路徑中可能還存在兩個線段交叉，如圖6虛線框B處，可以移除交叉進行優(yōu)化；（3）交換兩個城市點的順序可以將拜訪的總距離減少，如圖6虛線框C處。由于TSP問題是NP難問題較多的城市點導(dǎo)致計算復(fù)雜度較高，因此只對每一次交叉、變異后局部最優(yōu)選擇得到的個體用上述三種方法進行優(yōu)化，具體過程如下。

優(yōu)化1：對存在交叉的路徑進行去交叉操作，具體步驟為：利用1.3中的判斷兩條線段相交的算法找出路徑中相交線段，改變相交線段點的順序，使得路徑不存在交叉，路徑中其他點的順序不變，如圖1。

圖1 移除交叉路徑示意圖

優(yōu)化2：對于一些距離其他路徑非常近的城市點，將這些城市點就近插入到與其最近的路徑中，然后比較插入前和插入后的局部路徑的距離。如圖2，計算優(yōu)化前路徑與優(yōu)化后路徑的距離差值，如果插入后的距離有所減少，則插入成功，否則不插入。

圖2 城市點就近插入示意圖

優(yōu)化 3：采用 2-opt方法［12］對路徑進行優(yōu)化，具體步驟為選取有序的四個城市a→b→c→d，交換b→ c的順序，交換后的路徑為a→c→b→d，然后計算交換前后的路徑的距離，如果距離優(yōu)于交換前則接受這個交換，否則不接受。

1.5 子問題的合并

通過上述的遺傳算法求得了TSP問題子路徑的優(yōu)化解，本小節(jié)主要將每個子路徑連接成一個最短路徑。文獻［13］中，作者給出了一種連接兩個不相交多邊形成一條最短回路的算法。在本問題采用該方法對子問題進行相繼合并。先將所有子問題兩兩計算合并后增加的距離，找出增加距離最小的兩個子問題進行合并，將合并后的路徑與剩下所有子問題分別計算合并后增加的距離，然后將已合并的路徑與增加距離最短的子問題進行合并，依次這樣合并，直到所有子問題被全部合并。其合并算法具體步驟如下：

（1）將兩個子路徑path1和path2的首尾分別相連組成回路，如圖3，分別求出回路的凸殼p1p2p3p4p5p6p7p1和q1q2q3q4q6q7q1。

圖3 未刪除Delaunay邊的剖分圖

（2）求出凸殼的兩條不相交的切線段p2q7和p6q3，path1的切點分別為 p2和 p6，path2的切點分別為q7和q3。分別將子路徑相近一側(cè)的切點之間的點組成序列sqe1為p2p3p4p5p6和sqe2為q3q4q5q6q7，將sqe1和sqe2的首尾相連組成一個不相交的回路，sqe為p2p3p4p5p6q3q4q5q6q7p2。

（3）對sqe進行Delaunay三角剖分［14］，圖3中虛線段則為Delaunay邊，Delaunay三角剖分中的任意一條Delaunay邊均存在一個過該邊端點的圓，其圓內(nèi)不包含點集中其他的點，圓上最多三點共圓，這樣避免了距離較大的頂點對連接成凸四邊形，使得相鄰兩個三角形組成的凸四邊形對邊長度和的差較小。刪除兩個頂點都在同一個路徑點集中的Delaunay邊，例如p3p5、q6q4等，僅保留頂點在不同的路徑點集中的Delaunay邊，如p2q6、p3q6等。圖4是刪除頂點在同一路徑點集中Delaunay邊的三角剖分圖。對三角剖分后形成的凸四邊形進行遍歷，如p2p3q6q7、p4p5q3q4等，然后計算每一個凸四邊形兩組對邊和的差值，如：將差值最小的一組凸四邊形作為兩個子問題合并的接口，如凸四邊形p4p5q3q4刪除p4p5和q3q4邊，連接p4q4和p5q3邊，這樣得到的路徑是最短的，合并后的路徑為p1p2p3p4q4q5q6q7q1q2q3p5p6p7p8p1。

圖4 刪除Delaunay邊的剖分圖

在小本節(jié)通過k-均值聚類算法將大規(guī)模TSP問題進行分組，有效地降低了求解時間復(fù)雜度。利用改進的貪心策略對種群進行初始化，大幅度提升了初始種群的質(zhì)量。利用改進的分布式并行遺傳算法進行求解，同時使用三種優(yōu)化方法對局部最優(yōu)個體進行優(yōu)化，使得求到的解精度大大提高。對于大規(guī)模問題，通過Delaunay三角剖分算法進行子問題的合并，保證了所有子問題合并后距離是最短的。整個算法的流程圖如圖5所示。

圖5 整個算法流程圖

2 實驗

針對提出的算法，選取了不同規(guī)模的TSP問題進行求解驗證算法的性能。實驗環(huán)境為：處理器Intel（R）CPU E5-2620 v4@2.10 GHz 2.10 GHz，內(nèi)存16.00 GB，操作系統(tǒng)為windows10，編程語言環(huán)境為Python3.7。算法中一些參數(shù)值預(yù)先設(shè)定：聚類的類別數(shù)以城市點個數(shù)除以250。在貪心策略初始化中w值取5。插入最優(yōu)個體時的迭代次數(shù)t為50，插入最優(yōu)個體次數(shù)r為5次。遺傳算法的種群設(shè)為40，迭代次數(shù)為1 000，或連續(xù)50次迭代結(jié)果無變化則終止算法。交叉染色體片段的最大長度為染色體長度的一半。

對于小規(guī)模TSP問題不進行k-均值聚類分組，直接使用改進的遺傳進行求解，其求解結(jié)果如表1和表2所示。已知最優(yōu)解是TSPlib公布的最優(yōu)解（http：//elib.zib.de/pub/mp-testdata/tsp/tsplib/stsp-sol.html），改進算法是通過改進的分布式并行遺傳算法進行求解的結(jié)果。誤差率計算公式為：（改進算法-已知最優(yōu)解）/已知最優(yōu)解，對比可以看出提出的算法在求解質(zhì)量和求解時間都較優(yōu)。由誤差率可以看出提出的算法求出的解十分接近已知最優(yōu)解，與已知最優(yōu)解誤差均在1%以內(nèi)。由10次實驗平均值與改進算法求得的解相近，說明提出的算法具有較強的穩(wěn)定性。表3給出了傳統(tǒng)遺傳算法和現(xiàn)有的用于求解TSP問題的蟻群算法結(jié)果，從表中可以看出傳統(tǒng)的遺傳算法的精度較低，且求解時間長，對比表1和表2可以看出，改進的遺傳算法較傳統(tǒng)的遺傳算法和蟻群算法無論是在求解精度和求解時間均相對較優(yōu)。

表1 小規(guī)模TSP問題求解結(jié)果1

表2 小規(guī)模TSP問題求解結(jié)果2

表3 傳統(tǒng)遺傳和蟻群算法求解TSP結(jié)果

以數(shù)據(jù)集st70為例，圖6～圖8給出了求解過程的可視化。圖6是數(shù)據(jù)集st70經(jīng)過改進貪心策略初始化的一個個體。相比于隨機初始化，個體質(zhì)量明顯較優(yōu)。圖7是經(jīng)過提出的算法優(yōu)化求解得到的最優(yōu)路徑圖。圖8是遺傳算法中最優(yōu)個體的路徑距離進化過程。可以看出剛開始迭代進化速度快，這是由于初始化形成的個體存在圖6虛線框A、B、C三種情形，優(yōu)化空間較大，因此前期曲線下降較快。隨著迭代的進行越來越趨近于最優(yōu)解，進化速度較慢，最終達到穩(wěn)定，收斂曲線圖符合理論分析。

圖6 數(shù)據(jù)集st70初始化染色體

圖7 數(shù)據(jù)集st70最優(yōu)路徑圖

圖8 數(shù)據(jù)集st70收斂曲線

對于超過300個城市點的大規(guī)模TSP問題，采用聚類分組對子問題進行求解，然后將子問題進行合并得到問題的解。選取了部分大規(guī)模TSP城市進行求解，其求解結(jié)果如表4和表5所示。

表4 大規(guī)模TSP問題求解結(jié)果1

表5 大規(guī)模TSP問題求解結(jié)果2

從表4和表5中可以看出，對于大規(guī)模TSP問題，改進算法求得的解與已知最優(yōu)解相近，其誤差均在10%以內(nèi)。其多次求解的平均值與最優(yōu)值相差不大，改進算法求解大規(guī)模TSP問題較為穩(wěn)定，求解質(zhì)量好，求解時間較少。在表1和表2最后一欄列出了文獻［15］中求解大規(guī)模TSP問題的誤差率，改進算法結(jié)果中除數(shù)據(jù)集pcb3038比文獻［15］稍差以外，其余結(jié)果均比文獻［15］較優(yōu)，特別是對于小規(guī)模TSP問題，提出的算法相比于文獻［15］的結(jié)果精度高很多。在表1和表2中，數(shù)據(jù)集pr439沒有進行聚類分組求解，直接使用遺傳算法求解。在表4和表5中數(shù)據(jù)集pr439采用聚類分組求解，通過對比可以看出聚類分組求解對于大規(guī)模問題在求解時間和求解精度上都明顯較優(yōu)。

隨著TSP城市點數(shù)量的增多，大規(guī)模TSP問題的求解的誤差和求解時間都有所增加。圖9給出rl1323優(yōu)化后最優(yōu)路徑圖。在大規(guī)模求解中，由于求解的各個子問題相對獨立，因此在大規(guī)模求解TSP問題時對子問題采用分布式并行運算，每一個子問題分配一個計算節(jié)點進行并行求解，以此提高求解速度。因此在表4和表5中的求解時間受多因素影響，如計算機性能、計算節(jié)點數(shù)、代碼優(yōu)化等。

圖9 數(shù)據(jù)集rl1323最優(yōu)路徑圖

3 結(jié)論

針對求解大規(guī)模TSP問題，采用k-均值算法對大規(guī)模TSP問題進行聚類分組，用分布式并行遺傳算法對分組后的子問題進行求解。首先用改進的貪心策略進行種群初始化，摒棄了傳統(tǒng)遺傳算法基于概率的交叉、變異、選擇方式，提出了按順序交叉、變異和局部最優(yōu)選擇的分布式并行遺傳算法，同時給出了三種優(yōu)化方法對局部最優(yōu)的個體進行優(yōu)化，有效地提升了遺傳算法的求解質(zhì)量。對于優(yōu)化求解后的子問題，采用Delaunay三角剖分算法對子問題進行合并，使得合并后的路徑最短。最后通過實驗仿真以及其他文獻結(jié)果對比，顯示了提出的算法性能良好。如今快遞、物流行業(yè)等的快速發(fā)展，車輛路徑優(yōu)化需求大，在此基礎(chǔ)上可以考慮更多的約束和具體實際背景，求解車輛路徑優(yōu)化相關(guān)問題，也是接下來研究的方向之一。