基于“反學習”理論的人工蜂群算法在訂單分批問題中的應用

吳天行，郭 鍵

（北京物資學院，北京 101149）

1 引言

當今社會市場競爭日益嚴重，企業(yè)生產(chǎn)的產(chǎn)品差異化程度日漸降低，如何提高企業(yè)的競爭優(yōu)勢以保證企業(yè)在市場競爭中占得先機已經(jīng)成為許多企業(yè)考慮的重點[1]，物流作為“第三利潤源”的概念由此而生。為了優(yōu)化物流系統(tǒng)，降低物流成本，目前眾多學者將如何提高物流系統(tǒng)的效率作為研究的重點內(nèi)容。

縱觀企業(yè)整個物流系統(tǒng)，配送和倉儲在物流系統(tǒng)中占據(jù)了很大的比重，而相關(guān)研究表明，倉儲與配送作業(yè)的成本在物流總成本中占據(jù)40%以上的比重[2]。而在倉儲和配送作業(yè)中，人工揀選作業(yè)中的揀選行走成本比例最大，如何優(yōu)化揀選作業(yè)，縮短揀選作業(yè)的行走距離已經(jīng)成為當前優(yōu)化物流系統(tǒng)的當務之急。訂單分批策略是現(xiàn)今優(yōu)化揀選作業(yè)研究的一個熱點問題。該問題最早可以追溯至Van den berg[3]在上世紀90年代發(fā)表的關(guān)于優(yōu)化倉儲作業(yè)的論文中，在文中該學者認為將訂單分成批次集中揀選可以有效的縮短揀選作業(yè)的路徑，提高揀選作業(yè)效率。

2 訂單分批模型的建立

傳統(tǒng)意義上訂單的揀選作業(yè)是按照先到先服務的原則進行的，即對訂單按照到達的時間先后順序進行揀選[4]，這種方法一般不會刻意對訂單進行分批，因此一般也不需要建立特定的模型進行研究。但是隨著訂單數(shù)量的增加，先到先服務的模式越來越難以滿足揀選作業(yè)的高效要求，這時如何快速高效揀選訂單就成為了研究的方向。

訂單分批問題就是利用數(shù)學優(yōu)化方法，首先是建立需要求解的目標函數(shù)，其次是根據(jù)問題的具體情況對限制性約束加以確定，最后在確定目標函數(shù)和限制性條件的基礎(chǔ)上，利用智能算法求解建立的數(shù)學模型，得到模型的最優(yōu)解，完成整個優(yōu)化過程。

2.1 模型建立的背景

現(xiàn)在某企業(yè)有一個單區(qū)型倉庫，該倉庫的基本布局如圖1所示。每天都會有一定數(shù)量的訂單到達倉庫，這時就需要對倉庫內(nèi)的貨品按照到達的訂單進行揀選。

圖1 倉庫基本布局圖

根據(jù)該單區(qū)型倉庫的實際情況，設(shè)定整個倉庫由A排貨架組成，每一排貨架的貨位數(shù)量是B，每一個貨位的長度和寬度都為C，倉庫內(nèi)揀選通道的寬度為D，倉庫的左下角有一個出入口，所有揀選完的訂單都由左下角的出入口送出倉庫。揀選設(shè)備是倉庫中常見的揀選車，每一排揀選通道只能容納一輛揀選車，即不存在兩輛揀選車在一個通道內(nèi)揀選的情況。為了方便說明和計算，訂單分批模型不考慮“緊急插單”、訂單拆分和商品缺貨的情況。每一個訂單內(nèi)的貨品重量和體積都為E。

2.2 分批模型的構(gòu)建

根據(jù)上文做出的相關(guān)假設(shè)，下面將會建立訂單分批模型。

目標函數(shù)：

約束條件：

根據(jù)以上函數(shù)，下面將會對分批模型中涉及到的符號進行說明，見表1。

表1 函數(shù)符號說明

下面將會對分批模型中的每一個公式的含義進行闡述。式（1）表示在對所有的訂單分批以后，總的揀選路徑是最短的。式（2）表示每一批訂單的體積不超過揀選車的容積。式（3）表示每一批訂單的重量不超過揀選車的載重量。式（4）表示需要揀選的訂單只可以在一個批次中，即訂單不可以被分割。式（5）表示貨物a、b是否為連續(xù)揀選，即揀完貨a后是否立即揀選貨b。

3 人工蜂群算法與“反學習”理論

3.1 人工蜂群算法概述

人工蜂群算法（Artificial Bee Colony）是2005年由土耳其學者Karaboga[5]提出的，該算法的核心思想是模仿蜜蜂之間的相互協(xié)作、共同完成采集蜂蜜的覓食行為。人工蜂群算法主要有四個要素，分別是蜂源、引領(lǐng)蜂、跟隨蜂和偵查蜂[6]。另外整個搜索過程還包括召集蜜蜂和蜜源的放棄兩種基本行為[7]。

為了更為方便的描述整個蜂群算法的過程，下面將會用數(shù)學語言對整個算法進行詳細的闡述。

（1）初始解的生成。隨機生成數(shù)量為N的初始種群P，種群的規(guī)模表示為N，種群中的每一個解表示為Xi，每一個Xi都是種群中的一個D維向量，生成解按照式（6）來生成。

式（6）中，Xid表示第i個解的第d維，Md和Qd分別表示為搜索區(qū)域的上限和下限，d=1,2,...,D。

（2）產(chǎn)生新的蜂源。在搜索的早期階段，引領(lǐng)蜂需要根據(jù)式（7）生成新的蜜源來進行搜索。

式（7）中d是[1,D]中的一個隨機整數(shù)，含義是引領(lǐng)蜂隨機選擇一個維度進行搜索，j=1,2，...，j≠ i，表示在蜂源中隨機選擇一個蜂源i且不與j相同。φ是一個在[-1,1]上均勻分布的隨機數(shù)。采用貪心算法的方式保留所有的適應度值高的蜂源Vi。

（3）計算需要跟隨的概率。跟隨蜂從引領(lǐng)蜂獲得蜜源的信息，依據(jù)式（8）計算得到概率并進行跟隨。

跟隨蜂隨機的選擇引領(lǐng)蜂，在[0,1]之間產(chǎn)生一個隨機數(shù)r，如果Pi＞r，則根據(jù)式（7）產(chǎn)生新的蜂源，并且依照貪心算法來確定是否對蜂源進行保留。

在搜索過程中，如果在多次迭代以后，依然沒有找到更好的蜂源，則拋棄現(xiàn)有蜂源，利用式（9）來產(chǎn)生新的蜂源。

（4）評價解的適應度。為了保證獲得的解具有一般性，引入適應度的概念，按照式（10）對得到的解的適應度進行評價。

式（10）中fi為函數(shù)值，i=1,2,....,N。

3.2 基于“反學習”理論的初始種群構(gòu)成

在基本的人工蜂群算法中，按照隨機的方式生成初始種群，這就必然使得隨機生成的初始種群在解的空間內(nèi)的分布是不均勻的，而這種方式無疑會限制算法的求解效率，因此為了增強初始解的多樣性，提高算法效率，現(xiàn)將“反向解”的概念引入到初始種群的構(gòu)建中。

“反學習”理論的核心思想就是綜合考慮當前解和反向解距離最優(yōu)解的距離，這樣就可以最大程度上提高算法的尋優(yōu)速度和收斂速度[8]。“反學習”理論不僅可以應用在算法早期的初始種群生成階段，還可以使用在算法的迭代過程中。在每一次的迭代中，可以在生成初始解的基礎(chǔ)上再生成與之相對應的一組“反向解”，進而提高算法在每一次迭代的效率。下面將以數(shù)學語言的方式闡述“反向解”生成的主要過程。

（1）產(chǎn)生初始解。初始解的產(chǎn)生可以參照式（6）來進行。利用式（6）可以產(chǎn)生數(shù)量為N的初始解構(gòu)成初始種群。

（2）產(chǎn)生反向解。反向解的產(chǎn)生依據(jù)式（11）來進行。根據(jù)式（11）可以產(chǎn)生數(shù)量同樣為N的反向解，構(gòu)成初始種群。

（3）計算適應度并進行比較。根據(jù)式（10）計算“正向解”Xid和“反向解”的適應度值，并且進行大小的比較，選擇適應度較高的解構(gòu)成初始種群。

4 分批算法的仿真驗證

4.1 仿真驗證背景

為了驗證算法的有效性，本文將在單區(qū)型倉庫下隨機生成一批訂單，使用本文提出的分批算法和兩種傳統(tǒng)分批算法進行仿真應用，從而驗證基于“反學習”理論的蜂群算法在訂單分批問題中的科學性和有效性。

現(xiàn)在根據(jù)單區(qū)型倉庫的特點，設(shè)定倉庫通道寬度為2，每一個貨位的寬度為1，倉庫由16排、每排為15個貨位的貨架組成，揀選車最大容積和載重量都為20個單位，每一個需要揀選的貨品的重量和體積都為1個單位，現(xiàn)在隨機生成了8張訂單需要揀選，到達的訂單具體的商品品項的分布如圖2所示。

圖2 訂單商品品項分布圖

4.2 兩種傳統(tǒng)的分批算法

為了便于比較驗證，本文選取了兩種傳統(tǒng)的訂單分批算法進行分批，這兩種算法分別為基于通道相似性的分批算法和基于圖論的分批算法。

基于通道相似性的算法核心思想就是“分布在同一通道內(nèi)的商品一般情況下揀選的距離較短[9]”。基本步驟是首先找到在相同或者相似的通道內(nèi)的訂單，然后通過判斷是否滿足分批模型的約束條件來確定哪些訂單劃分為一個揀選批次。

利用該算法進行分批，最重要的就是要得到通道的相似性以及建立訂單分批規(guī)則，為了方便說明和計算，通道相似的公式和訂單分批規(guī)則就使用李詩珍在文獻中創(chuàng)建的公式與規(guī)則，分批后的結(jié)果見表2。

表2 基于相似性的分批結(jié)果

基于圖論的訂單分批算法的核心思想是從一個貨品出發(fā)直接尋找距離該商品最短的商品進行聚類，再根據(jù)分批規(guī)則進行分批，該算法是文獻[10]中使用的一種訂單分批方法。具體過程為首先將每一個貨品進行編號并計算距離矩陣；其次利用廣度優(yōu)先搜索算法建立聚類鄰接矩陣；最后根據(jù)訂單分批規(guī)則進行分批。為了便于計算和說明，按照文獻[10]建立的規(guī)則進行分批，具體的分批結(jié)果見表3。

表3 基于圖論的分批結(jié)果

4.3 基于“反學習”理論的分批算法

根據(jù)前文的敘述和單區(qū)型倉庫的相關(guān)數(shù)據(jù)，下面將會使用本文提出的基于“反學習”理論的人工蜂群算法對訂單內(nèi)的貨品進行分批，利用MATLAB軟件設(shè)定算法的迭代次數(shù)為1 000次，在內(nèi)存為16G的Windows系統(tǒng)中運行，可以得到最后的分批結(jié)果，見表4。

表4 基于“反學習”理論的蜂群算法分批結(jié)果

人工蜂群算法的運行結(jié)果如圖3所示。

圖3 人工蜂群算法運行結(jié)果

4.4 結(jié)果分析

根據(jù)之前不同算法的分批結(jié)果，下面將各個算法的分批結(jié)果整理匯總，見表5。

表5 各分批算法結(jié)果對比

根據(jù)表5可以清楚地看到，基于“反學習”理論的人工蜂群算法的分批結(jié)果最優(yōu)，與基于相似性和基于圖論的分批算法相比，在揀選距離上分別縮短了35.9%和33.5%，并且根據(jù)圖3可知，在算法迭代到430次左右時已經(jīng)找到了最優(yōu)解，算法的搜索效率較高。

從人工蜂群算法原理的角度分析可知，利用人工蜂群算法進行分批是基于訂單中每一個貨品的角度尋找最優(yōu)解，這樣進行分批往往比基于通道相似性的分批算法得到的結(jié)果更為精確，同時由于人工蜂群算法的收斂速度較快，利用該算法進行分批在時間上相較于基于圖論的聚類算法更有優(yōu)勢。為了彌補算法早期容易陷入局部最優(yōu)解的缺點，本文嘗試引入了“反學習”理論，對人工蜂群算法在初始種群和迭代的初始解生成階段進行優(yōu)化，從分批的結(jié)果來看，優(yōu)化的效果較優(yōu)。

5 結(jié)語

根據(jù)上文的分批結(jié)果可以知道，采用基于“反學習”理論的人工蜂群算法對訂單進行分批，可以獲得較好的分批結(jié)果，在第4節(jié)仿真驗證中，采用該算法對訂單進行分批相較于兩種傳統(tǒng)的分批算法在揀選路徑的距離上，分別縮短了35.9%和33.5%，在揀選距離的縮短上有較大的提升。

針對現(xiàn)在人工揀選效率較低的問題，本文嘗試應用訂單分批策略對揀選作業(yè)進行優(yōu)化，根據(jù)單區(qū)型倉庫的特點，提出了基于人工蜂群算法的訂單分批方法，并且針對蜂群算法的缺陷，將“反學習”理論融合到蜂群算法中，通過仿真實驗對該算法和傳統(tǒng)的兩種分批算法進行分批驗證，根據(jù)分批結(jié)果認為，利用基于“反學習”理論的人工蜂群算法對訂單進行分批，無論是在分批時間上還是在揀選的距離上，都要優(yōu)于傳統(tǒng)的訂單分批算法，利用該算法在單區(qū)型倉庫中進行分批揀選具有一定的推廣意義。

[1]白冬.現(xiàn)代企業(yè)管理模式的改革與發(fā)展[J].企業(yè)技術(shù)開發(fā),2014,(14).

[2]李伊松.物流成本管理[M].北京:清華大學出版社,2005.

[3]劉志帥.YB公司天津分公司倉庫貨位優(yōu)化問題研究[D].天津:河北工業(yè)大學,2013.

[4]韓玉芳.配送中心訂單分批問題研究[D].濟南:山東大學,2015.

[5]Karabogad.An idea based on honey bee swarm for numerical optimization Computers Engineering Department[D].Engineering Faculty Erciyes University,2005．

[6]李艷娟.基于禁忌搜索的人工蜂群算法[J].計算機工程與應用,2017,(4).

[7]郝繼升.改進的人工蜂群算法[J].江西科學,2017,(2).

[8]秦全德.人工蜂群算法研究綜述[J].智能系統(tǒng)學報,2014,(2).

[9]李詩珍.配送中心訂單分批揀貨模型及種籽啟發(fā)式算法[J].起重運輸機械,2009,(1).

[10]吳天行.基于圖論的聚類算法在訂單分批問題中的應用[J].物流技術(shù),2017,(8).