【正文】 在編 碼的過程中不考慮約束，而在遺傳算法的計算過程中檢測得到的染色體相應(yīng)的解是否可行，若可行，則放入下一代群體中，否則將其舍棄。若車輛在 ib 之后到達(dá)點 i，則服務(wù)被延遲，須支付一定的罰金。如果車輛到達(dá) i的時間早于 ia ，則車輛需在 i處等待，如果車輛到達(dá)時間晚于 ib ，則任務(wù) i要延遲執(zhí)行。由于有時間窗的 VSP是典型的 NP難題，會隨著節(jié)點的增加出現(xiàn)組合爆炸的現(xiàn)象 ［５］ 。根據(jù)小組成員的分工，本文就適應(yīng)度函數(shù)的選定和變異算子進(jìn)行主要闡述。但在某些情況下，當(dāng)種群達(dá)到一定規(guī)模時，再增大種群規(guī)模，對搜索結(jié)果的改善并無多大幫助，甚至有可能變差。將 2— 交換和 3— 交換作為遺傳算法的變異算子，即在每代群體中以概率 P，隨機選取染色體上的兩點或 3點，進(jìn)行 2— 交換或 3— 交換。 表 32 變異算子類型 名稱 特點 研究者 適用編碼 常規(guī)位變異 標(biāo)準(zhǔn)遺傳算法成員 DeJong 二進(jìn)制 有效基因變異 避免有效基因缺失 Yun 二進(jìn)制 自適應(yīng)有效基因變異 最低有效基因個數(shù)自適應(yīng)變化 Yun 二進(jìn)制 概率自調(diào)整變異 由兩個串的相似性確定變異概率 Whitley 二進(jìn)制 均勻變異 由一個實數(shù)元素以相同的概率在域 內(nèi)變動 Michalewicz 十進(jìn)制 非均勻變異 使整個矢量在解空間輕微變動 Michalewicz 十進(jìn)制 三次高斯近似變異 Bosworth, Foo,Zeigler 十進(jìn)制 零變異 同上 十進(jìn)制 目前較常用的高級遺傳算子，來源于群體遺傳學(xué)。 19 圖 32 PMX運算的說明 隨機選擇子巡回 1 2 3 4 9 8 7 6 5 5 4 6 9 3 8 7 1 2 雙親 1： 雙親 2： 交換雙親中的子串 1 2 6 9 9 8 7 1 2 5 4 3 4 3 8 7 6 5 原始后代 1： 原始后代 2： 用映射關(guān)系將后代合法化 后代 1： 后代 2： 3 5 6 9 4 8 7 1 2 2 9 3 4 6 8 7 6 5 確定映射關(guān)系 6 9 1 2 3 4 6 5 1 6 3 2 5 9 4 20 圖 33 OX 運算的說明 基于位置的交叉 Step l：從第一雙親上隨機地選擇一組位置； Step 2：將這些位置復(fù)制到一個空子串的相應(yīng)位置，產(chǎn)生一個原始后代； Step 3：刪去第二雙親上該組中已有的城市，剩下的城市構(gòu)成了原始后代需要的順序； Step 4：按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。 18 交叉算子 交叉算子的作用是組合出新的個體，在串空間進(jìn)行有效搜索，同時需降低對有效模式的破壞概率。 表 31 遺傳算法中適應(yīng)度常用的定標(biāo)方法 定標(biāo)方法 方法描述 17 線性定標(biāo) 將群體中各個體的適應(yīng)度以線性關(guān)系縮放，這種方法控制每一代中表現(xiàn)最佳的個體復(fù)制數(shù)目，但當(dāng)群體中個體適應(yīng)度差異在定標(biāo)前就己經(jīng)有顯著差異時，經(jīng)由此法轉(zhuǎn)換的新適應(yīng)度可能會有負(fù)值產(chǎn)生， 違背了概率不得為負(fù)數(shù)的限制，必須輔以其他方法處理。如果群體中出現(xiàn)了超級個體，即該個體的適應(yīng)度大大超過了群體的平均適應(yīng)度，則按照適應(yīng)度比例選擇時，該個體很快在群體中占有絕對優(yōu)勢，從而導(dǎo)致算法較早的收斂到一個局部最優(yōu)點。 16 目標(biāo)函數(shù)映射成適應(yīng)度函數(shù) 遺傳算法適應(yīng)度函數(shù)值作為染色體的性能指標(biāo)，以及利用繁殖概率的大小來評估各染色體的優(yōu)劣程度，多半以最大化為目標(biāo) (亦即越大越好 )；但是許多優(yōu)化問題 (比如物流配送 VSP問題 )是求取費用函數(shù)的最小值，必須將目標(biāo)函數(shù)轉(zhuǎn)化為求最大值形式己得到適應(yīng)度函數(shù)，而且保證適應(yīng)度函數(shù)非負(fù)。 例如旅行商問題（ TSP）：選擇一條商人遍歷若干城市的最短路徑。 15 Gray 編碼 Gray編碼的目的是為了克服二進(jìn)制編碼的 Hamming懸崖缺陷。 二 進(jìn)制編碼 二進(jìn)制 編碼是最常用的編碼技術(shù)之一，許多數(shù)值與非數(shù)值優(yōu)化問題的解都可以用二進(jìn)制位串進(jìn)行編碼。Malmb,1996。 機器學(xué)習(xí) 基于遺傳算法的機器學(xué)習(xí)也是遺傳算法應(yīng)用研究的一個重要方面。第四是染色體的交叉。 遺傳算法的基本步驟和處理流程 遺傳算法的主要處理步驟是：首先構(gòu)造滿足約束條件的染色體。遺傳算法在優(yōu)化過程中，放棄使用這些輔助信息，具有廣泛適應(yīng)性。 遺傳算法的特點 同傳統(tǒng)的尋優(yōu)算法相比，遺傳算法具有以下特點： 算法對問題參數(shù)的代碼集起作用，而不是對參數(shù)本身起作用。圖 22就是一種可能的懲罰函數(shù)。 有時間窗的 VSP問題也稱為 VSPTW(Vehicle Scheduling Problem with Time Windows） ，根據(jù)時間約束的嚴(yán)格與否，分為軟時間窗和硬時間窗的 VSP。 （ 2）集貨和送貨一體化的車輛優(yōu)化調(diào)度 每一項貨運任務(wù)都有自己的集貨點和送貨點，車輛從車場出發(fā)，去某一任務(wù)的集貨地點裝貨后運至其送貨地點卸貨（即裝卸混合），完成所有任務(wù)后返回車場。這樣做通常會增加模型最終實現(xiàn)并被采用的可能性。 啟發(fā)式解法 (Heuristics) 由于上述三種方法的求解效率 較差，所以大部分的學(xué)者都致力于啟發(fā)式解法的發(fā)展。 由于情況的不同，車輛優(yōu)化調(diào)度問題的模型構(gòu)造及算法有很大的差別。 分類 VSP 被 提 出 后 ， Linus (1981),Bodin 和 Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和 Savelsbergh(1990)等許多學(xué) 者對 VSP從不同角度，按不同的標(biāo)準(zhǔn)進(jìn)行了分類。在 Christofides(1985)， Golden和 Assad(1988)編 輯的論文集，以及 Altinkermer 和 Gavish(1991)， Laporte(1992)，Salhi(1993)等的綜述文章中都進(jìn)行了詳盡闡述。 在 物流配送系統(tǒng)中，物流配送中心的成立可有效的簡化配送程序與減少配送的頻率，以i個供應(yīng)商和 j 個零售商為例，傳統(tǒng)的配送模式是假設(shè) j個零售 商的需求都是由 i個供應(yīng)商自行配送，則一共有 ij 次的運送，如圖 12 所示。 配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)。此外，我國具有強大物流配送資源優(yōu)勢的郵政業(yè)更是在遞送包裹的基礎(chǔ)上為企業(yè)、商家和電子商務(wù)網(wǎng)站積極開展配送業(yè)務(wù)。 在高度發(fā)展的商業(yè)社會中，傳統(tǒng)的 VSP算法已無法滿足顧客需求對物流配送提出的要求，于是時間窗的概念應(yīng)運而生。經(jīng)實驗分析，取得了較好的結(jié)果。 2 第 1 章 概 述 研究背景 隨著社會主義市場經(jīng)濟的發(fā)展， 在經(jīng)濟大循環(huán)中提高 經(jīng)濟運作 效率 的物流對經(jīng)濟活動 的影響日益明顯，越來越引起人們的重視。但是在現(xiàn)代的配送系統(tǒng)中，零售商為了減少資金積壓及提供多樣化的商品，勢必要減少各種商品的存貨數(shù)量，而同時又必須考慮到提供最好的服務(wù)品質(zhì) (不允許缺 貨 )。 圖 13 以物流中心為主的配送模式 1S 2S iS 1R 2R jR 供應(yīng)商（ S） 零售商（ R） 供應(yīng)商（ S） 零售商（ R） 1S 2S iS 1R 2R jR 物流 中心 4 物流配送車輛優(yōu)化調(diào)度的研究動態(tài)和水平 問題的提出 物 流配送車輛優(yōu)化調(diào)度問題最早是由 Dantzig和 Ramser于 1959年首次提出，自此，很快引起運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計算機應(yīng)用等學(xué)科的專家與運輸計劃制定者和管理者的極大重視，成為運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點問題。遺傳算法和神經(jīng)網(wǎng)絡(luò)方法對簡單 TSP的求解取得了一定成果。 按車輛類型數(shù)分，有單車型問題 (所有車輛容量相同 )和多車型問題 (執(zhí)行任務(wù)的車輛容 5 量不完全相同 )。 人機互動法 此方法結(jié)合人類決策與計算機計算能力，在求解的過程中，通過高度的人機交互模式，結(jié)合專家的決策信息，并據(jù)以計算出結(jié)果；優(yōu)點是尋優(yōu)的過程中，決策者可以很清楚地看到各約束條件之間的替代關(guān)系，以及 參數(shù)變化可能導(dǎo)致的成本變化。 （ 2）階段法 (Twophase Algorithm) 兩階段法是： 第一階段得到一可行解，第二階段通過對點的調(diào)整，在始終保持解可行的情況下，力圖向最優(yōu)目標(biāo)靠近，每一步都產(chǎn)生另一個可行解以代替原來的解，使目標(biāo)函數(shù)值得以改進(jìn)，一直繼續(xù)到不能再改進(jìn)目標(biāo)函數(shù)值為止 (Gillett 和 Miller， 1974； Christofids、Mingozzi和 Toth， 1979； Fisher 和 Jaikumar， 1981； Renaud、 Boctor 和 Laporte， 1996； Bramel和 SimchiLevi， 1995)。 貨運車輛優(yōu)化調(diào)度問題的分類 根據(jù)任務(wù)的性質(zhì)將貨物運輸分成以下幾類： 非滿載車輛優(yōu)化調(diào)度問題 當(dāng)貨物量小于車輛容量時，用一輛車執(zhí)行任務(wù)，存在不滿載運行情況，調(diào)度時可安排一 7 輛車執(zhí)行多項任務(wù)，即在一輛車上同時載有不同貨主的貨物。 所謂時間窗口是指配送車輛或顧客希望服務(wù)或被服務(wù)的時間范 圍。圖 21為一懲罰函數(shù) (Penalty Function)當(dāng)貨品送達(dá)時間超出 ? ?le, 時，其懲罰值 ??tP 等于一個非常大的正值， 表示硬時間窗的限制。 裝載 (Loading)問題 因為每一配送車輛都有規(guī)定負(fù)荷的載重量限制，所以在 TSP問題中加入配送車輛的裝載量限制，此時的問題成為一般車輛優(yōu)化調(diào)度問題。遺傳算法是以點集開始的尋優(yōu)過程，初始群體是隨機地在搜索空間中選取的，覆蓋面大，利于全局尋優(yōu)。 遺傳算法中的選擇、交叉、和變異都是隨機操作，而不是確定的精確規(guī)則。第三是是適應(yīng)度函數(shù)的構(gòu)造和應(yīng)用，計算每個染色體適應(yīng)度。 遺傳算法的應(yīng)用總的來說可以分為如下三大類： 優(yōu)化計算 優(yōu)化計算是遺傳算法最直接的應(yīng)用，應(yīng)用面也最廣。遺傳算法與神經(jīng)網(wǎng)絡(luò)的相結(jié)合應(yīng)用于機械設(shè)計、結(jié)構(gòu)優(yōu)化、決策分析。它實際上確定了對問題的描述方式，直接影響到選擇、交叉、變異這一系列基因操作，最終影響到整個遺傳算法的性能。 （ 2）在求解連續(xù)優(yōu)化問題時，采用 二進(jìn)制編碼，一般要預(yù)先給出解的精度以確定串長，而精度確定后難以在算法中調(diào)整。因此當(dāng)問題的解是實數(shù)向量時，可以直接采用實數(shù)向量編碼。 ??3 適應(yīng)度函數(shù)是用來區(qū)分群體中個體好壞的 工具，是算法演化過程的驅(qū)動力，是進(jìn)行自然選擇的唯一依據(jù)。 適應(yīng)度函數(shù)一般要求非負(fù)，上述適應(yīng)度函數(shù)的轉(zhuǎn)換方法并不能保證后代的適應(yīng)度函數(shù)值為正數(shù)，一旦在遺傳過程中出現(xiàn)了比 MAX更大的適應(yīng)度函數(shù)值，就可能出現(xiàn)負(fù)的適應(yīng)度，使復(fù)制算子失效。在這種情況下，應(yīng)該放大個體的適應(yīng)度，以提高個體之間的競爭力。復(fù)制算子策略與編碼方式無 關(guān)，復(fù)制的主要思想是染色體的復(fù)制概率正比于其適應(yīng)度。 過程說明見圖 32。 雙親 1： 5 7 4 9 8 2 6 3 1 原始后代 ： * * 4 9 * * * 3 1 雙親 2： 1 2 3 4 9 8 7 6 5 后代 ： 2 5 4 9 8 2 6 3 1 雙親 1： 5 4 6 3 8 7 2 9 1 原始后代 ： * 4 * * 8 * * 9 1 雙親 2： 1 2 3 4 9 8 7 6 5 后代 ： 2 4 3 5 8 7 6 9 1 選擇位置 21 圖 35 基于順序交叉運算的說明 變異算子 當(dāng)交叉算子產(chǎn)生的后代的適應(yīng)度不在比前輩好又未達(dá)到最優(yōu)解，就會產(chǎn)生 不成熟收斂，不成熟收斂的根源是發(fā)生了有效基因缺失，這時，為克服這種情況，只有依賴于變異。 圖 37 插入變異的說明 易位變異 隨機地選擇一個子巡回，并將其插入到一個隨機的位置中，如圖 38中所示。這主要是種群規(guī)模過小，導(dǎo)致種群內(nèi)個體多樣性減小，從而可能丟失一些有意義的搜索點或最優(yōu)點，然而種群過大，每次迭代所需要的計算量就會很大，這又可能導(dǎo)致一個無法接 受的慢收斂率。 時間窗約束下的物流配送運輸在實際中是存在的，如某些特定的用戶在斷貨時提出的緊急配送到貨的時間要求、為飯店配送鮮活水產(chǎn)品、為有固定時刻表的火車、飛機等轉(zhuǎn)運點送貨以及超市配送用戶要求送貨不能太早于開門營業(yè)時間、也不能太晚于銷售缺貨時間等。如一個中心貨場需向幾個顧客有運送貨物，每個顧客對貨物有一定的要求，運送貨物的車輛在貨場裝滿貨后發(fā)出，把貨送到各顧