基于遺傳算法的物流配送路徑優(yōu)化研究

1、PAGE 1PAGE 12用單親遺傳算法求解配送車輛調(diào)度問題的研究郎茂祥（北京交通大學 交通運輸學院，北京 100044）摘 要：論文建建立了物物流配送送車輛調(diào)調(diào)度問題題的數(shù)學學模型，并并針對傳傳統(tǒng)遺傳傳算法對對復(fù)雜問問題搜索索效率低低，易陷陷入“早熟收收斂”的缺點點，構(gòu)建建了求解解物流配配送車輛輛調(diào)度問問題的單單親遺傳傳算法，并并進行了了實驗計計算。計計算結(jié)果果表明，用用單親遺遺傳算法法求解物物流配送送車輛調(diào)調(diào)度問題題，可以以取得比比傳統(tǒng)遺遺傳算法法更優(yōu)的的結(jié)果。 關(guān)關(guān)鍵詞：物流配配送；車車輛調(diào)度度問題；單親遺遺傳算法法；遺傳傳算法Studyy onn thhe PPartthenno-GG

2、eneeticc Allgorrithhm ffor Phyysiccal Disstriibuttionn Veehiccle Schheduulinng Proobleem LLANGG Maao-xxianng，HHU SSi-jji（Schoool of Traaffiic aand Traanspporttatiion，NNorttherrn JJiaootonng UUnivverssityy，Beeijiing 10000444，Chhinaa）Abstrractt：Thiis ppapeer eestaabliisheed tthe moddel of pphyssicaal

3、ddisttribbutiion vehhiclle sscheedullingg prrobllem. Onn thhe bbasiis oof aanallyziing thee shhorttcomminggs oof ttradditiionaal ggeneeticc allgorrithhm iin llow seaarchhingg effficcienncy andd “Immmatuure Connverrgennce”, tthiss paaperr esstabblisshedd a parrtheeno-gennetiic aalgooritthm foor ssolv

4、vingg phhysiicall diistrribuutioon vvehiiclee scchedduliing proobleem aand madde ssomee exxperrimeentaal ccompputaatioons. Thhe ccompputaatioonall reesullts hadd deemonnstrrateed tthatt thhe ppartthenno-ggeneeticc allgorrithhm hhad higgherr opptimmiziing effficiienccy aand quaalitty tthann trradiiti

5、oonall geenettic alggoriithmm inn soolviing phyysiccal disstriibuttionn veehiccle schheduulinng pprobblemm.Keywoordss：phhysiicall diistrribuutioon; vehhiclle sscheedullingg prrobllem; perrtheeno-gennetiic aalgooritthm; geenettic alggoriithmm1 引言言 隨隨著市場場經(jīng)濟的的發(fā)展和和物流專專業(yè)化水水平的提提高，物物流配送送業(yè)得到到了迅速速發(fā)展。在在物流配配送業(yè)

6、務(wù)務(wù)中，配配送車輛輛調(diào)度問問題的涉涉及面較較廣，對對企業(yè)提提高服務(wù)務(wù)質(zhì)量、降降低物流流成本的的影響也也較大。在在現(xiàn)實生生產(chǎn)和生生活中，郵郵政投遞遞問題、公公共汽車車調(diào)度問問題、電電力調(diào)度度問題、管管道鋪設(shè)設(shè)問題、計計算機網(wǎng)網(wǎng)絡(luò)拓撲撲設(shè)計問問題等都都可以抽抽象為物物流配送送車輛調(diào)調(diào)度問題題。因此此，研究究物流配配送車輛輛調(diào)度問問題具有有重要的的理論和和現(xiàn)實意意義。物流配送車車輛調(diào)度度問題作作為一個個NP難難題，隨隨著客戶戶數(shù)量的的增加，可可選的車車輛路徑徑方案數(shù)數(shù)量將以以指數(shù)速速度急劇劇增長。因因此，用用啟發(fā)式式算法求求解該問問題就成成為人們們研究的的一個重重要方向向。求解解物流配配送車輛輛調(diào)度

7、問問題的方方法很多多，常用用的有旅旅行商法法、動態(tài)態(tài)規(guī)劃法法1、節(jié)約約法22、掃掃描法3、分分區(qū)配送送算法4、方方案評價價法55等。遺傳算法的的出現(xiàn)為為求解物物流配送送車輛調(diào)調(diào)度問題題提供了了新的工工具。BBerttholld、MMalmmborrg、OOchii、姜大大立、李李大衛(wèi)、李李軍、謝謝秉磊、張張濤等人人都曾利利用遺傳傳算法求求解物流流配送車車輛調(diào)度度問題6-115，并并取得了了一些研研究成果果。作者者也嘗試試采用新新的編碼碼方法和和遺傳算算子構(gòu)造造了求解解物流配配送車輛輛調(diào)度問問題的遺遺傳算法法，并對對文獻9中中的例題題進行了了實驗計計算，計計算結(jié)果果表明，雖雖然利用用傳統(tǒng)遺遺傳算

8、法法能夠方方便地求求得問題題的近似似最優(yōu)解解，但也也暴露出出其存在在對復(fù)雜雜問題搜搜索效率率低，易易陷入“早熟收收斂” 166 的缺缺點。為為了提高高優(yōu)化效效率和質(zhì)質(zhì)量，作作者構(gòu)造造了求解解物流配配送車輛輛調(diào)度問問題的單單親遺傳傳算法，通通過實驗驗計算，取取得比傳傳統(tǒng)遺傳傳算法更更好的計計算結(jié)果果。2 物流流配送車車輛調(diào)度度問題的的數(shù)學模模型 物物流配送送車輛調(diào)調(diào)度問題題可以描描述為：從某物物流中心心用多臺臺配送車車輛向多多個客戶戶送貨，每每個客戶戶的位置置和貨物物需求量量一定，每每臺配送送車輛的的載重量量一定，其其一次配配送的最最大行駛駛距離一一定，要要求合理理安排車車輛配送送路線，使使目標

9、函函數(shù)得到到優(yōu)化，并并滿足以以下條件件：（11）每條條配送路路徑上各各客戶的的需求量量之和不不超過配配送車輛輛的載重重量；（22）每條條配送路路徑的長長度不超超過配送送車輛一一次配送送的最大大行駛距距離；（33）每個個客戶的的需求必必須滿足足，且只只能由一一臺配送送車輛送送貨。 設(shè)設(shè)物流中中心有KK臺配送送車輛，每每臺車輛輛的載重重量為QQk（k=1，22，KK），其其一次配配送的最最大行駛駛距離為為Dk，需要要向L個個客戶送送貨，每每個客戶戶的貨物物需求量量為qi（i=1，22，LL），客客戶i到j(luò)的運距距為dij，物物流中心心到各客客戶的距距離為dd0j（ii、j=1，2，L），再再設(shè)nk

10、為第kk臺車輛輛配送的的客戶數(shù)數(shù)（nk=0表表示未使使用第kk臺車輛輛），用用集合RRk表示第第k條路徑徑，其中中的元素素rki表示客客戶rki在路路徑k中的順順序為ii（不包包括物流流中心），令令rk0=0表示示物流中中心，若若以配送送總里程程最短為為目標函函數(shù)，則則可建立立如下物物流配送送車輛調(diào)調(diào)度問題題的數(shù)學學模型： （11） ss.t. （22） （33） （4） （55） （66） （7） （88）上述模型中中，（11）式為為目標函函數(shù)；（22）式保保證每條條路徑上上各客戶戶的貨物物需求量量之和不不超過配配送車輛輛的載重重量；（33）式保保證每條條配送路路徑的長長度不超超過配送送車輛

11、一一次配送送的最大大行駛距距離；（44）式表表明每條條路徑上上的客戶戶數(shù)不超超過總客客戶數(shù)；（5）式式表明每每個客戶戶都得到到配送服服務(wù)；（66）式表表示每條條路徑的的客戶的的組成；（7）式式限制每每個客戶戶僅能由由一臺配配送車輛輛送貨；（8）式式表示當當?shù)趉輛輛車服務(wù)務(wù)的客戶戶數(shù)1時，說說明該臺臺車參加加了配送送，則取取siggn(nnk)=11，當?shù)诘趉輛車車服務(wù)的的客戶數(shù)數(shù)1時，表表示未使使用該臺臺車輛，因因此取ssignn(nk)=00。3 物流流配送車車輛調(diào)度度問題的的單親遺遺傳算法法3.1 單親遺遺傳算法法簡介 單單親遺傳傳算法17是對傳傳統(tǒng)遺傳傳算法的的一種改改進，它它不使用用傳

12、統(tǒng)遺遺傳算法法中常用用的交叉叉算子，對對某個個個體的遺遺傳操作作只在該該條染色色體上進進行，即即只通過過單個個個體繁殖殖后代。對對于采用用自然數(shù)數(shù)編碼的的個體，單單親遺傳傳算法常常用的遺遺傳操作作算子有有：基因因換位算算子、基基因倒位位算子和和基因移移位算子子等，使使用這些些算子可可完全實實現(xiàn)PMMX、CCX、OOX等傳傳統(tǒng)交叉叉算子18的功能能。由于于單親遺遺傳算法法不使用用交叉算算子，即即使群體體中的個個體完全全相同，也也不影響響遺傳迭迭代的進進行，從從而擺脫脫了對群群體多樣樣性的要要求，能能克服“早熟收收斂”問題。使用單親遺遺傳算法法求解問問題，也也需要從從任一初初始群體體出發(fā)，通通過選

13、擇擇、染色色體重組組等遺傳傳操作，使使群體一一代一代代地進化化到搜索索空間中中越來越越好的區(qū)區(qū)域。單單親遺傳傳算法包包括編碼碼、初始始群體生生成、適適應(yīng)性評評估、選選擇和染染色體重重組5個個基本要要素。3.2 物流配配送車輛輛調(diào)度問問題的單單親遺傳傳算法的的構(gòu)造 （11）編碼碼方法的的確定。根根據(jù)物流流配送車車輛調(diào)度度問題的的特點，作作者采用用了簡單單直觀的的自然數(shù)數(shù)編碼方方法，用用0表示示配送中中心，用用1、22、LL表示各各需求點點。由于于在配送送中心有有K臺車車輛，則則最多存存在K條條配送路路徑，為為了在編編碼中反反映車輛輛配送的的路徑，作作者巧妙妙地采用用了增加加K-11個虛擬擬配送中

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

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

16、條條件。為為此，對對每個個個體所對對應(yīng)的配配送方案案，要對對各條路路徑逐一一進行判判斷，看看其是否否滿足上上述兩個個約束條條件，若若不滿足足，則將將該條路路徑定為為不可行行路徑，最最后計算算其目標標函數(shù)值值。對于于某個個個體j，設(shè)設(shè)其對應(yīng)應(yīng)的配送送路徑方方案的不不可行路路徑數(shù)為為Mj（Mj=0表示示該個體體是一個個可行解解），其其目標函函數(shù)值為為Zj，則該該個體的的適應(yīng)度度Fj，可用用下式表表示： FFj=1/（Zj+MjPw） （99）式中，Pww為對每每條不可可行路徑徑的懲罰罰權(quán)重（該該權(quán)重可可根據(jù)目目標函數(shù)數(shù)的取值值范圍取取一個相相對較大大的正數(shù)數(shù)）。 （44）選擇擇操作。將將每代群群體

17、中的的N個個個體按適適應(yīng)度由由大到小小排列，排排在第一一位的個個體性能能最優(yōu)，將將它復(fù)制制一個直直接進入入下一代代，并排排在第一一位。下下一代群群體的另另N-11個個體體需要根根據(jù)前代代群體的的N個個個體的適適應(yīng)度，采采用賭輪輪選擇法法產(chǎn)生。具具體地說說，就是是首先計計算上代代群體中中所有個個體適應(yīng)應(yīng)度的總總和（Fj），再再計算每每個個體體的適應(yīng)應(yīng)度所占占的比例例（Fjj/Fj），以以此作為為其被選選擇的概概率。這這樣選擇擇方法既既可保證證最優(yōu)個個體生存存至下一一代，又又能保證證適應(yīng)度度較大的的個體以以較大的的機會進進入下一一代。 （55）染色色體重組組。對通通過選擇擇操作產(chǎn)產(chǎn)生的新新群體，除

18、除排在第第一位的的最優(yōu)個個體外，另另N-11個個體體要運用用單親遺遺傳算子子進行染染色體重重組。本本文選用用多點基基因換位位算子實實現(xiàn)染色色體重組組，現(xiàn)舉舉例說明明其操作作過程：根據(jù)預(yù)預(yù)先確定定的最大大基因換換位次數(shù)數(shù)（Ncc），取取隨機數(shù)數(shù)k（11kNc）。本本例中設(shè)設(shè)Nc=4，kk=2。在染色體上隨機選取k對基因，并交換其位置。本例中設(shè)原染色體為A=478563921，隨機產(chǎn)生的第一對交換基因位為2和5，則基因換位后染色體變?yōu)锳=468573921；隨機產(chǎn)生的第二對交換基因位為3和8，再次實施基因換位后染色體變?yōu)锳”=462573981。判斷實施多點基因換位后，個體的適應(yīng)值是否增加，若增加

19、，則用換位后的個體取代原個體，進入下一代，否則原個體直接進入下一代。本例中設(shè)A”的適應(yīng)值大于A的適應(yīng)值，則A”進入下一代。 （66）終止止準則。采采用進化化指定代代數(shù)的終終止準則則。4 實驗驗計算與與結(jié)果分分析作者用C語語言分別別編制了了物流配配送車輛輛調(diào)度問問題的傳傳統(tǒng)遺傳傳算法程程序和單單親遺傳傳算法程程序，并并對文獻獻9中某配配送中心心使用22臺車輛輛對8個個需求點點送貨的的問題進進行了實實驗計算算（計算算時在原原問題的的基礎(chǔ)上上增加了了車輛一一次配送送的最大大行駛距距離為440kmm的約束束條件）。實實驗中采采用了以以下參數(shù)數(shù)：群體體規(guī)模為為20，進進化代數(shù)數(shù)為500，傳統(tǒng)統(tǒng)遺傳算算法

20、的交交叉概率率和變異異概率分分別取00.95和和0.05，單單親遺傳傳算法的的最大基基因換位位次數(shù)取取4。將將兩種算算法的計計算機程程序分別別隨機運運行100次，得得到的計計算結(jié)果果（即配配送路徑徑總長度度）見表表1。表1 物物流配送送車輛調(diào)調(diào)度問題題的傳統(tǒng)統(tǒng)遺傳算算法和單單親遺傳傳算法計計算結(jié)果果的比較較計算次序12345678910傳統(tǒng)遺傳算算法的計計算結(jié)果果Z /km727276.57067.57073.57571.569單親遺傳算算法的計計算結(jié)果果 ZZ /kkm6967.5707067.56967.5726971.5從表1可以以看出，傳傳統(tǒng)遺傳傳算法和和單親遺遺傳算法法的100次計算

21、算結(jié)果均均優(yōu)于節(jié)節(jié)約法的的結(jié)果779.55km，而而且單親親遺傳算算法得到到的結(jié)果果更優(yōu)，110次計計算中，單單親遺傳傳算法有有3次得得到了問問題的最最優(yōu)解667.55km，還還有3次次得到了了問題的的次優(yōu)解解69kkm，而而傳統(tǒng)遺遺傳算法法僅1次次得到了了最優(yōu)解解，1次次得到了了次優(yōu)解解。這充充分說明明，單親親遺傳算算法可以以克服傳傳統(tǒng)遺傳傳算法的的“早熟收收斂”問題，具具有良好好的搜索索效率和和尋優(yōu)性性能。另外，作者者還對文文獻119中中一個某某配送中中心使用用3臺車車輛向110個需需求點送送貨的實實例進行行了實驗驗計算，計計算顯示示了同樣樣的效果果，用單單親遺傳傳算法能能夠方便便地求得得

22、問題的的兩個最最優(yōu)解，其其配送路路徑總長長度都是是80kkm，其其中一個個解與文文獻119中中節(jié)約法法的計算算結(jié)果相相同。由由于該問問題的約約束條件件比較強強，利用用傳統(tǒng)遺遺傳算法法求解，有有時甚至至不能得得到可行行解。5 結(jié)論論（1）本文文在建立立物流配配送車輛輛調(diào)度問問題的數(shù)數(shù)學模型型的基礎(chǔ)礎(chǔ)上，針針對傳統(tǒng)統(tǒng)遺傳算算法對復(fù)復(fù)雜問題題搜索效效率低，易易陷入“早熟收收斂”的缺點點，構(gòu)造造了求解解物流配配送選擇擇問題的的單親遺遺傳算法法。實驗驗計算結(jié)結(jié)果表明明，單親親遺傳算算法可以以克服傳傳統(tǒng)遺傳傳算法的的上述缺缺點，從從而取得得比傳統(tǒng)統(tǒng)遺傳算算法更優(yōu)優(yōu)的結(jié)果果，充分分顯示了了其良好好的尋優(yōu)優(yōu)性

23、能。（2）本文文構(gòu)造單單親遺傳傳算法的的思路，以以及在算算法中巧巧妙設(shè)計計的個體體編碼方方法、個個體適應(yīng)應(yīng)值計算算方法及及選擇、多多點基因因換位等等遺傳算算子，對對解決類類似的組組合優(yōu)化化問題有有一定的的參考價價值。參考文獻獻1 蔡蔡希賢，夏夏士智編編譯. 物流合合理化的的數(shù)量方方法MM. 武漢：華中工工學院出出版社，119855.2 CClarrk GG. aand Wriightt J. . Schheduulinng oof vvehiiclees ffromm a cenntraal ddepoot tto aa nuumbeer oof ddeliiverry poiintssJ.

24、Opeens. Rees，119644，Noo.4.3 GGilllettt B. E. annd MMilller L RR. . A Heuurissticc Allgorrithhm ffor thee Veehiccle Disspattch ProobleemJJ. Oppns. Rees.，119744，222.4 羅羅上遠，徐徐天亮，陳陳代芬. 零售售業(yè)庫存存分布模模型及分分區(qū)配送送算法研研究JJ. 物流技技術(shù)，220000，Noo.5，pp22-25.5 劉劉朝暉，范范榮華，萬萬毅. 物資管管理系統(tǒng)統(tǒng)工程M. 北京京：中國國物資出出版社，119977年1月月.6 BBertth

25、odd Krrgerr. GGilllotiineaablee Biin PPackkingg: AA Geenettic AppproaachJ. Euuroppeann Joournnal of Opeerattionnal Ressearrch,19995,VVol.84,p6445-6661.7 MMalmmborrg, Chaarlees. Gennetiic AAlgooritthm forr Seerviice Levvel Bassed Vehhiclle SScheedullinggJ. EEuroopeaan JJourrnall off Opperaatioonall Reeseaarchh,19996,Voll.933,Noo.1,p1221-1134.8 OOchii,Luuiz S. Viiannna, Parralllel Evooluttionnaryy Allgorrithhm ffor