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