項目組成員：王定杰陸婷任濤王艷純李斌文啟發式算法在送貨線路設計問題中的應用答辯人：王定杰答辯提綱

第一部分第二部分第三部分課題研究的背景和意義啟發式算法的介紹送貨線路設置問題的分析及解決方案第四部分模型的評價與推廣

第一部分課題研究的背景和意義背景：現今社會網絡越來越普及，網購已成為一種常見的消費方式，隨之物流行業也漸漸興盛，每個送貨員需要以最快的速度及時將貨物送達，而且他們往往一人送多個地方，這時就會遇到如何設計方案使其耗時最少。意義：本課題主要運用模擬退火、遺傳算法等啟發式算法對物流系統中一個具體的送貨路線設計問題進行了研究。目的在于通過對送貨線路問題的研究,了解啟發式算法在物流配送路徑規劃方面的優良特征，為經后物流行業設計送貨線路、降低運營成本提供理論參考。

第二部分啟發式算法的介紹啟發式算法是80年代初興起的優化算法，這些算法包括禁忌搜索、模擬退火、遺傳算法、人工神經網絡。它們主要用于解決大量的實際應用問題。目前，這些算法在理論和實際應用方面得到了較大的發展。無論這些算法是怎樣產生的，它們有一個共同的目標－求NP-hard組合優化問題的全局最優解。本課題主要運用了其中的模擬退火和遺傳算法。

（一）模擬退火算法

模擬退火算法是材料的統計力學的研究成果。統計力學表面材料中粒子的不同結構對應于粒子的不同能量水平。在高溫條件下，粒子的能量較高，可以自由運動和重新排列。在低溫條件下，粒子能量較低。如果從高溫開始，非常緩慢地降溫（這個過程被稱為退火），粒子就可以在每個溫度下達到熱平衡。當系統完全被冷卻時，最終形成處于低能狀態的晶體。

一個組合優化問題：優化函數為，其中它表示優化問題的一個可行解，表示函數的定義域。表示的一個鄰域集合。首先給定一個初始溫度和該優化問題的一個初始解并由生成下一解，是否接受作為一個新解依賴于下面的概率：

（二）遺傳算法

遺傳算法是一種基于自然選擇原理和自然遺傳機制的搜索算法，它是模擬自然界中的生命進化機制，在人工系統中實現特定目標的優化，其實質是通過群體搜索技術，根據適者生存的原則逐代進化，最終得到最優解或準最優解。它必須做以下操作：初始群體的產生、求任一個體的適應度、根據適者生存的原則選擇優良個體、被選出的優良個體兩兩配對，通過隨機交叉其染色體的基因并隨機變異某些染色體的基因后生成下一代群體，按此方法使群體逐代進化，直到滿足進化終止條件。

遺傳算法的實現方法：（1）根據具體問題確定可行解域，確定一種編碼方式，能用數值串或字符串表示可行解域的每一解。（2）確定適應度函數，適應度函數用來度量解的好壞，且適應度函數應為非負函數。（3）確定進化參數的種群規模，交叉概率，變異概率和進化終止條件。

表一生物遺傳概念在遺傳算法中的對應關系

生物遺傳概念遺傳算法中的作用適者生存算法停止時，最優目標值以最大概率被保留個體解染色體解的編碼基因解中每一分量的特征適應性適應度函數值種群根據適應度函數值選取的一組解交配通過交配原則產生一組新解的過程變異編碼的某一分量發生變化的過程

第三部分送貨線路設置問題的分析及解決方案送貨線路設計問題簡述：

現今社會網絡越來越普及，網購已成為一種常見的消費方式，隨之物流行業也漸漸興盛，每個送貨員需要以最快的速度及時將貨物送達，而且他們往往一人送多個地方，請設計方案使其耗時最少?，F有一快遞公司，庫房在圖1中O點，一送貨員需將貨物送至城市內多處，請設計送貨方案，使所用時間最少。該地形圖的示意圖見圖1，各點連通信息已知，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關信息已知，50個位置點的坐標已知。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時。假定每件貨物交接花費3分鐘，為簡化起見，同一地點有多件貨物也簡單按照每件3分鐘交接計算。

現在送貨員要將100件貨物送到50個地點。請完成以下問題。1、若將1~30號貨物送到指定地點并返回。設計最快完成路線與方式。給出結果。要求標出送貨線路。2、假定該送貨員從早上8點上班開始送貨，要將1~30號貨物的送達時間不能超過指定時間，請設計最快完成路線與方式。要求標出送貨線路。3、若不需要考慮所有貨物送達時間限制(包括前30件貨物)，現在要將100件貨物全部送到指定地點并返回。設計最快完成路線與方式。要求標出送貨線路，給出送完所有快件的時間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時間。

圖1快遞公司送貨地點示意圖（單位：米）

問題一的分析及解決對于問題一，首先建立了50個網點的鄰接矩陣，然后運用Floyd算法求出了任意兩點之間的最短距離，進而建立了從O點出發將前30件貨物送達21個指定點后再返回O點的最短距離函數，最后運用遺傳算法和模擬退火算法計算得到送貨路線的最短距離為54708米。

表一送貨網點兩兩之間的鄰接矩陣送貨網點12345……10Inf1916.28InfInf……2Inf02292.641252.94Inf……31916.28Inf03536.41Inf……4Inf2292.643536.410Inf……5Inf1252.94InfInf0……………………………………0

表二圖中任意兩點之間的最短距離送貨網點12345……105295.4925093.6757493.0083620.852……25295.49208455.64411063.328916.344……35093.6758455.64402607.6812195.723……47493.00811063.322607.68103872.156……53620.8528916.3442195.7233872.1560……………………………………0

首先對22個點進行編號，將起始點O編號為1，其他21個點依次編號為，最后對O進行第二次編號，為了便于程序實現，我們把23作為O點第二次編號的序數。于是，建立下列目標函數來求送貨最短路徑和最短距離：其中，，為任意兩點之間的距離。模型