基于改進(jìn)和聲搜索算法的越庫車輛排序

王占中，盧 月，劉曉峰，趙利英

(1.吉林大學(xué) 交通學(xué)院,長春 130022；2.吉林省運(yùn)輸管理局,長春 130022)

0 引 言

越庫是產(chǎn)品在物流環(huán)節(jié)中，不經(jīng)過中間倉庫或站點(diǎn)，直接從一個(gè)運(yùn)輸工具換載到另一個(gè)運(yùn)輸工具的物流銜接過程。越庫系統(tǒng)可以在短時(shí)間內(nèi)處理大量物品，加快庫存周轉(zhuǎn)速度，減少庫存需求空間和客戶響應(yīng)時(shí)間，在控制物流成本的同時(shí)，提高客戶服務(wù)水平。

目前，研究人員在越庫場景和求解目標(biāo)方面展開廣泛的研究。如：Yu等[1]根據(jù)越庫門的數(shù)量、是否有臨時(shí)庫存與集送貨車輛進(jìn)出的次數(shù)提出32種越庫組合方法，并著重研究帶有臨時(shí)庫存的單集、送貨門的越庫模型。Yu[2]在先前研究的基礎(chǔ)上，進(jìn)一步研究了多集貨門及送貨門的越庫模型。Madani-Isfahani等[3]以運(yùn)作時(shí)間作為目標(biāo)函數(shù)建立了多越庫門的越庫模型。Mohtashami[4]建立了允許送貨車輛反復(fù)進(jìn)出裝貨平臺的越庫模型，在車輛交換時(shí)間較短的情況下有較好的表現(xiàn)。

在求解方面，以智能算法為主，較為典型的有禁忌搜索算法、模擬退火算法和遺傳算法等。Madani-Isfahani等[3]通過螢火蟲算法求得的越庫車輛序列比模擬退火算法求得的序列運(yùn)作時(shí)間短。Arabani等[5]建立了帶有臨時(shí)庫存的單集、送貨門的越庫模型，采用多種智能算法(如遺傳算法、蟻群算法與粒子群算法等)求解相應(yīng)問題。Soltani等[6]運(yùn)用模擬退火算法和混合變量鄰域搜索算法求解大規(guī)模的越庫車輛排序問題。Assadi等[7]建立混合線性規(guī)劃模型，采用模擬退火算法和遺傳算法求解相應(yīng)問題?？姵療樀萚8]采用自適應(yīng)遺傳算法求解帶有車輛容量限制以及時(shí)間窗約束的越庫車輛排序問題。

和聲搜索算法作為新興的啟發(fā)式算法，具有概念容易理解、抽樣簡單和參數(shù)變量少的優(yōu)點(diǎn)。針對當(dāng)前研究存在的不足，本文將和聲搜索算法用于越庫車輛排序問題的優(yōu)化求解。

1 描述及模型設(shè)計(jì)

1.1 問題描述

假設(shè)越庫系統(tǒng)僅有一個(gè)卸貨平臺和一個(gè)裝貨平臺，在裝貨平臺前存在臨時(shí)庫存。當(dāng)?shù)竭_(dá)裝貨平臺的貨物與當(dāng)前送貨車輛的需求不匹配時(shí)，物品可以存儲在臨時(shí)庫存中，等到合適的送貨車輛進(jìn)入卸貨平臺后再將貨物進(jìn)行裝載。越庫系統(tǒng)作業(yè)流程如圖1所示。

圖1 越庫作業(yè)流程圖Fig.1 Flow chart of cross docking

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

建立模型前需進(jìn)行如下假設(shè)：

(1)所有的集、送貨車輛都可以被使用，且集、送貨作業(yè)可以同時(shí)進(jìn)行。

(2)禁止送貨車輛同時(shí)從集貨車輛和臨時(shí)庫存裝貨。

(3)臨時(shí)庫存大小沒有限制，但物品不允許長期存儲于臨時(shí)庫存中。

(4)每種類型的集貨物品總數(shù)等于每種類型的送貨物品總數(shù)。

(5)集貨車輛所裝載的不同類型的物品卸貨順序可以隨意確定。

(6)送貨車輛物品裝貨順序與集貨車輛物品卸貨順序保持一致。

(7)所有集、送貨車輛因交替裝卸貨所導(dǎo)致的延遲時(shí)間一致。

(8)所有物品從集貨平臺到裝貨平臺的移動時(shí)間相等。

(9)集、送貨車輛每次只能卸載或裝載一個(gè)物品，物品裝卸貨均耗1單位時(shí)間。

本文以越庫作業(yè)完工時(shí)間T為目標(biāo)函數(shù)建立數(shù)學(xué)模型，首先對建模所需數(shù)學(xué)符號做如下定義：T為總運(yùn)作時(shí)間；ci為集貨車輛i進(jìn)入集貨平臺的時(shí)刻；Fi為集貨車輛i離開集貨平臺的時(shí)刻；dj為送貨車輛j進(jìn)入裝貨平臺的時(shí)刻；Lj為送貨車輛j離開裝貨平臺的時(shí)刻。vij=1表示有物品從集貨車輛i移動到送貨車輛j，vij=0表示其他情況。pij=1表示在集貨車輛序列中集貨車輛i排在集貨車輛j之前，pij=0表示其他情況。qij=1表示在送貨車輛序列中送貨車輛i排在送貨車輛j之前，qij=0表示其他情況。R為集貨車輛數(shù)；S為送貨車輛數(shù)；N為物品種類數(shù)；rik為最初裝載在集貨車輛i中的k物品總數(shù)；sjk為最初送貨車輛所需要k物品的總數(shù)；D為因裝卸貨車輛交替所耽擱的時(shí)間；V為物品從集貨平臺到裝貨平臺移動時(shí)間；xijk為集貨車輛i轉(zhuǎn)移物品k到送貨車輛j的數(shù)量；M為較大正實(shí)數(shù)。

目標(biāo)函數(shù)P0為：

minT

s.t.T≥Lj,j∈?

(1)

(2)

(3)

xijk≤Mvij,i∈?,j∈?,k∈?

(4)

(5)

cj≥Fi+D-M(1-Pij)

(6)

i∈?,j∈?,i≠j

ci≥Fj+D-Mpij

(7)

pii=0,i∈?

(8)

(9)

dj≥Li+D-M(1-qij)

(10)

i∈?,j∈?,i≠j

di≥Lj+D-Mqij

(11)

i∈?,j∈?,i≠j

qii=0,i∈?

(12)

i∈?,j∈?

(13)

以上所有變量均大于等于零。

集貨車輛貨品一部分直接搬送到送貨車輛上，一部分暫存于臨時(shí)庫存中。貨品直接轉(zhuǎn)移到送貨車輛上比轉(zhuǎn)移到臨時(shí)庫存后再轉(zhuǎn)移到送貨車輛上所需時(shí)間少。為此，貨品轉(zhuǎn)移到臨時(shí)庫存中的數(shù)量越少，總越庫作業(yè)所需時(shí)間越少。儲存在臨時(shí)庫存中的物品數(shù)量多少由集、送貨車輛之間的排序引起，因此集、送貨車輛排序的優(yōu)劣可以通過臨時(shí)庫存中物品數(shù)量的多少判斷。

目標(biāo)函數(shù)P1為：

(14)

(15)

(16)

(17)

(18)

2 改進(jìn)的和聲搜索算法

2.1 和聲搜索算法求解過程

和聲搜索(Harmony search，HS)算法由Geem等于2001年提出[9]。首先在和聲解集HM內(nèi)隨機(jī)生成HMS組初始解，然后以記憶庫取值概率HMCR選擇是在HM內(nèi)搜索新解，還是在和聲記憶庫外取值。若解來自于HM內(nèi)，則需依據(jù)音調(diào)調(diào)整概率PAR選擇是否對新解作頻寬BW大小的局部擾動。最后，判斷新解目標(biāo)值是否優(yōu)于HM內(nèi)的最差解。若是，則用新解替換最差解，繼續(xù)迭代，直至滿足終止條件為止。

2.2 改進(jìn)的和聲搜索算法

基本的和聲搜索算法其參數(shù)是固定的，但參數(shù)在不同迭代時(shí)期有不同的表現(xiàn)形式。例如，在迭代初期較大的BW搜索較優(yōu)結(jié)果的能力較好，但在迭代末期較小的BW有更好的表現(xiàn)[10,11]。為提高HS算法的搜索能力，IHS算法在音調(diào)調(diào)整步驟對PAR和BW做動態(tài)調(diào)整。BW和PAR的計(jì)算過程如式(19)(20)(21)所示：

PAR(gn)=

(19)

BW(gn)=BWmaxexp(c×gn)

(20)

(21)

式中：PAR(gn)、BW(gn)分別為每一次迭代的PAR和BW的值；PARmax、PARmin分別為PAR的最大值和最小值；BWmax、BWmin分別為BW的最大值和最小值；gn為迭代次數(shù)；NI為總迭代次數(shù)。

2.3 參數(shù)設(shè)定

田口試驗(yàn)被廣泛地應(yīng)用于工程設(shè)計(jì)中，用來確定最優(yōu)的試驗(yàn)條件。每個(gè)參數(shù)的影響能力可以通過信噪比(Signal to noise ratio,SNR)表示，通過SNR在控制因子中尋找變異量小的組合。根據(jù)HS算法和IHS算法參數(shù)特點(diǎn)，設(shè)置不同參數(shù)水平如表1和表2所示。以試驗(yàn)組1中數(shù)據(jù)為基礎(chǔ)，通過MINITAB軟件得到兩種算法的參數(shù)在不同水平下的信噪比主效應(yīng)圖如圖2和圖3所示。

表1 HS算法的因子及其水平Table 1 Levels of parameters for HS

表2 IHS算法的因子及其水平Table 2 Levels of parameters for IHS

圖2 HS參數(shù)的信噪比主效應(yīng)圖Fig.2 Main effects plot for SNR of HS factors

圖3 IHS參數(shù)的信噪比主效應(yīng)圖Fig.3 Main effects plot for SNR of IHS factors

根據(jù)圖2可知，HS算法的4種參數(shù)中，HMS對信噪比的影響最大，PAR的影響次之，然后分別是BW和HMCR。根據(jù)圖2選取參數(shù)HMS為20，HMCR為0.9，PAR為0.2，BW為0.7。

根據(jù)圖3可知，IHS算法的6種參數(shù)中，HMS對信噪比的影響最大；BWmin和BWmax的影響分別次之；然后是PARmax和PARmin；最后是HMCR。根據(jù)圖3選取參數(shù)HMS為20；BWmin和BWmax分別為0.05和0.9；PARmax和PARmin分別為0.8和0.05；HMCR為0.99。

3 實(shí)例結(jié)果對比分析

本文采用文獻(xiàn)[1]中的20個(gè)測試組數(shù)據(jù)。利用Matlab編程實(shí)現(xiàn)應(yīng)用改進(jìn)的和聲搜索算法求解越庫系統(tǒng)數(shù)學(xué)模型。20個(gè)測試組用IHS算法、HS算法和TS算法各計(jì)算10次，分別得到每組數(shù)據(jù)的試驗(yàn)最優(yōu)解、試驗(yàn)最差解和試驗(yàn)平均解。應(yīng)用枚舉法求解20組數(shù)據(jù)最優(yōu)解與最差解。如表3所示，根據(jù)枚舉法對比TS算法、HS算法和IHS算法，3種算法的試驗(yàn)最優(yōu)解為最優(yōu)解的數(shù)量分別為12、17、19；試驗(yàn)最差解的均值分別為304.1、312.7和409.4，其中IHS算法的試驗(yàn)最差解整體小于HS算法和TS算法的試驗(yàn)最差解；試驗(yàn)總平均值分別為310.065、277.915和273.385，其中IHS算法的試驗(yàn)總平均值整體小于HS算法和TS算法的試驗(yàn)總平均值。

表3 算法的試驗(yàn)解比較Table 3 Comparison of experimental solutions

4 結(jié)束語

本文介紹了一種新穎的配送方式——越庫作業(yè)，研究了只有一個(gè)入庫門和一個(gè)出庫門且?guī)в袝捍鎱^(qū)的越庫中心的作業(yè)車輛調(diào)度問題。從越庫作業(yè)的總完工時(shí)間出發(fā)，以運(yùn)作時(shí)間最小化為目標(biāo)，建立了越庫車輛排序問題的數(shù)學(xué)模型。為了減小計(jì)算中延遲時(shí)間的影響，將總運(yùn)作時(shí)間的求解轉(zhuǎn)化為計(jì)算臨時(shí)庫存中存儲的物品數(shù)量。采用改進(jìn)的和聲搜索算法求解問題的近似最優(yōu)解，與基本和聲搜索算法和禁忌搜索算法進(jìn)行比較，結(jié)果表明：改進(jìn)的和聲搜索算法在最優(yōu)解數(shù)量與解整體優(yōu)越性方面均優(yōu)于基本和聲搜索和禁忌搜索算法。

參考文獻(xiàn)：

[1] Yu W,Egbelu P J. Scheduling of inbound and outbound trucks in cross docking systems with temporary storage[J]. European Journal of Operational Research,2008,184(1):377-396.

[2] Yu W. Truck scheduling for cross docking systems with multiple receiving and shipping docks[J]. International Journal of Shipping and Transport Logistics,2015,7(2):174-196.

[3] Madani-Isfahani M, Tavakkoli-Moghaddam R, Naderi B. Multiple cross-docks scheduling using two meta-heuristic algorithms[J]. Computers & Industrial Engineering,2014,74:129-138.

[4] Mohtashami A. Scheduling trucks in cross docking systems with temporary storage and repetitive pattern for shipping trucks[J]. Applied Soft Computing,2015,36(C):468-486.

[5] Arabani A R B, Ghomi S M T F, Zandieh M. Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage[J]. Expert Systems with Applications,2011,38(3):1964-1979.

[6] Soltani R, Sadjadi S J. Scheduling trucks in cross-docking systems: a robust meta-heuristics approach[J]. Transportation Research Part E: Logistics and Transportation Review,2010,46(5):650-666.

[7] Assadi M T, Bagheri M. Scheduling trucks in a multiple-door cross docking system with unequal ready times[J]. European Journal of Industrial Engineering,2016,10(1):103-125.

[8] 繆朝煒，蘇瑞澤，張杰. 越庫配送車輛調(diào)度問題的自適應(yīng)遺傳算法研究[J]. 管理工程學(xué)報(bào),2016,30(4):166-172.

Miao Zhao-wei,Su Rui-ze,Zhang Jie. An adaptive genetic algorithm for the truck scheduling problem in the crossdock distribution center[J]. Journal of Industrial Engineering and Engineering Management,2016,30(4):166-172.

[9] Geem Z H,Kim J H,Loganathan G V. A new heuristic optimization algorithm: harmony search[J]. Simulation,2001,76(2):60-68.

[10] Mahdavi M, Fesanghary M, Damangir E. An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation,2007,188(2):1567-1579.

[11] Valaei M R, Behnamian J. Allocation and sequencing in 1-out-of-N heterogeneous cold-standby systems: multi-objective harmony search with dynamic parameters tuning[J]. Reliability Engineering & System Safety,2016,157:78-86.