物流配送路徑優(yōu)化論文

1、山西工商學(xué)院畢業(yè)設(shè)計(jì)題目淺析物流配送路徑優(yōu)化問題學(xué)生姓名 楊美玲 學(xué) 號(hào) 專 業(yè) 班 級(jí) 08物流二班 指導(dǎo)教師 李桂娥二零一一年十月二十八日目 錄摘要一、引言（問題的提出） 1二、物流配送路徑優(yōu)化問題的數(shù)學(xué)模型X三、物流配送路徑優(yōu)化問題的遺傳算法X（一）遺傳算法的基本要素 X（二）物流配送路徑優(yōu)化問題的遺傳算法的構(gòu)造X四、實(shí)驗(yàn)計(jì)算與結(jié)果分析 X五、 結(jié)論X 參考文獻(xiàn) X 致謝 X中英文摘要摘 要：論文在建立物流配送路徑優(yōu)化問題的數(shù)學(xué)模型的基礎(chǔ)上，構(gòu)造了求解該問題的遺傳算法，并進(jìn)行了實(shí)驗(yàn)計(jì)算。計(jì)算結(jié)果表明，用遺傳算法進(jìn)行物流配送路徑優(yōu)化，可以方便有效地求得問題的最優(yōu)解或近似最優(yōu)解。 關(guān)鍵詞：物

2、流配送；遺傳算法；優(yōu)化Study on the Optimizing of Physical Distribution Routing Problem Based on Genetic AlgorithmAbstract：On the basis of establishing the optimizing model on physical distribution routing problem, this paper presents a genetic algorithm for solving this problem, and make some experimental calc

3、ulations. The experimental calculation results demonstrates that the optimal or nearly optimal solutions to the physical distribution routing problem can be easily obtained by using genetic algorithm.Keywords：physical distribution；genetic algorithm；optimizing一、引言（問題的提出）隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展和物流技術(shù)專業(yè)化水平的提高，物流配送業(yè)得到

4、了迅猛發(fā)展。物流配送是指按用戶的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送交收貨人。在物流配送業(yè)務(wù)中，存在許多優(yōu)化決策問題，本文討論其中的物流配送路徑優(yōu)化問題，即通過制定合理的配送路徑，快速而經(jīng)濟(jì)地將貨物送達(dá)用戶手中。配送路徑的選擇是否合理，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。研究表明，配送路徑優(yōu)化問題是一個(gè)NP難題，只有在需求點(diǎn)和路段較少時(shí)，才能求得精確解。因此，用啟發(fā)式算法求解該問題就成為人們研究的一個(gè)重要方向，并出現(xiàn)了多種啟發(fā)式算法，如Clarke和Wright提出的節(jié)約法，Gillett和Miller提出的掃描法等，雖然這些算法為求解配送

5、路徑優(yōu)化問題提供了有效的方法，但也存在一定的問題，如節(jié)約法雖然具有運(yùn)算速度快的優(yōu)點(diǎn)，但也有組合點(diǎn)零亂、邊緣點(diǎn)難以組合的問題，掃描法為非漸進(jìn)優(yōu)化等。如何針對(duì)物流配送路徑優(yōu)化問題的特點(diǎn)，構(gòu)造運(yùn)算簡(jiǎn)單、尋優(yōu)性能優(yōu)良的啟發(fā)式算法，是一個(gè)值得深入研究的課題。遺傳算法的出現(xiàn)為求解物流配送路徑優(yōu)化問題提供了新的工具，該算法是由美國的J.Holland教授于1975年提出的，它是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索方法。由于遺傳算法采用隨機(jī)選擇，對(duì)搜索空間無特殊要求，無需求導(dǎo)，具有運(yùn)算簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)，尤其適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性的問題，目前已廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)

6、、自適應(yīng)控制等領(lǐng)域。本文針對(duì)物流配送路徑優(yōu)化問題的特點(diǎn)，構(gòu)造了求解該問題的遺傳算法，通過實(shí)驗(yàn)計(jì)算，得到了較好的結(jié)果。二、物流配送路徑優(yōu)化問題的數(shù)學(xué)模型物流配送路徑優(yōu)化問題可以描述為：從配送中心（或稱物流據(jù)點(diǎn)）用多輛汽車向多個(gè)需求點(diǎn)（或稱顧客）送貨，每個(gè)需求點(diǎn)的位置和需求量一定，每輛汽車的載重量一定，要求合理安排汽車路線，使總運(yùn)距最短，并滿足以下條件：（1）每條配送路徑上各需求點(diǎn)的需求量之和不超過汽車載重量；（2）每條配送路徑的長度不超過汽車一次配送的最大行駛距離；（3）每個(gè)需求點(diǎn)的需求必須滿足，且 Z米凱利維茨. 演化程序遺傳算法和數(shù)據(jù)編碼的結(jié)合M. 北京：科學(xué)出版社，2000.只能由一輛汽車

7、送貨。本文借鑒文獻(xiàn)3建立的車輛路徑問題的數(shù)學(xué)模型，并通過考慮上述物流配路徑優(yōu)化問題的約束條件和優(yōu)化目標(biāo)，建立了物流配送路徑優(yōu)化問題的數(shù)學(xué)模型。設(shè)配送中心有K輛汽車，每輛汽車的載重量為Qk（k=1，2，K），其一次配送的最大行駛距離為Dk，需要向L個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的需求量為qi（i=1，2，L），需求點(diǎn)i到j(luò)的運(yùn)距為dij，配送中心到各需求點(diǎn)的距離為d0j（i、j=1，2，L），再設(shè)nk為第k輛汽車配送的需求點(diǎn)數(shù)（nk=0表示未使用第k輛汽車），用集合Rk表示第k條路徑，其中的元素rki表示需求點(diǎn)rki在路徑k中的順序?yàn)閕（不包括配送中心），令rk0=0表示配送中心，則可建立如下物流配送

8、路徑優(yōu)化問題的數(shù)學(xué)模型：Knkrk(i-1)rkiminZ=dk=1i=1+drknkrk0sign(nk) （1）nks.t.qi=1rkiQk （2）nkdi=1rk(i-1)rki+drknkrk0sign(nk)Dk （3）0nkLK（4）nk=1k=L （5）Rk=rki|rki1,2,.,L,i=1,2,.,nk （6）Rk Rk= k1k212（7）sign(nk)=10nk1其他（8）上述模型中，（1）式為目標(biāo)函數(shù)；（2）式保證每條路徑上各需求點(diǎn)的需求量之和不超過汽車的載重量；（3）式保證每條配送路徑的長度不超過汽車一次配送的最大行駛距離；（4）式表明每條路徑上的需求點(diǎn)數(shù)不超過

9、總需求點(diǎn)數(shù)；（5）式表明每個(gè)需求點(diǎn)都得到配送服務(wù)；（6）式表示每條路徑的需求點(diǎn)的組成；（7）式限制每個(gè)需求點(diǎn)僅能由一輛汽車送貨；（8）式表示當(dāng)?shù)趉輛汽車服務(wù)的客戶數(shù)1時(shí)，說明該輛汽車參加了配送，則取sign(nk)=1，當(dāng)?shù)趉輛汽車服務(wù)的客戶數(shù)1時(shí)，表示未使用該輛汽車，因此取sign(nk)=0。三、物流配送路徑優(yōu)化問題的遺傳算法（一）遺傳算法的基本要素遺傳算法是一種“生成+檢測(cè)”的迭代搜索算法。該算法以群體中的所有個(gè)體為操作對(duì)象，每個(gè)個(gè)體對(duì)應(yīng)研究問題的一個(gè)解。選擇、交叉和變異是遺傳算法的三個(gè)主要操作算子。該算法包括以下6個(gè)基本要素：1、編碼。由于遺傳算法不能直接處理解空間的數(shù)據(jù)，因此，必須通

10、過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。2、初始群體生成。由于遺傳算法是一種群體型搜索方法，所以必須為遺傳操作準(zhǔn)備一個(gè)由若干個(gè)體組成的初始群體，每個(gè)個(gè)體都應(yīng)通過隨機(jī)方法產(chǎn)生，并分別對(duì)應(yīng)研究問題的一個(gè)解。3、適應(yīng)度評(píng)估。遺傳算法在搜索過程中一般不需要其他外部信息，僅用適應(yīng)度來評(píng)估個(gè)體的優(yōu)劣，并以其作為遺傳操作的依據(jù)。4、選擇。選擇操作是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫，個(gè)體的適應(yīng)度越高，其被選擇的機(jī)會(huì)就越大。5、交叉。它是遺傳算法中最主要的操作，一般分兩步進(jìn)行，一是對(duì)群體中的個(gè)體進(jìn)行隨機(jī)配對(duì)；二是在配對(duì)個(gè)體中，隨機(jī)設(shè)定交叉處，使配對(duì)個(gè)體彼此交換部分信息。

11、6、變異。即按一定的概率改變個(gè)體的基因鏈。變異操作同樣是隨機(jī)進(jìn)行的，其目的是挖掘群體中個(gè)體的多樣性，克服遺傳操作可能限于局部解的弊端。（二）物流配送路徑優(yōu)化問題的遺傳算法的構(gòu)造針對(duì)物流配送路徑優(yōu)化問題的特點(diǎn)，作者構(gòu)造了求解該問題的遺傳算法。1、編碼方法的確定。根據(jù)物流配送路徑優(yōu)化問題的特點(diǎn)，作者采用了簡(jiǎn)單直觀的自然數(shù)編碼方法，用0表示配送中心，用1、2、L表示各需求點(diǎn)。由于在配送中心有K輛汽車，則最多存在K條配送路徑，每條配送路徑都始于配送中心，也終于配送中心，為了在編碼中反映車輛配送的路徑，作者巧妙地采用了增加K-1個(gè)虛擬配送中心的方法，分別用L+1、L+2、L+K-1表示。這樣，1、2、L

12、+K-1這L+K-1個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對(duì)應(yīng)一種配送路徑方案。例如，對(duì)于一個(gè)有7個(gè)需求點(diǎn)，用3輛汽車完成配送任務(wù)的問題，則可用1、2、9（8、9表示配送中心）這9個(gè)自然數(shù)的隨機(jī)排列，表示物流配送路徑方案。如個(gè)體129638547表示的的配送路徑方案為：路徑1：0-1-2-9（0），路徑2：9（0）-6-3-8（0），路徑3：8（0）-5-4-7-0，共有3條配送路徑；個(gè)體573894216表示的配送路徑方案為：路徑1：0-5-7-3-8（0），路徑2：9（0）-4-2-1-6-0，共有2條配送路徑。2、初始群體的確定。隨機(jī)產(chǎn)生一種1L+K-1這L+K-1個(gè)互不重復(fù)的自

13、然數(shù)的排列，即形成一個(gè)個(gè)體。設(shè)群體規(guī)模為N，則通過隨機(jī)產(chǎn)生N個(gè)這樣的個(gè)體，即形成初始群體。3、適應(yīng)度評(píng)估。對(duì)于某個(gè)個(gè)體所對(duì)應(yīng)的配送路徑方案，要判定其優(yōu)劣，一是要看其是否滿足配送的約束條件；二是要計(jì)算其目標(biāo)函數(shù)值（即各條配送路徑的長度之和）。本文根據(jù)配送路徑優(yōu)化問題的特點(diǎn)所確定的編碼方法，隱含能夠滿足每個(gè)需求點(diǎn)都得到配送服務(wù)及每個(gè)需求點(diǎn)僅由一輛汽車配送的約束條件，但不能保證滿足每條路徑上各需求點(diǎn)需求量之和不超過汽車載重量及每條配送路線的長度不超過汽車一次配送的最大行駛距離的約束條件。為此，對(duì)每個(gè)個(gè)體所對(duì)應(yīng)的配送路徑方案，要對(duì)各條路徑逐一進(jìn)行判斷，看其是否滿足上述兩個(gè)約束條件，若不滿足，則將該條路

14、徑定為不可行路徑，最后計(jì)算其目標(biāo)函數(shù)值。對(duì)于某個(gè)個(gè)體j，設(shè)其對(duì)應(yīng)的配送路徑方案的不可行路徑數(shù)為Mj（Mj=0表示該個(gè)體對(duì)應(yīng)一個(gè)可行解），其目標(biāo)函數(shù)值為Zj，則該個(gè)體的適應(yīng)度Fj可用下式表示：Fj=1/（Zj+MjG） （9）式中，G為對(duì)每條不可行路徑的懲罰權(quán)重，可根據(jù)目標(biāo)函數(shù)的取值范圍取一個(gè)相對(duì)較大的正數(shù)。4、選擇操作。將每代群體中的N個(gè)個(gè)體按適應(yīng)度由大到小排列，排在第一位的個(gè)體性能最優(yōu)，將它復(fù)制一個(gè)直接進(jìn)入下一代，并排在第一位。下一代群體的另N-1個(gè)個(gè)體需要根據(jù)前代群體的N個(gè)個(gè)體的適應(yīng)度，采用賭輪選擇法4產(chǎn)生。具體地說，就是首先計(jì)算上代群體中所有個(gè)體適應(yīng)度的總和（Fj），再計(jì)算每個(gè)個(gè)體的適應(yīng)

15、度所占的比例（Fj/Fj），以此作為其被選擇的概率。這樣選擇方法既可保證最優(yōu)個(gè)體生存至下一代，又能保證適應(yīng)度較大的個(gè)體以較大的機(jī)會(huì)進(jìn)入下一代。5、交叉操作。對(duì)通過選擇操作產(chǎn)生的新群體，除排在第一位的最優(yōu)個(gè)體外，另N-1個(gè)個(gè)體要按交叉概率Pc進(jìn)行配對(duì)交叉重組。本文采用了一種類似OX法2的交叉方法，現(xiàn)舉例說明之：隨機(jī)在父代個(gè)體中選擇一個(gè)交配區(qū)域，如兩父代個(gè)體及交配區(qū)域選定為：A=47|8563|921，B=83|4691|257；將B的交配區(qū)域加到A的前面，A的交配區(qū)域加到B的前面，得：A=4691|478563921，B=8563|834691257；在A、B中自交配區(qū)域后依次刪除與交配區(qū)相同的

16、自然數(shù)，得到最終的兩個(gè)體為：A”=469178532，B”=856349127。與其他交叉方法相比，這種方法在兩父代個(gè)體相同的情況下仍能產(chǎn)生一定程度的變異效果，這對(duì)維持群體的多樣化特性有一定的作用。6、變異操作。由于在選擇機(jī)制中采用了保留最佳樣本的方式，為保持群體內(nèi)個(gè)體的多樣化，本文采用了連續(xù)多次對(duì)換的變異技術(shù)，使個(gè)體在排列順序上的有較大變化。變異操作是以概率Pm發(fā)生的，一旦變異操作發(fā)生，則用隨機(jī)方法產(chǎn)生交換次數(shù)J，對(duì)所需變異操作的個(gè)體的基因進(jìn)行J次對(duì)換（對(duì)換基因的位置也是隨機(jī)產(chǎn)生的）。四、實(shí)驗(yàn)計(jì)算與結(jié)果分析作者根據(jù)上述遺傳算法編制了C語言程序，并對(duì)文獻(xiàn)列出的一個(gè)某配送中心使用2輛汽車對(duì)8個(gè)需

17、求點(diǎn)進(jìn)行送貨的物流配送路徑優(yōu)化問題實(shí)例進(jìn)行了實(shí)驗(yàn)計(jì)算。設(shè)汽車的載重量為8t，每次配送的最大行駛距離為40km，配送中心與各需求點(diǎn)之間、各需求點(diǎn)相互之間的距離及各需求點(diǎn)的需求量見表1。根據(jù)上述實(shí)例的特點(diǎn)，作者在實(shí)驗(yàn)計(jì)算中采用了以下參數(shù)：群體規(guī)模取20，交叉概率和變異概率分別取0.95和0.05，進(jìn)化代數(shù)取50，變異時(shí)基因換位次數(shù)取5，對(duì)不可行路徑的懲罰權(quán)重取100km。對(duì)上述問題，利用計(jì)算機(jī)隨機(jī)求解10次，得到的計(jì)算結(jié)果見表2。表2 物流配送路徑優(yōu)化問題的遺傳算法計(jì)算結(jié)果從表中數(shù)據(jù)可以看出，10次運(yùn)行得到的結(jié)果均優(yōu)于節(jié)約法所得的結(jié)果79.5km。而且第5次還得到了該問題的最優(yōu)解67.5km，其對(duì)

18、應(yīng)的配送路徑方案為：路徑1：0-4-7-6-0；路徑2：0-2-8-5-3-1-0?？梢?，利用遺傳算法可以方便有效地求得物流配送路徑優(yōu)化問題的最優(yōu)解或近似最優(yōu)解（或稱滿意解）。五、 結(jié)論（一）在物流配送業(yè)務(wù)中，合理確定配送路徑是提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟(jì)效益的重要手段。由于物流配送路徑優(yōu)化問題是一個(gè)NP難題，因此，采用啟發(fā)式算法求解是一個(gè)重要的研究方向。（二）本文在建立物流配送路徑優(yōu)化問題的數(shù)學(xué)模型的基礎(chǔ)上，構(gòu)造了求解物流配送路徑優(yōu)化問題的遺傳算法。實(shí)驗(yàn)計(jì)算結(jié)果表明，遺傳算法是一種性能優(yōu)良的啟發(fā)式搜索方法，利用該方法可以方便有效地求得物流配送路徑優(yōu)化問題的最優(yōu)解或滿意解。（三）本文所構(gòu)造的進(jìn)行物流配送路徑優(yōu)化的遺傳算法，包括巧妙設(shè)計(jì)的個(gè)體編碼方法、個(gè)體適應(yīng)值的計(jì)算方法以及選擇、交叉和變異算子，對(duì)解決類似的組合優(yōu)化問題具有一定的參考價(jià)值。參考文獻(xiàn)1