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

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

0 引 言

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

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

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

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

1 描述及模型設計

1.1 問題描述

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

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

1.2 數(shù)學模型

建立模型前需進行如下假設：

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

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

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

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

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

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

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

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

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

本文以越庫作業(yè)完工時間T為目標函數(shù)建立數(shù)學模型，首先對建模所需數(shù)學符號做如下定義：T為總運作時間；ci為集貨車輛i進入集貨平臺的時刻；Fi為集貨車輛i離開集貨平臺的時刻；dj為送貨車輛j進入裝貨平臺的時刻；Lj為送貨車輛j離開裝貨平臺的時刻。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為因裝卸貨車輛交替所耽擱的時間；V為物品從集貨平臺到裝貨平臺移動時間；xijk為集貨車輛i轉移物品k到送貨車輛j的數(shù)量；M為較大正實數(shù)。

目標函數(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ù)量越少，總越庫作業(yè)所需時間越少。儲存在臨時庫存中的物品數(shù)量多少由集、送貨車輛之間的排序引起，因此集、送貨車輛排序的優(yōu)劣可以通過臨時庫存中物品數(shù)量的多少判斷。

目標函數(shù)P1為：

(14)

(15)

(16)

(17)

(18)

2 改進的和聲搜索算法

2.1 和聲搜索算法求解過程

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

2.2 改進的和聲搜索算法

基本的和聲搜索算法其參數(shù)是固定的，但參數(shù)在不同迭代時期有不同的表現(xiàn)形式。例如，在迭代初期較大的BW搜索較優(yōu)結果的能力較好，但在迭代末期較小的BW有更好的表現(xiàn)[10,11]。為提高HS算法的搜索能力，IHS算法在音調調整步驟對PAR和BW做動態(tài)調整。BW和PAR的計算過程如式(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ù)設定

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

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

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

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

圖3 IHS參數(shù)的信噪比主效應圖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 實例結果對比分析

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

表3 算法的試驗解比較Table 3 Comparison of experimental solutions

4 結束語

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

參考文獻：

[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] 繆朝煒，蘇瑞澤，張杰. 越庫配送車輛調度問題的自適應遺傳算法研究[J]. 管理工程學報,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.