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