【正文】 法的性能，可在使用輪盤賭的基礎上采用最佳保留策略。 過程說明見圖 33，同樣步驟可用同一對雙親產生另一個后代 [7 9 3 4 5 6 1 2 8]。目前發(fā)展的主要變異算子如表 32所示。這里說明一下2— 交換和 3— 交換。建議的最優(yōu)參數(shù)范圍是30~20?n , ~?cp , ~?mp 。該問題屬于組合優(yōu)化領域的 NP 難題 ［１１］ ，本小組嘗試使用遺傳算法求得該類問題的最優(yōu)解或近似最優(yōu)解。 有時間窗的 VSP 則是在一般車輛優(yōu)化調度問題的基礎上要求每項任務 i 在時間范圍? ?ii ba, 內完成，并可根據(jù)時間約束的嚴格與否，分為軟時間窗和硬時間窗的 VSP。 得到車輛優(yōu)化調度數(shù)學模型如下： ? ?? ?? ?? mk ni ppk kiikdz 1 11 )1(m in (42) qgk kini p???1 nnk ??1 ， mk ,2,1 ?? (43) nnmk k ???1 (44) ? ?? ?kkikik ninppP ,2,1,2,1| ?? ??? mk ,2,1 ?? (45) ??21 kk PP ? 21 kk ?? ； mk ,2,11 ?? ； mk ,2,12 ?? (46) 27 有時間窗 VSP 模型 設完成任務 i 需要的時間 (裝貨或卸貨 )表示為 iT ，又設任務 i 的開始時間需在一定的時間范圍 ? ?ii ba, 內，其中 ia 為任務 i的允許最早開始時間，為任務 i的允許最遲開始時間。若車輛在 ia 之前到達點 i，則車輛在此等待，發(fā)生了機會成本損失。一般有下面幾種方法： 問題的約束在染色體中表現(xiàn)出來，設計專門的遺傳算子，使染色體所表示的解在遺傳算法的求解過程中始終保持為可行解。 采用懲罰的方法來處理約束。 算法設計 算法流程圖 算法流 程圖如圖 41示。求滿足貨運要求的費用最少的車輛行使線路。 數(shù)學模型 一般 VSP 模型 物流配送中心擁有足夠的載重量為 q 的車輛，現(xiàn)有 n 個需求點任務需要貨物運輸，以n,1? 表示，已知第 i個需求點的需要的貨物量為 ? ?nigi ,1?? ，且 qgi ? 。 問題描述 一般車輛優(yōu)化調度問題可描述為：一個物流配送中心使用載重量相同的多輛汽車完成多個貨物需求點的配送任務。目前常用的參數(shù)范圍是 200~20?n , ~?cp ， ~0?mp 。 2— 交換和 3— 交換說明分別示于圖 39和圖 310中。主要有以下四種： 反轉變異 在染色體上隨機地選擇兩點，將兩點間的子串反轉。 圖 34 說明了交叉過程，同樣步驟可產生另一個后代 [4 2 3 1 5 6 7 8 9]。交叉算子是遺傳算法區(qū)別于其他進化算法的重要特征 [5]。 標準差祛除法 此方法是利用平均適應度函數(shù)與其標準差間的差異來修正原個體的適應度，以解決線性定標會產生負值的問題，是線性定標前的一個預處理方法，但計算上比較復雜。這種現(xiàn)象稱為過早收斂。一般可采用以下的方法進行轉換： ? ? ? ?轉換前轉換后 kk fM A Xf ?? 其中 MAX為一常數(shù)，最好與群體無關，一般可以由下列四種方式?jīng)Q定 : 任意足夠大的正數(shù)。設共有 n 個城市，分別用 n,3,2,1 ? 來表示，每兩個城市 i 和 j 之間的距離用 ijd 表示，則商人的一次遍歷路線可以用一個 n,3,2,1 ? 的全排列 ? ?n??? , 21 ? 表示，該排列表示遍歷路線121 ???? ???? n?。 一個 n 階 Gray碼是一個由所有 n位二進制位串組成的有序循環(huán)序列，使得相鄰的位串之間恰有一位不同。 二進制編碼是將原問題的解空間映射到位串空間 ??L1,0 上，其中 L 為某個固定常數(shù)。Ochi 和 Luiz 1998 )，但僅僅是開始嘗試階段，還有待于進一步的研究。機器學習是為解決專家系統(tǒng)設計中的知識獲取瓶頸問題而設計的。父代的遺傳基因的結合是通過父代染色體之間的交叉并到達下一代個體的。編碼的目的主要是使優(yōu)化問題解的表現(xiàn)形式適合于遺傳算法中的遺傳運算。 算法具有極強的容錯能力。遺傳算法處理的對象是染色體，因而要求把所要優(yōu)化問題的基本參數(shù)轉化成一定長度的有限符號的染色體。 t e l ??tP M 10 圖 22 軟時間窗約束示意圖 混合型時間窗 (Mixed Time Windows )：系統(tǒng)中有些顧客屬于硬時間窗，有些則屬于軟時間窗；同一顧客，往往軟、硬兩種時間窗混合使用。由于有時間窗的 VSP是典型的NP— 難題，會隨著節(jié)點的增加出現(xiàn)組合爆炸的現(xiàn)象，因 此求解的困難度及時效性會有影響。 滿載車輛優(yōu)化調度問題 當貨主的貨物量不小于車輛容量時，執(zhí)行每項任務需要的車輛可能不只一輛，車輛為完成任務，需 滿載運行。 （ 3）不完全優(yōu)化算法 (Inplete Optimization Algorithm) 以 啟發(fā)式準則來代替精確算法中的決策準則，以縮小解搜索的空間 (Toth、 Christofides和 Mingozzi， 1979 等 )。該方法在解題時可減少搜尋的次數(shù)，所以是一種容易且快速的求解困難問題的算法。 基本問題與基本方法 為簡化貨運車輛優(yōu) 化調度問題的求解，常常應用一些技術將問題分解或轉化成一個或幾個已經(jīng)研究過的基本問題，再用相應比較成熟的基本理論和方法，以得到原貨運車輛優(yōu)化調度問題的最優(yōu)解或滿意解。 按任務特征分，有純裝問題或純卸題 (pure pick up or pure delivery, 車輛在所有任務點裝貨或卸貨，及集貨或送貨問題 ) 及裝卸混合問題 (bined pick up and delivery，每項任務有不同的裝貨點和卸貨點，即集貨、送貨一體化問題 )。該領域的代表人物有 Bodin， Christfids，Golden， Assad， Ball， Laporte， Rinnooy Kan， Lenstra， Desrosiers和 Desrochers等人［１］［３］ 。假設零售商與供應商之間通過一個物流配送中心來配送，則只需 i+j 次配送，如圖 13所示，如此一來即可減少 (ij(i+j))的配送次數(shù)，當供應商與零售商數(shù)目越多，節(jié)省的配送次數(shù)也就會越多。我國國家標準《物流術語》中對配送的定義是：“在經(jīng)濟合理區(qū)域范圍內，根據(jù)用戶要求，對物品進行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達指定地點的物流活動 ［７］ 。物流配送開始在我國迅速興起發(fā)展起來，對物流配送的研究引起了國內物流專家學者的廣泛關注。帶有時間窗的車輛優(yōu)化調度問題是比 VSP復雜程度更高的 NP 難題。 對于有時間窗的非滿載 VSP 問題，將貨運量約束和軟時間窗約束轉化為目標約束，建立了非滿載VSP模型，設計了基于自然數(shù)編碼，使用最大 保留交叉、改進的反轉變異等技術的遺傳算法。 本文第 1章研究目前物流配送車輛優(yōu)化調度問題的研究動態(tài)和水平；第 2章進一步研究有時間窗的物流配送車輛優(yōu)化調度問題；第 3章闡述和研究所采用遺傳算法的基本理論；第 4章詳細論述如何采用遺傳算法解決有時間窗的物流配送車輛優(yōu)化調度問題并通過實驗數(shù)據(jù)分析所采用改進的遺傳算法的性能。 圖 11 配送流程圖 在傳統(tǒng)的配送系統(tǒng)中，由于商品的需求量及種類較少，零售商可憑借較多的存貨及較常的定貨周期來減少供貨商的配送頻率，以降低運輸成本。該問題一般定義為 :對一系列裝（卸）貨點，組織適當?shù)男熊嚲€路，使車輛有序的通過它們，在滿足一定的約束條件 (如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等 )下，達到一定的目標 (如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等 )［３］ 。張震 (1995)針對單車場滿載問題，提出了考慮運輸行程約束的優(yōu)化方法。 按車場 (或貨場、配送中心等 )數(shù)目分，有單車場問題和多車場問題。 算法 貨運車輛優(yōu)化調度問題的求解方法非常 豐富，目前主要有以下四類： 系統(tǒng)仿真法 (Simulation ) 此方法最早由 Golden 和 Skiscim 于 1986 年提出，主要應用于行車線路與物流中心區(qū)位的選擇，優(yōu)點在于可直接觀察系統(tǒng)安排的效率與效果，但由于問題的實際情況多變且具有不確定性，是否能將實際的配送情形系統(tǒng)邏輯化為仿真程序，往往令人質疑。 構造算法是最早提出用來解決旅行商問題 (Traveling Salesman Problem,簡稱 TSP)及 VSP的，這些方法一般速度快，也很靈活，但這類方法有時找到的解離最優(yōu)解差的很遠。 亞啟發(fā)式算法包括表搜索算法 (Table Search)、模擬退火算法 (Simulated Annealing)、遺傳算法 (Geic Algorithm)和神經(jīng)網(wǎng)絡 (Neural Networks)方法。 研究的意義 目前有關 VSP的研究，多致力于單一車種或多車種優(yōu)化調度問題，很少涉及結合時間窗口的 VSP問題。三者分述如下： 硬時間窗 (Hard Time Windows)：指配送車必須在特定時間區(qū)段 (如圖 21中的 ? ?le, )內將貨品送達顧客手中，不論是遲到或早到都完全不予接受。所以對每一部車輛來說，是一個旅行商問題 (TSP)。這種點到點的搜索方法在多峰值優(yōu)化問題中，容易誤入局部最優(yōu)解。 Goldeberg對 GA的處理并行性進行了合理的分析，指出了GA對模式的處理效率是 ? ?3no ， Holland稱之為 GA的“隱式并行性” ［５］ 。初始群體群體的染色體數(shù)量應適當選擇。 圖 31 遺傳算法的基本流程 遺傳算法的應用 遺傳算法是 60年代由美國 J. Holland教授首先在《自然結合人工智能系統(tǒng)的適應性》一書中提出的，是一種新興的自適應隨機搜索方法，具有極強的魯棒性和內在的并行計算機制，特別適合于非凸空間中復雜的多極值優(yōu)化和組合優(yōu)化，在機器學習、自動控制、機器人技術、電器自動化以及計算機和通信領域以取得了非凡的成就。 神經(jīng)網(wǎng)絡 遺傳算法的另一個 活躍的研究方向是在神經(jīng)網(wǎng)絡方面的應用，這包括優(yōu)化神經(jīng)網(wǎng)絡的連接權系數(shù)、網(wǎng)絡的空間結構等。編碼方法決定了染色體的排列形式。例如 7和 8的二進制編碼分別為 0111和 Hamming懸崖（ Hamming cliffs） ,有可能降低遺傳算法的搜索效率。 實數(shù)向量編碼 在求解一些多維高精度優(yōu)化問題時，二進制編碼會占用大量的存儲空間，而且使得搜索空間極其龐大，從而影響遺傳算法的性能。遺傳算法正是基于適應度對個體進行選擇，以保證適應性好的個體有機會在下一代中產生更多的子個體。 目前遺傳世代中，最后 n代出現(xiàn)的最大的目標函數(shù)值。在這種情況下，群體中實際上已不存在競爭，從而搜索目標難以得到改善，出現(xiàn)了停滯現(xiàn)象。 遺傳算法的基因操作 選擇算子 發(fā)展各種復制算子的目的是為了避免基因缺失，提高全局收斂性和效率。步驟如下： Step l：在字串上均勻的選擇兩點，由這兩點定義的子串稱為映射段； Step 2：交換雙親的兩個子串，產生原始后代； Step 3：確定兩映射段之間的關系； Step 4： 根據(jù)映射關系將后代合法化。用同樣的步驟可產生另一個后代 [2 4 5 3 1 6 9 7 8]。過程示于圖 37中。通常認為：若種群過小，算法就有可能收斂于局部最優(yōu)解，而不能收斂到最優(yōu)結果或最優(yōu)結果附近。 隨機選擇三個位置 5 4 3 9 8 1 7 6 2 交換相應的城市 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)在各任務需求點，如零售商店、連鎖店等都盡可能的銷售暢銷商品，庫存數(shù)量最好不要太多，且不能缺貨，因此現(xiàn)在的物流配送一般是小范圍、近距離 、多品種、小批量、多批次、為多用戶服務的經(jīng)濟活動，這時每個任務點的貨物量小于車輛容量，用一輛車執(zhí)行單一任務，屬于非滿載運行情況，在一輛車上同時裝載有不同任務點的貨物，所以物流配送車輛優(yōu)化調度大部分是非滿載車輛優(yōu)化調度問題。在日常生活中和生產實際中，許多類似的問題都可以歸結為這類問題。本算法采用人機對話來調整 a 的大小。若超出這個時間范圍， 則得到的解為不可行解 ［２］［４］ 。這樣的染色體結構可通俗地理解為第一輛車從配送中心 0 出發(fā)，經(jīng)過需求點siii 11211 , ? 后，回到配送中心 0， 形成子路徑 1；第二輛車也從配送中心 0 出發(fā)，經(jīng)過以 28 前未訪問的需求點 tiii 22221 , ? 后，返回配送中心 0，形成子路徑 2；依次類推，直到所有的 n個需求點全部被遍歷，形成子路徑 m