張艷偉，程沙沙，張新艷

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

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

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

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

1 問題描述與假設

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

1.1 問題描述

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

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

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

1.2 相關假設

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

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

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

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

2 數(shù)學模型

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

2.1 優(yōu)化目標

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

(1)

(2)

2.2 距離計算公式

2.2.1 基本距離計算公式

設備組之間的距離定義為對應裝卸點之間的實際距離。假設設備組Mi屬于區(qū)段qz，則設備組Mi與Mj之間距離為：

(3)

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

2.2.2 空載距離計算公式

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

(4)

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

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

(5)

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

(6)

2.3 約束條件

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

3 增強精英保留的遺傳算法

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

3.1 適應度函數(shù)

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

f=αC+Cmax+ξ

(18)

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

3.2 染色體編碼與解碼

3.2.1 編碼方式

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

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

圖2 染色體編碼示意圖

3.2.2 解碼方式

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

(19)

3.3 選擇操作

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

3.4 交叉操作

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

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

3.5 變異操作

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

4 實例對比分析

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

4.1 算法對比

4.1.1 實例描述

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

表1 設備組尺寸

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

4.1.2 算法參數(shù)設計與問題求解

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

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

圖4 SEGA算法收斂圖

圖5 SGA算法收斂圖

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

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

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

4.2 模型對比

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

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

表5 設備組之間的物料搬運量

4.2.2 模型結(jié)果對比

表6 物料搬運成本對比

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

5 結(jié)論

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

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

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

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

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