【正文】 雖然這個(gè)設(shè)計(jì)做的也不太好，但是在設(shè)計(jì)過(guò)程中所學(xué)到的東西是這次畢業(yè)設(shè)計(jì)的最大收獲和財(cái)富，使我終身受益。在整個(gè)設(shè)計(jì)中我懂得了許多東西，也培養(yǎng)了我獨(dú)立工作的能力，樹(shù)立了對(duì)自己工作能力的信心，相信會(huì)對(duì)今后的學(xué)習(xí)工作生活有非常重要的影響。 在此要感謝我的指導(dǎo)老師雷德明對(duì)我悉心的指導(dǎo)，感謝老師給我的幫助。最后終于做完了有種如釋重負(fù)的感覺(jué)。 在這次畢業(yè)設(shè)計(jì)中也使我們的同學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽(tīng)聽(tīng)不同的看法對(duì)我們更好的理解知識(shí)，所以在這里 非常感謝幫助我的同學(xué)。自己要學(xué)習(xí)的東西還太多，以前老是覺(jué)得自己什么東西都會(huì)，什么東西都懂，有點(diǎn)眼高手低。畢業(yè)設(shè)計(jì)不僅是對(duì)前面所學(xué)知識(shí)的一種檢驗(yàn)，而且也是對(duì)自己能力的一種提高。經(jīng)過(guò)幾周的奮戰(zhàn)我的畢業(yè)設(shè)計(jì)終于完成了。所構(gòu)造的物流配送路徑優(yōu)化的遺傳算法，包括設(shè)計(jì)個(gè)體編碼方法、個(gè)體適應(yīng)度值的計(jì)算方法以及選擇、交叉和變異算子，對(duì)解決類似的組合優(yōu)化問(wèn)題具有一定的參考價(jià)值。在物流配送業(yè) 務(wù)中，合理確定配送路徑是提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟(jì)效益的重要手段?？山?jīng)驗(yàn)證，該解正是問(wèn)題的最優(yōu)解。 表 1 客戶間距離表 設(shè)置車輛數(shù)為 3，最大負(fù)載 10，車輛容積 30，最大行駛距離為 200，運(yùn)輸成本系數(shù) 4，平均時(shí)速為 40，不考慮裝卸及休息時(shí)間。用上述的帶時(shí)間窗的遺傳算法，對(duì)一個(gè)有 8 個(gè)客戶和 1 個(gè)配送中心，兩輛車（容量均為 8 噸）的配送系統(tǒng)的車輛路徑問(wèn)題進(jìn)行求解。遺傳操作重疊結(jié)構(gòu)的 SGA(simple geic algorithm),并在選擇操作前保留當(dāng)前最好解 :因此以概率 收斂到全局最優(yōu)解 。 如果 ，則轉(zhuǎn) 啟發(fā)式算法求解 ， 否則在染色體群中選擇 最小的染色體 ， 作為該問(wèn)題的求解變量 值 ； 與該變量相對(duì)應(yīng)的變量 就是優(yōu)化的路線安排 。 本文中 ， 取 , 變異操作 mutation（） 采用反順序變異法改變布爾矩陣中的某些位 （ 1 變成 0,0 變成 1）， 產(chǎn)生新的布爾矩陣 。 變異操作 變異操作 mutation（） 以概率 對(duì)染色體群中的某些染色體的某些位進(jìn)行變異 ， 產(chǎn)生新的個(gè)體染色體 、 作為交叉運(yùn)算的補(bǔ)充 ， 變異操作可增加車輛分配方案的多樣性 ， 克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象 。 交叉概率 對(duì)算法的收斂有較大的影響 ， 越大 ， 優(yōu)秀的個(gè)體出現(xiàn)的幾率也越大 ， 新舊個(gè)體替換快 ， 算法收斂也快 。 對(duì)染色體群實(shí)施交叉操作 crossover（） 可以產(chǎn)生新的 體 。 首先根據(jù)前面計(jì)算的 計(jì)算個(gè)體 i 在下一代中應(yīng)復(fù)制自 身的比例 ； 定義選擇概率 為個(gè)體適配值所占比例的反向排序 $即適配值最小的車輛分配方案其選擇概率最大 ； 依據(jù)選擇概率對(duì)種群中的個(gè)體進(jìn)行復(fù)制 ， 選擇概率大的個(gè)體被重復(fù)復(fù)制的機(jī)會(huì)大 ， 而選擇概率小的個(gè)體則趨向于減少或淘汰 ， 直到復(fù)制 N 22 條染色體 。 淘汰不符合約束條件的解 ， 調(diào)整次序重新搜索 ， 直到找到較佳的可行解為止 。 該子問(wèn)題可表示為 滿足約束條件 ： 本文采用文獻(xiàn) [3]中的啟發(fā)式方法進(jìn)行求解 。 過(guò)小將不能保證分配方案的多樣性 ， 本算法中取種群大小 ， 交叉概率 ,變異概。 N 的取值不宜過(guò)大或過(guò)小 。 個(gè)體適配值為 式中 ， 所以 ， 目標(biāo)函數(shù) 生成初始染色體種群 初始化遺傳世代 ； 每一代的染色體群的 種群數(shù)目 ； 交叉概率 ， 變異概率 等參數(shù) 。 例如 ， 圖 1 的布爾矩陣為 即車 輛 1 負(fù)責(zé)客戶 1 和 2， 車輛 2 負(fù)責(zé)客戶 4 和 5. 定義適配值計(jì)算函數(shù) 適應(yīng)度函數(shù)是遺傳算法中評(píng)價(jià)解集好壞的依據(jù) ,適配值高的個(gè)體優(yōu)先培養(yǎng) 。 對(duì)于車輛調(diào)度問(wèn)題 ， 可將求解變量 看作染色體 ， 因此 ， 一條染色體就代表一種可能的車輛分配方案 ， 然后可用布爾矩陣對(duì)該染色體的基因鏈進(jìn)行編碼 。 可以采用遺傳算法的思想作為總體框架對(duì)該問(wèn)題進(jìn)行求解 ， 用遺傳算法求解變量 ， 而變量 則用啟發(fā)式算法求解 。 步驟 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è)體濃度的群體多樣性保持策略來(lái)選擇個(gè)體； Step5：對(duì)個(gè)體進(jìn)行 CX 交叉重組； 19 Step6：按照變異方法對(duì)個(gè)體進(jìn)行變異； Step7：重復(fù)步驟 26； 20 6 算法的建立和求解 車輛優(yōu)化調(diào)度問(wèn)題由車輛分配和路線安排這兩個(gè)相互關(guān)聯(lián)的子問(wèn)題組成 ， 但關(guān)鍵是確定優(yōu)化的車輛分配方案 （ 即求解變量 ）。即事先設(shè)置一個(gè)最大代數(shù)，如當(dāng)前代數(shù)大于最大代數(shù)時(shí)，算法停止。為了使后代繼承更多的父代的基因信息，本文取變異概率 Pm 為 左右。A， 39。A=2 9 5 4|3 5 6 2 9 8 4 7 1 39。實(shí)施交叉操作。在得到新的兩個(gè)染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法加入了淘汰機(jī)制，即比較兩個(gè)新染色體，保留較好的一個(gè)進(jìn)入下一代，同時(shí)將較差的一個(gè)舍棄。簡(jiǎn) 單的說(shuō)就是人為選取較好的一對(duì)染色體作為新染色體的父母，按染色體按長(zhǎng)度分為前后兩段，取其中一個(gè)染色體的前半部分放在另一個(gè)染色體的前邊，再順序遍歷新染色體的基因并剔除重復(fù)基因，從而得到新的染色體 child1。生成一個(gè) [0,1]范圍內(nèi)的隨機(jī)數(shù)，看它落在哪個(gè)區(qū)域，則選擇該個(gè)體。由于適應(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) 遺傳算子 1. 遺傳選擇 選擇是用來(lái)確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。設(shè)群體規(guī)模為 M，則通過(guò)隨機(jī)產(chǎn)生 M 個(gè)這樣的個(gè)體，即形成初始群體。如個(gè)體 0l26354 表示的配送路徑方案為：路徑 1： 0126，路徑 2： 354共有 2 條配送路徑； 種群的初始化 群體初始化時(shí)，采用兩種機(jī)制，一種是隨機(jī)生成個(gè)體，一種是按 前相插入啟發(fā)式算法。這樣， l、 … 、 L＋ m－ l 這 L＋ m－ l 個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對(duì)應(yīng)一種配送路徑方案。由于在配送中心有 m 輛汽車，則最多存在 m 條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。如出現(xiàn)某客戶需求量大于車輛負(fù)載（容積）的情況時(shí)，需要先派車為其運(yùn)輸，直至該客戶剩余貨物需求量小于車輛最大負(fù)載（容積）即可參加優(yōu)化調(diào)度。硬時(shí)間窗 (Hard Time Windows)：指配送車輛必須在特定時(shí)間區(qū)段，將貨物送達(dá)顧客手中，不論是遲到或早到都完全不予接受；軟時(shí)間窗 (Soft Time Windows)：允許服務(wù)的開(kāi)始時(shí)間有所偏離時(shí)間窗，則必須按照違反時(shí)間的長(zhǎng)短施以一定的罰金或其他懲罰法則；混合型時(shí)間窗（ Mixed Time Windows）：是指系統(tǒng)中有些客戶 只接受硬時(shí)間窗服務(wù)，有些客戶接受軟時(shí)間窗服務(wù)，或者同一客戶，往往軟、硬兩種時(shí)間窗服務(wù)混合使用。客戶的服務(wù)必須在相應(yīng)的時(shí)間窗內(nèi)開(kāi)始，車輛必須在客戶點(diǎn)停留的時(shí)間長(zhǎng)度為 si。 圖 3 懲罰函數(shù) 帶時(shí)間窗的物流配送問(wèn)題優(yōu)化問(wèn)題 帶時(shí)間窗 VRP（ VRP with Time Windows， VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP， CVRP)的擴(kuò)展。 根據(jù)實(shí)際情況 ， 本文采用軟限制時(shí)間窗 ， 其懲罰函數(shù) 如圖 2所示 。 若車輛 k 為客戶 i 服務(wù) ， 則 1， 否則為 0， 即 ： 此變量表示車輛分配方案 ， 可用布爾矩陣表示 ； 若車輛 k 經(jīng)由客戶 i 到客戶 j， 則 為 1， 否則為 0， 即 ：， 表示車輛路線安排 。 遺傳算法流程圖 13 圖 2 遺傳算