遺傳算法在物流配送中心選址

1、遺傳算法在物流配送中心選址和車輛調(diào)度問題中的應(yīng)用物流是一個非常具有實際意義的問題，很長一段時間都是諸多學(xué)者研究的熱點。對于物流中的諸多問題，特別配送中心選址和車輛調(diào)度問題，他們應(yīng)用各種優(yōu)化方法對其進(jìn)行規(guī)劃，做了多方面的研究。配送中心選址和車輛調(diào)度問題對一個企業(yè)來說是至關(guān)重要的，解決此問題主要包括有：啟發(fā)式算法，雖然它規(guī)則簡單，計算速度也很快，但它的不足在于解決問題的準(zhǔn)確性較差，因此，它通常用于那些對于計算精度要求不高的方案；混合整數(shù)規(guī)劃方法，它具有較好的收斂性和準(zhǔn)確性。但由于這種算法在配置模型中存在太多的假設(shè)條件，以至于限制了它的應(yīng)用范圍；遺傳算法，它具有整體優(yōu)化的能力，同時適合于許多不同的模

2、型，因此它是一種合適的選擇。本文就是運(yùn)用遺傳算法將選址和車輛調(diào)度兩個方面的問題綜合在一起討論，在只知道需求點分布的時候，綜合考慮各類費用以及配送便捷的基礎(chǔ)上建立物流配送中心選址模型，用標(biāo)準(zhǔn)遺傳算法對該模型求解，問題即可得到有效的解決，找出配送中心的最佳位置。然后再根據(jù)已確定的配送中心和需求點位置來制定車輛路徑。在解決車輛優(yōu)化調(diào)度問題時，本文綜合考慮了各種成本費用，建立了適合物流配送模糊車輛調(diào)度問題的數(shù)學(xué)模型，同時采用期望值選擇法，將爬山法與遺傳算法相結(jié)合，從而構(gòu)成混合遺傳算法，使解決該問題快速地搜索到滿意的結(jié)果。結(jié)合以上兩種模型，同時解決這兩方面的問題，使其更加具有完整性和適用性。1物流配送中

3、心選址和車輛調(diào)度問題闡述物流配送中心選址主要因素及費用與物流配送1，2基本相同，主要包括：車輛費用，駕駛員工資（正常工作時間）和補(bǔ)助（加班費），車輛等待費用（提前到達(dá)客戶，車輛需要等待），但對于選址，需要考慮配送中心建設(shè)費用和貨物的存放費用。限制條件：1）所有路徑均起始于配送中心，并要求返回配送中心；2）每一個客戶只由一輛車送貨；3）每個客戶都有一個非負(fù)的貨物需求量，并且經(jīng)過該客戶的配送路徑貨物總需求量不能大于配送車的載貨量；問題假設(shè)主要如下：配送中心建設(shè)費用為W，坐標(biāo)為，客戶總數(shù)為 ，其坐標(biāo)為,，第個客戶需求量為 ，卸貨時間為 ，配送中心和客戶的預(yù)約時間為 ，配送中心與客戶或者客戶與客戶之間

4、的最短距離為 , )，車輛的平均車速度為 ,），每公里車輛的費用的為 , )，車輛種類為m，第p類卡車車輛數(shù)為 ，載貨量為 ，車輛等待費用每小時為 r ，正常工作時間 時司機(jī)的工資為每小時，加班時間 時的補(bǔ)助為每小時，車輛需要返回配送中心，表示車輛總費用，另，2標(biāo)準(zhǔn)遺傳算法解決配送中心選址問題 標(biāo)準(zhǔn)遺傳算法的基本思想和基本步驟在上文中已經(jīng)詳細(xì)的論述，但在實際問題中，其具體操作卻有著不同的地方，對于選址問題，主要方法和步驟3-5如下：第一步：選址數(shù)學(xué)模型 根據(jù)題目我們有：車輛行駛的費用為： （3.1）駕駛員的費用（工資和補(bǔ)助）為： （3.2）由此建立物流配送中心選址問題的數(shù)學(xué)模型： （3.3）（

5、配送中心選址考慮的費用）s.t. 保證任一客戶i只由一輛車來送貨 （3.4） 保證任一車輛送貨量不大于載貨量 （3.5）優(yōu)化目標(biāo)：找出配送中心選址所需費用最小時的第二步：編碼方案若需要選定m個配送中心，則染色體需要由2m個浮點數(shù)排列組成：,，其中表示第i個配送中心的地址坐標(biāo)，一個染色體所包含的m個地址就是配送中心的選址的一個方案。如，對于本文，只需要一個配送中心，則染色體為。第三步：初始種群在配送區(qū)域隨機(jī)產(chǎn)生一系列地址點，構(gòu)成N個個體，構(gòu)成初始種群，,(其中,),并作為遺傳迭代的第一代。第四步：適應(yīng)度函數(shù)遺傳算法的一個特點是它可以使用所求問題的目標(biāo)函數(shù)值即可得到下一步的有關(guān)收集信息，而對目標(biāo)函

6、數(shù)值的使用是通過評價個體的適應(yīng)度來體現(xiàn)的。適應(yīng)度是群體中個體生存機(jī)會選擇的唯一確定性指標(biāo)，所以適應(yīng)度函數(shù)的形式直接決定了群體的進(jìn)化行為。為了直接將適應(yīng)函數(shù)與群體中的個體優(yōu)劣質(zhì)量相聯(lián)系，在遺傳算法中適應(yīng)度規(guī)定為非負(fù)，并且在任何情況下總是越大越好。配送中心選址模型問題所建立的目標(biāo)函數(shù)式（3）是求最小值，則適應(yīng)度函數(shù)可采用2.4式，定義如下：， （3.6）可以取當(dāng)前出現(xiàn)過的最大值。第五步：選擇算子對于浮點數(shù)編碼，我們宜根據(jù)個體的適應(yīng)度大小從大到小排列個體，重排后的個體適應(yīng)度最高，性能最優(yōu)。根據(jù)排序決定每個個體復(fù)制到下一代的概率，用輪盤賭法復(fù)制L個個體，進(jìn)入下一代，代數(shù)增加1。第六步：交叉算子采用與二

7、進(jìn)制相似的單點交叉。在二進(jìn)制單點交叉中，只需要將交叉點對應(yīng)的元素進(jìn)行交換，浮點數(shù)編碼的單點交叉與此相同。如父代個體，父代個體交叉點為3，則交叉過后，子代個體為。在設(shè)定交叉概率后，從群體中隨機(jī)選出個個體進(jìn)行兩兩交叉，從而得出新的個體。第七步：變異算子變異操作以概率對染色體群中的某些染色體的某些位進(jìn)行變異，產(chǎn)生新的個體染色體，作為交叉運(yùn)算的補(bǔ)充，變異操作可能增加方案的多樣性，克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象，變異概率取不同的值對算法性能的影響很大，過大，求解時間會明顯增加，但算法收斂于局部最優(yōu)的可能性減少。第八步：算法停止準(zhǔn)則設(shè)計淘汰不符合約束條件（4）（5）的染色體，同時，在每一代產(chǎn)

8、生的染色體當(dāng)中，計算出個體的最大適配值和最小適配值，若（為停止準(zhǔn)則參數(shù)），則回到第五步，繼續(xù)進(jìn)行遺傳操作，否則就輸入最優(yōu)結(jié)果，停止計算。3混合遺傳算法解決車輛調(diào)度問題 在解決車輛調(diào)度問題時，本文在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，采用了期望值選擇方法，并且將爬山法和遺傳算法相結(jié)合，從而構(gòu)成求解該問題的混合遺傳算法，其主要步驟6-8如下：第一步：車輛調(diào)度數(shù)學(xué)模型車輛調(diào)度需要考慮的因素與配送中心選址基本相同，但，不需要考慮配送中心建設(shè)費用，并且需要增加考慮車輛等待費用。故，我們可以建立如下車輛調(diào)度模型： （3.7）（車輛的總費用）s.t. 保證任一客戶i只由一輛車來送貨 保證任一車輛送貨量不大于載貨量 優(yōu)化目

9、標(biāo)：車輛的總費用最小。第二步：編碼方案根絕物流配送問題的特點，物流中的車輛調(diào)度問題適宜采用自然數(shù)編碼。首先根據(jù)貨物的總的需求量C=，每輛車的平均載貨量，計算出需要車輛的數(shù)目n。根絕自然數(shù)編碼的原理我們可以產(chǎn)生1，2，3，的自然數(shù)排列，其中1，2，為客戶序列，為n虛擬配送中心，n為所需的車輛數(shù)。第三步：初始種群 在通過自然數(shù)編碼產(chǎn)生的排列當(dāng)中，我們隨機(jī)選擇n個符合約束條件（6）（7）的排列作為初始個體，構(gòu)成初始種群。例如用4輛車向7個客戶送貨，設(shè)某個排列為1，3，8，2，6，9，4，7，10 ，5，它表示4條路徑0-1-3-8-0，0-2-6-9-0，0-4-7-0，0-5-0，其中的0表示配送

10、中心。若每一條路徑上客戶的需求量之和均小于車輛的最大載貨量，則選擇改排列作為一個個體；否則，則不能選此個體作為個體。并輸入控制參數(shù)（交叉概率，變異概率，群體規(guī)模，最大運(yùn)行代數(shù)）。第四步：適應(yīng)度函數(shù)自然數(shù)編碼能夠很好的保證每一個客戶所需要的貨物只由一輛車配送，但不能保證交叉變異以后的個體滿足條件，故給予一定的懲罰。令，保證客戶i的需求量不大于給它送貨車輛的載貨量。,), 表示所有客戶對貨物的總需求量。若取懲罰權(quán)重為，則染色體的適應(yīng)度函數(shù)可以定義為：第五步：選擇算子 在物流配送的車輛調(diào)度問題中，我們采用期望值方法可以得到比較好的結(jié)果，根據(jù)式子2.14，群體中每一個個體在下一代生存的期望數(shù)目為，并且

11、，被選中參與配對和交叉的個體在下一代的生存期望為該個體生存期望減去0.5，未被選中的個體在下一大的生存期望為該個體生存期望減去1，但需要注意的是，個體生存期望為小于零的不參與配對和交叉。第六步：交叉算子對于自然數(shù)編碼個體，根絕前面節(jié)所講述的循環(huán)交叉算子（CX，cycle crossover）的方法，我們可以很容易由父個體產(chǎn)生出子個體。變異算子和算法停止準(zhǔn)則的設(shè)計與配送中心選址中的變異和停止準(zhǔn)則設(shè)計相同。4算例某牛奶公司在一城市中有12個銷售點，銷售點的需求量，位置，以及卸貨時間如表3.1所示。送貨車輛有兩種，A類載貨量為500箱，沒公里車輛費用為3元，B類載貨量為400箱，每公里車輛費用為2.

12、5元。駕駛員正常工作時間內(nèi)的工資為每小時10元，加班補(bǔ)助為每小時20元。設(shè)最早發(fā)車時間為早上6：00 。 1）試確定一個配送中心的地址（配送中心建設(shè)費用為1.5萬元，并且范圍坐標(biāo)為（1000，1000），使目標(biāo)函數(shù)值最小。2）確定配送中心地址后的車輛調(diào)度方案，使目標(biāo)函數(shù)值最小。表3.1 銷售點坐標(biāo)及需求表客戶牛奶箱數(shù)客戶位置（km）卸貨時間（min）預(yù)約時間X坐標(biāo)Y坐標(biāo)112030114607：3022004036907：3031204896607：30415052120807：30514092154707：306609266407：30711094100607：308180108100907

13、：3099044160507：3010602054907：301114010832607：301215013088707：301、 配送中心選址模型為（3.3）式，在matlab6.5環(huán)境下編程可實現(xiàn)此例中配送中心地址的尋找。其控制參數(shù)如下：N = 12 %種群規(guī)模n = 1 %配送中心個數(shù) 銷售點數(shù)目B = 0 1000 0 1000 配送中心邊界范圍 M = 1000 最大迭代代數(shù) 0.85 交叉概率 0.05變異概率1.0× 固定最大值W = 15000 %配送中心建設(shè)費用運(yùn)行程序，得出配送中心的坐標(biāo)為（60，140），目標(biāo)函數(shù)值為17532.54。2、配送中心確定后，我們可以

14、根據(jù)，,12)計算出各銷售點與配送中心的距離。同時我們可以看到各個銷售點的總需求量為1620箱，按照車輛調(diào)度問題中編碼的辦法可以計算出共需要4輛車（），因此求解出來的方案應(yīng)該為115（13，14，15為虛擬配送中心）的一個排列。設(shè)定群體規(guī)模為N20，交叉概率，變異概率，最大運(yùn)行代數(shù)為1000代。在matlab6.5中運(yùn)行，其結(jié)果顯示最優(yōu)染色體為321013581571261114914，A,B類車各需要2輛，總費用為2725.98元。具體運(yùn)行情況見下表3.2。表3.2 車輛調(diào)度情況序號車型車輛容量/實載量（箱）車輛路徑以及收發(fā)車時間總費用（元）1A500/4800(6:35)3(6:30)2(

15、9:05)10(11:35)13/0(13:57)892.322B400/32013/0(6:41)5(7:30)8(8:51)15/0(10:55)382.693A500/46015/0(6:28)7(7:30)12(8:56)6(10:5811(12:23)14/0(14:33)1054.584B400/36014/0(7:00)9(8:00)1(10:05)0(11:31)395.393、結(jié)論本題主要在考慮到降低成本的基礎(chǔ)上，建立了近似于現(xiàn)實生活中的物流活動的數(shù)學(xué)模型。采用了SGA解決選址問題，在解決車輛調(diào)度問題時，采用了期望值選擇法，將爬山法與GA結(jié)合起來構(gòu)成HGA,，克制了傳統(tǒng)選擇法

16、帶來的統(tǒng)計誤差和局部搜索能力差的特點，提高了解的精度。參考文獻(xiàn) 1 封全喜,劉誠.基于混合遺傳算法的物流配送模糊車輛調(diào)度問題的研究.長沙交通學(xué)院學(xué)報,2005.9.2CHEN Qing-Geng, WANG Ning, HUANG Shao-Feng. The Distribution Populationbased Genetic Algorithm for Parameter optimization PID Controller.ACTA AUTOM ATICA SINICA,vol.31,No.4,July,2005。3 陳火根,丁紅鋼,乘耀東.物流配送中心車輛調(diào)度模型與遺傳算法設(shè)計.

17、浙江大學(xué)學(xué)報,2003.9.4 QIAN Jing, PANG Xiao-hong, Zhi-ruing. An Improved Genetic Algorithm for Allocation Optimiiation of Distribution Centers. Journal of Shanghai Jiaotong University(Science),Vo1.E-9,No.4,2004,7376.5 LUO Pi, Li Qiang, GUO Jl-cheng, TENG Jian-fu. Improved Genetic Algorithm and Its Performance Analysis, Transactions of Tianjin University. vol.9, No.2, Jun.2003. 6 玄光男日,程潤偉.遺傳算法與工程設(shè)計.北京:科學(xué)出版社,2000.1:37-42 7 ZHAO Yong-ming, ZHANG Su, XIAO Chang-yen, CHEN Ya-zhu. A hybrid