多物流配送中心路徑優(yōu)化問題及其遺傳算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上多物流配送中心路徑優(yōu)化問題及其遺傳算法廖成林 柳茂森（重慶大學經(jīng)濟與工商管理學院，重慶，）摘 要：論文建立了多物流配送中心路徑優(yōu)化問題的數(shù)學模型，并針對該問題的特點構造出求解該問題的遺傳算法，把多物流配送中心路徑優(yōu)化問題綜合起來用一個數(shù)學模型求解。本文提出了無效基因的概念，從而不局限于使得個體中每個基因都必須表達出來，因此增強了編碼的靈活性。仿真實驗證明了該方法的有效性和可操作性。關鍵詞：無效基因 遺傳算法 物流配送1 引言物流配送是物流管理中一個極其重要的環(huán)節(jié)，它是指按用戶的訂貨要求,在配送中心進行分貨、配貨,并將配好的貨物及時送交收貨人的活動。物流配送主要研究車輛

2、調(diào)度及路徑安排問題。近年來，國內(nèi)外學者對物流配送問題進行了大量的研究，這些研究主要集中在單物流配送中心的車輛調(diào)度及路徑安排方面。由于配送路徑優(yōu)化問題是一個NP 難題，因此，研究者大都使用啟發(fā)式算法和智能算法或者是在智能算法優(yōu)化過程中加入優(yōu)化策略以構造混合智能算法來求解物流配送問題。但是，目前國內(nèi)外對多個物流配送中心的物流配送問題的研究成果很少，而且現(xiàn)有研究成果大都是把多個配送中心問題通過任務分派轉化為單物流配送中心問題來研究13，使用這種方法把需求點預先劃分給各個配送中心，在求解過程中再作適當?shù)恼{(diào)整，這種方法其實只是單物流配送中心優(yōu)化的簡單組合，通常只能求得近似最優(yōu)配送方案。魏百鑫等4 針對整

3、車配送需求點分散特征,解決了多倉庫的整車配送問題，但并不是一個通用的解決多物流中心配送問題的方法。由于遺傳算法具有良好的全局尋優(yōu)性能，并且對不要求搜索空間具是連續(xù)的，這正符合該問題的特點和要求。因此本文亦采用遺傳算法求解。本文基于整體路徑最優(yōu)由多個物流配送中心同時服務多個需求點建立一個通用的多物流配送中心的配送模型，并給出求解算法。單物流配送中心路徑優(yōu)化問題可以事先確定需要派出的車次，但是多物流配送中心路徑優(yōu)化問題中，每個配送中心需要派出多少車次是不確定的，因此，無法用常規(guī)的方法確定染色體的長度。為解決基因編碼的問題，本文提出了無效基因的概念。所謂無效基因就是在一次基因表達的過程中不作表達的基

4、因。但是，在交叉過程中無效基因處可以被選為交叉點，交叉后無效基因可能轉化為有效基因。因此，有些基因時而是有效基因時而是無效基因，因而無效基因在不清楚有些基因是否表達較好的時候起到緩沖作用。2 模型的建立多物流配送路徑優(yōu)化問題可描述為：從多個配送中心用多輛配送車向多個需求點送貨，每個需求點的位置和需求量一定，要求安排合理的配送路線，使得目標函數(shù)最優(yōu)或接近最優(yōu)。為了研究的方便且具有實際意義，做以下假設：(1) 每條配送路徑上各需求點的需求量之和不超過配送車的載重量；(2) 每個需求點都必須滿足，且只能由一輛配送車送貨。本文的各種符號及其含義做如下說明：M-配送中心的個數(shù)i-配送中心的下標j-配送車

5、輛的下標k-需求點的下標N-需求點的個數(shù)Li-第i個配送中心的配送車的個數(shù)Qij-第i個配送中心的第j輛車的載重量qk-第k個需求點的需求量dk(1)dk(2)-從需求點k(1)到k(2)的運距d0k-配送中心到需求點k的運距nij-第i個配送中心的第j輛車配送的需求點個數(shù)，nij=0表示未使用第j輛車Rij-第i個配送中心的第j輛車配送的路徑rijk-第i個配送中心的第j輛車配送的第k個需求點，rij0表示配送中心 其中， 表示不大于括號內(nèi)數(shù)字的最大整數(shù)若以配送路徑最短為目標函數(shù)，則可以建立如下配送路徑的優(yōu)化模型： 上述模型中：（1）式為目標函數(shù);（2）式保證每條路徑上各客戶的貨物需求量之和

6、不超過配送車輛的載重量; (3) 式表明每條路徑上的客戶數(shù)不超過總客戶數(shù); (4) 式表明每個客戶都得到配送服務; (5) 式表示每條路徑的客戶的組成;(6) 式限制每個客戶僅能由一臺配送車輛送貨; (7)式表示當?shù)趇個配送中心的第j輛車服務的客戶數(shù)1 時,說明該臺車參加了配送,則取f（nij）= 1 ,當?shù)趇個配送中心的第j輛車服務的客戶數(shù)< 1 時, 表示未使用該臺車輛, 因此取f（nij）= 0 。3 遺傳算法設計3.1 編碼方法的確定和初始種群的產(chǎn)生根據(jù)多物流配送中心路徑優(yōu)化問題的特點,作者提出了一種配送中心和需求點直接排列的編碼方法。這種表示方法是直接生產(chǎn)N個1N 間的互不重復

7、的自然數(shù)給這N個需求點編碼，再生產(chǎn)M個-M-1之間的互不重復的負整數(shù)給這M個配送中心編碼。 把這M個-M-1之間的互不重復的負整數(shù)各n個和這N個1N 間的互不重復的自然數(shù)各一個組成一個長度為n*M+N的數(shù)列，數(shù)列的第一個位置隨機排上一個負整數(shù)，其余位置隨機全排列，即形成一個染色體。隨機產(chǎn)生m個這樣的個體即可形成種群規(guī)模為m的初始種群。這樣的染色體結構可解釋為：（1） 從負數(shù)對應的配送中心出發(fā)向緊接著該負數(shù)后面的若干個正數(shù)所對應的需求點配送，再回到該配送中心，形成一條子路徑。（2） 后面未緊接著正數(shù)的負數(shù)為無效基因，不表示任何意義，但是可以在該基因處進行交叉操作。若交叉后該負數(shù)后面緊接正數(shù)，則該

8、負數(shù)由無效基因變?yōu)橛行Щ?，其意義與（1）所述相同。例如染色體（-1，-4，1，2，-1，-2，-3，3，4，5，-5）表示的意義：其中， -2、-5和兩個-1都是無效基因。這種染色體結構子路徑內(nèi)部是有序的，子路徑中需求點1和2交換位置，會使目標函數(shù)值改變；而子路徑之間是無序的，若子路徑1和2交換位置，卻不會改變目標函數(shù)值。3.2 適應度評估方法的確定。適應度函數(shù)同目標函數(shù)有關，要求非負，通過變換目標函數(shù)得到適應度函數(shù)：。其中，b為常數(shù)，為初始群體中最好的染色體配送距離，zk為當前染色體對應的配送距離。3.3選擇操作。本文采用如下最佳個體保留與賭輪選擇相結合的選擇策略:將每代群體中的m個個體按

9、適應度由大到小排列,排在第一位的個體性能最優(yōu),將它復制一個直接進入下一代,并排在第一位;下一代群體的另m - 1個個體需要根據(jù)前代群體的m個個體的適應度,采用賭輪選擇法產(chǎn)生,具體地說,就是首先計算上代群體中所有個體適應度的總和Fj ,再計算每個個體的適應度所占的比例Fj/Fj (j = 1 ,2 , ,m) ,以此作為其被選擇的概率。上述選擇方法既可保證最優(yōu)個體生存至下一代,又能保證適應度較大的個體以較大的機會進入下一代。3.4交叉操作對通過選擇操作產(chǎn)生的新群體,除排在第一位的最優(yōu)個體外,另 - 1 個個體要按交叉概率Pc 進行配對交叉重組。本文采用類OX法實施交叉操作,其操作過程為: 如果染

10、色體交叉點處的兩個基因都為負數(shù), 則直接用基于序的交叉進行運算; 如果染色體交叉點處的基因不全為負數(shù), 則將交叉點左移(右移) , 直到左右兩個交叉點處的基因都為負數(shù), 再進行運算. 如:父代1: -1，-4，1，2，-1，-2，-3，3，4，5，-5父代2: -5，-1，3，1，5，-2，-4，4，2，-1，-3內(nèi)為匹配段, 經(jīng)過最大保留交叉運算后形成子代1: -1，1，-4，4，2，-1，-2，-3，3， 5，-5子代2: -5，-1，3，5，-2，-4，1，2， -1，4，-33.5 變異操作由于在選擇機制中采用了保留最佳個體的方式,為保持群體內(nèi)個體的多樣化,本文采用連續(xù)多次對換的變異技

11、術,使個體在排列順序上有較大的變化。變異操作是以概率Pm 發(fā)生的,一旦變異操作發(fā)生,則用隨機方法產(chǎn)生交換次數(shù)J ,對所需變異操作的個體的基因進行J 次對換(對換基因的位置也是隨機產(chǎn)生的) 。3.6 終止準則采用最佳個體保留指定代數(shù)的終止準證，即若某個體在連續(xù)若干代都是最佳個體，說明該個體是很好的個體，則停止操作。4 仿真實驗本文用matlab編制了多物流配送中心路徑優(yōu)化問題的遺傳算法計算程序。算例：有兩個配送中心各兩輛配送車向9個需求點配送，配送車的載重量均是10噸。配送中心（編號為-1和-2）與需求點之間以及需求點相互之間的距離dk(1)dk(2)、9個客戶的需求量qk均見下表1。要求安排合

12、理的配送路線，使得總的配送路徑最短。根據(jù)算例的特點，在用遺傳算法對其求解時采用了一下參數(shù)：種群規(guī)模取25，進化代數(shù)取100，交叉概率取0.9，變異概率取0.01，對不可行路徑的懲罰權重取100km。對算例求解10次，所得的計算結果見表2。表1 算例的已知條件表dk(1)k(2)（km） k(2) -1 -2 1 2 3 4 5 6 7 8 9k(1) -1 0 10 6 12 4 10 4 6 10 13 3-2 0 12 8 12 4 6 8 4 9 91 0 13 5 11 8 9 13 10 62 0 15 10 10 8 10 5 113 0 10 6.5 10 11 14 64 0

13、3 7 3 10 85 0 5 7 12 76 0 8 8 47 0 12 108 0 109 0 qk（t） - - 3 4 4 2 3 2 3 2 1表2 算例的遺傳算法計算結果計算次序 1 2 3 4 5 6 7 8 9 10 平均配送總距離（km） 67 64 68 70 64 68 64 67 68 64首次搜索到最終解的代數(shù) 43 38 36 42 53 57 49 51 48 52由表2可以看出：用遺傳算法對算例的10次求解中，有4次得到了問題的最優(yōu)解64km（其對應的配送路徑方案為：路徑1:-1,1,3,-1;路徑2：-1，5，6，9，-1；路徑3：-2，4，7，-2；路徑4：

14、-2，2，8，-2），6次得到了問題的近似最優(yōu)解，這種方法求解多物流配送中心路徑優(yōu)化問題明顯的優(yōu)于把多個配送中心問題通過任務分派轉化為單物流配送中心問題求解。5 結束語（1）本文建立了一個多物流配送中心模型，并基于多物流配送中心配送的特點，設計了求解算法。由于每個配送中心需要派出多少車次是不確定的，文章通過采用無效基因很好的解決了這個由于各配送中心需要派出多少車次不確定引起的對個體無法編碼的問題。這樣就可以把多個物流配送中心配送優(yōu)化問題用一個數(shù)學模型來求解，這種方法要優(yōu)于把需求點預先劃分給各個配送中心，以轉化為單物流配送中心求解的方法。（2）遺傳算法是模擬生物遺傳學的規(guī)律的算法，但是，在生物體

15、內(nèi)的基因是存在無效基因的，而目前使用的遺傳算法編碼的基因都是有效的。因此，無效基因的概念的提出是遺傳算法的一次發(fā)展，拓寬了遺傳算法適用范圍，也使得遺傳算法更接近生物遺傳的規(guī)律。本文設計個體的編碼方法對解決類似的組合優(yōu)化問題具有一定的參考價值。（3）個體中增加了無效基因，就等于在更大的空間內(nèi)尋優(yōu)。這樣一來就加大了尋優(yōu)的難度，需要迭代更多的代數(shù)才能尋得最優(yōu)解或近似最優(yōu)解。如何降低迭代次數(shù)以盡快尋得最優(yōu)解或近似最優(yōu)解，有待進一步研究。參考文獻1 張俊偉,王勃,馬范援. 多倉庫多配送點的物流配送算法J . 計算機工程,2005 ,31 (21) :192 - 194. 2 Skok M , Skrle

16、c D , Krajcar S. The genetic algorithm methodfor multiple depot capacitated vehicle routing problem solving C/ / The Fourth International Conference on Knowled ge -based Intelligent Engineering Systems & Allied Technologies.Brighton ,U K: U K Press , 2000 :520 - 526. 3 Filipec M , Skrlec D , Kra

17、jcar S. Genetic algorithm approachfor multiple depot capacitated vehicle routing problem solvingwith heuristic improvements built - inJ .International Jour2nal of Modeling and Simulation , 2000 , 20 (4) :320 - 328. 4 魏百鑫,史海波. 基于整車配送的多倉庫開路VRPTW 問題的研究與實現(xiàn)J . 信息與控制,2005 ,34 (3) :350 - 355. 5 李大衛(wèi),王莉,王夢光. 遺傳算法在有時間窗車輛路徑問題上的應用J . 系