楊小明，徐子奇，金雯，舒 帆

(1.上海海事大學(xué)離岸工程研究院，上海 201306;2.上海海事大學(xué)物流工程學(xué)院，上海 201306)

0 引言

訂單貨物揀選作業(yè)在物流配送中心總勞動(dòng)量占比高達(dá)60%以上，是物流配送中心諸多作業(yè)中最費(fèi)時(shí)費(fèi)力的環(huán)節(jié)[1]。堆垛機(jī)自動(dòng)化揀選作業(yè)是解決人工揀選效率低下的重要技術(shù)手段。因此，在電商迅猛發(fā)展背景下自動(dòng)化立體倉(cāng)庫(kù)得到了快速發(fā)展。近年，配送速度逐漸成為電商最重要的競(jìng)爭(zhēng)力之一，以盒馬生鮮、京東到家為代表的新興電商甚至要求門店附近3公里范圍內(nèi)，30分鐘送貨上門。在制造企業(yè)中，生產(chǎn)線上零配件的準(zhǔn)時(shí)需求同樣關(guān)鍵，越來(lái)越多的制造企業(yè)開(kāi)始重視零配件的倉(cāng)儲(chǔ)管理和配送效率。

倉(cāng)儲(chǔ)配送中心貨物揀選通常分為摘取式(digital picking)和播種式(digital assorting)，為適應(yīng)高標(biāo)準(zhǔn)的揀選效率和揀選質(zhì)量，避免錯(cuò)漏等問(wèn)題影響配送和生產(chǎn)，“播種+摘取”的復(fù)合式揀選方式得到快速推廣。該方式秉持了播種式進(jìn)行領(lǐng)料需求匯總的方法，將需要的物料逐個(gè)取出并放置于分揀區(qū)內(nèi)，再根據(jù)領(lǐng)料單先后順序進(jìn)行揀選，既發(fā)揮播種式揀選優(yōu)點(diǎn)，避免堆垛機(jī)雜亂反復(fù)行走，又能兼顧領(lǐng)料單先后順序，但這種揀選方式也給堆垛機(jī)揀選作業(yè)序列的決策帶來(lái)了新的困難。

自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)揀選序列優(yōu)化問(wèn)題類似于旅行商問(wèn)題(Traveling Salesman problem，TSP)，都是屬于NP難題[2]。近年來(lái)國(guó)內(nèi)外有眾多學(xué)者對(duì)這類問(wèn)題展開(kāi)了研究，研究的重點(diǎn)主要集中于系統(tǒng)揀選效率的提高。

堆垛機(jī)揀選路徑優(yōu)化問(wèn)題中一個(gè)重要目標(biāo)是設(shè)備揀選行程最短?；诖?，Khojasteh Ghamari[3]針對(duì)多巷道單堆垛機(jī)揀選序列優(yōu)化問(wèn)題提出高效遺傳算法實(shí)現(xiàn)優(yōu)化目標(biāo)。Dornberger[4]在文獻(xiàn)[3]基礎(chǔ)上考慮了更多現(xiàn)實(shí)需求因素，如貨物種類、分布及形狀，并在遺傳算法選擇策略及精英保留機(jī)制中進(jìn)行改進(jìn)，使得所提出的算法更加適應(yīng)實(shí)際需求。Hsu等[5]在貨物存儲(chǔ)規(guī)模和訂單數(shù)量不同的情況下建立了揀選行程最短的優(yōu)化模型，并提出批次揀選序列優(yōu)化遺傳算法有效求解大規(guī)模揀選優(yōu)化問(wèn)題。類似的，眾多學(xué)者以揀選行程最短為目標(biāo)，建立揀選路徑優(yōu)化問(wèn)題數(shù)學(xué)模型，并通過(guò)遺傳算法、蟻群算法等不同啟發(fā)式算法對(duì)問(wèn)題進(jìn)行求解，優(yōu)化過(guò)程主要考慮到多臺(tái)揀選設(shè)備及訂單分批等相關(guān)因素[6-9]。

堆垛機(jī)揀選路徑優(yōu)化問(wèn)題中另一個(gè)重要目標(biāo)是設(shè)備揀選時(shí)間最短。在這方面，Khojasteh等[10]以最小化作業(yè)完成時(shí)間為目標(biāo)建立非線性優(yōu)化模型，并提出啟發(fā)式算法求解非線性優(yōu)化問(wèn)題，實(shí)驗(yàn)算例表明，該算法隨著揀選貨物的數(shù)量增加，目標(biāo)函數(shù)及算法耗時(shí)呈線性增長(zhǎng)。蔡安江等[11]以堆垛機(jī)揀選所需總時(shí)間最短為目標(biāo)，建立了一種基于混合命令序列的堆垛機(jī)調(diào)度模型，并利用遺傳算法對(duì)堆垛機(jī)揀選路徑問(wèn)題進(jìn)行求解。Nenad[12]以揀選時(shí)間最小化為目標(biāo)，通過(guò)時(shí)間窗方法進(jìn)行了相關(guān)揀選路徑優(yōu)化研究。類似研究[13-15]主要以揀選作業(yè)時(shí)間最短為目標(biāo)，建立揀選路徑優(yōu)化問(wèn)題數(shù)學(xué)模型，并通過(guò)模擬退火算法、啟發(fā)式規(guī)則等啟發(fā)式算法對(duì)問(wèn)題進(jìn)行求解。

除此之外，部分學(xué)者將堆垛機(jī)揀選路徑優(yōu)化問(wèn)題中揀選行程和時(shí)間最小化兩個(gè)目標(biāo)進(jìn)行綜合考慮，建立揀選路徑優(yōu)化的多目標(biāo)優(yōu)化模型[16-18]，以實(shí)現(xiàn)堆垛機(jī)揀選路徑問(wèn)題的綜合優(yōu)化。

現(xiàn)有研究中，學(xué)者們對(duì)于堆垛機(jī)揀選路徑優(yōu)化問(wèn)題主要是建立單目標(biāo)優(yōu)化模型來(lái)對(duì)問(wèn)題進(jìn)行求解，其中堆垛機(jī)的揀選總行程以及揀選總時(shí)間是最?？紤]到的兩個(gè)優(yōu)化目標(biāo)。然而，系統(tǒng)運(yùn)行成本以及“播種+摘取”的復(fù)合式揀選方式導(dǎo)致的貨物出庫(kù)緊急程度各不相同等因素并沒(méi)有得到充分考慮。為滿足新形勢(shì)下的物流配送需求，本文考慮了堆垛機(jī)在執(zhí)行揀選任務(wù)時(shí)，同一揀選批次內(nèi)的貨物存在著不同的出貨順序要求，將貨物按照出貨的緊急程度進(jìn)行了分類，并賦予了每一類貨物不同的出貨懲罰值。建立了以運(yùn)行成本、作業(yè)時(shí)間以及出貨總懲罰值3個(gè)目標(biāo)函數(shù)最小化為目標(biāo)的多目標(biāo)優(yōu)化模型。通過(guò)隨機(jī)分配法和貪婪策略生成法相結(jié)合的方式，改進(jìn)帶精英策略的快速非支配排序遺傳算法(fast elitist Nondominant Sequencing Genetic Algorithm，NSGA-II)，實(shí)現(xiàn)堆垛機(jī)揀選序列多目標(biāo)優(yōu)化模型高效求解。為自動(dòng)化立體倉(cāng)庫(kù)管理決策者在揀選成本、效率與服務(wù)3個(gè)維度提供科學(xué)參考依據(jù)，解決快速配送物流需求形勢(shì)下，混合揀選策略中堆垛機(jī)揀選序列優(yōu)化問(wèn)題。

1 堆垛機(jī)的揀選作業(yè)序列優(yōu)化模型

1.1 問(wèn)題描述

本文研究的對(duì)象是固定貨架巷道式堆垛起重機(jī)(如圖1)，其主要組成部分包括機(jī)架(上橫梁、下橫梁)、水平行走機(jī)構(gòu)(立柱)、提升機(jī)構(gòu)(升降機(jī)、載貨臺(tái))、貨叉(位于載貨臺(tái))。在水平行走機(jī)構(gòu)及提升機(jī)構(gòu)合作下實(shí)現(xiàn)立體倉(cāng)庫(kù)貨物存取。

堆垛機(jī)揀選作業(yè)的流程如下:揀選任務(wù)發(fā)布后，堆垛機(jī)立柱從起點(diǎn)出發(fā)沿水平方向行至首個(gè)揀貨位置，載貨臺(tái)與升降機(jī)在立柱軌道上沿垂直方向到達(dá)貨位，載貨臺(tái)到達(dá)后伸出貨叉取出貨物，隨后載貨臺(tái)將貨物放到升降機(jī)的平臺(tái)上，再由升降機(jī)將貨物放置到傳送帶上，最后由傳送帶將貨物轉(zhuǎn)運(yùn)到出貨口處。把貨物放到傳送帶之后，堆垛機(jī)開(kāi)始下一個(gè)揀貨任務(wù)，繼續(xù)重復(fù)上述過(guò)程，直到最后一個(gè)貨物揀選完畢，等待下一批次揀選任務(wù)的發(fā)布。

本文研究的堆垛機(jī)揀選作業(yè)序列優(yōu)化問(wèn)題可描述為:設(shè)一個(gè)揀選周期內(nèi)有n個(gè)分屬于多個(gè)不同優(yōu)先級(jí)別的領(lǐng)料單的揀選任務(wù)，堆垛機(jī)從貨架起點(diǎn)出發(fā)分別到達(dá)n個(gè)貨位點(diǎn)取貨，完成該批次任務(wù)后停在最后一個(gè)貨位點(diǎn)等待下一揀選周期任務(wù)分配。為方便數(shù)學(xué)建模，揀選完最后一個(gè)任務(wù)后，增加回到原點(diǎn)形成環(huán)路的虛擬過(guò)程，但在計(jì)算目標(biāo)函數(shù)時(shí)這一虛擬過(guò)程不考慮在內(nèi)。揀選時(shí)由于考慮到貨物屬于不同優(yōu)先級(jí)別的領(lǐng)料單，會(huì)存在出貨優(yōu)先級(jí)別的問(wèn)題，因此每一個(gè)貨物根據(jù)領(lǐng)料單優(yōu)先級(jí)別設(shè)置不同出貨懲罰值。該問(wèn)題的目標(biāo)有3項(xiàng)，即在一個(gè)揀選周期中，使得堆垛機(jī)在揀選貨物時(shí)各機(jī)構(gòu)(立柱、升降機(jī)、載貨臺(tái))消耗能源成本、揀選作業(yè)總時(shí)長(zhǎng)以及出貨懲罰值最小。

1.2 堆垛機(jī)揀選作業(yè)序列優(yōu)化模型的建立

1.2.1 符號(hào)定義

堆垛機(jī)揀選作業(yè)序列優(yōu)化模型使用的符號(hào)定義如表1所示。

表1 符號(hào)定義表

1.2.2 假設(shè)條件

(1)各機(jī)構(gòu)運(yùn)動(dòng)速度為常數(shù)。

(2)立柱和載貨臺(tái)單位移動(dòng)能耗成本為常數(shù)。

(3)貨物重量均不大于堆垛機(jī)的額定載荷。

(4)貨格的大小相等，每個(gè)貨格長(zhǎng)、寬都記為d。

1.2.3 堆垛機(jī)揀選路徑優(yōu)化模型

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

在整個(gè)揀選過(guò)程中，最小化所有機(jī)構(gòu)總能耗成本C、揀選總時(shí)間T以及一個(gè)揀選周期中總的出貨懲罰值W。

立柱、載貨臺(tái)、升降機(jī)三大機(jī)構(gòu)的總行程乘以單位成本可以得到機(jī)構(gòu)總能耗成本C。由于任何情況下升降機(jī)行走的行程固定，即能耗固定，優(yōu)化過(guò)程只需考慮立柱和載貨臺(tái)。從貨位i揀選到貨位j的過(guò)程中，立柱的行走行程為:

載貨臺(tái)行走的行程為:

則整個(gè)過(guò)程各機(jī)構(gòu)能耗成本為:

因?yàn)槎讯鈾C(jī)中各機(jī)構(gòu)是協(xié)同工作的，所以只有當(dāng)機(jī)構(gòu)都到達(dá)其中某一個(gè)要揀選的貨位時(shí)，才能進(jìn)行取貨任務(wù)。在作業(yè)開(kāi)始及中間階段，立柱、載貨臺(tái)以及升降機(jī)同時(shí)從起點(diǎn)出發(fā)，分別到達(dá)要揀選的貨位處。

載貨臺(tái)從貨位i到貨位j的時(shí)間為:

升降機(jī)從貨位i到貨位j的時(shí)間為:

則從貨位i揀選到貨位j的時(shí)間為:

整個(gè)揀選過(guò)程的總時(shí)間為:

在揀選過(guò)程中將貨物分為A、B、C三類。A類代表出庫(kù)時(shí)間要求一般，B類代表出庫(kù)時(shí)間要求較高，C類代表出庫(kù)時(shí)間要求最高。相應(yīng)地賦予A、B、C類貨物不同的出庫(kù)懲罰值wi。若緊急程度低的貨物先于緊急程度高貨物出庫(kù)，則需要依據(jù)wi絕對(duì)差值懲罰，揀選過(guò)程中的總懲罰值為:

(2)約束條件

其中:式(10)表示任意貨位只有一個(gè)前點(diǎn);式(11)表示任意貨位只有一個(gè)后點(diǎn);式(12)表示揀選路徑包含所有貨位;式(13)保證了一次作業(yè)過(guò)程中，針對(duì)同一個(gè)貨位，到達(dá)后一定會(huì)離開(kāi)該貨位;式(14)～式(16)表示當(dāng)堆垛機(jī)揀選完貨位i后揀選貨位j時(shí)，如果貨位i中貨物出庫(kù)時(shí)間要求高于貨位j中貨物出庫(kù)時(shí)間要求(wj＞wi)，則pij=0;反之pij=1，其中M為一個(gè)極大正整數(shù)。

2 改進(jìn)NSGA-Ⅱ算法設(shè)計(jì)

2.1 算法整體框架

NSGA-Ⅱ算法是在第一代非支配排序遺傳算法(NSGA)的基礎(chǔ)上改進(jìn)而來(lái)的，它降低了NSGA算法的復(fù)雜性，具有運(yùn)行速度快，解集收斂性好的優(yōu)點(diǎn)，在多目標(biāo)優(yōu)化問(wèn)題中表現(xiàn)優(yōu)異[19]。本文中NSGA-Ⅱ算法的總體操作流程如圖2所示。

(1)隨機(jī)產(chǎn)生初始種群Pt，假設(shè)種群規(guī)模為N，對(duì)初始種群Pt進(jìn)行快速非支配排序;并將每個(gè)個(gè)體的適應(yīng)度函數(shù)值記為其所在的非支配層的層號(hào);通過(guò)選擇適應(yīng)度值較小的個(gè)體的方式來(lái)進(jìn)行遺傳算法選擇算子的操作。

(2)通過(guò)交叉、變異等操作，得到新種群即子代Qt。

(3)將父代與子代種群進(jìn)行合并，得到臨時(shí)種群Rt，對(duì)其進(jìn)行快速非支配排序，并對(duì)每個(gè)個(gè)體計(jì)算其擁擠度，通過(guò)擁擠度比較算子的操作，按照精英選擇策略原則從臨時(shí)種群Rt中選擇N個(gè)個(gè)體，組成下一輪迭代中的父代Pt+1。

(4)判斷是否滿足結(jié)束條件，若未滿足，重復(fù)步驟(2)和步驟(3)，直至滿足終止條件。

2.2 NSGA-Ⅱ算法改進(jìn)

堆垛機(jī)揀選作業(yè)序列優(yōu)化問(wèn)題，類似于TSP，具有鮮明的特點(diǎn)，因此在算法設(shè)計(jì)過(guò)程中，根據(jù)求解問(wèn)題的特點(diǎn)在基因編碼以及初始種群生成策略方面進(jìn)行了針對(duì)性改進(jìn)。

染色體編碼時(shí)，使用基因順序表示作業(yè)順序，基因代碼表示揀選任務(wù)所在貨位，例如染色體中第一個(gè)基因?yàn)椤?”表示起始點(diǎn)為1號(hào)貨位，第二個(gè)基因?yàn)椤?”表示在揀選任務(wù)中第2個(gè)要揀選任務(wù)貨位號(hào)為5。這種編碼方式高效方便，在類似問(wèn)題研究中得到了有效驗(yàn)證。

通常，NSGA-II算法在初始種群生成時(shí)采用隨機(jī)策略，然而堆垛機(jī)揀選作業(yè)序列優(yōu)化問(wèn)題與TSP類似，在類似問(wèn)題中迪杰斯特拉算法與貪心算法等基于貪婪策略的算法得到了很好的應(yīng)用，因此本文將貪婪策略應(yīng)用到初始種群生成中。對(duì)于多目標(biāo)優(yōu)化問(wèn)題，各目標(biāo)可能存在相互沖突情況，例如貨物出庫(kù)優(yōu)先順序與揀選時(shí)間或是能耗成本往往不能統(tǒng)一，不能簡(jiǎn)單采用貪婪策略，因此在初始種群生成時(shí)本文采用隨機(jī)策略與基于3個(gè)目標(biāo)分量的貪婪策略隨機(jī)組合的混合策略，如圖3所示。

通過(guò)圖3所示混合策略生成初始種群，一方面避免完全隨機(jī)策略盲目性，引進(jìn)在TSP等類似問(wèn)題中應(yīng)用成熟的貪婪策略使得算法在較高起點(diǎn)上進(jìn)行演化;另一方面，保留部分隨機(jī)策略避免算法早熟。

2.3 其他詳細(xì)步驟

2.3.1 快速非支配排序

在快速非支配排序過(guò)程中，假設(shè)Pt為初始生成的種群，Qt為對(duì)種群Pt進(jìn)行一系列操作后得到的子代種群，Rt為將種群Pt與種群Qt合并之后所得到的臨時(shí)種群，p代表臨時(shí)種群Rt中的個(gè)體。針對(duì)每個(gè)個(gè)體p，都需要計(jì)算np與sp兩個(gè)參數(shù)。np表示在臨時(shí)種群Rt的所有個(gè)體中，全面優(yōu)于p的個(gè)體數(shù)量;sp表示在臨時(shí)種群Rt中，全面劣于p的個(gè)體數(shù)量。

具體操作步驟如下:

(1)首先計(jì)算臨時(shí)種群Rt中每個(gè)個(gè)體的np與sp兩個(gè)參數(shù)。

(2)找出種群中np=0的所有個(gè)體，并將這些個(gè)體保存到集合F1中。

(3)遍歷集合F1中的所有個(gè)體，找出被這些個(gè)體所支配的個(gè)體(所找出的個(gè)體可能存在重復(fù)被記錄的情況)，將被找出的個(gè)體都記錄在集合S中。

(4)遍歷集合S，將S中所有個(gè)體的np值減去1(若個(gè)體被多次記錄，該個(gè)體的np值需被多次減1)，將所得的新參數(shù)記為n'p，找出n'p=0的個(gè)體，并將這些個(gè)體保存到集合F2中。

(5)將集合F1中的個(gè)體作為首個(gè)非支配層中的個(gè)體;集合F2為第二層非支配層，同時(shí)以該集合為當(dāng)前集合，重復(fù)上述操作，直到臨時(shí)種群Rt被完全分級(jí)。

通過(guò)上述操作，使得種群Rt中除了第一層集合F1外，其他分層集合只被層級(jí)數(shù)更低的集合支配，而同層級(jí)中的個(gè)體則組成互不支配的集合。

2.3.2 遺傳算子操作

(1)交叉算子 本文采用中間重組的交叉方法，將兩條父代染色體中間部位的某幾個(gè)基因進(jìn)行交叉互換;并找出新生成的兩條染色體中多余和重復(fù)的基因，將每條染色體上多余的基因用缺少的基因依次替換掉，這樣就能得到兩條新的子代染色體。

(2)變異算子 變異算子是根據(jù)事先設(shè)定的變異概率，判斷是否對(duì)該個(gè)體進(jìn)行變異，對(duì)進(jìn)行變異的個(gè)體隨機(jī)選擇變異位進(jìn)行變異。本文采用交換變異的方法，選取需要變異的染色體上任意兩個(gè)位置上的基因，將這兩個(gè)基因的順序進(jìn)行對(duì)調(diào)完成變異。

2.3.3 計(jì)算擁擠度

擁擠度表示的是在種群中給定點(diǎn)的周圍個(gè)體的密度，用符號(hào)id表示。從直觀角度來(lái)看，三目標(biāo)優(yōu)化問(wèn)題中，可將擁擠度理解為僅能將個(gè)體p包圍的最大長(zhǎng)方體的長(zhǎng)度。擁擠度的計(jì)算方法為[20]:將個(gè)體以非支配層為單位，基于每一目標(biāo)函數(shù)，對(duì)種群進(jìn)行重新排序，假設(shè)邊界個(gè)體的擁擠度為無(wú)窮大，即I(d1)=I(dn)=∞，其余個(gè)體的擁擠度用差值法進(jìn)行計(jì)算:

式中:I(dk)為第k個(gè)個(gè)體的擁擠度;Im(k+1)為第k+1個(gè)個(gè)體的第m個(gè)目標(biāo)函數(shù)值;Im(k-1)為第k-1個(gè)個(gè)體的第m個(gè)目標(biāo)函數(shù)值;分別表示該支配層中第m個(gè)目標(biāo)函數(shù)的最大、最小值。

經(jīng)過(guò)上述操作，種群中任意個(gè)體p的兩個(gè)屬性非支配排序和擁擠度均得以確定，運(yùn)用這兩個(gè)屬性，能夠明確種群中任意兩個(gè)個(gè)體間的優(yōu)劣關(guān)系。記irank為個(gè)體i所在的非支配層序列號(hào)，個(gè)體間優(yōu)劣關(guān)系判斷依據(jù)如下:

(1)如果個(gè)體i所處非支配層優(yōu)于個(gè)體j所處的非支配層，即irank＜jrank，則i優(yōu)于j。

(2)如果兩個(gè)體處于相同的非支配層，且個(gè)體i比個(gè)體j有著更大的擁擠距離，即irank=jrank且id＞jd，則i優(yōu)于j。

將父代種群Pt和子代種群Qt進(jìn)行合并，得到臨時(shí)種群Rt，并對(duì)臨時(shí)種群Rt進(jìn)行快速非支配排序，利用擁擠度比較算子從臨時(shí)種群Rt中選取N個(gè)較為優(yōu)秀的個(gè)體作為下一代種群。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文實(shí)驗(yàn)以上海某自動(dòng)化立體倉(cāng)庫(kù)制造商產(chǎn)品中大型自動(dòng)化立體倉(cāng)庫(kù)的巷道式堆垛機(jī)為案例。實(shí)驗(yàn)中設(shè)備各項(xiàng)參數(shù)如下:貨格長(zhǎng)寬ds=0.8 m;貨叉將貨物從貨格中揀取出來(lái)的時(shí)間Δt1為20 s;貨叉將貨物放在升降機(jī)貨臺(tái)上的時(shí)間Δt2為20 s;升降機(jī)將貨物放在傳送帶上的時(shí)間Δt3為20 s;立柱水平方向的移動(dòng)速度vh為5 m/s;載貨臺(tái)垂直方向的移動(dòng)速度vr為2 m/s;立柱移動(dòng)距離單位成本為0.5，載貨臺(tái)單位移動(dòng)成本為0.1(預(yù)估相對(duì)值)。升降機(jī)垂直方向的移動(dòng)速度ve為2 m/s。另外，本文所有算例基于Intel Xeon(R)E5520 CPU@2.25 GHz，4 GB內(nèi)存的Windows 10系統(tǒng)運(yùn)行。

3.1 典型算例分析

本節(jié)通過(guò)一個(gè)典型的算例，分析改進(jìn)NSGA-II算法收斂過(guò)程及最終計(jì)算結(jié)果。在該算例中，需要通過(guò)復(fù)合式策略揀選20個(gè)單位貨物，分別堆存于20個(gè)貨位，該批次貨物分屬于4個(gè)訂單。貨位編碼、坐標(biāo)、所屬訂單順序以及懲罰因子設(shè)置如表2所示。表中，所屬訂單順序越小，說(shuō)明該貨物需求越緊急。

表2 算例設(shè)置

為考察算法進(jìn)化過(guò)程，通過(guò)預(yù)先實(shí)驗(yàn)分析設(shè)置算法最大迭代次數(shù)為250代，即max(t)=250。圖4和圖5分別展示了3個(gè)目標(biāo)函數(shù)收斂過(guò)程。

由圖4可知，該算例最佳能耗成本由初代值58.32，經(jīng)過(guò)算法迭代后在60代左右接近最優(yōu)值47.92。由圖5 可知，最佳作業(yè)時(shí)間由初代值1345.76，在前10代迭代過(guò)程快速下降至1337.76，穩(wěn)定一段時(shí)間后在160代左右進(jìn)一步下降至最小值1337.28。由圖6可知，最小懲罰值從初代值25，一步步下降到最小值15。圖4～圖6表明，改進(jìn)的NSGA算法在求解堆垛機(jī)作業(yè)序列多目標(biāo)優(yōu)化問(wèn)題中，收斂性較好，優(yōu)化效果明顯。

該算例最終得到的Pareto解集包含4個(gè)解，目標(biāo)函數(shù)值如表3所示，其中最佳目標(biāo)函數(shù)值通過(guò)灰色背景標(biāo)記。由表3可知，第3個(gè)解擁有最小能耗成本值47.92，其揀選順序?yàn)?(0，3，9，12，20，8，2，10，13，6，5，1，7，16，17，17，14，4，19，11，15)(如圖7)。第4個(gè)解擁有最小作業(yè)時(shí)間1337.28 s，其作業(yè)順序?yàn)?(0，20，4，14，12，8，2，10，13，6，5，1，7，16，17，18，19，9，15，3，11)(如圖8)。第2個(gè)解擁有最小懲罰值15，其作業(yè)順序?yàn)?(0，8，7，3，2，19，17，10，14，12，5，13，1，16，18，9，20，4，15，11，16)(如圖9)。通過(guò)比較表3中各訂單完成時(shí)間，可見(jiàn)訂單完成時(shí)間先后順序與訂單優(yōu)先級(jí)別基本一致，訂單順序號(hào)越小完成越早。通過(guò)比較圖7～圖9可見(jiàn)，能耗成本和揀選時(shí)間最小的解，其揀選路徑相對(duì)連貫，懲罰值最小的解揀選路徑來(lái)回反復(fù)頻次高。但是從表3中發(fā)現(xiàn)，解2中1號(hào)、2號(hào)和3號(hào)訂單完成時(shí)間相對(duì)于完全“播種式”揀選方式可分別提前62%，52%及10%時(shí)間完成，可見(jiàn)犧牲一定成本與效率可以整體上提高物流配送的服務(wù)質(zhì)量，使大部分訂單優(yōu)先完成揀選。另外，3、4號(hào)任務(wù)不僅在效率上可以實(shí)現(xiàn)最優(yōu)化，相對(duì)于完全“播種”式揀選大部分訂單也能提前完成。

表3 Pareto解集目標(biāo)函數(shù)值(#N：第N 號(hào)訂單完成時(shí)間(s)與提前完成時(shí)間比例)

3.2 靈敏度分析

為得到改進(jìn)NSGA-II算法交叉概率和變異概率合理值，對(duì)表2 算例分別設(shè)置交叉概率為0.4～0.6，變異概率0.03～0.07共15組組合測(cè)試，每組測(cè)試運(yùn)行10次取各個(gè)目標(biāo)函數(shù)均值得到表4所示結(jié)果。

表4 交叉概率和變異概率對(duì)目標(biāo)函數(shù)值影響

由表4可知，交叉概率為0.4，變異概率為0.06時(shí)，最小完成時(shí)間和最小懲罰值均值都是所有試驗(yàn)中最小值，分別為1332.42和12.00。此時(shí)，最小成本均值為42略大于0.4和0.07組合。綜合比較分析，交叉概率選擇0.4變異概率選擇0.06時(shí)算法具有最佳優(yōu)化效果。

為得到一個(gè)較好的算法結(jié)束判別條件，對(duì)表3算例分別設(shè)置判別條件不同的9組實(shí)驗(yàn):3個(gè)最佳目標(biāo)函數(shù)值連續(xù)20、30、40、50、60代不變，以及最大迭代數(shù)為150、200、250和300。每組測(cè)試實(shí)驗(yàn)運(yùn)行10次得到3個(gè)目標(biāo)函數(shù)值以及CPU 運(yùn)算時(shí)間均值如表5所示。

表5 不同收斂條件對(duì)算法影響

由表5可知，當(dāng)算法終止條件設(shè)置為目標(biāo)函數(shù)連續(xù)60代不變時(shí)，得到最小成本、最小作業(yè)時(shí)間和最佳罰值均值分別為38.32、1330.92，以及12.0在所有測(cè)試實(shí)驗(yàn)中均為最小，此時(shí)CPU 運(yùn)行時(shí)間為3.40 s，相對(duì)于批次揀選時(shí)間可以忽略。因此，可以設(shè)定算法終止條件為目標(biāo)函數(shù)連續(xù)60代不變。

3.3 算法性能分析

為分析算法對(duì)不同計(jì)算規(guī)模適應(yīng)能力，根據(jù)該系列堆垛機(jī)不同規(guī)格型號(hào)產(chǎn)品高度范圍[10，15，20]，長(zhǎng)度范圍[30，40，50]，以及不同揀選批次任務(wù)數(shù)[20，30，40]，隨機(jī)生成27組算例。每組算例分別使用改進(jìn)前NSGA-II算法以及針對(duì)該問(wèn)題特征改進(jìn)后NSGA-II算法運(yùn)行10次，取得10次算例最佳目標(biāo)函數(shù)均值及CPU運(yùn)算時(shí)間如表6所示。由表6可知，當(dāng)貨架型號(hào)以及任務(wù)數(shù)增大后，改進(jìn)前算法目標(biāo)函數(shù)值增加明顯，改進(jìn)后算法目標(biāo)函數(shù)值增長(zhǎng)趨勢(shì)明顯小于改進(jìn)前算法，可見(jiàn)改進(jìn)后算法對(duì)目標(biāo)函數(shù)優(yōu)化效果明顯好于改進(jìn)前算法。同時(shí)，改進(jìn)前算法隨著任務(wù)數(shù)增加CPU 運(yùn)算時(shí)間顯著增長(zhǎng)，改進(jìn)后算法盡管運(yùn)算時(shí)間也有所增加，但增加幅度很小。由此可見(jiàn)，改進(jìn)后算法相對(duì)于改進(jìn)前算法在不同規(guī)模算例中都表現(xiàn)出明顯優(yōu)勢(shì)。

表6 不同計(jì)算規(guī)模下改進(jìn)前后NSGA-II算法比較分析

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

本文采用改進(jìn)NSGA-II算法求解自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)揀選序列多目標(biāo)優(yōu)化問(wèn)題。從提高自動(dòng)化立體倉(cāng)庫(kù)效率以及物流服務(wù)質(zhì)量角度，通過(guò)對(duì)優(yōu)化問(wèn)題進(jìn)行分析，建立了以一個(gè)揀選周期內(nèi)的能耗成本、揀選時(shí)間以及懲罰值最小化為目標(biāo)的多目標(biāo)優(yōu)化數(shù)學(xué)模型?；贜SGA-II的算法框架，通過(guò)隨機(jī)分配法和貪婪策略生成法相結(jié)合的方式，改進(jìn)帶精英策略的快速非支配排序遺傳算法(NSGA-II)中初始解生成策略，提高了算法整體優(yōu)化效果與效率。綜合分析算例運(yùn)行的結(jié)果，證明了“播種+摘取”復(fù)合式揀選策略下可實(shí)現(xiàn)大多數(shù)訂單提前完成揀選工作，同時(shí)本文所提出的改進(jìn)NSGA-II算法可以有效求解復(fù)合式揀選策略下堆垛機(jī)揀選序列優(yōu)化問(wèn)題。雖然大多數(shù)固定貨架巷道式堆垛起重機(jī)一般是單機(jī)作業(yè)，但是隨著物流系統(tǒng)整體效率的提高，對(duì)自動(dòng)化立體倉(cāng)庫(kù)作業(yè)效率的要求越來(lái)越高，單巷道多堆垛機(jī)組合形式將會(huì)越來(lái)越多出現(xiàn)在對(duì)效率要求較高的自動(dòng)化立體倉(cāng)庫(kù)中，這類堆垛機(jī)揀選路徑優(yōu)化問(wèn)題涉及堆垛機(jī)任務(wù)分配、設(shè)備間相互干涉等更復(fù)雜因素，是進(jìn)一步研究的重點(diǎn)。