【導讀】近年來，物流作為“第三方利潤的源泉”受到國內各行業(yè)的極大重視并得到了較大的發(fā)展。帶有時間窗的車輛優(yōu)化調度問題是比VSP復雜程度更高的NP難題。本文在研究物流配送車輛優(yōu)化調度問題的基礎上，對有時間窗的車輛優(yōu)化調度問題進行了分析。對所采用的遺傳算法的基本理論做了論述。VSP模型，設計了基于自然數編碼，使用最大保留交叉、改進的反轉變異等技術的遺傳算法。析，取得了較好的結果。由于此問題為小組成員共同研究，本文重點論述了本人完成的關于適應度函數。和變異操作的部分。

　　

【正文】 1 8 9 * * * 雙親 2： 1 2 3 4 9 8 7 6 5 后代： 4 2 3 1 8 9 7 6 5 選擇位置 22 圖 36 反轉變異的說明 插入變異 隨機地選擇一個城市，并將它插入到一個隨機的位置中 。過程示于圖 37中。 圖 37 插入變異的說明 易位變異 隨機地選擇一個子巡回，并將其插入到一個隨機的位置中，如圖 38中所示。 隨機選擇子巡回 5 4 3 9 8 1 7 6 2 插入子巡回 5 4 3 7 8 1 9 2 6 隨機選擇一個城市 5 4 3 9 8 1 7 6 2 插入到一個隨機位置 5 4 3 9 8 2 1 7 6 23 圖 38 易位變異的說明 k— 交換變異 k— 交換變異是解決 VSP 的一種局域尋優(yōu)技術，即對初始可行路線的 k 條邊（或弧）進行交換，在初始可行解的鄰域內逐步改進方案，直到在鄰域內不能改進為止。這里說明一下2— 交換和 3— 交換。將 2— 交換和 3— 交換作為遺傳算法的變異算子，即在每代群體中以概率 P，隨機選取染色體上的兩點或 3點，進行 2— 交換或 3— 交換。 2— 交換和 3— 交換說明分別示于圖 39和圖 310中。 圖 39 2— 交換變異的說明 隨機選擇一個子巡回 5 4 3 9 8 1 7 6 2 插入到一個隨機位置 5 4 3 7 8 6 2 9 1 隨機選擇兩個位置 5 4 3 9 8 1 7 6 2 交換相應的城市 5 4 6 9 8 1 7 3 2 24 圖 310 3— 交換變異的說明 遺傳算法控制參數設定 遺傳算法中需要選擇的參數主要有染色體長度 l 、群體規(guī)模 n、交叉率 cp 、變異率 mp等，這些參數對 GA 性能影響很大。為了選擇合適的群體規(guī)模 n、交叉率 cp 、變異率 mp ，許多學者進行了研究。通常認為：若種群過小，算法就有可能收斂于局部最優(yōu)解，而不能收斂到最優(yōu)結果或最優(yōu)結果附近。這主要是種群規(guī)模過小，導致種群內個體多樣性減小，從而可能丟失一些有意義的搜索點或最優(yōu)點，然而種群過大，每次迭代所需要的計算量就會很大，這又可能導致一個無法接 受的慢收斂率。一般，當種群規(guī)模增大時，將有利于改善種群的多樣性，從而可能有利于使算法收斂到最優(yōu)解或最優(yōu)解附近。建議的最優(yōu)參數范圍是30~20?n , ~?cp , ~?mp 。但在某些情況下，當種群達到一定規(guī)模時，再增大種群規(guī)模，對搜索結果的改善并無多大幫助，甚至有可能變差。目前常用的參數范圍是 200~20?n , ~?cp ， ~0?mp 。由于控制參數會相互影響，所以無法確定獨立的最佳參數值，但當種群規(guī)模小時可選擇較大的交叉及變異率以防止過早收斂；當群體規(guī)模大時可選擇較小交叉及變異率以節(jié)省運算時間。目前許多學者認識到這些參數需要隨著遺傳進程而自適應變化，這種有自組織性能的遺傳算法具有更強的魯棒性、全局收斂性和計算效率 ［９］［１０］ 。 隨機選擇三個位置 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 由于現在各任務需求點，如零售商店、連鎖店等都盡可能的銷售暢銷商品，庫存數量最好不要太多，且不能缺貨，因此現在的物流配送一般是小范圍、近距離 、多品種、小批量、多批次、為多用戶服務的經濟活動，這時每個任務點的貨物量小于車輛容量，用一輛車執(zhí)行單一任務，屬于非滿載運行情況，在一輛車上同時裝載有不同任務點的貨物，所以物流配送車輛優(yōu)化調度大部分是非滿載車輛優(yōu)化調度問題。 時間窗約束下的物流配送運輸在實際中是存在的，如某些特定的用戶在斷貨時提出的緊急配送到貨的時間要求、為飯店配送鮮活水產品、為有固定時刻表的火車、飛機等轉運點送貨以及超市配送用戶要求送貨不能太早于開門營業(yè)時間、也不能太晚于銷售缺貨時間等。 有時間窗約束的車輛優(yōu)化調度問題歸結為車輛優(yōu)化調度問題 中的單車場、單車型、非滿載、多約束（含時間窗約束）、多目標、車輛封閉的對點服務問題。該問題屬于組合優(yōu)化領域的 NP 難題 ［１１］ ，本小組嘗試使用遺傳算法求得該類問題的最優(yōu)解或近似最優(yōu)解。根據小組成員的分工，本文就適應度函數的選定和變異算子進行主要闡述。 問題描述 一般車輛優(yōu)化調度問題可描述為：一個物流配送中心使用載重量相同的多輛汽車完成多個貨物需求點的配送任務。每個需求點 (供貨點 )的需求量 (供貨量 )已知，且都小于配送車輛的載重量；配送中心和各需求點中任意兩點間的運距已知或可以推算出來；一個需求點的任務 只能由一輛車一次運送完成；每個配送車輛從配送中心出發(fā)，完成運送任務后返回配送中心。求滿足貨運需求和車輛載重量的費用最小的車輛行使線路。在日常生活中和生產實際中，許多類似的問題都可以歸結為這類問題。如一個中心貨場需向幾個顧客有運送貨物，每個顧客對貨物有一定的要求，運送貨物的車輛在貨場裝滿貨后發(fā)出，把貨送到各顧客處，完成任務后，返回貨場，如何確定滿足用戶需求的費用最小的車輛行使路線，即送貨車輛優(yōu)化調度。又如，若干廠家生產一些產品，需要運到配送中心，車輛從配送中心出發(fā)，到各廠家去裝貨，裝滿貨后返回配送中心，在滿足 廠家發(fā)貨要求的情況下，按什么線路行駛，可使總費用最小，即集貨車輛優(yōu)化調度。 有時間窗的 VSP 則是在一般車輛優(yōu)化調度問題的基礎上要求每項任務 i 在時間范圍? ?ii ba, 內完成，并可根據時間約束的嚴格與否，分為軟時間窗和硬時間窗的 VSP。由于有時間窗的 VSP是典型的 NP難題，會隨著節(jié)點的增加出現組合爆炸的現象 ［５］ 。 數學模型 一般 VSP 模型 物流配送中心擁有足夠的載重量為 q 的車輛，現有 n 個需求點任務需要貨物運輸，以n,1? 表示，已知第 i個需求點的需要的貨物量為 ? ?nigi ,1?? ，且 qgi ? 。 26 一般來講，當問題的約束越多，組織線路就越難，一輛車所完成的滿足所有約束的任務就越少，這時，一輛車實際所能容納的任務量要小，而所用的車輛數可能要多。為了使線路安排具有一定的彈性，可預先估計一個完成任務所需要的車輛數 m： 11 ????????????????aqgmnii (41) 其中， [ ]表示不大于括號內數字的 最大整數， ? ?10 ??aa 是對裝車或卸車的復雜性程度及約束多少的估計，一般來講，裝 (卸 )車越復雜，約束越多， a 應越小，表示一輛車所能承載的貨物量越小。本算法采用人機對話來調整 a 的大小。 為構造數學模型方便，將物流配送中心編號為 0，需求點編號為 n,1? ，則物流配送中心及需求點均以點 ? ?nii ,1,0 ?? 來表示， 完成配送任務共需要車輛 數目為 m ，每輛車的載重量為 q ，每個需求點的需求量為 ? ?nigi ,2,1 ?? ，配送中心及各需求點中任意兩點間的距離為 ? ?njnid ij ,1,0。,1,0 ?? ?? ，第 k 輛車的行車路徑稱為第 k條子路徑，其中經過的需求點數目為 kn ， kp 表示第 k 條子路徑中包含的 kn 個需求點組成的集合 ，其中的元素? ?nipki ,2,1 ?? 代表第 k 條子路徑中順序為 i 的需求點； )1(0, ?knkk pp 均表示配送中心，且有 0)1(0 ?? ?knkk pp。 得到車輛優(yōu)化調度數學模型如下： ? ?? ?? ?? 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的允許最遲開始時間。如果車輛到達 i的時間早于 ia ，則車輛需在 i處等待，如果車輛到達時間晚于 ib ，則任務 i要延遲執(zhí)行。求滿足貨運要求的費用最少的車輛行使線路。此問題稱之為有時間窗的車輛優(yōu)化調度問題。 以 is 表示車輛到達點 i的時間，一般應有以下關系式： 00?s iii bsa ?? ni ,2,1 ?? (47) 硬時間窗 VSP指每項任務必須在要求的時間范圍內完成，即必須滿足式 (47)。若超出這個時間范圍， 則得到的解為不可行解 ［２］［４］ 。 軟時間窗 VSP指如果每項任務不能在要求的時間范圍內完成，則給予一定的懲罰。懲罰成本函數的設定一般以配送中心與顧客在商議之后所簽定的合同為主，但因實際上所簽定合同是為維護買賣雙方共同的利益，故考慮的因素相當多。若車輛在 ia 之前到達點 i，則車輛在此等待，發(fā)生了機會成本損失。若車輛在 ib 之后到達點 i，則服務被延遲，須支付一定的罰金。 算法設計 算法流程圖 算法流 程圖如圖 41示。 染色體結構 為提高效率，對 VSP采用自然數編碼方式，即序數編碼。 單車場車輛優(yōu)化調度問題的一條可行線路可編成長度為 mn? 的染色體? ?mwmts iiiiiiii ???? ,0,,0,0 12222111211 ，其中 kji 用自然數表示，代表編號為 kj 的需求點。這樣的染色體結構可通俗地理解為第一輛車從配送中心 0 出發(fā)，經過需求點siii 11211 , ? 后，回到配送中心 0， 形成子路徑 1；第二輛車也從配送中心 0 出發(fā)，經過以 28 前未訪問的需求點 tiii 22221 , ? 后，返回配送中心 0，形成子路徑 2；依次類推，直到所有的 n個需求點全部被遍歷，形成子路徑 m。如染色體 021304605870表示的行車線路為： 子路徑 1: 配送中心 0 → 需求點 2 → 需求點 1→ 需求點 3→ 配送中心 0 子路徑 2: 配送中心 0 → 需求點 4 → 需求點 6→ 配送中心 0 子路徑 3: 配送中心 0 → 需求點 5→ 需求點 8→ 需求點 7→ 配送中心 0 29 圖 41 遺傳算法解決 VSPTW算法流程圖 這種染色體結構子路徑內部是有序的，若子路徑 1中點 1， 3相互交換位置，會使目標函數值改變；而子路徑之間是無序的，若子路徑 1和 2相互交換位置，卻不會改變目標函數的值；若子路徑倒轉，如 0460倒轉為 0640，也不會改變目標函數的值。 開始 輸入配送中心及需求點數據 輸入系統(tǒng)控制參數 輸出配送中心及需求點數據和系統(tǒng)控制參數 初始化運距數組 dd 遺傳代數 GEN=0 初始化染色體種 群 計算染色體適應度 輸出中間結果 輸出結果 滿足終止條件？ GEN=GEN+1 進行遺傳操作 結束 Y N 30 約束處理 對于 VSP這類約束較復雜的優(yōu)化問題，用遺傳算法求解時，需要對約束進行處理。一般有下面幾種方法： 問題的約束在染色體中表現出來，設計專門的遺傳算子，使染色體所表示的解在遺傳算法的求解過程中始終保持為可行解。 在編 碼的過程中不考慮約束，而在遺傳算法的計算過程中檢測得到的染色體相應的解是否可行，若可行，則放入下一代群體中，否則將其舍棄。 采用懲罰的方法來處理約束。如果一個染色體對應的解違反了某個約束，試其違反程度給予一定懲罰，使其具有較小的適應度。這樣，一些不可行解也有可能進入群體，以保證群體中染色體的數目，使遺傳算法得以