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

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

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

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

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

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

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

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

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

9、標(biāo)：車輛的總費(fèi)用最小。第二步：編碼方案根絕物流配送問(wèn)題的特點(diǎn)，物流中的車輛調(diào)度問(wèn)題適宜采用自然數(shù)編碼。首先根據(jù)貨物的總的需求量C=，每輛車的平均載貨量，計(jì)算出需要車輛的數(shù)目n。根絕自然數(shù)編碼的原理我們可以產(chǎn)生1，2，3，的自然數(shù)排列，其中1，2，為客戶序列，為n虛擬配送中心，n為所需的車輛數(shù)。第三步：初始種群 在通過(guò)自然數(shù)編碼產(chǎn)生的排列當(dāng)中，我們隨機(jī)選擇n個(gè)符合約束條件（6）（7）的排列作為初始個(gè)體，構(gòu)成初始種群。例如用4輛車向7個(gè)客戶送貨，設(shè)某個(gè)排列為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、中心。若每一條路徑上客戶的需求量之和均小于車輛的最大載貨量，則選擇改排列作為一個(gè)個(gè)體；否則，則不能選此個(gè)體作為個(gè)體。并輸入控制參數(shù)（交叉概率，變異概率，群體規(guī)模，最大運(yùn)行代數(shù)）。第四步：適應(yīng)度函數(shù)自然數(shù)編碼能夠很好的保證每一個(gè)客戶所需要的貨物只由一輛車配送，但不能保證交叉變異以后的個(gè)體滿足條件，故給予一定的懲罰。令，保證客戶i的需求量不大于給它送貨車輛的載貨量。,), 表示所有客戶對(duì)貨物的總需求量。若取懲罰權(quán)重為，則染色體的適應(yīng)度函數(shù)可以定義為：第五步：選擇算子 在物流配送的車輛調(diào)度問(wèn)題中，我們采用期望值方法可以得到比較好的結(jié)果，根據(jù)式子2.14，群體中每一個(gè)個(gè)體在下一代生存的期望數(shù)目為，并且

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

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

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

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

15、: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í)生活中的物流活動(dòng)的數(shù)學(xué)模型。采用了SGA解決選址問(wèn)題，在解決車輛調(diào)度問(wèn)題時(shí)，采用了期望值選擇法，將爬山法與GA結(jié)合起來(lái)構(gòu)成HGA,，克制了傳統(tǒng)選擇法帶

16、來(lái)的統(tǒng)計(jì)誤差和局部搜索能力差的特點(diǎn)，提高了解的精度。參考文獻(xiàn) 1 封全喜,劉誠(chéng).基于混合遺傳算法的物流配送模糊車輛調(diào)度問(wèn)題的研究.長(zhǎng)沙交通學(xué)院學(xué)報(bào),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è)計(jì).浙

17、江大學(xué)學(xué)報(bào),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 玄光男日,程潤(rùn)偉.遺傳算法與工程設(shè)計(jì).北京:科學(xué)出版社,2000.1:37-42 7 ZHAO Yong-ming, ZHANG Su, XIAO Chang-yen, CHEN Ya-zhu. A h