物流中心車輛調度問題的算法研究

陳向陽

（安慶醫藥高等專科學校，安徽 安慶 246003）

物流中心車輛調度問題的算法研究

陳向陽

（安慶醫藥高等專科學校，安徽 安慶 246003）

對物流中心的貨物進行合理的規劃和調度，對于物流成本的降低、物流業的持續發展起到了重要的作用。文章分析和比較各種貨物調度算法，重點是對遺傳算法和退火算法這兩種生物仿真算法進行分析和研究，并比較兩種算法的性能。

物流；貨物規劃；遺傳算法；退火算法

1 問題描述

物流產業的發展對于促進經濟的發展起到了一個良好的潤滑作用，信息化物流早就逐漸流行，客戶點的增加，使得許多依舊依賴人工經驗管理物流的配送中心“力不從心”。如何更好的解決車輛調度及路線安排，成為管理者的一個重要研究課題，但這一問題又不是一個單一的問題，它是一個VRP問題[3]，這一問題中總是以成本最低為目的。圖1所示是一個簡單的VRP問題。

圖1 簡單的VRP圖

2 建立模型

結合上面對問題的描述，設計了一個以n輛車和m個客戶為例的最小成本函數fun：

其中aij表示車輛k從客戶i到客戶j的所有運輸成本，cijk等于1或0，如果從客戶i到客戶j運輸車輛是車輛k時，其值為1，否則為0。piti為懲罰函數，車輛在時間ti到達客戶i時所對應的懲罰成本。若設A={1,2,…,m},A0=A∪{0},其中1,2,…,m表示m個客戶的編號依為客戶1到客戶m，0表示配貨中心。 B={1,2,…,n},那么（*）中的 i和 j屬于 A0,k屬于B，而且（*）要滿足以下的約束條件。

其中，aik的值等于0或1，當車輛k為客戶i服務時，aik=1，否則 aik=0，其中 i∈A0,k∈B

其中，ei表示客戶i所需貨物量，aik意義同上，Ek表示車輛k的最大裝載量。（2）意味著車輛k服務的所有客戶的貨物量之和不能超過自身的最大裝載量。

上面（3）式和（4）式的含義指的是：車輛 K為任一客戶服務時，在到達該客戶之前，事先一定會為另一個客戶服務，即先到達該客戶處（至少會先經過配送中心）。

其中，T0k表示車輛k要求返回到配送中心的時間，tij表示車輛k從客戶i到客戶j的行車時間，wik表示車輛k在客戶i處停留的時間，Tk表示車輛k從配送中心出發再返回到配送中心的總耗時不超過事先預定的值。

其中：tik表示車輛k從配送中心出發到達客戶點i時所耗時間，wik是車輛k在客戶點i處停車時間，tij是車輛k從客戶點i到客戶點j的時間，M是一個任意大的正數，tj表示車輛k到達客戶點j時客戶是要求的時間段（是一個具體的時間范圍）。

3 矩陣編碼的GA求解

第一步：GA的二進制編碼

對染色體的確定以及如何處理該染色體的二進制編碼是Genetic Algorithm的首要問題，這一問題對應到配送中心對車輛如何進行調度的問題時，我們可以將aik看作染色體，所以求出一個aik就意味著求出了一條可能用來做為復制的染色體，也即是這有可能是一種可行的分配車輛的方案，aik求出來以后，就可以用二進制數據構成的矩陣進行該染色體的基因編碼。假設有這樣一個二進制構成的布爾陣：

該布爾矩陣表示的意思是：一共有3輛車參加了本次的送貨任務，共有12個客戶需要送貨，其中第一輛貨車負責客戶1、客戶4、客戶5和客戶10的送貨任務；第二輛貨車負責客戶2、客戶6、客戶7和客戶11的送貨任務；第三輛貨車負責客戶3、客戶8、客戶9和客戶12的送貨任務。

第二步：適應度函數的定義

在Genetic Algorithm中，適應度函數定義的好壞將會直接影響最終所求解是否真正接近最優解，甚至是真正的最優解。在對個對進行培養時，首先看看它是不是能充分滿足適應度函數，如果是，則優先考慮它。在本文所述的問題中，當個體i所對應的適應度函數值Fi越小，就說明當前所選擇的這一個個體的適配值越高。對于其中的任意一個個體i，我們定義它的適配值函數如下：

所以，目標函數F為：F=min(Fi) i∈A

第三步：初始染色體種群的生成

首先，定義幾個變量：在每一代染色體的群體中，記下其種群數量，并用變量S表示；變量G表示遺傳世代，并將G的值初化為1；變量Pc記為交叉概率；Pm記為變異概率。aik的值（車輛分配方案）隨機生成，并將約束條件⑴和⑵不滿足的染色體淘汰，一直做到這一代染色體群的種群數目到N條為止。但N的值取得不應太或太小，太大不僅增加了計算量，而且迭代解也不能有效地獲得。太小分配方案的多樣化又不能滿足。

第四步：求解（啟發式算法）

前面的公式已經告訴了cijk含義，它的值要么是1，要么是0，當從客戶i到客戶j的運輸車輛是車輛k時，其值為1，否則為0。所以cijk的值實際上表示的是配送中對車輛k的排序問題，當然車輛k的排序也是需要滿足所提出的約束條件的，也就是要對車輛k服務的客戶群集合Ak中的各陣車輛進行排序，求出適配值（假設為fk）最小的車輛k，使得文中要求的約束條件得到滿足。即：

滿足約束條件：

個體染色體的適配值Fi的求法可以使用啟發式算法，這一點在參考文獻[4]和文獻[2]中都闡述得十分清楚，引用到我們文中的問題就可以歸納為：按照客戶要求的時間，對車輛k所服務的客戶群進行升序排序，在排序過程中，假充出現了要求送貨時間相同的客戶，可以按區域進行升序排序，然后舍棄不能滿足（3.2.1）到（3.2.5）的解，對每個 aik，我們在求出了它對應的cijk后，即可計算該個體對應的Fi：

第五步：復制與選擇合適的個體

在第四步中，我們可以求出每個個體i的Fi，這時可以求出Fi/(F1+F2+…Fm)的值，該值越小，則意味著該個體i被選擇出來進行復制的概率（假設記為Pi）越大；該值越大，則意味著該個體i被選擇出來進行復制的概率越小，甚至會直接淘汰。依次類推，一直做到這一代染色體總的種群數目為N。

第六步：交叉操作函數（overlapping()）

新的車輛分配方案很難因為第五步操作就輕易獲得，實際上，對這一代群體進行適當的交叉操作（overlapping()）往往可以“誕生”出更加優秀的個體。

具體的做法是：交換前面步驟所得的布爾矩陣中的某些行或列，會生成兩個新的布爾陣。

交叉概率（Pc）選擇的是否合適對于算法收斂速度的加快影響很大。Pc的大小決定了新個體的優劣，從理論上來說，要使新個體越優秀，Pc就要求越大；當然Pc越大，對新個體的要求就越高，事實上，本例中Pc的值設置為0.75比較適宜。

第七步：變異操作函數（variation()）

作為overlapping（）函數的補充，變異操作variation（）通常用來克服在“求解過程中出現的早熟或是求解時陷入局部最優解”，它可以產生多種多樣的車輛分配方案。影響算法的性能也主要取決于變異概率Pm的取值，當變異概率過大，會明顯增加求解的時間，但是減少了算法收斂于局部最優解的可能性；反之，當變異概率達小，雖然會縮短求解的時間，但是好外是算法收斂于全局最優解的可能性就增加了。在本文中，Pm取值為0.3比較合適，變異操作variation（）所使用的是采取反順序變異法來改變布爾矩陣中的某些二進制位（0與1變換），從而產生新的布爾矩陣。

第八步：合理的設計算法停止準則

將不符合約束條件（3.2.2）與（3.2.3）的染色體淘汰。如果|Fg－Fmin|＞ε，則將該染色體保留下來，否則繼續在這一代染色體群中繼續選擇Fi值較小的個體，求出本問題中的aik以及與之相對應的cijk。

本算法的主要優點：（1）因為遺傳算法具有不需要求導，而且并發執行等優點，所以能夠在比較短的時間內求出全局最優解。（2）算法中所采用的適應函數起到了十分良好的優化作用，同時它對已經存在過的模型進行了針對性的設計和規劃（3）對于交叉及變異算子的選擇，本算法根據原有的經驗及反反復復的測算，也起到了非常好的優化效果，而且對求解全局最優的可靠性也起到了很好的保證。

本算法的主要不足：（1）算法模型中沒有考慮到車輛k在執行完一次送貨任務后返回配送中心的時間比較早，完全本有時間去執行第二次送貨任務。對于配送中心來說就有可能造成了一部分車輛的能量浪費。（2）在車輛實際貨運的過程中，因為客戶點的位置不同，地域的不同，使得貨運成本及人力資源的消耗也有可能不同，甚至并異很大。（3）方案一所采用的算法中使用了二進制編碼，這一點于規模比較小的調度規劃，簡單方便，也不用占有較大的存儲空間，但如果問題的規模到了一定數量級時，將會成指數增長。

4 改進的模擬退火算法

在常用的模擬退火算法當中，總是預先設定一個停止準則S，讓算法在此終止。可以賦予該準則各種各樣的選擇，比如說，可讓控制參數t小于一個充分小的正數R；可讓兩個相繼的Mapkov鏈所得到的解的差的絕對值小于某個正數R等。但是在模擬退火算法中，其搜索過程是任意的、隨機的；并且在控制參數t的值較大時，它可以接受一部分惡化的解，而隨著控制參數t的衰減，惡化的解被接受的概率減小一直到趨向于零。另外，有一些當前解要想達到最優解時，它必須經過暫時的惡化的“山脊”。所以說，算法中假設的這些準則都沒有辦法保證其最終所得解就一定是最優的解。為了解決這一問題，在算法中我們增加一個“記憶器”，使得它能夠記下在搜索過程中所遇到過的所有的最好的結果，在整下退火過程全部結束時，將所求得的“最優解”和“記憶器”中的解比較，從而取得真正的最優解。算法經過這樣的修改，在很多情況下都將會提高算法的質量。

通過記憶器的設置，可以得到一種改進的模擬退火算法。

5 改進的遺傳算法

傳統的遺傳算法在求物流配送路徑優化問題最優解時很容易陷入局部最優解，而退火算法恰恰能夠很好的彌補這一缺陷，將模擬退火算法和遺傳算法給合在一起，再在這種混合算法中增加一個記憶裝置，就構成了一種混合的算法，本文稱之為遺傳模擬退火算法。這種算法的特征是：它擴大了遺傳算法原有的搜索領域，在概率滿足一定條件時可以暫時接受一些惡化解；同時利用“記憶器”保證了在一定的停止準則下所得到的最終解至少是搜索過程中曾經求得的所有解中的最優解。傳統的遺傳算+模擬退火算法+“記憶器”構成所謂的遺傳模擬退火算法。

算法實現

⑴變量及函數的定義。變量Tk：溫度，初始溫度T0；由N條染色體組成的種群集合，用函數max pop()表示，由pop(k)返回下一代種群集中的優生染色體，其中k的初值為0；目標函數記為fi()，它表示染色體i的目標函數值；當k=0時，求出fi(T0)，意為染色體i在初始溫度T0時的目標函數值，其中i是當代種群集中的一條染色體，記作i∈pop(k)。每次求出一個最小的fi()值，都記下i：ii=i，并記下此時的函數值：ff=fi(Tk)。

⑵在第1步中，每次求出一條染色體ii及其相應的目標函數值ff以后，判斷一下它們是否滿足規定的結束條件，一旦條件成立，則表示ii為“優生”染色體，其對應的值ff亦為當前的一個最優解。如果規定的結束條件得不到滿足，就在群體pop(k)的染色體i(i∈pop(k))的某鄰域中隨機選擇一個狀態j(j∈N(i)),給定模擬退火算法的概率：Aij(Tk)=min{1,exp((fi(Tk)－fj(Tk))/Tk)}并以此作為一個判定條件看j能否被留下來，此處的fj(Tk)表示的是狀態j在溫度Tk時的目標值。經過N次迭代后產生新的群體（N為初始種群規模），記為newpop1。

⑶在新一代種群newpop1中求出適應度函數：fi(Tk)=exp((fmin－fj(Tk))/Tk)。 此處的 fmin表示的意思是本代種群集中染色體所對應的目標函數值中最小的函數值。由fi(Tk)決定的概率依次產生新一代染色體組成的種群集newpop2。

⑷根據第三章講到的Genetic Algorithm中的方法，進行Cross()操作，可以得到下一代種群集，本算法中用overlappingpop表示，然后經過variation()后產生新的群體,本算法中用variationpop。

⑸k++;pop(k+1)=variationpop;求出 fi(Tk)并找到MIN f（記為f,染色體I對應的最小目標函數值），if(f＜ff){ii=I;ff=f;Tk+1=β*Tk;k++}(Tk+1=β*Tk表示溫度衰減)，轉2。

6 實驗結果對比

實驗一:實驗的初始數據取自文獻[2]，見表6.1。

按照各個倉庫的貨物需求量，求出所需要的車輛數量：n=[17.82/(0.85*8)]+1=3，并且得到最終的染色體結構：032405061780。即：

子路徑 1：0→3→2 →4→0

子路徑 2：0→5→0

子路徑 3：0→6→1→7→8→0

在本文提出的算法中，取T0為10，β取值0.85,最終得到的染色體結構是：060417508320。即：

子路徑 1：0→6→0

子路徑 2：0→4→1→7→5→0

子路徑 3：0→8→3→2→0

【結論】：文獻[2]中的進化代數為50，但是本算法的進化代數大大縮短了，僅為20，這就大大節約了運算時間。

實驗二：假設：群體規模取值100，進化代數分別設置為 20、50、100，衰減系數設為 0.85，初始溫度為10。得到的兩種遺傳算法結果如表6.2和6.3。

表6.2 傳統遺傳算法結果

從這些實驗數據可以看出，與傳統的遺傳算法相比較，本文所述具有如下優點：

⑴整體算法的收斂速度提高了。

⑵理論上可以保證所求解全局最優。

⑶本文所述算法使用用自然數作為染色體中基因的編碼，這不僅使得染色體可以表示的客戶信息更多，而且所需存儲空間也相對較小。

⑷在獲得相同或相近結果時，因為進化代數的明顯減少，使算法運算的時間減少了。

⑸隨著進化代數的變化，最優解的獲得越來越明顯。

[1]2009－2010年中國物流行業市場研究與發展預測報告[EB/OL].（2011－10－25）.http://www.zikoo.con/reports/4fjizi62q.html.

[2]潘正君,康立山,陳毓屏.演化計算[M].北京：清華大學出版社，2003.

[3]林巖,胡祥培,王旭茵.物流系統優化中的定位—運輸線路安排問題（LRP）研究評述[J].管理工程學報，2004 年，17（4）：45－48.

[4]Gilbert Laporte.The vehicle routing problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,59:345－358.

[5]Ochi,Luiz S.Vianna.A Parallel Evolutionary Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet[J].Future Generation Computer System,1998,14(5/6):285–292.

[6]姜大立,楊西龍,杜文，等.車輛路徑問題的遺傳算法研究[J].系統工程理論與實踐,1999,19(6):40－45.

[7]薛荔,袁際軍.現代物流信息管理中配送車輛路線優化研究[J].武漢理工大學學報,2006,20(5):64－67.

[8]張雪東,季一木.基于模擬退火遺傳混合算法的物流中心選址問題研究[J].電腦開發與應用,2006,16(6):4－6.

[9]郭茂祖,王亞東,孫華梅,等.基于Metropolis的Q—學習算法研究[J].計算機研究與發展,2006,39（6）：92－93.

[10]Montane F A T,Galvao R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick－up and delivery service[J].Computers&Operations Research,2006,33(3):595－619.

O14

A

1674-1102(2011)06-0028-04

2011-11-17

陳向陽（1971-），男，安徽太湖人，安慶醫藥高等專科學校講師，碩士，研究方向為智能計算。

[責任編輯：曹懷火]