改進的和聲搜索算法求解帶時間窗的物流運輸調度問題

廣東工業大學自動化學院 李旭陽 蔡延光

針對帶時間窗的物流運輸調度問題，設計一種改進的和聲搜索算法。該算法利用類電磁機制算法改進和聲搜索的隨機產生規則，并且使用了和聲記憶庫擾動策略和2-Opt局部搜索策略提高算法性能。結果表明：相比基本和聲搜索算法及其他啟發式算法，所設計的算法具有更好的收斂速度和收斂精度。

物流運輸調度問題國外一般稱為車輛路徑規劃問題（Vehicle Routing Problem，VRP），該問題自提出以來就一直是研究的熱點。戚遠航等提出了一種雙層變鄰域蝙蝠算法求解帶容量約束的物流問題，該算法采用變鄰域局部搜索策略加強算法的尋優能力，很好的解決了帶容量約束的物流運輸調度問題；鄧麗娟等提出了一種混合蟻群算法求解帶時間窗的VRP，該算法探索兩個目標函數，獲得了很好的實驗效果；蔡延光等提出了一種帶遺傳算子的自適應蟻群算法，求解帶軟時間窗的車輛路徑問題。

2001年Geem ZW等人源于音樂的創作，提出了和聲搜索（Harmony Search，HS）算法，一種新的元啟發算法；高立群等把粒子群算法與和聲搜索算法相結合，提出自適應和聲粒子群搜索算法；歐陽海濱等研究了在非對稱區間內，證明了和聲搜索算法的參數與即興創作過程的探索之間的關系，從而證明了算法的迭代收斂性，提出了一種改進的和聲搜索算法；王艷等采用改進的和聲搜索算法，用一種離散編碼方式，解決了車間調度問題。本文針對帶時間窗的物流運輸調度問題，設計了改進的和聲搜索算法。該算法利用類電磁機制算法改進和聲搜索算法的隨機生成的規則，并且使用了和聲記憶庫擾動策略和2-Opt局部搜索策略提高算法性能。實驗結果表明：該算法比基本和聲搜索算法有更好的收斂速度和精度。

1 問題描述

帶時間窗物流運輸調度(Vehicle Routing Problem with Time Windows，VRPTW)問題可描述為：某車場需要為N個客戶提供貨物配送服務，并要求在[Ei,Li]所表示的時間窗內將貨物送達，其中Ei表示客戶i要求的最早貨物到達時間，Li表示客戶i要求的最晚貨物到達時間。若未按時送達則增加相應的時間懲罰成本，用C1（單位：元/min）表示早到的懲罰系數，C2（單位：元/ min）表示晚到的懲罰系數；tik表示車輛k到達客戶i的實際時間；UTik表示運輸車輛k在客戶i卸貨所需的時間；RTijk表示運輸車輛k從客戶i行駛到客戶j所需的時間；每條客戶的貨物需求量為qi(i=1,2,3,...N)，該倉庫有K輛車且車型相同，車的最大載重為W，客戶i到客戶j的距離為dij，其中i=0表示倉庫，定義決策變量：，當k經過客戶i駛向客戶j時為1，否則為0，；，當客戶i由車輛滿足時為1，否則為0。并建立數學模型如下：

目標函數：

約束條件：

式(1)為VRPTW的目標函數，式(2)(3)表示封閉式的車輛路徑規劃，式(4)(5)(6)表示每條客戶僅要一輛車完成任務，式(7)(8)表示車的最大容量和行駛限制，式(9)表示參與任務的車輛數不能超過車場所擁有的車輛總數，式(10)(11)表示保證運輸車輛在配送貨物在時時間上的連續性，避免時間沖突。

2 算法設計

2.1 和聲搜索算法

2.1.1 基本變量

（1）和聲記憶庫大小HMS：指和聲記憶庫中和聲的數量。

（2）記憶庫取值概率HMCR：在每次迭代中，有一組和聲將從庫中被選擇為一個新和聲的特定概率。

（3）微調概率PAR：選擇一組和聲需要用微調概率判斷是否要微調。如果PAR值過小，算法的優化范圍減小，而PAR值過大，搜索算法會變成隨機選擇。

（4）音調微調帶寬 bw：指微調時的調整幅度。

（5）創作的次數 Tmax：即算法的迭代次數。

根據相關研究，算法參數為HMS值可取10～50，HMCR可取0.70～0.95，PAR可取0.20～0.50。

2.1.2 和聲搜索算法步驟

Step 1：初始化算法，指定和聲搜索算法各項基本參數：HMS、HMCR、PAR、bw、Tmax。

Step 2：根據HMS生成和聲記憶庫，并計算目標函數的值，組成如下所示的和聲記憶庫HM：Step 3：產生新的和聲X'=[x'1,x'

2,...,x'N]。新的和聲通過三種方式生成：①由HM隨機產生。②音調微調。③隨機選擇，其生成過程可表示為：

IF rand(0,1)

ELSE

END IF

其中，rand(0,1)是在0和1之間的隨機變量值，xi,min,xi,max分別是決策變量xi的最小、最大值。若新的和聲來自和聲記憶庫HM，則用微調概率來判斷是否要微調規則：

Step 4：更新記憶庫。若Step3得到的一組新的和聲比HM中最差和聲要好，則用新和聲替換最差和聲。

Step 5：重復Step3和Step4，直到滿足最大迭代次數Tmax。

2.2 類電磁機制算法

在物理學中，帶電粒子之間存在著相互吸引或相互排斥的庫侖力。Birbil和Fang受到這一現象的啟發，于2003年提出了類電磁機制（Electromagnetism-like Mechanism，EM）算法，并且用該算法成功解決了無約束優化問題。

EM算法將待優化問題的每個解模擬為電磁場中的帶電粒子，并根據解的適合度來確定每個粒子的電荷。每個帶電粒子會被其他粒子吸引或排斥，這取決于它們所攜帶的電荷和它們之間的距離。根據粒子受到的合力的大小，粒子會沿著合力的方向移動一定的距離。由于算法是對電磁原理的一種類比，兩者之間并不完全相同，因此稱為類電磁機制。

EM算法主要由以下四個步驟組成：

（1）初始化。將一定數量的粒子隨機、均勻地分布在待優化問題的可行解域里，然后計算出每個粒子所在位置的適應度值，并將適應度最好的粒子的位置記為Xbest。

（2）局部搜索。EM算法中的局部搜索是指以粒子當前的位置為中心，按照一定的步長搜索解空間的每個維度。如果找到了更好的解決方案，搜索將被終止，并執行下一步。

（3）計算合力。計算合力是為了將EM算法的局部搜索能力和全局搜索能力相結合，提高算法的求解能力，并為下一步更新粒子位置提供相應的信息。

粒子i所帶電荷量的多少qi決定了粒子i所受的庫倫力的大小，電荷量qi的計算公式為：

式中，n為待優化問題的維度，m為解空間中帶電粒子的個數。由式(16)可知，適應度越好的粒子所帶的電荷數越大，對其他帶電粒子的吸引或排斥能力也就越強。一個粒子受另一個粒子的庫侖力的方向由兩個粒子的適應度好壞決定。在計算粒子i受到解空間中其他每個粒子的力的大小和方向后，即可通過累加方法得到作用在粒子i上的合力Fi：

（4）移動粒子

計算完合力Fi之后，粒子i將沿著Fi的方向移動，移動后粒子i的位置為：

式中，步長λ在[0,1]上服從矩形分布；Range為一個向量，向量中的每一個分量表示粒子在解空間的對應維度上能夠移動的距離。同時，為了保證每個粒子移動后的位置不會超出解空間的范圍，EM算法對粒子所受的合力做了無量綱化處理。

這樣，粒子的位置得到更新，也就完成了EM算法的一次迭代。

2.3 和聲記憶庫擾動策略

當和聲搜索算法運算一定的次數后，和聲記憶庫中的和聲多樣性水平降低，甚至出現大部分和聲的適應度都相等的情形。此時，算法將會限入局部最優解。這個時候如果能夠對和聲記憶庫中的一部分和聲進行擾動，以提高和聲記憶庫的和聲多樣性水平，將會有利于算法跳出局部最優解繼續尋優，從而增加得到全局最優解的概率。

2.3.1 擾動時機

和聲記憶庫的擾動需要在算法迭代至一定次數，且和聲記憶庫中的和聲相似程度達到一定閾值時進行。設和聲記憶庫大小為HMS，算法最大迭代次數為Tmax，當前迭代次數為gn，則進行和聲記憶庫擾動的時機需要同時滿足如下兩個條件：

②和聲記憶庫連續t次迭代未更新：

2.3.2 擾動步驟

當滿足擾動時機時，擾動步驟如下：

Step1：對HM中的和聲按照適應度值排序，隨機選取(HMS/2)組非最優和聲；

Step2：對Step1中選擇的(HMS/2)組非最優和聲進行混沌擾動；

Step3：計算生成的新和聲的適應度值，若優于和聲記憶庫中的最差和聲，則用新和聲替換最差和聲，更新和聲記憶庫；否則需要重新擾動。

2.4 局部搜索策略

在求解物流運輸調度問題時，常用的局部搜索算法主要有2-Opt搜索，0-1搜索和1-1搜索等算法。本文采用2-Opt方法進行局部搜索。一次2-Opt操作可描述為：在一條路徑中隨機選擇兩個點i和j，將i-1與j連接，i與j+1連接，并將i和j之間的路徑反向，若2-Opt操作后的路徑長度比操作之前的長度小，則更新路徑。2-Opt操作示意如圖1所示。

圖1 2-Opt操作示意圖

2.5 編碼策略

為實現VRPTW路線的解空間和和聲搜索算法的搜索空間的解空間之間的轉換，本文采用序列號編碼方案。對于n個客戶，k輛車的車輛路徑規劃問題，采用個n+k-1個的整數來編碼，編碼中的n位表示客戶，k-1位為車輛號，0表示配送中心。例如對于10個客戶，3輛車的車輛路徑規劃問題，有如下編碼：3，10，9，11，5，8，7，2，12，6，4，1，其中11和12為車輛標識編碼，該編碼對應和聲庫里面的一個和聲。該組編碼表示第一輛車行車路徑為0－3－10－9－0，第二輛車行車路徑為0－5－8－7－2－0，第三輛車行車路徑為0－6－4－1－0。這些編碼就組成了和聲記憶庫，接下來就是對庫中編碼尋找最優解的過程。

2.6 算法步驟

將改進策略整合到基本的和聲搜索算法，改進的算法的具體步驟如下：

Step1：初始化算法各項參數；生成和聲記憶庫，并計算每個和聲的適應度值，采用車輛的行駛總路程與時間窗懲罰之和的倒數作為適應度值，適應度越大，表示和聲越優。

Step2：生成新和聲；

Step2-1：若生成的隨機數rand(0,1)

Step2-2：以當前和聲記憶庫中的所有和聲作為類電磁機制算法中的粒子，以HM中的最優和聲作為最優粒子Xbest，根據式(16)與式(17)計算所有粒子的電荷量以及每個粒子受到的合力，并結合式(18)計算每個粒子移動后的位置，選擇最優的粒子賦值給Xnew，轉Step3；

Step2-3：若生成的隨機數rand(0,1)

Step3：2-Opt操作，將迭代次數gn加1。對Xnew進行一次2-Opt操作，若操作后路徑長度變短則更新Xnew；

Step4：更新和聲記憶庫。計算Xnew的適應度值，如果優于庫中的最差和聲，則使用Xnew替換最差和聲，否則，庫不變；

Step5：判斷是否滿足擾動條件，若滿足則根據擾動策略對HM進行擾動，否則轉Step6；

Step6：判斷gn是否達到最大迭代次數Tmax，若沒有則返回Step2，否則轉Step7；

Step7：輸出適應度最好的和聲并輸出其對應的適應度值，該和聲即為最優解。

3 實驗與分析

3.1 實驗數據

為驗證算法的有效性，假設一個配送中心需要為14個客戶配送貨物，客戶坐標隨機產生，各客戶所需的貨物量、時間需求如表1所示。設定車場坐標(0,0)，編號為0擁有4輛運輸車輛，每次最大載重量為15t，配送中心于上午8:00開始為各客戶運輸，運輸車輛勻速行駛，車速為2020km/h，運輸車輛早到的懲罰系數為2元/min，晚到的懲罰系數為5元/min。

表1 客戶坐標、需求量與時間窗

本章和聲搜索算法參數設置為：HMS=20，HMCR=0.75，PAR=0.3，Tmax=200。

3.2 實驗結果與分析

算法運行50次取平均結果，仿真結果與基本和聲搜索算法及其他三種算法的對比如表2所示，最優配送線路如表3所示，最優配送軌跡圖如圖2所示。

表2 結果對比

表3 最優配送線路

圖2 最優配送軌跡圖

由表2中的數據可知，基于類電磁機制的和聲搜索算法因為引入了類電磁機制算法加快了收斂速度，并使用了和聲記憶庫擾動策略和2-Opt局部搜索策略能夠有效的跳出局部最優解，提高了算法的局部搜索能力，所以在50次運算后，所得到的平均里程、平均搜索時間以及平均時間窗懲罰都要優于基本和聲搜索算法所得到的平均結果，并且優于其他幾種算法。

算法在迭代完成后，得到最優配送路徑圖，配送車輛行駛路徑總長度為91.65km，總時間窗懲罰為143元。其中，編號為1、2和4的配送車輛所執行的配送任務中，分別出現59元、32元和52元的時間窗懲罰，而編號為3的運輸車輛所執行的配送任務沒有時間窗懲罰，即不存在早到和遲到的情況。由此可見，本文提出的改進的和聲搜索算法能夠有效地解決帶時間窗的物流運輸調度問題。

總結：本文設計了改進的和聲搜索算法來解決帶時間窗的路徑規劃問題，該算法通過類電磁機制算法改進和聲搜索算法的隨機產生規則，并且使用了和聲記憶庫擾動策略和2-Opt局部搜索策略提高算法的搜索能力，性能得到了提高，具有更快的收斂速度和更高的精度。本文所提的模型在很大程度上貼合了實際情況，但是車輛過少，下一步準備研究多車場下的模型，提出一種適合求解多車場下物流運輸調度問題的算法。

基金項目：國家自然科學基金（61074147）；廣東省自然科學基金（S2011010005059）；廣東省教育部產學研結合項目（2012B091000171，2011B090400460）；廣東省科技計劃項目（2012B050600028，2014B010118004，2016A050502060）；廣州市花都區科技計劃項目（HD14ZD001）；廣州市科技計劃項目（201604016055）；廣州市天河區科技計劃項目（2018CX005）。