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