【正文】 VRPTW。 VRP仿真實驗室在本文的研究中發(fā)揮了重要的作用 ,是研究車輛路徑問題的有力工具。 7 3 問題描述 車輛路徑問題定義 車輛路線問題（ VRP）最早是由 Dantzig 和 Ramser 于 1959 年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求， 配送中心 向客戶提供貨物，由一個車隊負責分送貨物， 組織 適當?shù)男熊嚶肪€，目標是使得客戶的 需求 得到滿足，并能在一定的約束下，達到諸如路程最短、 成本 最小、耗費時間最少等目的。 已證明 TSP 問題 是 NP 難題 ，因此， VRP 也屬于 NP 難題。車輛路線問題可以描述如 下（如圖 1）： 圖 1 路徑問題描述 設(shè)有一場站（ depot），共有 M 輛貨車，車輛容量為 Q，有 N 位 顧客 （ customer），每位顧客有其需求量 D。車輛路線的實際問題包括 配送中心配送 、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。 相同的單一起點和終點。 車輛路線問題研究現(xiàn)狀 經(jīng)過幾十年的研究發(fā)展，車輛路線問題研究取得了大量成果。 車輛路線問題型態(tài) 在基本車輛路線問題（ VRP）的基礎(chǔ)上，車輛路線問題在學術(shù)研究和實際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括 時窗限制車輛路線問題 （ vehicle routing problems with time windows， VRPTW）、 追求最佳服務(wù)時間的車輛路線問題 （ VRPDT）、 多車種車輛路線問題 （ fleet size and mix vehicle routing problems， FSVRP）、 車輛多次使用的車輛路線問題 （ vehicle routingproblems with multiple use of vehicle， VRPM）、 考慮收集的車輛路線問題 （ vehicle routingproblems with backhauls， VRPB）、 隨機需求車輛路線問題 （ vehicle routing problem with stochastic demand， VRPSD）等。 1995 年， Fisher曾將求解車輛路線問題的算法分成三個階段。 啟發(fā)式算法 由于 VRP 是 NPhard 問題，難以用精確算發(fā)求解，啟發(fā)式算法 9 是求解車輛 運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發(fā)式方法。 簡單啟發(fā)式方法包括節(jié)省法或 插入法 、路線內(nèi) /間節(jié)點交換法、貪婪法和局部搜索法等方法。交換法則是依賴其他方法產(chǎn)生一個起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。簡單啟發(fā)式方法簡單易懂、求解速度快，但只適合求解小型、簡單的 VRP 問題。前者是 先將所有需求點大略分為幾個組，然后再對各個組分別進行路線排序；后者則是先將所有的需求點建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨路線。 禁忌搜索法 （ TS）基本上是屬于一種人工智能型（ AI）的局部搜尋方法， Willard 首先將此算法用來求解 VRP ，隨后亦有許多位學者也發(fā)表了求解 VRP 的 TS 算法。模擬退火方法具有收斂速度快，全局搜索的特點， Osman 對 VRP 的模擬退火算法進行了研究，他提出的模擬退火方法主要適合于解決路線分組?，F(xiàn)在多數(shù)學者采用混合策略，分別采用兩種人工智能方法進行路線分組和路線優(yōu)化。 Bent 和 Van Hentenryck 則首先用 模擬退火算法 將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（ largneighborhood search）將運輸費用降到最低。 11 4 遺傳算法介紹 遺傳算法簡稱 GA(Geic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。遺傳算法的概念最早是由 Bagley 在 1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開創(chuàng)性工作是由 Michigan 大學的 . Holland 所實行。 遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強，適用于并行處理和應(yīng)用范圍廣等優(yōu)點。具有如下特點： (1) 遺傳算法運算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個種群，而不是單個解； (3) 遺傳算法只使用報酬信息（適值函數(shù)），不使用導數(shù)或其他輔助知識； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。作為一種隨機優(yōu)化技術(shù)在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個顯著優(yōu) 勢是不需要目標函數(shù)明確的數(shù)學方程和導數(shù)表達式，同時又是一種全局尋優(yōu)算法，不會象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。遺傳算法中包含了如下 5 個基本要素： 1)參數(shù)編碼； 2)初始群體的設(shè)定； 3)適應(yīng)度函數(shù)的設(shè)計； 4)遺傳操作設(shè)計； 12 5） 控制參數(shù)設(shè)定 (主要是指群體大小和使用遺傳操作的概率等 )。 遺傳算法的基本思想 遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于 適者生存思想的一種較通用的問題求解方法。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強，適用于并行處理和應(yīng)用范圍廣等優(yōu)點。具有如下特點： (1) 遺傳算法運算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個種群，而不是單個解； (3) 遺傳算法只使用報酬 信息（適值函數(shù)），不使用導數(shù)或其他輔助知識； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 另外 ， 變量 和 的值為 0 或 1。 約束條件 2： 保證每個客戶均被服務(wù) ， 而且每輛車都從配送中心出發(fā) ； 約束條件 3： 表示每輛車負責的客戶點的貨物需求量總和不超過該車輛的最大裝載量 ； 15 約束條件 5： 表示對任一由 k服務(wù)的客戶點 j必定有另一 (而且只有一個 )由 k服務(wù)的客戶點 (包括配送中心 )I,車輛 k從客戶點 i到達客戶點 j,而對由 k服務(wù)的客戶點 i同樣存在由 k服務(wù)的另一客戶點 ,車輛 k是從該客戶點到達客戶點 i的 ,依次類推 ； 約束條件 6： 保證每輛車的行車路線的總耗時不超過一個事先定下的數(shù)值 ； 約束條件 7： 對某個客戶點 ， 車輛到達時間限制 在某一時間段內(nèi) 。 其中 ，為客戶所要求的送貨時區(qū) ， 為時間窗 ， 超過該范圍客戶將拒絕收貨 ， 因此設(shè)定一個極大的懲罰成本 以避免此情況的發(fā)生 。在該類問題中，有車輛裝載能力約束，且每個客戶 i 都有一個與之相聯(lián)系的時間區(qū)間 [ai ,bi]， 稱為時間窗。按客戶對物流中心違反時間窗約束規(guī)定時的接受程度，可分為硬時間窗、軟時間窗和混合型時間窗。 16 如問題為硬時間窗問題，則必須滿足到客戶 i 的時間要比承諾到達時間早，即到達 i 的時間 ≤到達 i 的最晚時間限制； 如有緊急貨物（高優(yōu)先級客戶）時，則自動將優(yōu)先級高的貨物按優(yōu)先級順序排入隊列前端，然后將其它普通貨物再進行優(yōu)化；即如有 N 個客戶，其中有一個為緊急運單，則自動將其放在隊首，其他 N1 個客戶進行優(yōu)化，即將問題降為 N1 階的路徑優(yōu)化問題； 任一客戶只由一臺運輸車輛提供服務(wù)，即算法解決的是任一客戶的貨物需求均小于車輛最大負載（容積）的情況。 帶時間窗的物流配送路徑問題的遺傳算法 染色體結(jié)構(gòu)編碼 根據(jù)物流配送路徑優(yōu)化問題的特點，本文采用了簡單直觀的自然數(shù)編碼方法，用 0 表示配送中心，用 … 、 L 表示各需求點。為了在編碼中反映車輛配送的路徑，采用了增加 m－ 1 個虛擬 配送中心的方法，分別用 L＋ L＋ … 、 L＋ K－ l 表示。例如，對于一個有 6 個需求點，用 2 輛汽車完成配送任務(wù)的問題， 則可用 0、 … 、 6 (0 表示配送中心 )這 7 個自然數(shù)的隨機排列表示物流配送路徑方案。本文采用隨機產(chǎn)生