【正文】 它普通貨物再進(jìn)行優(yōu)化；即如有N 個(gè)客戶，其中有一個(gè)為緊急運(yùn)單，則自動(dòng)將其放在隊(duì)首，其他N1 個(gè)客戶進(jìn)行優(yōu)化，即將問(wèn)題降為N1 階的路徑優(yōu)化問(wèn)題；任一客戶只由一臺(tái)運(yùn)輸車輛提供服務(wù)，即算法解決的是任一客戶的貨物需求均小于車輛最大負(fù)載（容積）的情況。約束條件2：保證每個(gè)客戶均被服務(wù)，而且每輛車都從配送中心出發(fā)；約束條件3：表示每輛車負(fù)責(zé)的客戶點(diǎn)的貨物需求量總和不超過(guò)該車輛的最大裝載量；約束條件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í)不超過(guò)一個(gè)事先定下的數(shù)值；約束條件7：對(duì)某個(gè)客戶點(diǎn)，車輛到達(dá)時(shí)間限制在某一時(shí)間段內(nèi)。 遺傳算法的基本思想遺傳算法是受生物進(jìn)化學(xué)說(shuō)和遺傳學(xué)說(shuō)啟發(fā)而發(fā)展起來(lái)的，基于適者生存思想的一種較通用的問(wèn)題求解方法。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡(jiǎn)單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。Bent和Van Hentenryck則首先用模擬退火算法將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（largneighborhood search）將運(yùn)輸費(fèi)用降到最低。前者是先將所有需求點(diǎn)大略分為幾個(gè)組，然后再對(duì)各個(gè)組分別進(jìn)行路線排序；后者則是先將所有的需求點(diǎn)建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨(dú)路線。 啟發(fā)式算法 由于VRP是NPhard問(wèn)題，難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運(yùn)輸問(wèn)題的主要方法，多年來(lái)許多學(xué)者對(duì)車輛運(yùn)輸問(wèn)題進(jìn)行了研究，提出了各種各樣的啟發(fā)式方法。 相同的單一起點(diǎn)和終點(diǎn)。3 問(wèn)題描述車輛路線問(wèn)題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。子路徑交換算法可以有效提高遺傳算法的求解精度。 (2)旅行商問(wèn)題(TSP)是車輛路徑問(wèn)題的子問(wèn)題。在上述研究基礎(chǔ)上,本文基于遺傳算法,研究了物流系統(tǒng)中的庫(kù)存優(yōu)化問(wèn)題及車輛路徑問(wèn)題。CVRP 實(shí)際是多目標(biāo)組合優(yōu)化問(wèn)題，一般以派出車輛最少（運(yùn)輸路線條數(shù)最少）為首要目標(biāo)，行車總距離最短，即總代價(jià)最小為次要目標(biāo)。本文詳細(xì)分析了有時(shí)間窗裝卸問(wèn)題的數(shù)學(xué)模型，深入研究解決此問(wèn)題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標(biāo)的適應(yīng)度函數(shù)，設(shè)計(jì)新的數(shù)據(jù)結(jié)構(gòu)，對(duì)分組編碼遺傳算法進(jìn)行有效實(shí)現(xiàn)。與傳統(tǒng)遺傳算法相比,掃描法和改進(jìn)遺傳算法的結(jié)合,其優(yōu)化能力、運(yùn)行效率、可靠性均有一定的提高。配送的核心為配送車輛的調(diào)度、貨物配裝及送貨過(guò)程。進(jìn)行配送系統(tǒng)優(yōu)化,主要是配送車輛調(diào)度的優(yōu)化。最后論文在對(duì)動(dòng)態(tài)行駛時(shí)間車輛路徑問(wèn)題進(jìn)行建模的基礎(chǔ)上,嘗試采用掃描法和改進(jìn)遺傳算法相結(jié)合的方法對(duì)此類問(wèn)題進(jìn)行求解,在保證客戶服務(wù)水平的要求下,取得了比較好的結(jié)果。在分組編碼遺傳算法中提出路徑調(diào)整思想，設(shè)計(jì)出一種多策略分組編碼遺傳算法。CVRP 要求滿足以下條件及假設(shè)：（1）所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心；（2）每條配送路徑上各客戶點(diǎn)的需求量之和不超過(guò)車輛的負(fù)載量；（3）每個(gè)客戶點(diǎn)的需求僅由一輛車一次滿足。本文將庫(kù)存仿真優(yōu)化問(wèn)題與車輛路徑問(wèn)題都看作是組合優(yōu)化問(wèn)題,并應(yīng)用遺傳算法進(jìn)行求解。為了求解TSP問(wèn)題,研究了常用于TSP問(wèn)題的三種交叉算子的優(yōu)化效果,提出了一種求解TSP問(wèn)題的高效混合遺傳算法HGATSP?；谏鲜鲭p層染色體編碼方案和子路徑交換算法,設(shè)計(jì)了兩種求解CVRP問(wèn)題的混合遺傳算法,分別是HGACVRP算法和HGASECVRP算法。 由此定義不難看出，旅行商問(wèn)題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery。 多個(gè)起點(diǎn)和終點(diǎn)。車輛運(yùn)輸問(wèn)題的啟發(fā)式方法可以分為簡(jiǎn)單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 1990年以來(lái)，人工智能方法在解決組合優(yōu)化問(wèn)題上顯示出強(qiáng)大功能，在各個(gè)領(lǐng)域得到充分應(yīng)用，很多學(xué)者也將人工智能引入車輛路線問(wèn)題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法。 總結(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長(zhǎng)，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的發(fā)展前途的方法；SA算法求解速度非?？?，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問(wèn)題上具有較好效果。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。根據(jù)實(shí)際情況，本文采用軟限制時(shí)間窗，其懲罰函數(shù)如圖2所示。如出現(xiàn)某客戶需求量大于車輛負(fù)載（容積）的情況時(shí)，需要先派車為其運(yùn)輸，直至該客戶剩余貨物需求量小于車輛最大負(fù)載（容積）即可參加優(yōu)化調(diào)度。設(shè)群體規(guī)模為M，則通過(guò)隨機(jī)產(chǎn)生M 個(gè)這樣的個(gè)體，即形成初始群體。在得到新的兩個(gè)染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法加入了淘汰機(jī)制，即比較兩個(gè)新染色體，保留較好的一個(gè)進(jìn)入下一代，同時(shí)將較差的一個(gè)舍棄。為了使后代繼承更多的父代的基因信息，本文取變異概率Pm 左右。對(duì)于車輛調(diào)度問(wèn)題，可將求解變量看作染色體，因此，一條染色體就代表一種可能的車輛分配方案，然后可用布爾矩陣對(duì)該染色體的基因鏈進(jìn)行編碼。過(guò)小將不能保證分配方案的多樣性，本算法中取種群大小，交叉概率,變異概。對(duì)染色體群實(shí)施交叉操作crossover（）可以產(chǎn)生新的體。如果，則轉(zhuǎn)啟發(fā)式算法求解，否則在染色體群中選擇最小的染色體，作為該問(wèn)題的求解變量值；與該變量相對(duì)應(yīng)的變量就是優(yōu)化的路線安排?？山?jīng)驗(yàn)證，該解正是問(wèn)題的最優(yōu)解。畢業(yè)設(shè)計(jì)不僅是對(duì)前面所學(xué)知識(shí)的一種檢驗(yàn)，而且也是對(duì)自己能力的一種提高。在此要感謝我的指導(dǎo)老師雷德明對(duì)我悉心的指導(dǎo)，感謝老師給我的幫助。在整個(gè)設(shè)計(jì)中我懂得了許多東西，也培養(yǎng)了我獨(dú)立工作的能力，樹立了對(duì)自己工作能力的信心，相信會(huì)對(duì)今后的學(xué)習(xí)工作生活有非常重要的影響。自己要學(xué)習(xí)的東西還太多，以前老是覺(jué)得自己什么東西都會(huì)，什么東西都懂，有點(diǎn)眼高手低。在物流配送業(yè)務(wù)中，合理確定配送路徑是提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟(jì)效益的重要手段。遺傳操作重疊結(jié)構(gòu)的SGA(simple genetic algorithm),并在選擇操作前保留當(dāng)前最好解:因此以概率收斂到全局最優(yōu)解。交叉概率對(duì)算法的收斂有較大的影響，越大，優(yōu)秀的個(gè)體出現(xiàn)的幾率也越大，新舊個(gè)體替換快，算法收斂也快。該子問(wèn)題可表示為滿足約束條件：本文采用文獻(xiàn)[3]中的啟發(fā)式方法進(jìn)行求解。例如，圖1的布爾矩陣為即車輛1負(fù)責(zé)客戶1和2，車輛2負(fù)責(zé)客戶4和5.適應(yīng)度函數(shù)是遺傳算法中評(píng)價(jià)解集好壞的依據(jù),適配值高的個(gè)體優(yōu)先培養(yǎng)。即事先設(shè)置一個(gè)最大代數(shù)，如當(dāng)前代數(shù)大于最大代數(shù)時(shí)，算法停止。實(shí)施交叉操作。由于適應(yīng)度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問(wèn)題則是求最小經(jīng)濟(jì)成本，為了便于計(jì)算且增大區(qū)分度，算法采用的是目標(biāo)函數(shù)的倒數(shù)乘以區(qū)分度系數(shù)β作為適應(yīng)度函數(shù)，即maxF = 1 / S * β (3231) 遺傳算子