【正文】 實際物流配送系統(tǒng)中的車輛路徑問題。子路徑交換算法可以有效提高遺傳算法的求解精度。 (5)對于帶時間窗約束的車輛路徑問題(VRPTW,首先改進了雙層染色體編碼方案,以便在編程實現(xiàn)時更方便地進行子路徑的處理。最后提出了一種求解VRPTW問題的新型混合遺傳算法HGAVRPTW。VRP仿真實驗室在本文的研究中發(fā)揮了重要的作用,是研究車輛路徑問題的有力工具。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ā)展，車輛路線問題研究取得了大量成果。在基本車輛路線問題（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，F(xiàn)SVRP）、車輛多次使用的車輛路線問題（vehicle routingproblems with multiple use of vehicle，VRPM）、考慮收集的車輛路線問題（vehicle routingproblems with backhauls，VRPB）、隨機需求車輛路線問題（vehicle routing problem with stochastic demand，VRPSD）等。1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個階段。 啟發(fā)式算法 由于VRP是NPhard問題，難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發(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）將運輸費用降到最低。 4 遺傳算法介紹遺傳算法簡稱 GA(Genetic 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è)計；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：表示每輛車負責的客戶點的貨物需求量總和不超過該車輛的最大裝載量；約束條件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ī)定時的接受程度，可分為硬時間窗、軟時間窗和混合型時間窗。如問題為硬時間窗問題，則必須滿足到客戶i 的時間要比承諾到達時間早，即到達i 的時間≤到達i 的最晚時間限制；如有緊急貨物（高優(yōu)先級客戶）時，則自動將優(yōu)先級高的貨物按優(yōu)先級順序排入隊列前端，然后將其它普通貨物再進行優(yōu)化；即如有N 個客戶，其中有一個為緊急運單，則自動將其放在隊首，其他N1 個客戶進行優(yōu)化，即將問題降為N1 階的路徑優(yōu)化問題；任一客戶只由一臺運輸車輛提供服務(wù)，即算法解決的是任一客戶的貨物需求均小于車輛最大負載（容積）的情況。根據(jù)物流配送路徑優(yōu)化問題的特點，本文采用了簡單直觀的自然數(shù)編碼方法，用0表示配送中心，用…、L 表示各需求點。為了在編碼中反映車輛配送的路徑，采用了增加m－1 個虛擬配送中心的方法，分別用L＋L＋…、L＋K－l 表示。例如，對于一個有6 個需求點，用2 輛汽車完成配送任務(wù)