基于有向圖強(qiáng)連通改進(jìn)變鄰域搜索算法的AGV單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)

廖 勇，陳慶新，毛 寧，張惠煜

(1.廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006；2.湘南學(xué)院物理與電子電氣工程學(xué)院，湖南 郴州，423000)

制造系統(tǒng)生產(chǎn)過(guò)程中的物料搬運(yùn)活動(dòng)需要占用25%的總?cè)肆Α?5%的工廠空間和87%的生產(chǎn)時(shí)間。物料搬運(yùn)成本占到產(chǎn)品制造總成本的15% ～70%，并影響所有作業(yè)流程和設(shè)施規(guī)劃的效率[1]。降低物料搬運(yùn)成本成為提高企業(yè)利潤(rùn)的一條重要途徑。鑒于由自動(dòng)導(dǎo)向小車(automatic guided vehicle,AGV)組成的物流儲(chǔ)運(yùn)系統(tǒng)具有成本低、可擴(kuò)展性強(qiáng)、可維護(hù)性好和柔性高的特點(diǎn)[2]，許多企業(yè)都采用由AGV所組成的儲(chǔ)運(yùn)系統(tǒng)取代人工和叉車，削減物料搬運(yùn)成本，縮短物料周轉(zhuǎn)周期，提高企業(yè)利潤(rùn)和核心競(jìng)爭(zhēng)力。因此，設(shè)計(jì)合理且高效的AGV物料儲(chǔ)運(yùn)系統(tǒng)就顯得極為有意義。AGV導(dǎo)向路徑網(wǎng)絡(luò)作為AGV儲(chǔ)運(yùn)系統(tǒng)的最重要部分，不僅決定了物料的搬運(yùn)路線和距離(總運(yùn)輸距離)，而且對(duì)AGV的資源配置和調(diào)度具有非常大的影響。所以在設(shè)計(jì)AGV物料儲(chǔ)運(yùn)系統(tǒng)過(guò)程中，首先需要解決導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。

考慮單向?qū)蚵窂骄W(wǎng)絡(luò)能有效避免AGV間的碰撞和死鎖，簡(jiǎn)化物料儲(chǔ)運(yùn)系統(tǒng)的調(diào)度策略，目前研究都是將導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題處理成單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。Gaskins等[3]首次對(duì)單向?qū)蚵窂骄W(wǎng)絡(luò)進(jìn)行研究，以最小化AGV的負(fù)載運(yùn)輸距離為目標(biāo)，構(gòu)建0-1整數(shù)規(guī)劃模型。除考慮與距離相關(guān)的目標(biāo)函數(shù)外，Beamon[4]提出了最小化生產(chǎn)周期、運(yùn)輸時(shí)間等目標(biāo)函數(shù)。就運(yùn)輸效率而言，無(wú)軌AGV優(yōu)于單向AGV，因此，Gaskins等[5]提出虛擬路徑網(wǎng)絡(luò)的概念。Kaspi[6]在此基礎(chǔ)上，構(gòu)建數(shù)學(xué)模型，并給出一個(gè)高效的求解算法?？紤]AGV空載對(duì)單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)的影響，Sun[7]對(duì)其作進(jìn)一步拓展，將AGV空載距離納入優(yōu)化目標(biāo)中，并用分支定界算法求解該模型。單向?qū)蚵窂皆O(shè)計(jì)問(wèn)題屬于NP-Hard問(wèn)題，以上文獻(xiàn)中的精確算法，只適合解決小規(guī)模問(wèn)題。為有效解決中大規(guī)模問(wèn)題，Seo等[8]首先提出采用禁忌搜索算法求解，并在此基礎(chǔ)上再提出禁忌搜索算法與遺傳算法相結(jié)合的混合算法。關(guān)于元啟發(fā)式算法求解導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題的最新進(jìn)展可參考文獻(xiàn)[9]。在國(guó)內(nèi)，也有很多學(xué)者對(duì)車道網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題進(jìn)行了研究。管賢平等[10-11]以最小化負(fù)載與空載總路程為目標(biāo)，分別采用小生境遺傳算法[10]和改進(jìn)的類電磁激勵(lì)機(jī)制算法[11]對(duì)其進(jìn)行求解。 肖海寧等[12]綜合考慮空載和負(fù)載總路程最小化，提出一種混合遺傳算法。實(shí)驗(yàn)結(jié)果表明，該算法比傳統(tǒng)的遺傳算法和禁忌搜索算法具有更好的整體性能。肖海寧等[13]以最小化最大完工時(shí)間為目標(biāo)，提出一種改進(jìn)的小生境遺傳算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性。進(jìn)一步考慮設(shè)施布局與導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)兩者間的耦合關(guān)系，文獻(xiàn)[14-15]對(duì)其進(jìn)行聯(lián)合研究。

采用元啟發(fā)式算法雖能求解大規(guī)模問(wèn)題，但對(duì)于導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題求解效率和質(zhì)量并不佳[9]。由于一個(gè)可行的導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)方案，需要導(dǎo)向路徑網(wǎng)絡(luò)對(duì)應(yīng)的有向圖具有強(qiáng)連通性質(zhì)，即有向圖中的任意兩個(gè)頂點(diǎn)之間可相互到達(dá)。然而當(dāng)前啟發(fā)式算法在鄰域搜索中都采用如改變導(dǎo)向路徑網(wǎng)絡(luò)中某條路徑的方向，改變某個(gè)頂點(diǎn)相連路徑的方向等鄰域動(dòng)作[8]，都無(wú)法保證生成的解滿足強(qiáng)連通性質(zhì)。不僅需要額外的算法來(lái)判定解的合法性，而且造成鄰域搜索過(guò)程中存在大量無(wú)效搜索，極大地降低了元啟發(fā)式算法的求解效率和質(zhì)量。

因此，本文針對(duì)AGV單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，結(jié)合有向圖強(qiáng)連通性提出一種改進(jìn)的變鄰域搜索算法，求解AGV單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。以有向圖強(qiáng)連通性中反轉(zhuǎn)路、反轉(zhuǎn)圈保持強(qiáng)連通性為基礎(chǔ)，提出3種鄰域結(jié)構(gòu)生成方法，以保證鄰域解搜索過(guò)程中解的可行性，提高求解效率和質(zhì)量。為驗(yàn)證本文所提出的改進(jìn)變鄰域搜索算法有效性，對(duì)6個(gè)基準(zhǔn)案例進(jìn)行計(jì)算，并將其與精確算法和多種其他啟發(fā)式算法進(jìn)行比較。

1 問(wèn)題描述

本文所研究的單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，即在已知每一個(gè)單元上下料口位置和單元間物流量的情況下，設(shè)置一條AGV車道的行駛方向，使得導(dǎo)向路徑網(wǎng)絡(luò)滿足強(qiáng)連通約束條件 (即導(dǎo)向路徑網(wǎng)絡(luò)對(duì)應(yīng)的有向圖為強(qiáng)連通有向圖)，以達(dá)到最小化由AGV運(yùn)載過(guò)程和空載過(guò)程所形成的總運(yùn)輸距離的目的。下面以含4個(gè)加工單元的車間為例，未定向的AGV導(dǎo)向路徑網(wǎng)絡(luò)如圖1所示，其相應(yīng)的無(wú)向圖模型為G=(V,E)，其中，頂點(diǎn)集V表示AGV上/下料口、交匯點(diǎn)、轉(zhuǎn)彎點(diǎn)，邊集E表示頂點(diǎn)之間相連的導(dǎo)向路徑。若從圖論的角度研究AGV導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，可將其簡(jiǎn)化成圖的最優(yōu)強(qiáng)連通定向問(wèn)題，即找到無(wú)向圖G的一個(gè)強(qiáng)連通定向D，使得總運(yùn)輸距離最小。所以單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)可等效成圖的最優(yōu)強(qiáng)連通定向問(wèn)題。

圖1 未定向AGV導(dǎo)向路徑網(wǎng)絡(luò)圖Figure 1 The undirected flow path network

為便于建立該問(wèn)題的數(shù)學(xué)規(guī)劃模型，先假設(shè)車間含有W個(gè)單元，每一個(gè)單元有唯一上料口pw和下料口dw，所有單元的上料口pw和下料口dw構(gòu)成集合p和d。e(i,j)表 示從頂點(diǎn)i到 頂點(diǎn)j的車道，變量Zij表示車道的方向(若Zij為 1，則車道方向?yàn)閺捻旤c(diǎn)i到頂點(diǎn)j；若Zij為 0，則為從頂點(diǎn)j到頂點(diǎn)i) 。hij表示車道的長(zhǎng)度。fwu表 示從下料口dw到 上料口pu的搬運(yùn)次數(shù)。guw表 示從上料口pu到 下料口dw的空載次數(shù)。Lij表 示從頂點(diǎn)i到 頂點(diǎn)j的最短路徑。變量表示車道e(i,j) 位 于下料口dw到 上料口pu的搬運(yùn)路線上(若為1，則表示車道e(i,j)處 于搬運(yùn)路線；若為0，則表示車道e(i,j)未處于搬運(yùn)路線上)。類似定義變量表示車道e(i,j) 位 于處于上料口pu到下料口dw的空載路線上。該問(wèn)題的數(shù)學(xué)規(guī)劃模型如下[11]。

式(1)為該數(shù)學(xué)規(guī)劃模型的優(yōu)化目標(biāo)，即最小化由搬運(yùn)距離和空載距離所組成的總運(yùn)輸距離。約束(2)、(3)確保從上料口pw到下料口du、從下料口du到上料口pw的空載路線距離等于選擇的車道長(zhǎng)度和。約束(4)、(5)保證從上料口pw指向其他頂點(diǎn)和從其他頂點(diǎn)指向上料口pw的車道數(shù)量有且僅有一條。約束(6)、(7)保證從下料口du指向其他頂點(diǎn)和從其他頂點(diǎn)指向下料口du的車道數(shù)量有且僅有一條。約束(8)、(9)為非上、下料口頂點(diǎn)流量約束，AGV進(jìn)入該頂點(diǎn)的次數(shù)等于離開(kāi)的次數(shù)。約束(10)、(11)為路線約束，每一條搬運(yùn)(空載)路線中不能出現(xiàn)重復(fù)車道。約束(12)保證每一條車道都是單向。約束(13)、(14)保證任意頂點(diǎn)集S都存在一條導(dǎo)向路徑起始于、終止于當(dāng)前頂點(diǎn)，使得導(dǎo)向路徑網(wǎng)絡(luò)為強(qiáng)連通。約束(15)、(16)為物流平衡約束，即AGV的搬運(yùn)次數(shù)等于AGV的空載次數(shù)。式(17)為變量約束，每一個(gè)變量都為0-1整數(shù)。不難看出，該數(shù)學(xué)模型不僅存在大量的0-1變量和約束，且隨著決策變量規(guī)模的增加，其解空間呈指數(shù)性增長(zhǎng)；加之目標(biāo)函數(shù)中的空載距離為二次非凸函數(shù)，使得精確算法無(wú)法在有效時(shí)間內(nèi)求得問(wèn)題的最優(yōu)解。

元啟發(fā)式算法具有良好的搜索優(yōu)化能力，能有效解決大多數(shù)組合優(yōu)化問(wèn)題；若采用元啟發(fā)式算法求解單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，需要設(shè)計(jì)合理的鄰域動(dòng)作。由于一個(gè)可行的AGV導(dǎo)向路徑方案對(duì)應(yīng)的有向圖必須為強(qiáng)連通有向圖，所以一個(gè)合理的鄰域動(dòng)作應(yīng)該能保持強(qiáng)連通性質(zhì)。本文基于有向圖強(qiáng)連通性理論中的反轉(zhuǎn)路、反轉(zhuǎn)圈保持強(qiáng)連通性質(zhì)，設(shè)計(jì)3個(gè)鄰域動(dòng)作，證明并給出具體的鄰域生成方法，在此基礎(chǔ)上提出改進(jìn)的變鄰域算法，以求解單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。

2 改進(jìn)的變鄰域搜索算法

本節(jié)首先介紹深度優(yōu)先搜索過(guò)程。給出一種滿足強(qiáng)連通約束的初始解生成方法。接著，建立目標(biāo)函數(shù)的網(wǎng)絡(luò)流模型。然后，基于有向圖強(qiáng)連通理論中的反轉(zhuǎn)路、反轉(zhuǎn)圈保持強(qiáng)連通性質(zhì)，提出3種鄰域動(dòng)作，證明3種鄰域動(dòng)作所生成的鄰域結(jié)構(gòu)的合理性，并給出鄰域結(jié)構(gòu)的具體方法。最后，簡(jiǎn)單敘述改進(jìn)變鄰域搜索算法的整體流程。

2.1 初始解生成方法

利用圖的深度優(yōu)先搜索過(guò)程，可在線性時(shí)間內(nèi)確定圖的一個(gè)強(qiáng)連通定向。首先，按照深度優(yōu)先搜索過(guò)程從小到大標(biāo)簽頂點(diǎn)并標(biāo)記邊。接著，利用標(biāo)簽和標(biāo)記邊的集合T定義一個(gè)方向。最后按照文獻(xiàn)[16]中的方法，以圖1為例，基于深度優(yōu)先搜索的先后順序，從小到大給予頂點(diǎn)一個(gè)標(biāo)簽值(< >內(nèi)數(shù)字為頂點(diǎn)的標(biāo)簽值)，如圖2所示，記為非標(biāo)記邊集合，則={{6,7},{3,9},{9,12},{7,14}}。按照定向規(guī)則所得圖的一個(gè)強(qiáng)連通定向，如圖3所示。考慮G的深度優(yōu)先搜索過(guò)程，可以完成當(dāng)且僅當(dāng)G是連通圖，且G中不含橋，所以上面定向規(guī)則所生成的有向圖一定滿足強(qiáng)連通約束。

圖2 使用深度搜索過(guò)程得到的一個(gè)頂點(diǎn)標(biāo)簽Figure 2 The label of a node by the deep search process

2.2 目標(biāo)函數(shù)計(jì)算方法

考慮網(wǎng)絡(luò)流求解運(yùn)輸問(wèn)題具有更高的效率，本文建立網(wǎng)絡(luò)流模型計(jì)算空載距離，求最小成本網(wǎng)絡(luò)流。網(wǎng)絡(luò)是一個(gè)有向圖D=(V,A)，其中，V為單元上料口和下料口所構(gòu)成的集合；A表示上料口和下料口之間的運(yùn)輸路線，詳細(xì)的建模方法可見(jiàn)文獻(xiàn)[17]。

2.3 鄰域動(dòng)作設(shè)計(jì)

本節(jié)介紹反轉(zhuǎn)強(qiáng)連通有向圖中路、圈的方向和重定向子圖3種鄰域動(dòng)作。前2種鄰域動(dòng)作主要基于下文的定理1。由該定理可知，假定D為一個(gè)強(qiáng)連通有向圖，則一定存在D中的一些路和圈，反轉(zhuǎn)路或圈中弧的方向所得有向圖D'滿足強(qiáng)連通約束。更進(jìn)一步，令強(qiáng)連通有向D為AGV導(dǎo)向路徑網(wǎng)絡(luò)規(guī)劃的一個(gè)方案，則通過(guò)前面2個(gè)鄰域動(dòng)作，在一定時(shí)間范圍內(nèi)可找到AGV導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)的最優(yōu)方案。理論上采用以上2個(gè)鄰域動(dòng)作即可確定一個(gè)最優(yōu)方案，但為避免搜索過(guò)程陷入局部最優(yōu)，還需擴(kuò)大搜索范圍，所以提出重定向子圖鄰域動(dòng)作。

圖3 強(qiáng)連通導(dǎo)向路徑網(wǎng)絡(luò)Figure 3 The strongly connected flow path network

定理1[18]若D和D'分別是無(wú)向圖G的強(qiáng)連通定向，則存在G的一個(gè)強(qiáng)連通定向序列D=D0,D1,···,Dr，i=1,2,3,···,r，每 一 個(gè)Di是 反 轉(zhuǎn)Di?1中 一 條 路P或一個(gè)圈C的所有弧而生成的強(qiáng)連通有向圖。

2.3.1 反轉(zhuǎn)圈鄰域動(dòng)作

定理2[19]令D=(V,A∪C)為強(qiáng)連通有向圖，其中C為D的有向圈，為反轉(zhuǎn)圈C中弧的方向所得，則D′=(V,A∪)為強(qiáng)連通有向圖。反轉(zhuǎn)強(qiáng)連通有向圖D中圈的所有弧方向，可以保持有向圖D為強(qiáng)連通圖。因此，只需找到強(qiáng)連通有向圖中的圈，就能確定反轉(zhuǎn)圈鄰域動(dòng)作所形成的鄰域結(jié)構(gòu)。目前，Johnson[20]的算法是求1個(gè)強(qiáng)連通有向圖中圈的最高效算法，該算法的時(shí)間復(fù)雜度為o((m+n)(c+1))，其中，n、m分別為有向圖的頂點(diǎn)和弧的數(shù)量；c為有向圖中有向圈的數(shù)量。以圖3為例，采用該算法可找到4個(gè)圈，以其中的一個(gè)圈C:1,6,7,8,9,10,11,5,4,3,2為例，反轉(zhuǎn)圈中弧的方向，得到AGV導(dǎo)向路徑網(wǎng)絡(luò)方案如圖4所示(虛線弧代表反轉(zhuǎn)后的弧)。

圖4 反轉(zhuǎn)圈所得強(qiáng)連通導(dǎo)向路徑網(wǎng)絡(luò)Figure 4 The strongly connected flow path network transformed by reversals of cycles

2.3.2 反轉(zhuǎn)路鄰域動(dòng)作

定理3[19]令D=(V,A∪P)為強(qiáng)連通有向圖，其中P為從頂點(diǎn)x到y(tǒng)的 一條路，令D′=(V,A∪)為反轉(zhuǎn)P后所得有向圖，則D為強(qiáng)連通有向圖的充分必要條件為強(qiáng)連通有向圖D中存在至少2條從頂點(diǎn)x到y(tǒng)的不交路。

反轉(zhuǎn)強(qiáng)連通有向圖D中路的所有弧，可以保持有向圖D的強(qiáng)連通性。因此只需確定存在2條弧不交路的頂點(diǎn)，就能確定反轉(zhuǎn)路鄰域動(dòng)作所形成的鄰域結(jié)構(gòu)。由于頂點(diǎn)間弧不相交路的數(shù)量等價(jià)于頂點(diǎn)間的最大流，因此可采用Dinic算法[19]獲得弧不交路數(shù)量，該算法的時(shí)間復(fù)雜度為o(n2/3m)。以圖3為例，頂點(diǎn)3和7之間存在2條弧不交路P1:16,12,9和P2:16,15,14,7,8，可改變P1和P2中弧方向，得到2個(gè)新的AGV導(dǎo)向路徑網(wǎng)絡(luò)方案，其中的一個(gè)方案如圖5所示。

圖5 反轉(zhuǎn)路的弧方向所得強(qiáng)連通導(dǎo)向路徑網(wǎng)絡(luò)Figure 5 The strongly connected flow path network transformed by reversals of paths

2.3.3 子圖重定向鄰域動(dòng)作

設(shè)D=(V,A)為 有向圖，定義D=(V,A)的一個(gè)二分解，是將圖D=(V,A)分 解成兩個(gè)子圖D1=(V1,A1)和D2=(V2,A2) ，使得兩個(gè)子圖是弧不交的，其中V(D)=V1(D1)∪V2(D2),V1(D1)∩V2(D2)≠?,A(D)=A1(D1)∪A2(D2)。 設(shè)D1=(V1,A1)和D2=(V2,A2)為有向圖，定義D1∪D2是一個(gè)有向圖D，其頂點(diǎn)集V(D)=V(D1)∪V(D2)，弧集A(D)=A1(D1)∪A2(D2)。

定理4令D=(V,A)為 強(qiáng)連通有向圖，D1=(V1,A1)和D2=(V2,A2)為D的一個(gè)二分解，且D1=(V1,A1)的底圖為無(wú)橋連通圖；若將D1=(V1,A1)重定向?yàn)閺?qiáng)連通，則D2和D′1的 并為強(qiáng)連通有向圖。

證明令α =V(D1)∩V(D2)，由圖的二分解定義可知，子圖D1和D2的頂點(diǎn)交集不為空集，因此集合α 不為空，由于有向圖D為強(qiáng)連通有向圖，所以對(duì)于每一對(duì)頂點(diǎn)x∈{x|x∈V(D1),x?α}和y∈{y|x∈V(D2),y?α}，兩者之間的路都必須經(jīng)過(guò)α 中的頂點(diǎn)。從而，對(duì)于每一對(duì)頂點(diǎn)y∈{y|x∈V(D2),y?|x∈V(D1),x?α}和z∈α，兩者之間都存在一條從y到z和從z到y(tǒng)的路。因?yàn)镈1=(V1,A1) 的 底圖G為無(wú)橋連通圖，由Robbins定理[16]可知(連通圖G有一個(gè)強(qiáng)連通定向當(dāng)且僅當(dāng)G不含橋)G存 在強(qiáng)連通定向，令為G的一個(gè)強(qiáng)連通定向，則對(duì)于每一對(duì)頂點(diǎn)和z∈α，都存在一條從x到z和從z到x的路?？紤]D1強(qiáng)定向不會(huì)改變D2中弧的方向，對(duì)于每一對(duì)頂點(diǎn)y∈{y|x∈V(D2),y?α}和z∈α ，兩者之間都存在一條從y到z和從z到y(tǒng)的路，從而每一對(duì)頂點(diǎn)x和y∈{y|x∈V(D2),y?α}在 有向圖D2∪D′1中存在一條從x到y(tǒng)和 從y到x的路。所以，D2∪D′1為強(qiáng)連通有向圖。若能找到一類有向子圖D1，使得D1的底圖為無(wú)橋連通圖，便能確定子圖重定向鄰域動(dòng)作所形成的鄰域結(jié)構(gòu)?？紤]當(dāng)前的AGV導(dǎo)向路徑網(wǎng)絡(luò)是由單元的邊界構(gòu)成的特點(diǎn)，任意2個(gè)相鄰的單元所包含邊界構(gòu)成的子圖，其底圖均為無(wú)橋圖。以圖3為例，單元1和單元2構(gòu)成的子圖的一種強(qiáng)定向如圖6所示，通過(guò)圖合并操作，可以得到一個(gè)如圖7所示的新AGV導(dǎo)向路徑網(wǎng)絡(luò)方案。

圖6 子圖的一種強(qiáng)連通定向Figure 6 The strongly connected orientation of subgraph

圖7 子圖重定向所得強(qiáng)連通導(dǎo)向路徑網(wǎng)絡(luò)Figure 7 The strongly connected flow path network obtained by subgraph re-orientation

2.4 改進(jìn)的變鄰域搜索算法

變鄰域搜索算法(variable neighborhood search,VNS)由Hansen等[21]提出，考慮了局部搜索中不同的鄰域可能有不同的局部最優(yōu)，且全局最優(yōu)是鄰域內(nèi)的局部最優(yōu)特點(diǎn)。系統(tǒng)地搜尋一組預(yù)定義的鄰域，通過(guò)這些鄰域進(jìn)行局部搜索以找到局部最優(yōu)，并在此基礎(chǔ)上采用擾動(dòng)方法來(lái)改變鄰域結(jié)構(gòu)，以避免求解陷入局部最優(yōu)，達(dá)到尋找全局最優(yōu)的目的。因此，基于本文的3種鄰域動(dòng)作，并結(jié)合變鄰域下降法(variable neighborhood descent, VND)和簡(jiǎn)化變鄰域搜索 (reduced variable neighborhood search, RVNS)兩種局部搜索算法[22]，給出兩種改進(jìn)的變鄰域搜索算法。

VND 是完整地搜索整個(gè)鄰域結(jié)構(gòu)，以尋找鄰域中最優(yōu)的局部搜索算法。本文的鄰域搜索順序?yàn)榉崔D(zhuǎn)圈、反轉(zhuǎn)路和子圖重定向，具體的算法流程如下。首先設(shè)置循環(huán)數(shù)k=1和 初始解，基于k值對(duì)應(yīng)的鄰域動(dòng)作產(chǎn)生一組鄰域解。接著選擇其中最優(yōu)的鄰域解并與已知的最優(yōu)解比較；若能改善當(dāng)前的最優(yōu)解，則更新最優(yōu)解并設(shè)置k=1； 否則，設(shè)置k=k+1。最后根據(jù)k值確定下一步。R VNS搜索鄰域結(jié)構(gòu)中一個(gè)解，以近似表示整個(gè)鄰域結(jié)構(gòu)的最優(yōu)解。首先設(shè)置循環(huán)數(shù)k=1和 初始解，基于k值對(duì)應(yīng)的鄰域動(dòng)作產(chǎn)生1個(gè)鄰域解。接著與已知的最優(yōu)解比較，若能改善當(dāng)前的最優(yōu)解，則更新最優(yōu)解并設(shè)置k=1；否則，設(shè)置k=k+1。 最后根據(jù)k值確定下一步。

改進(jìn)變鄰域搜索算法中擾動(dòng)方法采用2.3節(jié)的鄰域動(dòng)作設(shè)計(jì)，其流程如圖8所示。其中，ε表示初始解，第k個(gè)鄰域動(dòng)作f(ε)產(chǎn) 生一個(gè)鄰域結(jié)構(gòu)用S表示；函 數(shù) OFV(ε)為 解 ε的 目 標(biāo) 函 數(shù) 值。由 VND和RVNS的 局部搜索方式可知，V ND 相 比 R VNS會(huì)作更詳細(xì)的局部搜索，所有采用V ND會(huì)耗費(fèi)更多的計(jì)算時(shí)間，但其搜索結(jié)果會(huì)優(yōu)于 RVNS。若考慮求解質(zhì)量，則采用基于V ND的變鄰域算法。若考慮求解時(shí)間，則采用R VNS的變鄰域算法。

圖8 改進(jìn)的變鄰搜索算法及2種局部搜索算法Figure 8 Improved variable neighborhood search algorithm and two local search algorithms

3 計(jì)算實(shí)例與分析

為驗(yàn)證基于有向圖連通性理論所提出的改進(jìn)變鄰域算法的有效性，構(gòu)建采用 V ND為局部搜索的變鄰域算法和采用 RVNS為局部搜索的變鄰域搜索算法，分別用 V_VND 、V_RVNS表示。針對(duì)基準(zhǔn)案例、隨機(jī)案例進(jìn)行計(jì)算，并與 G urobi和多種元啟發(fā)算法進(jìn)行比較。變鄰域算法中的鄰域搜索順序?yàn)榉崔D(zhuǎn)圈、反轉(zhuǎn)路、子圖重定向。本文程序采用Python編寫(xiě)，運(yùn)行環(huán)境為Windows 10系統(tǒng)，Intel(R) E3-1231 v3 3.4 GHz 處理器，8 G內(nèi)存。

3.1 基準(zhǔn)案例計(jì)算與分析

基準(zhǔn)案例中包含4個(gè)中小規(guī)模和2個(gè)大規(guī)模案例。案例所包含路徑條數(shù)分別為20、33、42、60、67、89，采用符號(hào)Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅵ表示，詳細(xì)的導(dǎo)向路徑網(wǎng)絡(luò)信息和物流矩陣見(jiàn)文獻(xiàn)[9]和[12]。為保證算法所求解的可靠性，對(duì)每個(gè)案例作10次獨(dú)立實(shí)驗(yàn)，以10次實(shí)驗(yàn)結(jié)果計(jì)算最優(yōu)運(yùn)輸距離( Opt) 、平均運(yùn)輸距離(A vg)、CPU時(shí)間(t)、平均運(yùn)輸距離與已知最好運(yùn)輸距離(K _Opt)的相對(duì)差距。求解結(jié)果如表1所示，表中加粗部分為案例最優(yōu)解，Δ表示與已知最優(yōu)解的相對(duì)差距。

表1 V _VND、V _RVNS變鄰域算法求解結(jié)果Table 1 Overall performances of the V _VND and V _RVNS algorithms

由表1可知，對(duì)于大規(guī)模案例Ⅴ，V _VND 、V_RVNS算法能求得更好的設(shè)計(jì)方案。該方案下AGV的運(yùn)輸距離為17 732 m，其中運(yùn)載距離為13 187 m，空載距離為4 545 m，相對(duì)已知的最好設(shè)計(jì)方案，減少了5.71%。導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)方案如圖9所示。對(duì)于大規(guī)模案例Ⅵ，V _VND 和V _RVNS算法也求得更好的設(shè)計(jì)方案。該方案下AGV的運(yùn)輸距離為162 900 m，其中運(yùn)載距離為118 150 m，空載距離為44 750 m，相對(duì)已知的最好設(shè)計(jì)方案，減少了3.37%，導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)方案如圖10所示。

圖9 案例Ⅴ對(duì)應(yīng)最優(yōu)AGV導(dǎo)向路徑網(wǎng)絡(luò)方案Figure 9 The optimal orientation of flow path network of Case V

圖10 案例Ⅵ對(duì)應(yīng)最優(yōu)AGV導(dǎo)向路徑網(wǎng)絡(luò)方案Figure 10 The optimal orientation of flow path network of Case VI

對(duì)于中小規(guī)模案例，V_VND 和 V _RVNS算法求得已知最優(yōu)運(yùn)輸距離設(shè)計(jì)方案。對(duì)于大規(guī)模案例Ⅴ和Ⅵ，兩個(gè)算法求得比已知最好設(shè)計(jì)方案更優(yōu)的設(shè)計(jì)方案，分別節(jié)省了5%和3%左右的運(yùn)輸距離。對(duì)于中小規(guī)模案例，兩個(gè)算法的求解時(shí)間都在20 s以內(nèi)；即使對(duì)于大規(guī)模案例Ⅵ，兩個(gè)算法的求解時(shí)間最大也僅為120 s左 右。 V_VND相 比 V_RVNS算法，消耗更多的計(jì)算時(shí)間，但兩者都能求得最優(yōu)設(shè)計(jì)方案，且Δ非常小。顯然，從節(jié)約求解時(shí)間角度考慮，V_RVNS算法更適合求解AGV導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。

3.2 與其他元啟發(fā)式算法對(duì)比分析

為進(jìn)一步分析本文所提兩個(gè)算法，與文獻(xiàn)中的其他元啟發(fā)式算法(都采用文獻(xiàn)[8]中鄰域動(dòng)作產(chǎn)生鄰域解作局部搜索)比較，各元啟發(fā)式算法描述如表2所示。采用前文所用的Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅵ 5個(gè)基準(zhǔn)案例，從平均運(yùn)輸距離、平均運(yùn)輸距離與已知最優(yōu)運(yùn)輸距離的差距及平均求解時(shí)間3個(gè)方面進(jìn)行對(duì)比，對(duì)比結(jié)果如表3 ～ 5所示。對(duì)于2個(gè)大規(guī)模案例Ⅴ和Ⅵ，考慮 Gurobi無(wú)法在有效時(shí)間內(nèi)求得最優(yōu)運(yùn)輸距離，只能將本文算法和其他元啟發(fā)式算法與已知的最好運(yùn)輸距離比較。

表2 比較的元啟發(fā)式算法描述Table 2 Comparison of meta-heuristic algorithms in literature

表3 各元啟發(fā)式算法的平均運(yùn)輸距離對(duì)比結(jié)果Table 3 Compared results of the average transportation distances for meta-heuristic algorithm m

由表3和表4中可知，對(duì)于案例Ⅱ，除了文獻(xiàn)[11]的P VNS算法外，其他元啟發(fā)式算法所求平均運(yùn)輸距離與 Gurobi一致。對(duì)于案例Ⅲ，只有本文的兩個(gè)算法與 G urobi的求解結(jié)果一致。對(duì)于案例Ⅳ，文獻(xiàn)[9]的HACO算法和本文的兩個(gè)算法，與 Gurobi的求解結(jié)果一致。對(duì)于2個(gè)大規(guī)模案例Ⅴ和Ⅵ，其他啟發(fā)式算法所求平均運(yùn)輸距離都大于已知最好運(yùn)輸距離，V_VND 和 V_RVNS算法所求平均運(yùn)輸距離小于已知最好運(yùn)輸距離。從求解時(shí)間方面而言，由表5可知，對(duì)于案例Ⅳ，G urobi的求解時(shí)間高達(dá)18 657.8 s，所以采用 Gurobi無(wú)法在有效時(shí)間內(nèi)求解大規(guī)模導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。雖然本文兩個(gè)算法和其他元啟發(fā)式算法所搭載的實(shí)驗(yàn)平臺(tái)不一致，無(wú)法比較各算法間求解時(shí)間的優(yōu)劣性，但從結(jié)果來(lái)看，本文兩個(gè)算法的求解所消耗的時(shí)間還是遠(yuǎn)少于其他元啟發(fā)式算法。即使對(duì)于大規(guī)模案例Ⅵ，求解時(shí)間也只僅為120 s左右，優(yōu)于其他元啟發(fā)式算法。總之，就以上實(shí)驗(yàn)結(jié)果而言，本文的兩個(gè)算法都優(yōu)于文獻(xiàn)中的其他元啟發(fā)式算法。

表4 各啟發(fā)式算法的平均運(yùn)輸距離與已知最好運(yùn)輸?shù)膶?duì)比結(jié)果Table 4 Comparison of each meta-heuristic algorithm with optimal average transportation distance %

表5 各元啟發(fā)式算法的平均求解時(shí)間對(duì)比結(jié)果Table 5 Compared results of each meta-heuristic algorithm in the average solution time s

3.3 隨機(jī)案例實(shí)驗(yàn)分析

為進(jìn)一步驗(yàn)證V _VND 和V _RVNS算 法求解的有效性，基于前文6個(gè)基準(zhǔn)案例，對(duì)每一個(gè)基準(zhǔn)案例，生成5個(gè)隨機(jī)案例，并按照文獻(xiàn)[13]中的方法隨機(jī)生成每一個(gè)案例下的物流矩陣。分別采用G urobi、V_RVNS和 V_VND對(duì)每個(gè)案例作10次獨(dú)立實(shí)驗(yàn)求解?？紤]Gurobi只能求解小規(guī)模案例，針對(duì)案例Ⅴ和Ⅵ所包括的隨機(jī)案例，設(shè)置 Gurobi求 解時(shí)間為1 800 s。平均運(yùn)輸距離(Avg)、CPU求解時(shí)間(t)、平均運(yùn)輸距離與最優(yōu)運(yùn)輸距離的相對(duì)差距( ?)對(duì)比結(jié)果如表6所示。

從表6可看出，對(duì)于Ⅰ、Ⅱ、Ⅲ、Ⅳ案例，V_VND和 V_RVNS算 法所得平均運(yùn)輸距離與 Gurobi求解一致，每次都能求得最優(yōu)運(yùn)輸距離。對(duì)于Ⅴ、Ⅵ案例，兩個(gè)算法所得平均運(yùn)輸距離遠(yuǎn)優(yōu)于 Gurobi，且求解時(shí)間遠(yuǎn)小于 Gurobi的 求解時(shí)間。相比 V_VND算法，V_RVNS算法求解時(shí)間更短，而且求解質(zhì)量與V_VND算法相差很小。以上的隨機(jī)實(shí)驗(yàn)表明，本文兩個(gè)算法在求解AGV導(dǎo)向路徑網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題方面具有較高的求解質(zhì)量和效率。

表6 隨機(jī)案例下不同算法的求解結(jié)果Table 6 The result for each method in the randomly generated cases

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

本文針對(duì)AGV單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題，基于有向圖強(qiáng)連通性中反轉(zhuǎn)路、反轉(zhuǎn)圈保持強(qiáng)連通性，提出3種鄰域動(dòng)作，證明了3種鄰域動(dòng)作所產(chǎn)生的鄰域解的可行性，并給出確定鄰域結(jié)構(gòu)的具體方法；在此基礎(chǔ)提出 V _VND 和 V _RVNS 兩種變鄰域搜索算法，求解6個(gè)基準(zhǔn)案例。對(duì)于4個(gè)中小規(guī)模案例，V_VND 和 V _RVNS算法均求得案例的最優(yōu)運(yùn)輸距離。對(duì)于2個(gè)大規(guī)模案例，V _VND和 V _RVNS算法求得新的設(shè)計(jì)方案，分別有效減少5%和3%左右的運(yùn)輸距離。與文獻(xiàn)中其他算法相比，對(duì)于大規(guī)模案例，V_VND 和 V _RVNS算法的求解質(zhì)量遠(yuǎn)優(yōu)于文獻(xiàn)中其他元啟發(fā)式算法，且 V _VND和 V_RVNS算法具有更少的求解時(shí)間。 R VNS的局部 搜索空間遠(yuǎn)小于VND，但 V_RVNS的 求解質(zhì)量?jī)H略優(yōu)于 V_VND，所以對(duì)于大規(guī)模案例，采用 V _RVNS算法具有更少的計(jì)算時(shí)間。以上均說(shuō)明本文所提的兩個(gè)算法可以有效解決AGV單向?qū)蚵窂骄W(wǎng)絡(luò)設(shè)計(jì)問(wèn)題。

未來(lái)將在此基礎(chǔ)上，考慮AGV間的阻塞現(xiàn)象，設(shè)計(jì)一種具有柔性的AGV導(dǎo)向路徑網(wǎng)絡(luò)，并將其耦合到車間設(shè)施規(guī)劃中，提出一種設(shè)施布局和導(dǎo)向路徑網(wǎng)絡(luò)集成規(guī)劃的方法。