基于SEGA算法的區(qū)段式車(chē)間系統(tǒng)協(xié)同布局優(yōu)化

張艷偉，程沙沙，張新艷

(1.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063；2.同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

車(chē)間設(shè)備布局和物料搬運(yùn)路徑規(guī)劃不合理是導(dǎo)致制造系統(tǒng)物流成本居高不下的重要原因。牛占文等[1]針對(duì)現(xiàn)有布局下車(chē)間生產(chǎn)效率低等問(wèn)題，提出了多目標(biāo)車(chē)間布局改善方法。KUMAR等[2]采用仿真技術(shù)對(duì)單回路、區(qū)域式及區(qū)域式環(huán)形3種AGV系統(tǒng)進(jìn)行分析，發(fā)現(xiàn)不同的AGV路徑布置方式各有所長(zhǎng)。近幾年，設(shè)備布局與AGV路徑集成優(yōu)化方法逐步引起人們的關(guān)注。葛華輝等[3]針對(duì)SFT系統(tǒng)建立了設(shè)備布局與AGV路徑規(guī)劃集成優(yōu)化模型，但未考慮需求不確定性和空載成本。REZAPOUR等[4]針對(duì)區(qū)域式AGV系統(tǒng)，提出一種將設(shè)備分配、區(qū)域內(nèi)設(shè)備布局、車(chē)間區(qū)域布局和轉(zhuǎn)運(yùn)中心設(shè)計(jì)進(jìn)行串聯(lián)求解的方法。SEDEHI等[5]綜合考慮分塊布局、AGV單回路物流路徑和裝卸點(diǎn)位置，對(duì)設(shè)備布局和物料搬運(yùn)系統(tǒng)進(jìn)行并行設(shè)計(jì)。王闖等[6]綜合考慮車(chē)間實(shí)際搬運(yùn)路徑和物流效率，研究智能車(chē)間布局規(guī)劃的建模與求解方法。李?lèi)?ài)平等[7]建立了魯棒性布局與物料搬運(yùn)系統(tǒng)協(xié)同優(yōu)化模型。劉莊成[8]將區(qū)域式AGV系統(tǒng)的設(shè)備布局與路徑規(guī)劃進(jìn)行集成設(shè)計(jì)，提出一種協(xié)同求解框架。

空載運(yùn)行成本是車(chē)間完成物料搬運(yùn)任務(wù)過(guò)程中產(chǎn)生的額外成本，在計(jì)算物流成本時(shí)，鮮少有研究將其考慮在內(nèi)。李玉蘭等[9]以重載和空載搬運(yùn)成本之和最小為目標(biāo)，采用曼哈頓距離計(jì)算公式建立數(shù)學(xué)模型，但忽略了車(chē)輛行駛過(guò)程中需繞過(guò)障礙物和設(shè)備等情況。董舒豪等[10]建立了以物料搬運(yùn)成本、車(chē)輛空載運(yùn)行成本及作業(yè)單元相互關(guān)系為優(yōu)化目標(biāo)的多行設(shè)備布局模型，但未考慮設(shè)備布局對(duì)搬運(yùn)車(chē)輛路徑規(guī)劃的影響。針對(duì)空載成本的研究，目前均以多行線(xiàn)性布局車(chē)間系統(tǒng)為對(duì)象，未考慮區(qū)段劃分和中轉(zhuǎn)緩存區(qū)布置等問(wèn)題，模型中的決策變量較少。車(chē)間布局規(guī)劃是企業(yè)的一個(gè)戰(zhàn)略性決策過(guò)程，在布局時(shí)考慮需求不確定性有助于實(shí)現(xiàn)可持續(xù)發(fā)展[11]。為了解決不確定性需求下的設(shè)備布局難題，部分研究假設(shè)加工產(chǎn)品種類(lèi)固定，引入隨機(jī)變量[11-13]或采用模糊理論[14-16]等方式描述產(chǎn)品需求水平的不確定性，但均存在相關(guān)參數(shù)難以確定等問(wèn)題。

綜上所述，目前已有學(xué)者將車(chē)間設(shè)備布局與AGV路徑規(guī)劃進(jìn)行綜合考慮，大部分研究將二者進(jìn)行串聯(lián)處理，忽略了設(shè)備布局與搬運(yùn)路徑規(guī)劃的耦合性。為了避免曼哈頓距離和歐氏距離公式導(dǎo)致的計(jì)算誤差，分析區(qū)段式AGV系統(tǒng)特征、物料搬運(yùn)工藝和車(chē)間物流動(dòng)線(xiàn)，研究車(chē)輛重載和空載搬運(yùn)距離的實(shí)際計(jì)算方法。在考慮需求不確定性和車(chē)間設(shè)備布局與AGV路徑規(guī)劃耦合性的基礎(chǔ)上，以AGV重載和空載搬運(yùn)成本最小為優(yōu)化目標(biāo)，建立SFT系統(tǒng)設(shè)備布局與AGV路徑協(xié)同優(yōu)化模型，提出一種雙鏈染色體編碼的增強(qiáng)精英保留遺傳算法，通過(guò)實(shí)例分析與求解，驗(yàn)證模型和算法的有效性。

1 問(wèn)題描述與假設(shè)

區(qū)段式AGV系統(tǒng)通過(guò)“分區(qū)控制”避免了復(fù)雜的AGV調(diào)度和路徑?jīng)_突問(wèn)題，以簡(jiǎn)單、易控、柔性好的特點(diǎn)逐漸引起學(xué)者關(guān)注。其設(shè)計(jì)難點(diǎn)在于如何合理地進(jìn)行區(qū)段劃分和設(shè)備布局，即在滿(mǎn)足AGV最大負(fù)載能力和各區(qū)段負(fù)載均衡的前提下，將車(chē)間設(shè)備分配至車(chē)間內(nèi)不同區(qū)段，同時(shí)基于設(shè)備之間的物流量對(duì)區(qū)段內(nèi)設(shè)備進(jìn)行布局規(guī)劃。

1.1 問(wèn)題描述

車(chē)間采用SFT系統(tǒng)布局形式，AGV軌道被劃分成幾個(gè)互不交叉的區(qū)段，將一定數(shù)量的設(shè)備組和中轉(zhuǎn)緩存區(qū)分區(qū)段布置在固定尺寸的車(chē)間，每個(gè)區(qū)段由一臺(tái)AGV負(fù)責(zé)物料搬運(yùn)，AGV可在本區(qū)段內(nèi)雙向行駛，緩存區(qū)為區(qū)段間的物料中轉(zhuǎn)設(shè)施，優(yōu)化目標(biāo)為所有AGV重載和空載總搬運(yùn)成本最小。已知產(chǎn)品種類(lèi)、每種產(chǎn)品被加工概率及加工順序。r∈{1,2,…,R}近似表示產(chǎn)品低、中、高的需求水平，其中R為產(chǎn)品最高需求水平。同一類(lèi)別的設(shè)備成組放置形成設(shè)備組，2個(gè)及多個(gè)設(shè)備組劃分為一個(gè)區(qū)段，如圖1所示。每個(gè)設(shè)備組在區(qū)段內(nèi)主通道一側(cè)中間設(shè)置1個(gè)裝卸點(diǎn)，中轉(zhuǎn)緩存區(qū)根據(jù)需求在上、下邊界中點(diǎn)設(shè)置裝卸點(diǎn)。在任意時(shí)刻，AGV執(zhí)行完某個(gè)任務(wù)后，從當(dāng)前任務(wù)的終點(diǎn)行駛至新任務(wù)的起點(diǎn)，期間產(chǎn)生空載行駛距離。

圖1 區(qū)段式AGV系統(tǒng)示意圖

平面直角坐標(biāo)系原點(diǎn)位于矩形車(chē)間的左上角，L和W分別為車(chē)間總長(zhǎng)度和總寬度；Mi表示第i個(gè)設(shè)備組，i∈{1,2,…,n}；Sz表示第z個(gè)中轉(zhuǎn)緩存區(qū)，z∈{1,2,…,v-1}；qz表示第z個(gè)區(qū)段，z∈{1,2,…,v}。當(dāng)有一批物料需要跨區(qū)段搬運(yùn)時(shí)，每個(gè)區(qū)段的 AGV只負(fù)責(zé)本區(qū)段的搬運(yùn)任務(wù)。如接到M2→M6的搬運(yùn)任務(wù)后，區(qū)段q1中的AGV將物料從設(shè)備組M2搬運(yùn)到中轉(zhuǎn)緩存區(qū)S1，再通過(guò)區(qū)段q2中的AGV將物料從中轉(zhuǎn)緩存區(qū)S1搬運(yùn)到設(shè)備組M6。在執(zhí)行當(dāng)前任務(wù)的過(guò)程中，若AGV接到新的搬運(yùn)任務(wù)M5→M8，則區(qū)段q2中的AGV先將物料從中轉(zhuǎn)緩存區(qū)S1搬運(yùn)到設(shè)備組M6處，再?gòu)脑O(shè)備組M6行駛至設(shè)備組M5，即可執(zhí)行M5→M8的搬運(yùn)任務(wù)。其中，從設(shè)備組M6至設(shè)備組M5的距離稱(chēng)為空載搬運(yùn)距離。

1.2 相關(guān)假設(shè)

實(shí)際生產(chǎn)中，功能不同的設(shè)備組所占區(qū)域可能存在邊緣不規(guī)則的情況，在建立數(shù)學(xué)模型時(shí)，需對(duì)一些車(chē)間布局參數(shù)進(jìn)行標(biāo)準(zhǔn)化處理，作出如下假設(shè)：

(1)車(chē)間產(chǎn)品、工藝過(guò)程已知，設(shè)備配備滿(mǎn)足生產(chǎn)工藝要求。

(2)設(shè)備組所占區(qū)域?yàn)樾螤钜?guī)則、尺寸已知的矩形；中轉(zhuǎn)緩存區(qū)所占區(qū)域?yàn)樾螤钜?guī)則、尺寸已知、容量不限的正方形。其中，所有設(shè)備組和中轉(zhuǎn)緩存區(qū)的裝卸點(diǎn)同時(shí)具有上料和下料功能。

(3)AGV為單一負(fù)載，沿水平和垂直方向移動(dòng)，空載與重載單位距離運(yùn)行成本均為1。

2 數(shù)學(xué)模型

區(qū)段式車(chē)間系統(tǒng)作為一種柔性較好的布局形式，其規(guī)劃過(guò)程需綜合考慮AGV搬運(yùn)路徑規(guī)劃、中轉(zhuǎn)緩存區(qū)布置、設(shè)備布局等問(wèn)題。現(xiàn)有研究中，大多采用設(shè)備組幾何中心之間的歐氏距離或曼哈頓距離作為距離的計(jì)算方法，忽略了AGV在物料搬運(yùn)途中需避開(kāi)設(shè)備組或中轉(zhuǎn)緩存區(qū)等障礙物，且車(chē)輛進(jìn)行物料裝卸的位置往往不在設(shè)備組幾何中心處，造成距離成本的計(jì)算會(huì)有較大誤差。將設(shè)備組之間的距離定義為對(duì)應(yīng)裝卸點(diǎn)之間的實(shí)際距離，使距離成本更接近實(shí)際車(chē)間情況；考慮到車(chē)間物流量隨需求而變化，采用離散概率分布近似表示產(chǎn)品需求的不確定性；在綜合考慮車(chē)間尺寸、設(shè)備組尺寸、中轉(zhuǎn)緩存區(qū)尺寸、最小安全距離等幾何約束的條件下，建立車(chē)間設(shè)備布局和AGV物料搬運(yùn)路徑規(guī)劃協(xié)同優(yōu)化模型。

2.1 優(yōu)化目標(biāo)

目標(biāo)為計(jì)劃期內(nèi)總物料搬運(yùn)成本最小，包含AGV重載和空載搬運(yùn)成本。

(1)

(2)

2.2 距離計(jì)算公式

2.2.1 基本距離計(jì)算公式

設(shè)備組之間的距離定義為對(duì)應(yīng)裝卸點(diǎn)之間的實(shí)際距離。假設(shè)設(shè)備組Mi屬于區(qū)段qz，則設(shè)備組Mi與Mj之間距離為：

(3)

式中：(xi,yi)和(xj,yj)分別表示設(shè)備組Mi和Mj的坐標(biāo)；DiSz為設(shè)備組Mi與中轉(zhuǎn)緩存區(qū)Sz之間的距離；DSz+m-1j為設(shè)備組Mj與中轉(zhuǎn)緩存區(qū)Sz+m-1之間的距離；DSlSl+1為中轉(zhuǎn)緩存區(qū)Sl與Sl+1之間的距離;跨m個(gè)區(qū)段，即設(shè)備組Mi與Mj之間有m個(gè)中轉(zhuǎn)緩存區(qū)。

2.2.2 空載距離計(jì)算公式

當(dāng)AGV即將執(zhí)行下一項(xiàng)搬運(yùn)任務(wù)時(shí)，其所處位置具有不確定性，即AGV可能處于該區(qū)段任一設(shè)備組或鄰近中轉(zhuǎn)緩存區(qū)的裝卸點(diǎn)處。AGV處于區(qū)段qz中任一設(shè)備組Mo處的概率為：

(4)

由式(4)可知，PMo越大，表示其他設(shè)備組到Mo的物流量越大，則AGV在接到新任務(wù)時(shí)處于設(shè)備組Mo處的概率越大。由此可得，任意時(shí)刻為完成下一搬運(yùn)任務(wù)(Mi→Mj)，AGV所需空載搬運(yùn)距離的計(jì)算公式如式(5)和式(6)所示。

(1)若設(shè)備組Mi與Mj之間不跨區(qū)段，則：

(5)

(2)若設(shè)備組Mi與Mj之間跨m個(gè)區(qū)段，則：

(6)

2.3 約束條件

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

3 增強(qiáng)精英保留的遺傳算法

車(chē)間設(shè)備布局與AGV路徑協(xié)同優(yōu)化是一個(gè)復(fù)雜的離散優(yōu)化問(wèn)題，同時(shí)受設(shè)備組之間相對(duì)位置、AGV數(shù)量、中轉(zhuǎn)緩存區(qū)位置、車(chē)間幾何約束等影響，算法求解關(guān)鍵在于設(shè)備組之間的距離。為求解該問(wèn)題，提出一種增強(qiáng)精英保留的遺傳算法(strengthen elitist genetic algorithm，SEGA)。采用雙鏈染色體編碼表示車(chē)間綜合布局方案，設(shè)備組布局的染色體采用排列編碼方式，0-1整數(shù)編碼表示中轉(zhuǎn)緩存區(qū)的染色體，有效提高了進(jìn)化過(guò)程解的質(zhì)量；對(duì)適應(yīng)度函數(shù)進(jìn)行線(xiàn)性尺度變換，增加了種群的多樣性，提高了算法的全局搜索能力；結(jié)合精英錦標(biāo)賽選擇算子和父子合并競(jìng)爭(zhēng)選擇等進(jìn)化策略，提高了算法的進(jìn)化效率和全局收斂性。

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

為了保證最終解的質(zhì)量和進(jìn)化過(guò)程的搜索效率，對(duì)目標(biāo)函數(shù)進(jìn)行線(xiàn)性尺度變換, 得到適應(yīng)度函數(shù)，如式(18)所示。變換后，少數(shù)適應(yīng)度高的個(gè)體，其適應(yīng)度等比例縮?。贿m應(yīng)度較差的個(gè)體，其適應(yīng)度等比例擴(kuò)大。在種群進(jìn)化過(guò)程中，一部分超常個(gè)體的競(jìng)爭(zhēng)力可能遠(yuǎn)遠(yuǎn)超過(guò)其他個(gè)體，而部分適應(yīng)度較差的個(gè)體可能攜帶一些優(yōu)良基因。因此，適當(dāng)保留一些適應(yīng)度較差的個(gè)體，同時(shí)降低適應(yīng)度較高個(gè)體被選擇的概率，有利于種群跳出局部最優(yōu)解，增加種群的多樣性，提高算法的全局搜索能力。

f=αC+Cmax+ξ

(18)

式中：Cmax為目標(biāo)函數(shù)最大值；α=-1，保證適應(yīng)度增大方向與總物料搬運(yùn)成本減小方向一致；ξ是一個(gè)較小的正數(shù)，保證種群中最差的個(gè)體也可獲得繁衍機(jī)會(huì)。

3.2 染色體編碼與解碼

3.2.1 編碼方式

設(shè)備布局與AGV路徑協(xié)同優(yōu)化模型相當(dāng)于資源分配問(wèn)題，即將有限的車(chē)間資源分配給數(shù)量有限的設(shè)備組，由于不同設(shè)備組具有不同尺寸和功能特性，采用排列編碼方式可表示不同設(shè)備組位置；不同中轉(zhuǎn)緩存區(qū)的尺寸和功能相同，排列編碼方式無(wú)法有效表示不同中轉(zhuǎn)緩存區(qū)在車(chē)間的空間位置。因此，單一的染色體編碼方式難以同時(shí)表達(dá)設(shè)備組和中轉(zhuǎn)緩存區(qū)位置。將表達(dá)不同元素的基因在同一條染色體上進(jìn)行分段編碼可以滿(mǎn)足模型求解要求，但經(jīng)過(guò)交叉、變異等進(jìn)化操作后容易出現(xiàn)非可行解。

設(shè)備組和中轉(zhuǎn)緩存區(qū)分別采用不同的編碼方式，可大大降低編碼和進(jìn)化難度。表示設(shè)備組布局的染色體采用排列編碼方式，序號(hào)0,1,2,…,n-1表示設(shè)備組的編號(hào)，染色體的長(zhǎng)度為n；0-1整數(shù)編碼表示中轉(zhuǎn)緩存區(qū)的染色體，1表示該位置對(duì)應(yīng)設(shè)備組后面有中轉(zhuǎn)緩存區(qū)，0表示其對(duì)應(yīng)設(shè)備組后面沒(méi)有中轉(zhuǎn)緩存區(qū)。由于每個(gè)區(qū)段設(shè)備組數(shù)量不少于2，因此排布在開(kāi)頭和末尾兩個(gè)位置的設(shè)備組后不可能設(shè)置中轉(zhuǎn)緩存區(qū)，對(duì)應(yīng)數(shù)字必須為0。在算法進(jìn)化過(guò)程中，染色體通過(guò)交叉、變異等操作后，種群個(gè)體的染色體在這幾個(gè)位置容易出現(xiàn)非0元素，引起后代種群中非可行解占比增加。為了降低非可行解的出現(xiàn)頻率，提高進(jìn)化過(guò)程中解的質(zhì)量并加快種群的進(jìn)化效率，縮減中轉(zhuǎn)緩存區(qū)的染色體長(zhǎng)度至n-3。染色體編碼示意圖如圖2所示。

圖2 染色體編碼示意圖

3.2.2 解碼方式

在求設(shè)備組和中轉(zhuǎn)緩存區(qū)中心位置坐標(biāo)前，首先對(duì)染色體進(jìn)行初次解碼，采用一個(gè)不同于所有設(shè)備組序號(hào)的整數(shù)表示中轉(zhuǎn)緩存區(qū)，得到一條包含設(shè)備組和中轉(zhuǎn)緩存區(qū)綜合位置信息的序列表。將圖2中的染色體進(jìn)行初次解碼得到：[0,5,7,10,9,4,10,1,8,2,10,3,6]，其中序號(hào)10表示中轉(zhuǎn)緩存區(qū)。將初次解碼得到的序列表按從左至右，從上往下依次排列，當(dāng)車(chē)間寬度不足時(shí)采取自動(dòng)換行策略，最終解碼求得每個(gè)設(shè)備組和中轉(zhuǎn)緩存區(qū)的中心坐標(biāo)值。若已知設(shè)備組Mi的中心坐標(biāo)為(xi,yi)，則與設(shè)備組Mi位于同一行的下一個(gè)設(shè)備組Mo的中心位置坐標(biāo)為：

(19)

3.3 選擇操作

算法進(jìn)化過(guò)程包含2個(gè)階段的選擇。第1階段是選擇參與進(jìn)化過(guò)程的種群個(gè)體，該階段采用精英錦標(biāo)賽選擇算子，確保最優(yōu)個(gè)體一定會(huì)被選中參加錦標(biāo)賽，從而保留了精英個(gè)體所攜帶的優(yōu)良基因。第2階段為“環(huán)境選擇”過(guò)程，經(jīng)過(guò)交叉、變異等操作，從進(jìn)化后的種群中選擇一定數(shù)量的個(gè)體形成新一代種群。在這個(gè)階段采用父子兩代合并的競(jìng)爭(zhēng)選擇方式，即將進(jìn)化后的個(gè)體與父代個(gè)體合并形成規(guī)模為2N的種群，再按照適應(yīng)度值排序,從中選擇前N個(gè)個(gè)體保留到下一代。

3.4 交叉操作

針對(duì)設(shè)備布局編碼的染色體，采用部分匹配交叉算子。針對(duì)中轉(zhuǎn)緩存區(qū)編碼的染色體，采用兩點(diǎn)交叉算子。對(duì)于兩條設(shè)備布局編碼的父代染色體，先隨機(jī)產(chǎn)生兩個(gè)隨機(jī)數(shù)k1和k2作為截取染色體片段的起始和終止位置，0≤k1≤k2≤n；將截取到的兩個(gè)片段進(jìn)行位置互換；若交叉后出現(xiàn)重復(fù)編碼，則根據(jù)映射關(guān)系進(jìn)行染色體修復(fù)，得到最終的兩條子代染色體。對(duì)于兩條父代染色體，取k1=3，k2=6，其交叉操作如圖3所示。

圖3 染色體交叉操作示意圖

3.5 變異操作

針對(duì)設(shè)備布局編碼的染色體，采用染色體片段逆轉(zhuǎn)變異算子，為了防止進(jìn)化過(guò)程陷入局部最優(yōu)解，往往選取較大的變異概率。針對(duì)中轉(zhuǎn)緩存區(qū)編碼的染色體，采用遺傳算法育種變異算子。

4 實(shí)例對(duì)比分析

為了驗(yàn)證所提出的協(xié)同優(yōu)化模型和算法的有效性，分別從算法和模型兩個(gè)方面進(jìn)行對(duì)比分析。首先，隨機(jī)生成一組算例，采用SEGA算法和標(biāo)準(zhǔn)遺傳算法(standard genetic algorithm，SGA)進(jìn)行求解，通過(guò)對(duì)比分析驗(yàn)證SEGA算法的有效性；其次，采用SEGA算法對(duì)文獻(xiàn)[3]中的算例進(jìn)行求解，將求得的最小搬運(yùn)成本與文獻(xiàn)[3]中最優(yōu)布局的物料搬運(yùn)成本進(jìn)行對(duì)比，進(jìn)一步檢驗(yàn)?zāi)Ｐ秃退惴ǖ暮侠硇?。算法均采用Python語(yǔ)言編寫(xiě)，并在配置為 Intel Core i5 8th Gen，2.30 GHz CPU，8.0GB內(nèi)存的電腦上運(yùn)行。

4.1 算法對(duì)比

4.1.1 實(shí)例描述

車(chē)間長(zhǎng)為80 m，寬為60 m，通道寬度為3 m，最小安全距離為2 m。車(chē)間需放置10組設(shè)備和3個(gè)中轉(zhuǎn)緩存區(qū)，AGV處于中轉(zhuǎn)緩存區(qū)的概率PS=0.5。產(chǎn)品需求水平r∈{1,2,3}，分別表示產(chǎn)品低、中、高的需求水平。設(shè)備組尺寸如表1所示，產(chǎn)品需求信息如表2所示。

表1 設(shè)備組尺寸

表2 產(chǎn)品需求信息

4.1.2 算法參數(shù)設(shè)計(jì)與問(wèn)題求解

算法參數(shù)設(shè)置為：隨機(jī)生成初始種群，種群規(guī)模為100，最大迭代次數(shù)為100；對(duì)于表示設(shè)備布局的染色體，交叉概率Pc=0.7，變異概率Pm=0.5；對(duì)于表示中轉(zhuǎn)緩存區(qū)的染色體，交叉概率Pc=0.7，變異概率Pm=1/Dim，其中Dim為決策變量的維度，此時(shí)取值為17。針對(duì)上述算例，分別采用SGA和SEGA算法求解30次并取平均值，結(jié)果如表3所示。由表3可知，兩種算法求解時(shí)間相近，SEGA算法求解得到的總物料搬運(yùn)成本的最差解、最優(yōu)解及平均解均優(yōu)于SGA算法，表明SEGA算法在求解協(xié)同優(yōu)化模型時(shí)具有更強(qiáng)的尋優(yōu)能力。SEGA算法與SGA算法取最優(yōu)解時(shí)的算法收斂圖分別如圖4和圖5所示，可知SEGA算法的全局收斂性較好，SGA算法無(wú)法獲得收斂。

表3 SEGA算法與SGA算法結(jié)果對(duì)比

圖4 SEGA算法收斂圖

圖5 SGA算法收斂圖

SEGA算法求得最優(yōu)解時(shí)，設(shè)備組和中轉(zhuǎn)緩存區(qū)位置坐標(biāo)如表4所示，最優(yōu)方案如圖6所示。綜合分析設(shè)備組之間的相對(duì)位置和物流量大小可知，該最優(yōu)布局方案符合“物流量大的距離近、物流量小的距離遠(yuǎn)”布局原則。

表4 設(shè)備組和中轉(zhuǎn)緩存區(qū)位置坐標(biāo)

圖6 最優(yōu)方案示意圖

4.2 模型對(duì)比

4.2.1 算例數(shù)據(jù)

文獻(xiàn)[3]中的算例數(shù)據(jù)為：車(chē)間長(zhǎng)100 m，寬90 m，通道寬度和最小安全距離均為5 m，車(chē)間需放置8組設(shè)備，設(shè)備組長(zhǎng)和寬均為20 m，不考慮中轉(zhuǎn)緩存區(qū)的尺寸。設(shè)備組之間的物料搬運(yùn)量如表5所示，表中數(shù)據(jù)單位為批次。

表5 設(shè)備組之間的物料搬運(yùn)量

4.2.2 模型結(jié)果對(duì)比

表6 物料搬運(yùn)成本對(duì)比

筆者提出的協(xié)同優(yōu)化模型考慮了AGV空載搬運(yùn)成本，求解出的最優(yōu)解使得車(chē)間總物料搬運(yùn)成本降低了約2%。對(duì)比結(jié)果也表明，在AGV執(zhí)行物料搬運(yùn)任務(wù)的過(guò)程中，產(chǎn)生的空載運(yùn)行成本不可輕易忽略，若搬運(yùn)路線(xiàn)設(shè)置不合理，可能導(dǎo)致較高的車(chē)輛空載成本。

5 結(jié)論

(1)考慮到產(chǎn)品需求不確定性及車(chē)間設(shè)備布局與搬運(yùn)路徑規(guī)劃之間的耦合性，研究不確定需求環(huán)境下區(qū)段式AGV系統(tǒng)路徑規(guī)劃與設(shè)備布局協(xié)同優(yōu)化建模及求解方法，并通過(guò)算例對(duì)比分析驗(yàn)證模型和算法的有效性。

(2)考慮到歐氏距離和曼哈頓距離計(jì)算公式會(huì)造成距離誤差偏大，提出考慮裝卸點(diǎn)位置的車(chē)輛重載和空載搬運(yùn)距離計(jì)算方法，使得模型與實(shí)際生產(chǎn)車(chē)間更相近。

(3)以AGV重載和空載運(yùn)行成本總和最小為目標(biāo)，建立不確定需求下車(chē)間設(shè)備布局與AGV路徑規(guī)劃協(xié)同優(yōu)化模型，實(shí)例分析表明，所提出的優(yōu)化模型能求解出合理的布局方案。

(4)設(shè)計(jì)一種雙鏈染色體編碼的增強(qiáng)精英保留遺傳算法，與SGA算法對(duì)比發(fā)現(xiàn)，提出的 SEGA算法有效提升了遺傳算法的全局尋優(yōu)能力和穩(wěn)定性，并克服了遺傳算法無(wú)法收斂的問(wèn)題。

(5)在后續(xù)研究中，可綜合考慮AGV數(shù)量、物料搬運(yùn)成本、車(chē)間面積利用率等優(yōu)化目標(biāo)，建立多目標(biāo)協(xié)同優(yōu)化模型；為實(shí)現(xiàn)不確定需求環(huán)境下的經(jīng)濟(jì)可持續(xù)發(fā)展，可進(jìn)一步研究動(dòng)態(tài)設(shè)備布局與搬運(yùn)路徑協(xié)同優(yōu)化問(wèn)題的建模與求解方法；設(shè)計(jì)算法時(shí)，可將多種智能算法進(jìn)行融合，改善求解算法的穩(wěn)定性和計(jì)算效率，并結(jié)合仿真技術(shù)驗(yàn)證方案的合理性。