【正文】 配送服務(wù)最后返回場(chǎng)站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。 多個(gè)起點(diǎn)和終點(diǎn)。 求解方法演進(jìn) 綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻殖民算法等。車輛運(yùn)輸問題的啟發(fā)式方法可以分為簡(jiǎn)單啟發(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 問題。 總結(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長(zhǎng)，是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)解。 遺傳算法是具有“生成+檢測(cè)”(generateandtest)的迭代過程的搜索算法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。 遺傳算法流程圖圖2 遺傳算法流程圖5 模型建立求解及實(shí)例應(yīng)用根據(jù)上述對(duì)問題的描述，可以采用混合整數(shù)規(guī)劃方法對(duì)車輛調(diào)度進(jìn)行建模設(shè)N為最小成本，則目標(biāo)函數(shù)為滿足約束條件1：式中：K為所有車輛的集合， ；G為所有客戶的集合， ， ，其中{0}代表配送中心； 為由車輛k服務(wù)的客戶的集合； 為車輛到達(dá)客戶i的時(shí)間；為懲罰函數(shù)，車輛在時(shí)間 到達(dá)客戶i時(shí)所對(duì)應(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í)間長(zhǎng)度為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è)體，并對(duì)應(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 139。為了使后代繼承更多的父代的基因信息，本文取變異概率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：對(duì)個(gè)體進(jìn)行CX 交叉重組；Step6：按照變異方法對(duì)個(gè)體進(jìn)行變異；Step7：重復(fù)步驟26；6算法的建立和求解車輛優(yōu)化調(diào)度問題由車輛分配和路線安排這兩個(gè)相互關(guān)聯(lián)的子問題組成，但關(guān)鍵是確定優(yōu)化的車輛分配方案（即求解變量）。對(duì)于車輛調(diào)度問題，可將求解變量看作染色體，因此，一條染色體就代表一種可能的車輛分配方案，然后可用布爾矩陣對(duì)該染色體的基因鏈進(jìn)行編碼。個(gè)體適配值為式中，所以，目標(biāo)函數(shù)生成初始染色體種群初始化遺傳世代；每一代的染色體群的種群數(shù)目；交叉概率，變異概率 等參數(shù)。過小將不能保證分配方案的多樣性，本算法中取種群大小，交叉概率,變異概。淘汰不符合約束條件的解，調(diào)整次序重新搜索，直到找到較佳的可行解為止。對(duì)染色體群實(shí)施交叉操作crossover（）可以產(chǎn)生新的體。變異操作mutation（）以概率對(duì)染色體群中的某些染色體的某些位進(jìn)行變異，產(chǎn)生新的個(gè)體染色體、作為交叉運(yùn)算的補(bǔ)充，變異操作可增加車輛分配方案的多樣性，克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象。如果，則轉(zhuǎn)啟發(fā)式算法求解，否則在染色體群中選擇最小的染色體，作為該問題的求解變量值；與該變量相對(duì)應(yīng)的變量就是優(yōu)化的路線安排。用上述的帶時(shí)間窗的遺傳算法，對(duì)一個(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ì)算方法以及選擇、交叉和變異算子，對(duì)解決類似的組合優(yōu)化問題具有一定的參考價(jià)值。畢業(yè)設(shè)計(jì)不僅是對(duì)前面所學(xué)知識(shí)的一種檢驗(yàn)，而且也是對(duì)自己能力的一種提高。在這次畢業(yè)設(shè)計(jì)中也使我們的同學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽聽不同的看法對(duì)我們更好的理解知識(shí)，所以在這里非常感謝幫助我的同學(xué)。在此要感謝我的指導(dǎo)老師雷德明對(duì)我悉心的指導(dǎo)，感謝老師給我的幫助。雖然這個(gè)設(shè)計(jì)做的也不太好，但是在設(shè)計(jì)過程中所學(xué)到的東西是這次畢業(yè)設(shè)計(jì)的最大收獲和財(cái)富，使我終身受益。在整個(gè)設(shè)計(jì)中我懂得了許多東西，也培養(yǎng)了我獨(dú)立工作的能力，樹立了對(duì)自己工作能力的信心，相信會(huì)對(duì)今后的學(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 genetic algorithm),并在選擇操作前保留當(dāng)前最好解:因此以概率收斂到全局最優(yōu)解。本文中，取,（）采用反順序變異法改變布爾矩陣中的某些位（1變成0,0變成1），產(chǎn)生新的布爾矩陣。交叉概率對(duì)算法的收斂有較大的影響，越大，優(yōu)秀的個(gè)體出現(xiàn)的幾率也越大，新舊個(gè)體替換快，算法收斂也快。首先根據(jù)前面計(jì)算的計(jì)算個(gè)體i在下一代中應(yīng)復(fù)制自身的比例；定義選擇概率為個(gè)體適配值所占比例的反向排序$即適配值最小的車輛分配方案其選擇概率最大；依據(jù)選擇概率對(duì)種群中的個(gè)體進(jìn)行復(fù)制，選擇概率大的個(gè)體被重復(fù)復(fù)制的機(jī)會(huì)大，而選擇概率小的個(gè)體則趨向