基于改進遺傳算法的物流配送點選址問題研究

《基于改進遺傳算法的物流配送點選址問題研究》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、第24卷第4期蘭州交通大學學報(自然科學版)Vol.24No.42005年8月JournalofLanzhouJiaotongUniversity(NaturalSciences)Aug.2005文章編號:1001O4373(2005)04O0135O03基于改進遺傳算法的物流配送點選址問題研究*于波,李引珍(蘭州交通大學交通運輸學院,甘肅蘭州730070)摘要:在已知物流配送點數(shù)目的條件下,以最低送貨運輸費用為目標,利用最小二乘法推導出多物流配送點的選址模型及其迭代算法;根據(jù)遺傳算法的基本思想,設計了求解已知物流配送點數(shù)目條件下的選址和物流服務分配問題的遺傳算法.通過實例證明該

2、模型及算法具有較好的應用價值.關鍵詞:配送點選址模型;迭代算法;遺傳算法;最小二乘法中圖分類號:O224文獻標識碼:A物流配送點選址是物流系統(tǒng)規(guī)劃的一項重要內客始終只能從某一個配送點進貨,由此確定了物流服[1]m容,選址是否合理將直接影響到物流配送點的各項務分配的約束條件:Elij=1(j=1,2,,,n).經(jīng)營成本和獲利程度.隨著社會分工的日益專業(yè)化,i=1為了滿足顧客日益增長的需要和實現(xiàn)規(guī)模效益,企業(yè)由最小二乘法原理,對于一個給定的矩陣將不得不建立多個配送點.我國對物流配送點選址問(lij)m@n,欲使送貨運輸費用最低(目標函數(shù)最小),[2,3]題較為成熟的研究多為單配送點選

3、址問題.本文必有5c=0,5c=0,從而可推導出迭代公式[4]5ui5vi運用高效有向搜索的遺傳算法來確定物流服務分配nn方案,借鑒最小二乘法推導的迭代公式進行選址計uki=lijtjwjxj/lijtjwj(2)EkEkj=1dijj=1dij算,有效地解決了多物流配送點的選址問題.nnklijtjwjyjlijtjwjvi=Ek/Ek(3)1模型的建立與分析j=1dijj=1dijk+1k2k2dij=(ui-xj)+(vi-yj)(4)建設費用一般為固定費用,對多物流配送點選(i=1,2,,,m;j=1,2,,,n)址采用運輸成本最小化原則,即用占物流成本絕大當配送點位置未

4、知時,解決此問題可用迭代方部分的運輸費用代替物流成本.建立目標函數(shù)[5]mn法,迭代方法能保證收斂到最優(yōu)值.方法如下:令22f=EElijtjwj(ui-xj)+(vi-yj)(1)d00000ij=1,代入式(2),(3)得到ui,vi;再將ui,vi代入i=1j=11111式中:m為已知物流配送點數(shù)目;n為已知顧客數(shù)目;式(4)求出dij,將dij代入式(2),(3)求出ui,vi的kkk+1k+1(xj,yj)為位置已知的顧客地址坐標,j=1,2,,,n;值;如此反復,直到(ui,vi)與(ui,vi)的變化值k+1k+1(ui,vi)為位置待定的物流配送點地址坐標,i=1

5、,2,小于某一指定的較小值E時為止.此時(ui,vi)即,,m;wj為顧客j的貨物需求量;tj為到顧客j的單位為這一服務分配方案的最優(yōu)地址.運輸費用;lij=1表示第i個配送點向第j個顧客送當m和n的值較小時,可通過排列組合列舉出貨;lij=0表示第i個配送點不向顧客j送貨.lij的值每一服務分配方案,然后由迭代算法求出每一方案共有m@n個,若以m為行、Fn為列,就形成一個物流相對應的配送點坐標并求出送貨運輸費用,經(jīng)過比服務分配矩陣(lij)m@n,每一個布爾矩陣(lij)m@n對應較后,即可確定出送貨運輸費用最低的配送點坐標一種物流服務分配方案,多物流配送點選址問題必須及容量;

6、但當m和n的值較大時,將出現(xiàn)配送方案組先確定物流服務分配方案,所以也稱為選址分配問合爆炸,成為一個較為復雜的組合優(yōu)化問題,此時必[4]題.為簡化多配送點選址分配問題,假設每一個顧須運用優(yōu)化算法來求解,遺傳算法便成為解決這一*收稿日期:2005O03O12作者簡介:于波(1980O),女,內蒙古海拉爾人,碩士研究生.136蘭州交通大學學報(自然科學版)第24卷問題的有效算法之一.2.3確定適應度函數(shù)和評價函數(shù)根據(jù)模型特點,提出了如下求解方法:適應度函數(shù)常為目標函數(shù),由于此問題的目標1)由遺傳算法隨機產(chǎn)生可行的初始服務分配函數(shù)取最小值,可重新構造一個新的適應度函數(shù)方案;2)將每一服務

7、分配方案通過上述迭代方法求fc(x)=C-f(x)(5)出各配送點的位置;3)根據(jù)求出的配送點位置及分式中:fc(x)為適應度函數(shù);C為一個較大的常數(shù);配方案,計算送貨運輸費用;4)經(jīng)過遺傳算法的選f(x)為目標函數(shù).在已確定服務分配方案(lij)m@n擇、交叉、變異操作產(chǎn)生新的服務分配方案.如此反后,應先由迭代算法求出各配送點的地址坐標(ui,復將遺傳算法與迭代方法有效結合,便可求出多個vi),再由目標函數(shù)經(jīng)過式(5)的轉換后求出各染色物流配送點的最優(yōu)服務分配方案及最優(yōu)地址.體