面向帶時(shí)間窗車輛路徑問(wèn)題的PGSA算法優(yōu)化

王 闊,郝福珍

(華北計(jì)算技術(shù)研究所,北京 100080)

0 引 言

隨著現(xiàn)代社會(huì)的發(fā)展，物流場(chǎng)景下的路徑規(guī)劃問(wèn)題的重要性也越來(lái)越凸顯出來(lái)，自從1959年被Dantzig等[1]提出以后，就引起了人們廣泛的關(guān)注[2-3]。該類問(wèn)題的存在對(duì)于人類在實(shí)際場(chǎng)景中應(yīng)用先進(jìn)的計(jì)算機(jī)技術(shù)、合理調(diào)度與規(guī)劃物流車輛的路徑、節(jié)約時(shí)間、降低成本等方面具有十分突出的現(xiàn)實(shí)意義[4]。

車輛運(yùn)輸路徑問(wèn)題(VRP)是應(yīng)急物流研究的基本問(wèn)題，也是在有限時(shí)間內(nèi)實(shí)現(xiàn)物資及時(shí)送達(dá)、提高救援效率、將災(zāi)害降到最小化的有效途徑[5]。VRPTW問(wèn)題是VRP問(wèn)題的帶時(shí)間窗約束的分支問(wèn)題，接近現(xiàn)實(shí)場(chǎng)景中的任務(wù)需求，屬于NP難題，其計(jì)算量會(huì)隨著問(wèn)題規(guī)模的增大而呈指數(shù)增長(zhǎng)[6]，傳統(tǒng)的精確算法在此場(chǎng)景下難以在規(guī)定時(shí)間內(nèi)求解，而啟發(fā)式算法適用于計(jì)算大規(guī)模問(wèn)題，所以成為了學(xué)者們研究的重點(diǎn)。關(guān)于此類問(wèn)題的求解，學(xué)者們依次提出禁忌搜索算法[7-8]、蟻群算法[9-10]、遺傳算法[11-12]、粒子群算法[13-14]等多個(gè)算法。本文采用的是李彤等[15]提出的PGSA算法，它最初被用于解決非線性整數(shù)規(guī)劃問(wèn)題，由于其算法原理不需過(guò)度依靠參數(shù)，性能優(yōu)越，因而被學(xué)者廣泛應(yīng)用于許多工程技術(shù)領(lǐng)域。

曹慶奎等[16]設(shè)計(jì)了用以求解VRPTW問(wèn)題的PGSA算法，結(jié)合車輛調(diào)度的物流任務(wù)需求，建立客戶需求隨機(jī)性機(jī)會(huì)約束模型，在求解效率上與傳統(tǒng)的遺傳算法進(jìn)行比較，驗(yàn)證PGSA算法是一種有效的方法。石開(kāi)榮等[17]在對(duì)PGSA算法基本原理進(jìn)行深入研究之后，結(jié)合植物實(shí)際生長(zhǎng)規(guī)律，提出雙生點(diǎn)并行生長(zhǎng)機(jī)制來(lái)增加了尋優(yōu)搜索路徑，拓寬搜索覆蓋面，降低陷入局部最優(yōu)解的概率。石開(kāi)榮等[18]提出可生長(zhǎng)點(diǎn)集合限定機(jī)制、可生長(zhǎng)點(diǎn)剔除機(jī)制以及混合步長(zhǎng)并行搜索機(jī)制，其核心思想是使用一種篩選優(yōu)質(zhì)可生長(zhǎng)點(diǎn)的策略，有效控制計(jì)算規(guī)模、提高搜索能力。然而，優(yōu)質(zhì)點(diǎn)的篩選雖然可以提高解的搜索能力，但會(huì)導(dǎo)致解過(guò)早收斂，且一定程度上去除了劣點(diǎn)的搜索機(jī)會(huì)。

PGSA算法依賴于初始值，初始值的質(zhì)量關(guān)系著算法的求解性能，且后期收斂性較差，容易陷入局部最優(yōu)解。所以本文在文獻(xiàn)[16]和文獻(xiàn)[18]基礎(chǔ)上對(duì)PGSA算法做了3個(gè)方面的改進(jìn)：設(shè)計(jì)雙階段的PGSA搜索方案、增加有向生長(zhǎng)機(jī)制和局部解跳出機(jī)制。首先，在算法的開(kāi)始階段，將問(wèn)題簡(jiǎn)化為TSP問(wèn)題進(jìn)行處理求解，迭代一定次數(shù)之后得到第二階段算法搜索的初始解，再使用本文改進(jìn)后的生長(zhǎng)策略，計(jì)算問(wèn)題最優(yōu)解。同時(shí)本文針對(duì)PGSA的過(guò)早收斂問(wèn)題，引入局部解跳出機(jī)制，使其能在一定次數(shù)的搜索之后，跳出局部最優(yōu)。最后，利用Solomon中的標(biāo)準(zhǔn)算例進(jìn)行測(cè)試，與原始算法[16]進(jìn)行對(duì)比。

1 背 景

1.1 VRPTW問(wèn)題描述

VRPTW問(wèn)題[19]一般被描述為：客戶、配送中心的橫縱坐標(biāo)已知，給定每個(gè)客戶配送需求，車輛從配送中心出發(fā)對(duì)每個(gè)客戶進(jìn)行配送，且只可訪問(wèn)客戶一次，每輛車所配送需求量之和不可超過(guò)車輛最大載運(yùn)量和行駛距離[20]，此外，各個(gè)客戶存在的時(shí)間窗要求也需考慮在內(nèi)，車輛必須在時(shí)間窗[ei,li]內(nèi)服務(wù)客戶，以行駛距離最短為目標(biāo)進(jìn)行車輛調(diào)度，完成客戶配送任務(wù)。

1.2 VRPTW數(shù)學(xué)模型

對(duì)于VRPTW問(wèn)題，通過(guò)建立通用的數(shù)學(xué)模型來(lái)進(jìn)行計(jì)算。設(shè)有N臺(tái)配送車輛存在于配送中心，每臺(tái)車輛(編號(hào)k)的載重量為Capk，行駛距離上限為Dk，現(xiàn)需配送M個(gè)客戶，每個(gè)客戶i的需求量為qi(i=1,2,3,…,M)，每個(gè)客戶要求的配送時(shí)間窗為[ei,li]，配送中心的標(biāo)號(hào)為0，客戶i到客戶j的距離為dij(i,j=0,1,2,3,…,M)，tij表示配送車輛由客戶i行駛到客戶j的行駛時(shí)間，ti表示車輛到達(dá)顧客i位置的時(shí)間[21]，tsi則表示車輛需要在客戶i處的服務(wù)時(shí)間。再設(shè)nk為第k輛車配送的客戶數(shù)(nk=0則表示未使用第k臺(tái)車),集合Rk表示第k輛車行駛的路徑，其中的單個(gè)元素rki表示客戶rki在路徑Rk中的順序?yàn)閕[22]。rk0=0代表車輛k是從配送中心0出發(fā)，初始時(shí)間t0賦值為0。

目標(biāo)函數(shù)：

(1)

約束條件：

(2)

(3)

0≤nk≤M

(4)

(5)

Rk={rki|rki∈{1,2,…,M},i=1,2,…,nk}

(6)

Rk1∩Rk2=φ, ?k1≠k2

(7)

(8)

ei≤ti≤li;i=1,2,…,M

(9)

(10)

其中，式(1)表示行駛距離最短的目標(biāo)函數(shù)；式(2)與式(3)表示容量約束、距離約束，式(6)與式(7)表示客戶只被一輛車服務(wù)一次，式(9)與式(10)代表時(shí)間窗約束和遞推公式。

2 PGSA算法的優(yōu)化設(shè)計(jì)

2.1 PGSA算法原理

PGSA算法(模擬植物生長(zhǎng)算法)是將優(yōu)化問(wèn)題的解空間視作植物的生長(zhǎng)環(huán)境，通過(guò)模擬植物生長(zhǎng)的分支模式(L-系統(tǒng))，以植物的向性運(yùn)動(dòng)為啟發(fā)式準(zhǔn)則進(jìn)行優(yōu)化問(wèn)題求解的近似算法[19]。

L-系統(tǒng)的形式化描述：破土而出的主干會(huì)在稱之為節(jié)的地方長(zhǎng)出新枝，新枝也會(huì)因?yàn)樾螒B(tài)素的規(guī)則長(zhǎng)出更新的枝，這種生長(zhǎng)過(guò)程會(huì)反復(fù)進(jìn)行，各個(gè)新枝彼此之間存在相似性，整個(gè)植物由自相似結(jié)構(gòu)構(gòu)成[23]。

PGSA算法在搜索空間中通過(guò)模擬植物生長(zhǎng)的方式來(lái)搜索最優(yōu)解，求解過(guò)程中得到的生長(zhǎng)節(jié)點(diǎn)可以作為此類優(yōu)化問(wèn)題的可行解。生長(zhǎng)節(jié)點(diǎn)的形態(tài)素濃度決定了該節(jié)點(diǎn)被選擇作為新枝的可能性，形態(tài)素濃度更高的節(jié)點(diǎn)具有更高的環(huán)境適應(yīng)性，更容易被選擇。

設(shè)一棵樹(shù)從樹(shù)根所在點(diǎn)x0開(kāi)始生長(zhǎng)，形成樹(shù)干X0，經(jīng)過(guò)計(jì)算，選取形態(tài)素濃度超過(guò)x0的點(diǎn)作為生長(zhǎng)點(diǎn)，假定這些點(diǎn)為X01,X02,…,X0k，每個(gè)點(diǎn)對(duì)應(yīng)的形態(tài)素濃度為PX01,PX02,PX03,…, PX0k，其計(jì)算公式如下:

PX0i=[Z(x0)-Z(X0i)]/Δi，i=1,2,…,k

(11)

其中：

(12)

Z(X)表示生長(zhǎng)點(diǎn)X的環(huán)境信息(目標(biāo)函數(shù)值)，也被稱作背光函數(shù)，函數(shù)取值越小的生長(zhǎng)點(diǎn)，對(duì)應(yīng)生長(zhǎng)點(diǎn)的陽(yáng)光照射條件就越好。由以上2式不難看出，迭代計(jì)算中各點(diǎn)形態(tài)素濃度之和始終為1。目標(biāo)函數(shù)值越小，該點(diǎn)的形態(tài)素濃度就越高，被選中的概率就越大。PX01,PX02,PX03,…, PX0k共同組成和為1的區(qū)間，隨機(jī)生成一個(gè)[0,1]的實(shí)數(shù)，其在哪個(gè)生長(zhǎng)點(diǎn)的區(qū)間內(nèi)，就被選作生長(zhǎng)新枝。如果實(shí)數(shù)生成在PX03的區(qū)間，那么生長(zhǎng)點(diǎn)X03就會(huì)長(zhǎng)出樹(shù)枝X1，假設(shè)樹(shù)枝X1上有q個(gè)生長(zhǎng)點(diǎn)X11，X12，…，X1q，對(duì)應(yīng)形態(tài)素濃度為PX11，PX12，…，PX1q。生長(zhǎng)新枝以后植物的生長(zhǎng)環(huán)境會(huì)發(fā)生變化，所以需重新計(jì)算形態(tài)素濃度，公式如下：

(13)

(14)

其中：

(15)

(16)

以此類推，反復(fù)進(jìn)行此過(guò)程，直到迭代結(jié)束。

2.2 雙階段PGSA算法

文獻(xiàn)[16]在對(duì)現(xiàn)有VRP問(wèn)題研究的基礎(chǔ)上，使用PGSA算法分開(kāi)處理VRPTW的目標(biāo)函數(shù)和約束條件，得到最終解決方案。但是原PGSA算法在求解過(guò)程中，結(jié)果收斂性差，容易陷入局部最優(yōu)解，算法策略有待進(jìn)一步改善。由于PGSA在搜索生長(zhǎng)點(diǎn)時(shí)，對(duì)于初始值的依賴性較強(qiáng)[24]，算法隨機(jī)生成初始調(diào)度方案的方式，對(duì)求解精度影響較大。所以，本文針對(duì)初始值的質(zhì)量問(wèn)題，設(shè)計(jì)雙階段的PGSA算法，并且改進(jìn)生長(zhǎng)點(diǎn)的生長(zhǎng)策略。在算法的初始階段，原有VRPTW問(wèn)題被理想化為一個(gè)不考慮需求，只將路程作為評(píng)價(jià)標(biāo)準(zhǔn)的TSP問(wèn)題，針對(duì)此問(wèn)題展開(kāi)初始階段的鄰域搜索。

TSP問(wèn)題又被稱作旅行商問(wèn)題，研究者通常將其視作VRP問(wèn)題的一個(gè)特殊變體，被描述為一個(gè)旅行商從一個(gè)城市出發(fā)，經(jīng)過(guò)所有城市后回到出發(fā)地，選擇行進(jìn)路線使得總體行程最短的問(wèn)題[25]。

其評(píng)價(jià)公式為：

(17)

根據(jù)VRPTW問(wèn)題和TSP問(wèn)題的定義，不難看出它們實(shí)質(zhì)上都是NP難題，在多項(xiàng)式時(shí)間內(nèi)無(wú)法驗(yàn)證一個(gè)解的正確性。問(wèn)題規(guī)模n的情況下解空間的大小為n!，隨著n的增大，計(jì)算難度呈指數(shù)上升。

在這種情況下，傳統(tǒng)精確算法無(wú)法在規(guī)定時(shí)間內(nèi)求解問(wèn)題，因此，針對(duì)這一點(diǎn)，國(guó)內(nèi)外學(xué)者重點(diǎn)使用近似算法和啟發(fā)式算法2類算法求解大規(guī)模問(wèn)題。本文引用的PGSA算法是啟發(fā)式算法的一種，它通過(guò)在搜索過(guò)程中獲得的啟發(fā)式信息來(lái)引導(dǎo)搜索，消除組合爆炸，使得問(wèn)題的復(fù)雜度降低，同時(shí)降低了搜索工作量。

下面給出算法的可行性證明：

設(shè)在迭代搜索的過(guò)程中，針對(duì)每次迭代的生長(zhǎng)點(diǎn)s∈S，S代表符合解的狀態(tài)空間中的所有點(diǎn)集，s是其中一個(gè)元素變量(下文中的route即為s，代表每一代搜索的起始算子)，由s的取值序列構(gòu)成了迭代過(guò)程中的初始狀態(tài)集合{s0,s1,s2,…,sn};每次迭代都可以視作對(duì)狀態(tài)s進(jìn)行一次搜索。而搜索操作的結(jié)果是生成了以s為起點(diǎn)的搜索集合以及產(chǎn)生了集合中的最小值s*。定義S上的Next-State關(guān)系為T，T?S×S，它可以產(chǎn)生各種行為，每個(gè)行為可以表示成s1→s2→s3…的形式，并且滿足?i,∈T,可以把T理解成輸入和輸出都屬于S的動(dòng)作。定義搜索算法的歸納不變式為Inv=Search(s0)=Search(s)=s*，按照歸納法，基本推導(dǎo)為：

1)Init?Inv

初始化時(shí)，s=s0顯然成立。

2)Inv∧T?Inv

設(shè)當(dāng)前狀態(tài)滿足Inv，那么Search(s)=Search(s0)=s*,設(shè)s的鄰接狀態(tài)為s′，s*不是不變式Search(s′)的搜索結(jié)果，即Search(s′)=h，?h∈S，h

3)在程序執(zhí)行結(jié)束時(shí)，s*=Search(s)=Search(s0)。

綜上，在計(jì)算復(fù)雜度高的問(wèn)題中，采用本文的啟發(fā)式算法可以在迭代一定代數(shù)之后取得較優(yōu)解。

改進(jìn)后的PGSA算法基本流程見(jiàn)圖1。

圖1 基本流程圖

2個(gè)階段共用同一個(gè)算法基本流程，但在第一階段開(kāi)始時(shí)，初始算子route是隨機(jī)生成，并且第一階段的目標(biāo)函數(shù)來(lái)自于公式(17)。而在第二階段開(kāi)始時(shí)，初始算子route使用的是第一階段搜索得到的res，第二階段的目標(biāo)函數(shù)來(lái)自于公式(1)，使用VRPTW的約束進(jìn)行解的評(píng)估、搜索，在經(jīng)過(guò)雙階段搜索之后，最終生成較高質(zhì)量解。

本文在5個(gè)規(guī)模為50的數(shù)據(jù)集上分別使用單階段PGSA算法與雙階段PGSA算法進(jìn)行測(cè)試，記錄20次實(shí)驗(yàn)所得最優(yōu)值、平均值，并將其與已知最優(yōu)解之間的誤差計(jì)算值作為縱坐標(biāo)，結(jié)果如圖2和圖3所示。從圖中不難看出，雙階段的搜索方案誤差更低，解的質(zhì)量得到了有效提高。

圖2 最優(yōu)解誤差對(duì)比圖

圖3 平均解誤差對(duì)比圖

2.3 有向生長(zhǎng)機(jī)制

在選定生長(zhǎng)點(diǎn)route之后，PGSA算法會(huì)對(duì)route進(jìn)行鄰域搜索。但搜索過(guò)程中，較多劣質(zhì)的生長(zhǎng)點(diǎn)會(huì)保留在可生長(zhǎng)點(diǎn)集合中,大大降低了其優(yōu)化效率[18]。針對(duì)這一問(wèn)題，本文提出一種有向生長(zhǎng)機(jī)制，在每代進(jìn)行搜索時(shí)，更改生長(zhǎng)策略，優(yōu)先將route點(diǎn)有向變換到當(dāng)前最小值xmin，使route能夠在生長(zhǎng)開(kāi)始時(shí)得到一個(gè)初始的生長(zhǎng)方向，之后對(duì)route進(jìn)行鄰域搜索，選取搜索過(guò)程中得到的最優(yōu)鄰域算子更新xmin。具體的流程見(jiàn)圖4。

圖4 算法route的有向生長(zhǎng)子流程

圖4中xmin.size代表xmin算子的大小，xmin[i]代表算子中的第i個(gè)元素，可取范圍為1～M。

如果在搜索過(guò)程中，搜索點(diǎn)通過(guò)插入法得到結(jié)果不優(yōu)于當(dāng)前生長(zhǎng)點(diǎn)route，則會(huì)對(duì)route進(jìn)行兩交換法搜索。經(jīng)過(guò)上述2個(gè)搜索過(guò)程之后，如果不能更新route，則會(huì)結(jié)束本次迭代中的搜索過(guò)程。

圖5是數(shù)據(jù)規(guī)模為50的RC101算例在迭代次數(shù)為15次時(shí)候搜索得到生長(zhǎng)點(diǎn)的樣本圖。隨機(jī)選取2種策略下該代搜索所得的50個(gè)生長(zhǎng)點(diǎn)樣本，從圖中可以看出，使用有向生長(zhǎng)機(jī)制優(yōu)化之后的PGSA算法搜索得到的生長(zhǎng)點(diǎn)目標(biāo)值更低，搜索效率更高。

圖5 生長(zhǎng)點(diǎn)樣本圖

2.4 局部解跳出機(jī)制

在多次迭代搜索以后，PGSA可能會(huì)陷入局部最優(yōu)解，為了跳出局部最優(yōu)解，本文設(shè)計(jì)跳出機(jī)制。定義歷史最優(yōu)解fres、當(dāng)前最優(yōu)解fmin、頻率判斷最優(yōu)解fmin2這3個(gè)變量。如果在搜索得到的最小值出現(xiàn)次數(shù)f(即當(dāng)前最優(yōu)解與頻率判斷最優(yōu)解相等的次數(shù))超過(guò)一定頻率F之后，對(duì)其連續(xù)使用5次隨機(jī)交換操作，得到新的算子，替代原來(lái)的最小值。同時(shí)將f置0，更新當(dāng)前最優(yōu)解、頻率判斷最優(yōu)解、歷史最優(yōu)解，重新開(kāi)始下代搜索。具體流程見(jiàn)圖6。

圖6 局部解跳出子流程

如圖7所示，對(duì)R101算例進(jìn)行測(cè)試，客戶數(shù)量為50個(gè)。線1是使用局部解跳出機(jī)制的算法曲線，線2是未使用局部解跳出機(jī)制的算法曲線，縱坐標(biāo)是該代搜索得到的歷史最優(yōu)解res目標(biāo)函數(shù)值fres。從圖中可以看出，引入局部解跳出機(jī)制之后，算法取得了更好的收斂結(jié)果。

圖7 結(jié)果對(duì)比圖

2.5 PGSA優(yōu)化算法設(shè)計(jì)要點(diǎn)

PGSA優(yōu)化算法設(shè)計(jì)要點(diǎn)包括：

1)解的表示方法：客戶直接排列法。

2)解的評(píng)價(jià)方法：采用式(1)對(duì)解進(jìn)行評(píng)價(jià)。根據(jù)客戶要求將貨物按時(shí)送達(dá)的時(shí)間窗約束，將解中的元素依次納入到各條配送路徑中，在不滿足時(shí)間窗約束時(shí)，結(jié)束本條配送路徑，并將剩余點(diǎn)分配給下一車輛。最早計(jì)算出該解的評(píng)價(jià)值E。

3)鄰域算子搜索方法：兩交換法、插入法。

4)搜索規(guī)模：N2。

5)鄰域算子的確定：從當(dāng)前算子的鄰域中選擇搜索過(guò)程中評(píng)價(jià)值最高的鄰域算子。

6)生長(zhǎng)點(diǎn)選取策略：隨機(jī)數(shù)法。

7)終止準(zhǔn)則：采用迭代指定步數(shù)的終止準(zhǔn)則。

鄰域算子搜索方法包括：

1)插入法：使用隨機(jī)函數(shù)，隨機(jī)生成一個(gè)客戶編號(hào)，并將其插入到算子的任意位置。

如原算子是0-5-6-2-4-3-1，任意選取一數(shù)字3，將其插入到客戶6和客戶2之間，得到鄰域算子：0-5-6-3-2-4-1。

2)兩交換法：使用隨機(jī)函數(shù)，隨機(jī)生成2個(gè)客戶編號(hào)，交換其位置。

如將上述算子中的客戶5、1位置交換之后，可得到鄰域算子：0-1-6-3-2-4-5。

引入兩交換法是為了使搜索過(guò)程中避開(kāi)局部最優(yōu)解，提高算法搜索效率。在對(duì)當(dāng)前解進(jìn)行搜索時(shí)，如果插入法搜索得到的鄰域算子不優(yōu)于當(dāng)前算子route，則會(huì)再對(duì)當(dāng)前算子route進(jìn)行一次交換搜索。

3 實(shí)驗(yàn)分析

本文采用VRPTW的Solomon算例集測(cè)試雙階段PGSA算法的求解性能。使用Win10系統(tǒng)、CPU i7-5500U、RAM 8 GB、Java語(yǔ)言編程實(shí)現(xiàn)，軟件為VScode。表1是以RC207算例所展示的Solomon標(biāo)準(zhǔn)數(shù)據(jù)格式。

表1中，第1列代表客戶編號(hào)，客戶0代表倉(cāng)庫(kù)位置，第2列代表客戶位置的橫坐標(biāo)，第3列代表客戶位置的縱坐標(biāo)，第4列代表客戶所需物資數(shù)，第5列代表最早交付時(shí)間，第6列代表最晚交付時(shí)間，最后一列代表在該客戶點(diǎn)服務(wù)時(shí)長(zhǎng)。

表1 RC207數(shù)據(jù),車輛數(shù)目25，容量1000

計(jì)算得到RC207算例的解決方案如表2所示，在車輛路線一欄，每行代表一個(gè)車輛的行駛路徑，車輛從配送點(diǎn)0(倉(cāng)庫(kù))出發(fā)最終返回配送點(diǎn)0(倉(cāng)庫(kù))。

表2 RC207算例解決方案

本文實(shí)驗(yàn)部分采用的Solomon benchmark是一個(gè)用于研究VRPTW問(wèn)題的標(biāo)準(zhǔn)數(shù)據(jù)算例集。其中R1和R2的客戶位置是隨機(jī)生成，而C1、C2的客戶位置則較為集中，RC1和RC2則混合了隨機(jī)分布以及集中分布的客戶位置。此外，R1、C1、RC1的任務(wù)時(shí)間窗排列較為緊湊，R2、C2、RC2的任務(wù)時(shí)間窗排列則較為寬松。實(shí)驗(yàn)考慮實(shí)際配送工作中客戶位置、數(shù)量和時(shí)間窗口分布不同的情況，針對(duì)不同規(guī)模(分別包含25、50、100個(gè)客戶)、多種客戶分布類型的Solomon算例，使用原PGSA算法和改進(jìn)后的雙階段PGSA算法計(jì)算20次，并記錄下每次的運(yùn)行結(jié)果，計(jì)算平均解、與數(shù)據(jù)集所提供的歷史最優(yōu)解的誤差，結(jié)果記錄到表3～表5中。

表3 PGSA與雙階段PGSA在25個(gè)客戶規(guī)模數(shù)據(jù)仿真對(duì)比

表4 PGSA與雙階段PGSA在50個(gè)客戶規(guī)模數(shù)據(jù)仿真對(duì)比

表5 PGSA與雙階段PGSA在100個(gè)客戶規(guī)模數(shù)據(jù)仿真對(duì)比

為了進(jìn)一步驗(yàn)證雙階段PGSA算法的性能，采用蟻群算法(ACO)、禁忌搜索算法(TS)、自適應(yīng)大鄰域搜索算法(ALNS)，對(duì)Solomon數(shù)據(jù)集中100個(gè)客戶規(guī)模的算例進(jìn)行求解，6種類型算例各選其一進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果記錄在表6中。

表6 雙階段PGSA于ACO、TS、ALNS仿真對(duì)比結(jié)果 單位：km

實(shí)驗(yàn)選取21個(gè)算例對(duì)改進(jìn)后的算法和原算法進(jìn)行測(cè)試，通過(guò)結(jié)果比對(duì)，雙階段PGSA在最優(yōu)解的求解問(wèn)題上表現(xiàn)出了較好的收斂性，并且也提高了平均解的質(zhì)量。原始PGSA算法在小規(guī)模數(shù)據(jù)集上的求解質(zhì)量較好，但隨著數(shù)據(jù)集計(jì)算規(guī)模的增大，原始PGSA算法對(duì)最優(yōu)解的求解能力逐漸下降，本文改進(jìn)后的有向生長(zhǎng)機(jī)制和局部解跳出機(jī)制可以提升PGSA算法在大規(guī)模數(shù)據(jù)集上的搜索能力，提高搜索效率，有效改善算法過(guò)早陷入局部最優(yōu)解的情況。

從表6與其它算法的對(duì)比結(jié)果看，本文改進(jìn)之后的雙階段PGSA算法在6種不同類型的算例中都取得了一個(gè)較優(yōu)結(jié)果，除去在C105算例實(shí)驗(yàn)中高于TS算法,在C203、RC203算例實(shí)驗(yàn)中高于ALNS算法之外，其它算例中都取得了不錯(cuò)的收斂結(jié)果。

4 結(jié)束語(yǔ)

在分析PGSA算法的基礎(chǔ)上，本文的雙階段策略通過(guò)對(duì)初始解構(gòu)造的優(yōu)化，提高了解的搜索質(zhì)量，使算法搜索效率提升。這個(gè)策略的優(yōu)點(diǎn)是易于實(shí)現(xiàn)，代碼復(fù)用率高。有向生長(zhǎng)機(jī)制的引入可以使得迭代開(kāi)始時(shí)所選取的生長(zhǎng)點(diǎn)可以有導(dǎo)向地收斂到當(dāng)前局部最小值，提高當(dāng)前鄰域搜索的效率。局部解跳出機(jī)制可以在算法陷入局部最優(yōu)解時(shí)，破壞解的結(jié)構(gòu)，從而搜索到更好的解決方案。

PGSA算法的生長(zhǎng)策略與生長(zhǎng)點(diǎn)選取策略對(duì)求解效率起著重要作用。本文的有向生長(zhǎng)機(jī)制與局部解跳出機(jī)制都僅是對(duì)生長(zhǎng)策略的優(yōu)化，這2個(gè)機(jī)制的設(shè)計(jì)方式是否會(huì)對(duì)求解性能產(chǎn)生影響，還需繼續(xù)深入研究。而對(duì)于PGSA算法本身來(lái)說(shuō)，在其計(jì)算大規(guī)模算例的過(guò)程中暴露出內(nèi)存占用高的缺點(diǎn)。如何針對(duì)這一缺點(diǎn)，優(yōu)化生長(zhǎng)策略和生長(zhǎng)點(diǎn)選取策略，對(duì)PGSA算法求解效率的提高會(huì)有很大幫助。