【正文】 我的心得也就這么多了，總之，不管學(xué)會(huì)的還是學(xué)不會(huì)的的確覺得困難比較多，真是萬事開頭難，不知道如何入手。已知各客戶的需求和各客戶之間的距離如表 1(其中0 表示配送中心)，要求合理安排車輛的行駛路線，使總的運(yùn)距最短。對(duì)每一條染色體，求解變量，并計(jì)算每一條染色體的適配值：!本算法采用與適配值成比例的概率方法，對(duì)種群的個(gè)體進(jìn)行選擇與復(fù)制。一旦車輛分配方案確定，那么路線安排問題也就比較容易求解（即求解變量）。2. 遺傳基因的交叉對(duì)通過選擇操作產(chǎn)生的新群體，需要進(jìn)行配對(duì)交叉重組。按客戶對(duì)物流中心違反時(shí)間窗約束規(guī)定時(shí)的接受程度，可分為硬時(shí)間窗、軟時(shí)間窗和混合型時(shí)間窗。遺傳算法中包含了如下5個(gè)基本要素：1)參數(shù)編碼；2)初始群體的設(shè)定；3)適應(yīng)度函數(shù)的設(shè)計(jì)；4)遺傳操作設(shè)計(jì)；5）控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)?，F(xiàn)在多數(shù)學(xué)者采用混合策略，分別采用兩種人工智能方法進(jìn)行路線分組和路線優(yōu)化。1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個(gè)階段。VRP仿真實(shí)驗(yàn)室在本文的研究中發(fā)揮了重要的作用,是研究車輛路徑問題的有力工具。提出了M精英選擇算子,用于保護(hù)潛在的最優(yōu)個(gè)體,使它們?cè)诮徊?、變異算子中不被破壞。本文重點(diǎn)研究解決有時(shí)間窗裝卸問題（PDPTW）的遺傳算法，作為前期準(zhǔn)備，本文作者對(duì)遺傳算法解決具有簡單約束條件的VRP（包括有容量約束的車輛路徑問題CVRP 和有時(shí)間窗的車輛路徑問題VRPTW）進(jìn)行了初步研究。在對(duì)遺傳算法中的選擇操作、鄰域結(jié)構(gòu)操作進(jìn)行改進(jìn)的基礎(chǔ)上,提出了一種求解車輛路徑問題的自適應(yīng)遺傳算法。本文主要對(duì)單車場(chǎng)非滿載無時(shí)間窗的車輛路徑問題和動(dòng)態(tài)車輛路徑問題進(jìn)行了研究。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)問題。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時(shí),其難點(diǎn)之一在于仿真的優(yōu)化。然后研究了遺傳算法與鄰域搜索算法的結(jié)合方式,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個(gè)方面介紹車輛路線問題的研究現(xiàn)狀。西南交通大學(xué)的袁慶達(dá)等設(shè)計(jì)了考慮時(shí)間窗口和不同車輛類型的禁忌算法，這種算法主要采用GENIUS方法產(chǎn)生初始解，然后禁忌算法對(duì)初始解優(yōu)化。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。圖3 懲罰函數(shù) 帶時(shí)間窗的物流配送問題優(yōu)化問題帶時(shí)間窗 VRP（VRP with Time Windows，VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP，CVRP)的擴(kuò)展。由于適應(yīng)度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問題則是求最小經(jīng)濟(jì)成本，為了便于計(jì)算且增大區(qū)分度，算法采用的是目標(biāo)函數(shù)的倒數(shù)乘以區(qū)分度系數(shù)β作為適應(yīng)度函數(shù)，即maxF = 1 / S * β (3231) 遺傳算子1. 遺傳選擇選擇是用來確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。即事先設(shè)置一個(gè)最大代數(shù)，如當(dāng)前代數(shù)大于最大代數(shù)時(shí)，算法停止。該子問題可表示為滿足約束條件：本文采用文獻(xiàn)[3]中的啟發(fā)式方法進(jìn)行求解。遺傳操作重疊結(jié)構(gòu)的SGA(simple genetic algorithm),并在選擇操作前保留當(dāng)前最好解:因此以概率收斂到全局最優(yōu)解。自己要學(xué)習(xí)的東西還太多，以前老是覺得自己什么東西都會(huì)，什么東西都懂，有點(diǎn)眼高手低。在此要感謝我的指導(dǎo)老師雷德明對(duì)我悉心的指導(dǎo)，感謝老師給我的幫助。可經(jīng)驗(yàn)證，該解正是問題的最優(yōu)解。對(duì)染色體群實(shí)施交叉操作crossover（）可以產(chǎn)生新的體。對(duì)于車輛調(diào)度問題，可將求解變量看作染色體，因此，一條染色體就代表一種可能的車輛分配方案，然后可用布爾矩陣對(duì)該染色體的基因鏈進(jìn)行編碼。在得到新的兩個(gè)染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法加入了淘汰機(jī)制，即比較兩個(gè)新染色體，保留較好的一個(gè)進(jìn)入下一代，同時(shí)將較差的一個(gè)舍棄。如出現(xiàn)某客戶需求量大于車輛負(fù)載（容積）的情況時(shí)，需要先派車為其運(yùn)輸，直至該客戶剩余貨物需求量小于車輛最大負(fù)載（容積）即可參加優(yōu)化調(diào)度。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。 總結(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的發(fā)展前途的方法；SA算法求解速度非常快，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問題上具有較好效果。車輛運(yùn)輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 由此定義不難看出，旅行商問題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery。為了求解TSP問題,研究了常用于TSP問題的三種交叉算子的優(yōu)化效果,提出了一種求解TSP問題的高效混合遺傳算法HGATSP。CVRP 要求滿足以下條件及假設(shè)：（1）所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心；（2）每條配送路徑上各客戶點(diǎn)的需求量之和不超過車輛的負(fù)載量；（3）每個(gè)客戶點(diǎn)的需求僅由一輛車一次滿足。最后論文在對(duì)動(dòng)態(tài)行駛時(shí)間車輛路徑問題進(jìn)行建模的基礎(chǔ)上,嘗試采用掃描法和改進(jìn)遺傳算法相結(jié)合的方法對(duì)此類問題進(jìn)行求解,在保證客戶服務(wù)水平的要求下,取得了比較好的結(jié)果。配送的核心為配送車輛的調(diào)度、貨物配裝及送貨過程。本文詳細(xì)分析了有時(shí)間窗裝卸問題的數(shù)學(xué)模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標(biāo)的適應(yīng)度函數(shù)，設(shè)計(jì)新的數(shù)據(jù)結(jié)構(gòu)，對(duì)分組編碼遺傳算法進(jìn)行有效實(shí)現(xiàn)。在上述研究基礎(chǔ)上,本文基于遺傳算法,研究了物流系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。子路徑交換算法可以有效提高遺傳算法的求解精度。 相同的單一起點(diǎn)和終點(diǎn)。前者是先將所有需求點(diǎn)大略分為幾個(gè)組，然后再對(duì)各個(gè)組分別進(jìn)行路線排序；后者則是先將所有的需求點(diǎn)建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨(dú)路線。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。約束條件2：保證每個(gè)客戶均被服務(wù)，而且每輛車都從配送中心出發(fā)；約束條件3：表示每輛車負(fù)責(zé)的客戶點(diǎn)的貨物需求量總和不超過該車輛的最大裝載量；約束條件5：表示對(duì)任一由k服務(wù)的客戶點(diǎn)j必定有另一(而且只有一個(gè))由k服務(wù)的客戶點(diǎn)(包括配送中心)I,車輛k從客戶點(diǎn)i到達(dá)客戶點(diǎn)j,而對(duì)由k服務(wù)的客戶點(diǎn)i同樣存在由k服務(wù)的另一客戶點(diǎn),車輛k是從該客戶點(diǎn)到達(dá)客戶點(diǎn)i的,依次類推；約束條件6：保證每輛車的行車路線的總耗時(shí)不超過一個(gè)事先定下的數(shù)值；約束條件7：對(duì)某個(gè)客戶點(diǎn)，車輛到達(dá)時(shí)間限制在某一時(shí)間段內(nèi)。本文采用隨機(jī)產(chǎn)生一種l～L＋m－l 這L＋m－l 個(gè)互不重復(fù)的自然數(shù)的排列，即形成一個(gè)個(gè)體。B 中自交配區(qū)域后依次刪除與交配區(qū)域相同的自然數(shù)，得到最終的兩個(gè)后代：C1=2 9 5 4 3 6 8 7 1C2=6 2 9 8 3 8 4 1 73. 遺傳基因的變異基因的變異是在選出的染色體中按其變異概率隨機(jī)找出若干基因位置，再隨機(jī)產(chǎn)生一個(gè)基因替換原有位置基因，并查找因替換基因產(chǎn)生的此基因的另一重復(fù)位置，修改使之成為一個(gè)不重復(fù)基因染色體。過大不但增加計(jì)算量，而且不能有效地獲得迭代解。算法停止準(zhǔn)則的設(shè)計(jì)淘汰不符合約束條件2）、3）的染色體。在沒有