【正文】 1. 遺傳選擇選擇是用來(lái)確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。由于在配送中心有m 輛汽車(chē)，則最多存在m 條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。圖3 懲罰函數(shù) 帶時(shí)間窗的物流配送問(wèn)題優(yōu)化問(wèn)題帶時(shí)間窗 VRP（VRP with Time Windows，VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP，CVRP)的擴(kuò)展。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問(wèn)題，可廣泛用于組合優(yōu)化、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。它是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。西南交通大學(xué)的袁慶達(dá)等設(shè)計(jì)了考慮時(shí)間窗口和不同車(chē)輛類(lèi)型的禁忌算法，這種算法主要采用GENIUS方法產(chǎn)生初始解，然后禁忌算法對(duì)初始解優(yōu)化。節(jié)省法或插入法（savings or insertion）是在求解過(guò)程中使用節(jié)省成本最大的可行方式構(gòu)造路線，直到無(wú)法節(jié)省為止。下面從車(chē)輛路線問(wèn)題的現(xiàn)有研究型態(tài)和求解方法兩個(gè)方面介紹車(chē)輛路線問(wèn)題的研究現(xiàn)狀。 車(chē)輛路線問(wèn)題自1959年提出以來(lái)，一直是網(wǎng)絡(luò)優(yōu)化問(wèn)題中最基本的問(wèn)題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，一直受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。然后研究了遺傳算法與鄰域搜索算法的結(jié)合方式,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。提出了K近鄰點(diǎn)集的概念以縮減搜索空間并提高算法的時(shí)間效率。用系統(tǒng)仿真方法求解最優(yōu)庫(kù)存策略時(shí),其難點(diǎn)之一在于仿真的優(yōu)化。通過(guò)優(yōu)化物流系統(tǒng),可以降低物流成本,從而增強(qiáng)企業(yè)的市場(chǎng)競(jìng)爭(zhēng)能力。VRP 最早由Dantzig 和Ramser 于1959 年提出，引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科研究人員的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)問(wèn)題。 掃描法。本文主要對(duì)單車(chē)場(chǎng)非滿載無(wú)時(shí)間窗的車(chē)輛路徑問(wèn)題和動(dòng)態(tài)車(chē)輛路徑問(wèn)題進(jìn)行了研究。物流的目標(biāo)就在于以最少的費(fèi)用滿足消費(fèi)者的需求。在對(duì)遺傳算法中的選擇操作、鄰域結(jié)構(gòu)操作進(jìn)行改進(jìn)的基礎(chǔ)上,提出了一種求解車(chē)輛路徑問(wèn)題的自適應(yīng)遺傳算法。 genetic algorithm1引言車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）是一類(lèi)在物流配送調(diào)度中具有廣泛應(yīng)用的優(yōu)化組合問(wèn)題，在現(xiàn)代物流中居于中心地位。本文重點(diǎn)研究解決有時(shí)間窗裝卸問(wèn)題（PDPTW）的遺傳算法，作為前期準(zhǔn)備，本文作者對(duì)遺傳算法解決具有簡(jiǎn)單約束條件的VRP（包括有容量約束的車(chē)輛路徑問(wèn)題CVRP 和有時(shí)間窗的車(chē)輛路徑問(wèn)題VRPTW）進(jìn)行了初步研究。如果能降低庫(kù)存成本與配送成本,就能有效地降低物流成本。提出了M精英選擇算子,用于保護(hù)潛在的最優(yōu)個(gè)體,使它們?cè)诮徊妗⒆儺愃阕又胁槐黄茐?。雙層染色體編碼方案不需要預(yù)先知道最優(yōu)解所需要的車(chē)輛數(shù),并能確保染色體不違反能力約束,這更適合求解實(shí)際物流配送系統(tǒng)中的車(chē)輛路徑問(wèn)題。VRP仿真實(shí)驗(yàn)室在本文的研究中發(fā)揮了重要的作用,是研究車(chē)輛路徑問(wèn)題的有力工具。車(chē)輛路線的實(shí)際問(wèn)題包括配送中心配送、公共汽車(chē)路線制定、信件和報(bào)紙投遞、航空和鐵路時(shí)間表安排、工業(yè)廢品收集等。1995年，F(xiàn)isher曾將求解車(chē)輛路線問(wèn)題的算法分成三個(gè)階段。簡(jiǎn)單啟發(fā)式方法簡(jiǎn)單易懂、求解速度快，但只適合求解小型、簡(jiǎn)單的VRP問(wèn)題?，F(xiàn)在多數(shù)學(xué)者采用混合策略，分別采用兩種人工智能方法進(jìn)行路線分組和路線優(yōu)化。遺傳算法是受生物進(jìn)化學(xué)說(shuō)和遺傳學(xué)說(shuō)啟發(fā)而發(fā)展起來(lái)的，基于適者生存思想的一種較通用的問(wèn)題求解方法。遺傳算法中包含了如下5個(gè)基本要素：1)參數(shù)編碼；2)初始群體的設(shè)定；3)適應(yīng)度函數(shù)的設(shè)計(jì)；4)遺傳操作設(shè)計(jì)；5）控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)。另外，變量和的值為0或1。按客戶(hù)對(duì)物流中心違反時(shí)間窗約束規(guī)定時(shí)的接受程度，可分為硬時(shí)間窗、軟時(shí)間窗和混合型時(shí)間窗。例如，對(duì)于一個(gè)有6 個(gè)需求點(diǎn)，用2 輛汽車(chē)完成配送任務(wù)的問(wèn)題，則可用0、…、6 (0 表示配送中心)這7 個(gè)自然數(shù)的隨機(jī)排列表示物流配送路徑方案。2. 遺傳基因的交叉對(duì)通過(guò)選擇操作產(chǎn)生的新群體，需要進(jìn)行配對(duì)交叉重組。B=6 2 9 8|8 3 2 9 5 4 1 6 7最后在39。一旦車(chē)輛分配方案確定，那么路線安排問(wèn)題也就比較容易求解（即求解變量）。隨機(jī)產(chǎn)生初始車(chē)輛分配方案，并淘汰不符合約束條件的染色體,直到染色體群的種群數(shù)達(dá)N條。對(duì)每一條染色體，求解變量，并計(jì)算每一條染色體的適配值：!本算法采用與適配值成比例的概率方法，對(duì)種群的個(gè)體進(jìn)行選擇與復(fù)制。變異概率取不同的值對(duì)算法性能的影響很大；過(guò)大，求解時(shí)間明顯增加$但算法收斂于局部最優(yōu)的可能性減少。已知各客戶(hù)的需求和各客戶(hù)之間的距離如表 1(其中0 表示配送中心)，要求合理安排車(chē)輛的行駛路線，使總的運(yùn)距最短。7 結(jié)束語(yǔ)隨著畢業(yè)日子的到來(lái)，畢業(yè)設(shè)計(jì)也接近了尾聲。我的心得也就這么多了，總之，不管學(xué)會(huì)的還是學(xué)不會(huì)的的確覺(jué)得困難比較多，真是萬(wàn)事開(kāi)頭難，不知道如何入手。8 參考文獻(xiàn)[1] 鐘石泉，賀國(guó)光. 單車(chē)場(chǎng)復(fù)雜情況下的車(chē)輛調(diào)度[J]. 系統(tǒng)工程，2005,23(5):2932.[2] 肖健梅，黃有方，李軍軍,等. 基于離散微粒群優(yōu)化的物流配送車(chē)輛路徑問(wèn)題[J]. 系統(tǒng)工程，2005,23(4):97100.[3] 張建勇，郭耀煌，李軍. 基于顧客滿意度的多目標(biāo)模糊車(chē)輛優(yōu)化調(diào)度問(wèn)題研究[J]. 鐵道學(xué)報(bào)，2003,25(2):1517.[4] 李軍，郭耀煌. 物流配送車(chē)輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國(guó)物資出版社，2001.[5] 郭惠昕，車(chē)曉毅，肖偉躍. 混沌遺傳優(yōu)化算法及其在機(jī)械優(yōu)化設(shè)計(jì)中的應(yīng)用[J]. 機(jī)械設(shè)計(jì)，2003,20(10):2325.[6] YungChien Lin, FengSheng Wang, KaoShing Hwang. A hybrid method of evolutionary algorithms for mixedinteger nonlinear optimization problems[C] // Proceedings of the 1999 Congress on Evolutionary Computation, 1999:21602166.[7] 李?lèi)?ài)國(guó). 多粒子群協(xié)同優(yōu)化算法[J]. 復(fù)旦大學(xué)學(xué)報(bào)，2004(6):8790.[8] 陳一永，韓紅，龔延成. 帶時(shí)間約束的配載車(chē)輛調(diào)度問(wèn)題研究[J]. 物流技術(shù)，2005,25(3):4850.[9] Savelsbergh search for routing problem with time windows. Annals of OperationsResearch,1985,16(4): 285305.[10] 曾凡超. 車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J]，重慶大學(xué), 2007.[11] 徐天亮. 運(yùn)輸與配送[M]，北京：中國(guó)物資出版社, 2002.[12] 晏夢(mèng)君. 遺傳算法在配送線路優(yōu)化系統(tǒng)中的應(yīng)用[J], 吉林大學(xué), .[13]:Anovevriewofexactandapproximatealgorithms[J].EuroPeanJounralofOPerationalReseareh，:34535