【正文】 thm）與 啟發(fā)式解法 （ heuristics），其中精密算法有 分支界限法 、 分支切割法 、 集合涵蓋法 等；啟發(fā)式解法有 節(jié)約法 、 模擬退火法 、 確定性退火法 、 禁忌搜尋法 、 基因算法 、 神經(jīng)網(wǎng)絡(luò) 、 螞蟻殖民算法 等。車輛運(yùn)輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 1960 年， Clarke 和 Wrigh 首先提出一種啟發(fā)式節(jié)省法（ savings methods）來建立車隊(duì)配送路線。 1990 年以來，人工智能方法在解決組合優(yōu)化問題上顯示出強(qiáng)大功能，在各個(gè)領(lǐng)域得到充分應(yīng)用，很多學(xué)者也將 人工智能 引入車輛路線問題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法 。 遺傳算法 具有求解組合優(yōu)化問題的良好特性， Holland 首先采用遺傳算法（ GA）編碼解決 VRPTW 問題。 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ī)模問題上具有較好效果。當(dāng)時(shí)，其主要目的是說明自然和人工系統(tǒng)的自適應(yīng)過程。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗 者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。 遺傳算法是具有 “ 生成 +檢測 ”(generate andtest)的迭代過程的搜索算法 。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。 遺傳算法流程圖 13 圖 2 遺傳算法流程圖 14 5 模型建立求解及實(shí)例應(yīng)用 車輛調(diào)度模型 根據(jù)上述對問題的描述 ， 可以采用混合整數(shù)規(guī)劃方法對車輛調(diào)度進(jìn)行建模 設(shè) N為最小成本 ， 則目標(biāo)函數(shù)為 滿足約束條件 1： 式中： K為所有車輛的集合， ； G為所有客戶的集合， ， ， 其中 {0}代表配送中心 ； 為由車輛 k服務(wù)的客戶的集合； 為車輛到達(dá)客戶 i的時(shí)間； 為懲罰函數(shù)，車輛在時(shí)間 到達(dá)客戶 i時(shí)所對應(yīng)的懲罰成本； 為車輛從客戶 i到客戶 j的所有運(yùn)輸成本； 為車輛從客戶 i到客戶 j的行車時(shí)間； 為客戶 i的需求量 ； Q為車輛 k的最大裝載量； 為車輛在客戶 i處的停留的時(shí)間。 根據(jù)實(shí)際情況 ， 本文采用軟限制時(shí)間窗 ， 其懲罰函數(shù) 如圖 2所示 。客戶的服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)開始，車輛必須在客戶點(diǎn)停留的時(shí)間長度為 si。如出現(xiàn)某客戶需求量大于車輛負(fù)載（容積）的情況時(shí)，需要先派車為其運(yùn)輸，直至該客戶剩余貨物需求量小于車輛最大負(fù)載（容積）即可參加優(yōu)化調(diào)度。這樣， l、 … 、 L＋ m－ l 這 L＋ m－ l 個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對應(yīng)一種配送路徑方案。設(shè)群體規(guī)模為 M，則通過隨機(jī)產(chǎn)生 M 個(gè)這樣的個(gè)體，即形成初始群體。生成一個(gè) [0,1]范圍內(nèi)的隨機(jī)數(shù)，看它落在哪個(gè)區(qū)域，則選擇該個(gè)體。在得到新的兩個(gè)染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法加入了淘汰機(jī)制，即比較兩個(gè)新染色體，保留較好的一個(gè)進(jìn)入下一代，同時(shí)將較差的一個(gè)舍棄。A=2 9 5 4|3 5 6 2 9 8 4 7 1 39。為了使后代繼承更多的父代的基因信息，本文取變異概率 Pm 為 左右。 步驟 Step1： t=0，利用自然數(shù)編碼方式，采用前相插入啟發(fā)式算法和隨機(jī)的方式產(chǎn)生初始種群，并輸入控制參數(shù)； Step2：計(jì)算個(gè)體適應(yīng)度； Step3： t maxt， t=t+1，則轉(zhuǎn) Step4；否則停止計(jì)算，并輸出結(jié)果； Step4：采用基于個(gè)體濃度的群體多樣性保持策略來選擇個(gè)體； Step5：對個(gè)體進(jìn)行 CX 交叉重組； 19 Step6：按照變異方法對個(gè)體進(jìn)行變異； Step7：重復(fù)步驟 26； 20 6 算法的建立和求解 車輛優(yōu)化調(diào)度問題由車輛分配和路線安排這兩個(gè)相互關(guān)聯(lián)的子問題組成 ， 但關(guān)鍵是確定優(yōu)化的車輛分配方案 （ 即求解變量 ）。 對于車輛調(diào)度問題 ， 可將求解變量 看作染色體 ， 因此 ， 一條染色體就代表一種可能的車輛分配方案 ， 然后可用布爾矩陣對該染色體的基因鏈進(jìn)行編碼 。 個(gè)體適配值為 式中 ， 所以 ， 目標(biāo)函數(shù) 生成初始染色體種群 初始化遺傳世代 ； 每一代的染色體群的 種群數(shù)目 ； 交叉概率 ， 變異概率 等參數(shù) 。 過小將不能保證分配方案的多樣性 ， 本算法中取種群大小 ， 交叉概率 ,變異概。 淘汰不符合約束條件的解 ， 調(diào)整次序重新搜索 ， 直到找到較佳的可行解為止 。 對染色體群實(shí)施交叉操作 crossover（） 可以產(chǎn)生新的 體 。 變異操作 變異操作 mutation（） 以概率 對染色體群中的某些染色體的某些位進(jìn)行變異 ， 產(chǎn)生新的個(gè)體染色體 、 作為交叉運(yùn)算的補(bǔ)充 ， 變異操作可增加車輛分配方案的多樣性 ， 克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象 。 如果 ，則轉(zhuǎn) 啟發(fā)式算法求解 ， 否則在染色體群中選擇 最小的染色體 ， 作為該問題的求解變量 值 ； 與該變量相對應(yīng)的變量 就是優(yōu)化的路線安排 。用上述的帶時(shí)間窗的遺傳算法，對一個(gè)有 8 個(gè)客戶和 1 個(gè)配送中心，兩輛車（容量均為 8 噸）的配送系統(tǒng)的車輛路徑問題進(jìn)行求解?？山?jīng)驗(yàn)證，該解正是問題的最優(yōu)解。所構(gòu)造的物流配送路徑優(yōu)化的遺傳算法，包括設(shè)計(jì)個(gè)體編碼方法、個(gè)體適應(yīng)度值的計(jì)算方法以及選擇、交叉和變異算子，對解決類似的組合優(yōu)化問題具有一定的參考價(jià)值。畢業(yè)設(shè)計(jì)不僅是對前面所學(xué)知識(shí)的一種檢驗(yàn)，而且也是對自己能力的一種提高。 在這次畢業(yè)設(shè)計(jì)中也使我們的同學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽聽不同的看法對我們更好的理解知識(shí)，所以在這里 非常感謝幫助我的同學(xué)。 在此要感謝我的指導(dǎo)老師雷德明對我悉心的指導(dǎo)，感謝老師給我的幫助。雖然這個(gè)設(shè)計(jì)做的也不太好，但是在設(shè)計(jì)過程中所學(xué)到的東西是這次畢業(yè)設(shè)計(jì)的最大收獲和財(cái)富，使我終身受益。在整個(gè)設(shè)計(jì)中我懂得了許多東西，也培養(yǎng)了我獨(dú)立工作的能力，樹立了對自己工作能力的信心，相信會(huì)對今后的學(xué)習(xí)工作生活有非常重要的影響。最后終于做完了有種如釋重負(fù)的感覺。自己要學(xué)習(xí)的東西還太多，以前老是覺得自己什么東西都會(huì)，什么東西都懂，有點(diǎn)眼高手低。經(jīng)過幾周的奮戰(zhàn)我的畢業(yè)設(shè)計(jì)終于完成了。在物流配送業(yè) 務(wù)中，合理確定配送路徑是提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟(jì)效益的重要手段。 表 1 客戶間距離表 設(shè)置車輛數(shù)為 3，最大負(fù)載 10，車輛容積 30，最大行駛距離為 200，運(yùn)輸成本系數(shù) 4，平均時(shí)速為 40，不考慮裝卸及休息時(shí)間。遺傳操作重疊結(jié)構(gòu)的 SGA(simple geic algorithm),并在選擇操作前保留當(dāng)前最好解 :因此以概率 收斂到全局最優(yōu)解 。 本文中 ， 取 , 變異操作 mutation（） 采用反順序變異法改變布爾矩陣中的某些位 （ 1 變成 0,0 變成 1）， 產(chǎn)生新的布爾矩陣 。 交叉概率 對算法的收斂有較大的影響 ， 越大 ， 優(yōu)秀的個(gè)體出現(xiàn)的幾率也越大 ， 新舊個(gè)體替換快 ， 算法收斂也快 。 首先根據(jù)前面計(jì)算的 計(jì)算個(gè)體 i 在下一代中應(yīng)復(fù)制自 身的比例 ； 定義選擇概率 為個(gè)體適配值所占比例的反向排序 $即適配值最小的車輛分配方案其選擇概率最大 ； 依據(jù)選擇概率對種群中的個(gè)體進(jìn)行復(fù)制 ， 選擇概率大的個(gè)體被重復(fù)復(fù)制的機(jī)會(huì)大 ， 而選擇概率小的個(gè)體則趨向于減少或淘汰 ， 直到復(fù)制 N