基于改進和聲搜索算法的越庫車輛排序

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

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

0 引 言

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

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

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

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

1 描述及模型設計

1.1 問題描述

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

圖1 越庫作業流程圖Fig.1 Flow chart of cross docking

1.2 數學模型

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

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

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

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

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

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

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

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

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

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

本文以越庫作業完工時間T為目標函數建立數學模型，首先對建模所需數學符號做如下定義：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為集貨車輛數；S為送貨車輛數；N為物品種類數；rik為最初裝載在集貨車輛i中的k物品總數；sjk為最初送貨車輛所需要k物品的總數；D為因裝卸貨車輛交替所耽擱的時間；V為物品從集貨平臺到裝貨平臺移動時間；xijk為集貨車輛i轉移物品k到送貨車輛j的數量；M為較大正實數。

目標函數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)

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

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

目標函數P1為：

(14)

(15)

(16)

(17)

(18)

2 改進的和聲搜索算法

2.1 和聲搜索算法求解過程

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

2.2 改進的和聲搜索算法

基本的和聲搜索算法其參數是固定的，但參數在不同迭代時期有不同的表現形式。例如，在迭代初期較大的BW搜索較優結果的能力較好，但在迭代末期較小的BW有更好的表現[10,11]。為提高HS算法的搜索能力，IHS算法在音調調整步驟對PAR和BW做動態調整。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為迭代次數；NI為總迭代次數。

2.3 參數設定

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

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

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

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

圖3 IHS參數的信噪比主效應圖Fig.3 Main effects plot for SNR of IHS factors

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

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

3 實例結果對比分析

本文采用文獻[1]中的20個測試組數據。利用Matlab編程實現應用改進的和聲搜索算法求解越庫系統數學模型。20個測試組用IHS算法、HS算法和TS算法各計算10次，分別得到每組數據的試驗最優解、試驗最差解和試驗平均解。應用枚舉法求解20組數據最優解與最差解。如表3所示，根據枚舉法對比TS算法、HS算法和IHS算法，3種算法的試驗最優解為最優解的數量分別為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 結束語

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

參考文獻：

[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.