1、項(xiàng)目組成員：王定杰 陸婷 任濤 王艷純 李斌文啟發(fā)式算法在送貨線路設(shè)計(jì)問(wèn)題中的應(yīng)用答辯人：王定杰答辯提綱 第一部分第二部分第三部分課題研究的背景和意義啟發(fā)式算法的介紹送貨線路設(shè)置問(wèn)題的分析及解決方案第四部分模型的評(píng)價(jià)與推廣 第一部分 課題研究的背景和意義背景：現(xiàn)今社會(huì)網(wǎng)絡(luò)越來(lái)越普及，網(wǎng)購(gòu)已成為一種常見(jiàn)的消費(fèi)方式， 隨之物流行業(yè)也漸漸興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人送多個(gè)地方，這時(shí)就會(huì)遇到如何設(shè)計(jì)方案使其耗時(shí)最少。意義：本課題主要運(yùn)用模擬退火、遺傳算法等啟發(fā)式算法對(duì)物流系統(tǒng)中一個(gè)具體的送貨路線設(shè)計(jì)問(wèn)題進(jìn)行了研究。目的在于通過(guò)對(duì)送貨線路問(wèn)題的研究,了解啟發(fā)式算法在物

2、流配送路徑規(guī)劃方面的優(yōu)良特征，為經(jīng)后物流行業(yè)設(shè)計(jì)送貨線路、降低運(yùn)營(yíng)成本提供理論參考。 第二部分 啟發(fā)式算法的介紹 啟發(fā)式算法是80年代初興起的優(yōu)化算法，這些算法包括禁忌搜索、模擬退火、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)。它們主要用于解決大量的實(shí)際應(yīng)用問(wèn)題。目前，這些算法在理論和實(shí)際應(yīng)用方面得到了較大的發(fā)展。無(wú)論這些算法是怎樣產(chǎn)生的，它們有一個(gè)共同的目標(biāo)求NP-hard組合優(yōu)化問(wèn)題的全局最優(yōu)解。本課題主要運(yùn)用了其中的模擬退火和遺傳算法。 （一）模擬退火算法 模擬退火算法是材料的統(tǒng)計(jì)力學(xué)的研究成果。統(tǒng)計(jì)力學(xué)表面材料中粒子的不同結(jié)構(gòu)對(duì)應(yīng)于粒子的不同能量水平。在高溫條件下，粒子的能量較高，可以自由運(yùn)動(dòng)和重新排列。

3、在低溫條件下，粒子能量較低。如果從高溫開(kāi)始，非常緩慢地降溫（這個(gè)過(guò)程被稱(chēng)為退火），粒子就可以在每個(gè)溫度下達(dá)到熱平衡。當(dāng)系統(tǒng)完全被冷卻時(shí)，最終形成處于低能狀態(tài)的晶體。 （二）遺傳算法 遺傳算法是一種基于自然選擇原理和自然遺傳機(jī)制的搜索算法，它是模擬自然界中的生命進(jìn)化機(jī)制，在人工系統(tǒng)中實(shí)現(xiàn)特定目標(biāo)的優(yōu)化，其實(shí)質(zhì)是通過(guò)群體搜索技術(shù)，根據(jù)適者生存的原則逐代進(jìn)化，最終得到最優(yōu)解或準(zhǔn)最優(yōu)解。它必須做以下操作：初始群體的產(chǎn)生、求任一個(gè)體的適應(yīng)度、根據(jù)適者生存的原則選擇優(yōu)良個(gè)體、被選出的優(yōu)良個(gè)體兩兩配對(duì)，通過(guò)隨機(jī)交叉其染色體的基因并隨機(jī)變異某些染色體的基因后生成下一代群體，按此方法使群體逐代進(jìn)化，直到滿足進(jìn)化

4、終止條件。 遺傳算法的實(shí)現(xiàn)方法： （1）根據(jù)具體問(wèn)題確定可行解域，確定一種編碼方式，能 用數(shù)值串或字符串表示可行解域的每一解。 （2）確定適應(yīng)度函數(shù)，適應(yīng)度函數(shù)用來(lái)度量解的好壞，且 適應(yīng)度函數(shù)應(yīng)為非負(fù)函數(shù)。 （3）確定進(jìn)化參數(shù)的種群規(guī)模 ，交叉概率 ，變異概 率 和進(jìn)化終止條件。 第三部分送貨線路設(shè)置問(wèn)題的分析及解決方案送貨線路設(shè)計(jì)問(wèn)題簡(jiǎn)述： 現(xiàn)今社會(huì)網(wǎng)絡(luò)越來(lái)越普及，網(wǎng)購(gòu)已成為一種常見(jiàn)的消費(fèi)方式，隨之物流行業(yè)也漸漸興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人送多個(gè)地方，請(qǐng)?jiān)O(shè)計(jì)方案使其耗時(shí)最少。 現(xiàn)有一快遞公司，庫(kù)房在圖1中O點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請(qǐng)?jiān)O(shè)計(jì)送貨方案

5、，使所用時(shí)間最少。該地形圖的示意圖見(jiàn)圖1，各點(diǎn)連通信息已知，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關(guān)信息已知，50個(gè)位置點(diǎn)的坐標(biāo)已知。 假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時(shí)。假定每件貨物交接花費(fèi)3分鐘，為簡(jiǎn)化起見(jiàn)，同一地點(diǎn)有多件貨物也簡(jiǎn)單按照每件3分鐘交接計(jì)算。 現(xiàn)在送貨員要將100件貨物送到50個(gè)地點(diǎn)。請(qǐng)完成以下問(wèn)題。1、若將130號(hào)貨物送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。給出結(jié)果。要求標(biāo)出送貨線路。2、假定該送貨員從早上8點(diǎn)上班開(kāi)始送貨，要將130號(hào)貨物的送達(dá)時(shí)間不能超過(guò)指定時(shí)間，請(qǐng)?jiān)O(shè)計(jì)最快完成路線與方

6、式。要求標(biāo)出送貨線路。3、若不需要考慮所有貨物送達(dá)時(shí)間限制(包括前30件貨物)，現(xiàn)在要將100件貨物全部送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快件的時(shí)間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時(shí)間。 圖1 快遞公司送貨地點(diǎn)示意圖（單位：米） 表一 送貨網(wǎng)點(diǎn)兩兩之間的鄰接矩陣送貨網(wǎng)點(diǎn)1234510Inf1916.28InfInf2Inf02292.641252.94Inf31916.28Inf03536.41Inf4Inf2292.643536.410Inf5Inf1252.94InfInf00 表二 圖中任意兩點(diǎn)之間的最短距離送貨網(wǎng)點(diǎn)1

7、2345105295.4925093.6757493.0083620.85225295.49208455.64411063.328916.34435093.6758455.64402607.6812195.72347493.00811063.322607.68103872.15653620.8528916.3442195.7233872.15600 模擬退火算法的求解過(guò)程（1）確定解空間（2）建立目標(biāo)函數(shù) f（3）新解的產(chǎn)生（4）計(jì)算代價(jià)函數(shù)差（5）判斷是否接受,降溫，結(jié)束。 遺傳算法的求解過(guò)程（1）確定編碼策略和初始化種群（2）建立目標(biāo)函數(shù) f（3）交叉操作和變異操作（4）選擇 問(wèn)題二的分析

8、與解決 問(wèn)題二在問(wèn)題一的基礎(chǔ)上增加了時(shí)間約束，所以我們只要對(duì)模型一加以改進(jìn)，補(bǔ)充必要的約束條件便可達(dá)到解決問(wèn)題二的目的 。按照排隊(duì)論中先到先服務(wù)的原則，首先完成送達(dá)時(shí)間早的貨物的送貨任務(wù)，根據(jù)不同送達(dá)時(shí)間將30件貨物分為四類(lèi)，并將每一類(lèi)貨物的送達(dá)地點(diǎn)放到一個(gè)集合，這樣便得到四個(gè)時(shí)間點(diǎn)下的不同送達(dá)地點(diǎn)組成的集合，然后分別完成每一類(lèi)貨物的送貨任務(wù)，并計(jì)算出完成每一類(lèi)送貨任務(wù)的最佳送貨路線和最短時(shí)間。 表四 前30件貨物的分類(lèi)情況貨物類(lèi)別第一類(lèi)第二類(lèi)第三類(lèi)第四類(lèi)送達(dá)時(shí)間9：009:3010：1512：00送達(dá)地點(diǎn)13、18、 2431、34、40、4538、42、43、4926、21、14、17、2

9、3、32、39、36、27、16 （1）第一類(lèi)貨物的送貨路徑 ： O18131924 （2）第二類(lèi)貨物的送貨路徑： 2431344045 （3）第三類(lèi)貨物的送貨路徑： 454249424338 （4）第四類(lèi)貨物的送貨路徑： 38362739273126211714162332 表五 各區(qū)域劃分統(tǒng)計(jì)表區(qū)域包含的點(diǎn)總重量總體積A17 23 16 14 9 10 7 6 1 8 3 4 2 5 15 12 11 13 1849080959B21 32 35 38 43 42 49 50 47 45 36 27 3948940965C26 34 40 37 41 44 48 46 33 28 30 20 22 29 25 19 24 3149980875 51點(diǎn)最小生成樹(shù)圖 第四部分 模型的評(píng)價(jià)與推廣 本文在計(jì)算時(shí)采用的方法主要是遺傳算法和模擬退火算法，這兩種算法都是全局尋優(yōu)的良好算法，但由于要綜合考慮算法的空間復(fù)雜度和時(shí)間復(fù)雜度，對(duì)于大規(guī)模問(wèn)題，在盡量降低算法所需要的時(shí)間后很難求得最優(yōu)解，通常得到的解均為近似最優(yōu)解。 在實(shí)際生活中，經(jīng)常會(huì)遇到本文提出的問(wèn)題，如：背包問(wèn)題、貨郎擔(dān)問(wèn)題、郵遞員問(wèn)題、哈密爾頓回路問(wèn)題等等，這些問(wèn)題都是