【正文】 好的結(jié)果。帶有時間窗的車輛優(yōu)化調(diào)度問題是比 VSP復(fù)雜程度更高的 NP 難題。 在高度發(fā)展的商業(yè)社會中，傳統(tǒng)的 VSP算法已無法滿足顧客需求對物流配送提出的要求，于是時間窗的概念應(yīng)運而生。 對于有時間窗的非滿載 VSP 問題，將貨運量約束和軟時間窗約束轉(zhuǎn)化為目標約束，建立了非滿載VSP模型，設(shè)計了基于自然數(shù)編碼，使用最大 保留交叉、改進的反轉(zhuǎn)變異等技術(shù)的遺傳算法。此外，我國具有強大物流配送資源優(yōu)勢的郵政業(yè)更是在遞送包裹的基礎(chǔ)上為企業(yè)、商家和電子商務(wù)網(wǎng)站積極開展配送業(yè)務(wù)。 本文第 1章研究目前物流配送車輛優(yōu)化調(diào)度問題的研究動態(tài)和水平；第 2章進一步研究有時間窗的物流配送車輛優(yōu)化調(diào)度問題；第 3章闡述和研究所采用遺傳算法的基本理論；第 4章詳細論述如何采用遺傳算法解決有時間窗的物流配送車輛優(yōu)化調(diào)度問題并通過實驗數(shù)據(jù)分析所采用改進的遺傳算法的性能。 配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)。 圖 11 配送流程圖 在傳統(tǒng)的配送系統(tǒng)中，由于商品的需求量及種類較少，零售商可憑借較多的存貨及較常的定貨周期來減少供貨商的配送頻率，以降低運輸成本。 在 物流配送系統(tǒng)中，物流配送中心的成立可有效的簡化配送程序與減少配送的頻率，以i個供應(yīng)商和 j 個零售商為例，傳統(tǒng)的配送模式是假設(shè) j個零售 商的需求都是由 i個供應(yīng)商自行配送，則一共有 ij 次的運送，如圖 12 所示。該問題一般定義為 :對一系列裝（卸）貨點，組織適當?shù)男熊嚲€路，使車輛有序的通過它們，在滿足一定的約束條件 (如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等 )下，達到一定的目標 (如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等 )［３］ 。在 Christofides(1985)， Golden和 Assad(1988)編 輯的論文集，以及 Altinkermer 和 Gavish(1991)， Laporte(1992)，Salhi(1993)等的綜述文章中都進行了詳盡闡述。張震 (1995)針對單車場滿載問題，提出了考慮運輸行程約束的優(yōu)化方法。 分類 VSP 被 提 出 后 ， Linus (1981),Bodin 和 Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和 Savelsbergh(1990)等許多學(xué) 者對 VSP從不同角度，按不同的標準進行了分類。 按車場 (或貨場、配送中心等 )數(shù)目分，有單車場問題和多車場問題。 由于情況的不同，車輛優(yōu)化調(diào)度問題的模型構(gòu)造及算法有很大的差別。 算法 貨運車輛優(yōu)化調(diào)度問題的求解方法非常 豐富，目前主要有以下四類： 系統(tǒng)仿真法 (Simulation ) 此方法最早由 Golden 和 Skiscim 于 1986 年提出，主要應(yīng)用于行車線路與物流中心區(qū)位的選擇，優(yōu)點在于可直接觀察系統(tǒng)安排的效率與效果，但由于問題的實際情況多變且具有不確定性，是否能將實際的配送情形系統(tǒng)邏輯化為仿真程序，往往令人質(zhì)疑。 啟發(fā)式解法 (Heuristics) 由于上述三種方法的求解效率 較差，所以大部分的學(xué)者都致力于啟發(fā)式解法的發(fā)展。 構(gòu)造算法是最早提出用來解決旅行商問題 (Traveling Salesman Problem,簡稱 TSP)及 VSP的，這些方法一般速度快，也很靈活，但這類方法有時找到的解離最優(yōu)解差的很遠。這樣做通常會增加模型最終實現(xiàn)并被采用的可能性。 亞啟發(fā)式算法包括表搜索算法 (Table Search)、模擬退火算法 (Simulated Annealing)、遺傳算法 (Geic Algorithm)和神經(jīng)網(wǎng)絡(luò) (Neural Networks)方法。 （ 2）集貨和送貨一體化的車輛優(yōu)化調(diào)度 每一項貨運任務(wù)都有自己的集貨點和送貨點，車輛從車場出發(fā)，去某一任務(wù)的集貨地點裝貨后運至其送貨地點卸貨（即裝卸混合），完成所有任務(wù)后返回車場。 研究的意義 目前有關(guān) VSP的研究，多致力于單一車種或多車種優(yōu)化調(diào)度問題，很少涉及結(jié)合時間窗口的 VSP問題。 有時間窗的 VSP問題也稱為 VSPTW(Vehicle Scheduling Problem with Time Windows） ，根據(jù)時間約束的嚴格與否，分為軟時間窗和硬時間窗的 VSP。三者分述如下： 硬時間窗 (Hard Time Windows)：指配送車必須在特定時間區(qū)段 (如圖 21中的 ? ?le, )內(nèi)將貨品送達顧客手中，不論是遲到或早到都完全不予接受。圖 22就是一種可能的懲罰函數(shù)。所以對每一部車輛來說，是一個旅行商問題 (TSP)。 遺傳算法的特點 同傳統(tǒng)的尋優(yōu)算法相比，遺傳算法具有以下特點： 算法對問題參數(shù)的代碼集起作用，而不是對參數(shù)本身起作用。這種點到點的搜索方法在多峰值優(yōu)化問題中，容易誤入局部最優(yōu)解。遺傳算法在優(yōu)化過程中，放棄使用這些輔助信息，具有廣泛適應(yīng)性。 Goldeberg對 GA的處理并行性進行了合理的分析，指出了GA對模式的處理效率是 ? ?3no ， Holland稱之為 GA的“隱式并行性” ［５］ 。 遺傳算法的基本步驟和處理流程 遺傳算法的主要處理步驟是：首先構(gòu)造滿足約束條件的染色體。初始群體群體的染色體數(shù)量應(yīng)適當選擇。第四是染色體的交叉。 圖 31 遺傳算法的基本流程 遺傳算法的應(yīng)用 遺傳算法是 60年代由美國 J. Holland教授首先在《自然結(jié)合人工智能系統(tǒng)的適應(yīng)性》一書中提出的，是一種新興的自適應(yīng)隨機搜索方法，具有極強的魯棒性和內(nèi)在的并行計算機制，特別適合于非凸空間中復(fù)雜的多極值優(yōu)化和組合優(yōu)化，在機器學(xué)習(xí)、自動控制、機器人技術(shù)、電器自動化以及計算機和通信領(lǐng)域以取得了非凡的成就。 機器學(xué)習(xí) 基于遺傳算法的機器學(xué)習(xí)也是遺傳算法應(yīng)用研究的一個重要方面。 神經(jīng)網(wǎng)絡(luò) 遺傳算法的另一個 活躍的研究方向是在神經(jīng)網(wǎng)絡(luò)方面的應(yīng)用，這包括優(yōu)化神經(jīng)網(wǎng)絡(luò)的連接權(quán)系數(shù)、網(wǎng)絡(luò)的空間結(jié)構(gòu)等。Malmb,1996。編碼方法決定了染色體的排列形式。 二 進制編碼 二進制 編碼是最常用的編碼技術(shù)之一，許多數(shù)值與非數(shù)值優(yōu)化問題的解都可以用二進制位串進行編碼。例如 7和 8的二進制編碼分別為 0111和 Hamming懸崖（ Hamming cliffs） ,有可能降低遺傳算法的搜索效率。 15 Gray 編碼 Gray編碼的目的是為了克服二進制編碼的 Hamming懸崖缺陷。 實數(shù)向量編碼 在求解一些多維高精度優(yōu)化問題時，二進制編碼會占用大量的存儲空間，而且使得搜索空間極其龐大，從而影響遺傳算法的性能。 例如旅行商問題（ TSP）：選擇一條商人遍歷若干城市的最短路徑。遺傳算法正是基于適應(yīng)度對個體進行選擇，以保證適應(yīng)性好的個體有機會在下一代中產(chǎn)生更多的子個體。 16 目標函數(shù)映射成適應(yīng)度函數(shù) 遺傳算法適應(yīng)度函數(shù)值作為染色體的性能指標，以及利用繁殖概率的大小來評估各染色體的優(yōu)劣程度，多半以最大化為目標 (亦即越大越好 )；但是許多優(yōu)化問題 (比如物流配送 VSP問題 )是求取費用函數(shù)的最小值，必須將目標函數(shù)轉(zhuǎn)化為求最大值形式己得到適應(yīng)度函數(shù)，而且保證適應(yīng)度函數(shù)非負。 目前遺傳世代中，最后 n代出現(xiàn)的最大的目標函數(shù)值。如果群體中出現(xiàn)了超級個體，即該個體的適應(yīng)度大大超過了群體的平均適應(yīng)度，則按照適應(yīng)度比例選擇時，該個體很快在群體中占有絕對優(yōu)勢，從而導(dǎo)致算法較早的收斂到一個局部最優(yōu)點。在這種情況下，群體中實際上已不存在競爭，從而搜索目標難以得到改善，出現(xiàn)了停滯現(xiàn)象。 表 31 遺傳算法中適應(yīng)度常用的定標方法 定標方法 方法描述 17 線性定標 將群體中各個體的適應(yīng)度以線性關(guān)系縮放，這種方法控制每一代中表現(xiàn)最佳的個體復(fù)制數(shù)目，但當群體中個體適應(yīng)度差異在定標前就己經(jīng)有顯著差異時，經(jīng)由此法轉(zhuǎn)換的新適應(yīng)度可能會有負值產(chǎn)生， 違背了概率不得為負數(shù)的限制，必須輔以其他方法處理。 遺傳算法的基因操作 選擇算子 發(fā)展各種復(fù)制算子的目的是為了避免基因缺失，提高全局收斂性和效率。 18 交叉算子 交叉算子的作用是組合出新的個體，在串空間進行有效搜索，同時需降低對有效模式的破壞概率。步驟如下： Step l：在字串上均勻的選擇兩點，由這兩點定義的子串稱為映射段； Step 2：交換雙親的兩個子串，產(chǎn)生原始后代； Step 3：確定兩映射段之間的關(guān)系； Step 4： 根據(jù)映射關(guān)系將后代合法化。 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：按照這個城市順序，從左到右將這些城市定位到后代的空缺位置上。用同樣的步驟可產(chǎn)生另一個后代 [2 4 5 3 1 6 9 7 8]。 表 32 變異算子類型 名稱 特點 研究者 適用編碼 常規(guī)位變異 標準遺傳算法成員 DeJong 二進制 有效基因變異 避免有效基因缺失 Yun 二進制 自適應(yīng)有效基因變異 最低有效基因個數(shù)自適應(yīng)變化 Yun 二進制 概率自調(diào)整變異 由兩個串的相似性確定變異概率 Whitley 二進制 均勻變異 由一個實數(shù)元素以相同的概率在域 內(nèi)變動 Michalewicz 十進制 非均勻變異 使整個矢量在解空間輕微變動 Michalewicz 十進制 三次高斯近似變異 Bosworth, Foo,Zeigler 十進制 零變異 同上 十進制 目前較常用的高級遺傳算子，來源于群體遺傳學(xué)。過程示于圖 37中。將 2— 交換和 3— 交換作為遺傳算法的變異算子，即在每代群體中以概率 P，隨機選取染色體上的兩點或 3點，進行 2— 交換或 3— 交換。通常認為：若種群過小，算法就有可能收斂于局部最優(yōu)解，而不能收斂到最優(yōu)結(jié)果或最優(yōu)結(jié)果附近。但在某些情況下，當種群達到一定規(guī)模時，再增大種群規(guī)模，對搜索結(jié)果的改善并無多大幫助，甚至有可能變差。 隨機選擇三個位置 5 4 3 9 8 1 7 6 2 交換相應(yīng)的城市 5 4 3 9 8 6 7 1 2 5 4 6 9 8 1 7 3 2 5 4 6 9 8 3 7 1 2 5 4 1 9 8 6 7 3 2 5 4 1 9 8 3 7 6 2 25 第 4 章 遺傳算法求解有時間窗非滿載 VSP 由于現(xiàn)在各任務(wù)需求點，如零售商店、連鎖店等都盡可能的銷售暢銷商品，庫存數(shù)量最好不要太多，且不能缺貨，因此現(xiàn)在的物流配送一般是小范圍、近距離 、多品種、小批量、多批次、為多用戶服務(wù)的經(jīng)濟活動，這時每個任務(wù)點的貨物量小于車輛容量，用一輛車執(zhí)行單一任務(wù)，屬于非滿載運行情況，在一輛車上同時裝載有不同任務(wù)點的貨物，所以物流配送車輛優(yōu)化調(diào)度大部分是非滿載車輛優(yōu)化調(diào)度問題。根據(jù)小組成員的分工，本文就適應(yīng)度函數(shù)的選定和變異算子進行主要闡述。在日常生活中和生產(chǎn)實際中，許多類似的問題都可以歸結(jié)為這類問題。由于有時間窗的 VSP是典型的 NP難題，會隨著節(jié)點的增加出現(xiàn)組合爆炸的現(xiàn)象 ［５］ 。本算法采用人機對話來調(diào)整 a 的大小。如果車輛到達 i的時間早于 ia ，則車輛需在 i處等待，如果車輛到達時間晚于 ib ，則任務(wù) i要延遲執(zhí)行。若超出這個時間范圍， 則得到的解為不可行解 ［２］［４］ 。若車輛在 ib 之后到達點 i，則服務(wù)被延遲，須支付一定的罰金。這樣的染色體結(jié)構(gòu)可通俗地理解為第一輛車從配送中心 0 出發(fā)，經(jīng)過需求點siii 11211 , ? 后，回到配送中心 0， 形成子路徑 1；第二輛車也從配送中心 0 出發(fā)，經(jīng)過以 28 前未訪問的需求點 tiii 22221 , ? 后，返回配送中心 0，形成子路徑 2；依次類推，直到所有的 n個需求點全部被遍歷，形成子路徑 m。 在編 碼的過程中不考慮約束，而在遺傳算法的計算過程中檢測得到的染色體相應(yīng)的解是否可行，若可行，則放入下一代群體中，否則將其舍棄