【正文】 如果一個(gè)染色體對(duì)應(yīng)的解違反了某個(gè)約束，試其違反程度給予一定懲罰，使其具有較小的適應(yīng)度。 開(kāi)始 輸入配送中心及需求點(diǎn)數(shù)據(jù) 輸入系統(tǒng)控制參數(shù) 輸出配送中心及需求點(diǎn)數(shù)據(jù)和系統(tǒng)控制參數(shù) 初始化運(yùn)距數(shù)組 dd 遺傳代數(shù) GEN=0 初始化染色體種 群 計(jì)算染色體適應(yīng)度 輸出中間結(jié)果 輸出結(jié)果 滿足終止條件？ GEN=GEN+1 進(jìn)行遺傳操作 結(jié)束 Y N 30 約束處理 對(duì)于 VSP這類約束較復(fù)雜的優(yōu)化問(wèn)題，用遺傳算法求解時(shí)，需要對(duì)約束進(jìn)行處理。 染色體結(jié)構(gòu) 為提高效率，對(duì) VSP采用自然數(shù)編碼方式，即序數(shù)編碼。懲罰成本函數(shù)的設(shè)定一般以配送中心與顧客在商議之后所簽定的合同為主，但因?qū)嶋H上所簽定合同是為維護(hù)買(mǎi)賣雙方共同的利益，故考慮的因素相當(dāng)多。此問(wèn)題稱之為有時(shí)間窗的車輛優(yōu)化調(diào)度問(wèn)題。,1,0 ?? ?? ，第 k 輛車的行車路徑稱為第 k條子路徑，其中經(jīng)過(guò)的需求點(diǎn)數(shù)目為 kn ， kp 表示第 k 條子路徑中包含的 kn 個(gè)需求點(diǎn)組成的集合 ，其中的元素? ?nipki ,2,1 ?? 代表第 k 條子路徑中順序?yàn)?i 的需求點(diǎn)； )1(0, ?knkk pp 均表示配送中心，且有 0)1(0 ?? ?knkk pp。 26 一般來(lái)講，當(dāng)問(wèn)題的約束越多，組織線路就越難，一輛車所完成的滿足所有約束的任務(wù)就越少，這時(shí)，一輛車實(shí)際所能容納的任務(wù)量要小，而所用的車輛數(shù)可能要多。又如，若干廠家生產(chǎn)一些產(chǎn)品，需要運(yùn)到配送中心，車輛從配送中心出發(fā)，到各廠家去裝貨，裝滿貨后返回配送中心，在滿足 廠家發(fā)貨要求的情況下，按什么線路行駛，可使總費(fèi)用最小，即集貨車輛優(yōu)化調(diào)度。每個(gè)需求點(diǎn) (供貨點(diǎn) )的需求量 (供貨量 )已知，且都小于配送車輛的載重量；配送中心和各需求點(diǎn)中任意兩點(diǎn)間的運(yùn)距已知或可以推算出來(lái)；一個(gè)需求點(diǎn)的任務(wù) 只能由一輛車一次運(yùn)送完成；每個(gè)配送車輛從配送中心出發(fā)，完成運(yùn)送任務(wù)后返回配送中心。 有時(shí)間窗約束的車輛優(yōu)化調(diào)度問(wèn)題歸結(jié)為車輛優(yōu)化調(diào)度問(wèn)題 中的單車場(chǎng)、單車型、非滿載、多約束（含時(shí)間窗約束）、多目標(biāo)、車輛封閉的對(duì)點(diǎn)服務(wù)問(wèn)題。由于控制參數(shù)會(huì)相互影響，所以無(wú)法確定獨(dú)立的最佳參數(shù)值，但當(dāng)種群規(guī)模小時(shí)可選擇較大的交叉及變異率以防止過(guò)早收斂；當(dāng)群體規(guī)模大時(shí)可選擇較小交叉及變異率以節(jié)省運(yùn)算時(shí)間。一般，當(dāng)種群規(guī)模增大時(shí)，將有利于改善種群的多樣性，從而可能有利于使算法收斂到最優(yōu)解或最優(yōu)解附近。 圖 39 2— 交換變異的說(shuō)明 隨機(jī)選擇一個(gè)子巡回 5 4 3 9 8 1 7 6 2 插入到一個(gè)隨機(jī)位置 5 4 3 7 8 6 2 9 1 隨機(jī)選擇兩個(gè)位置 5 4 3 9 8 1 7 6 2 交換相應(yīng)的城市 5 4 6 9 8 1 7 3 2 24 圖 310 3— 交換變異的說(shuō)明 遺傳算法控制參數(shù)設(shè)定 遺傳算法中需要選擇的參數(shù)主要有染色體長(zhǎng)度 l 、群體規(guī)模 n、交叉率 cp 、變異率 mp等，這些參數(shù)對(duì) GA 性能影響很大。 隨機(jī)選擇子巡回 5 4 3 9 8 1 7 6 2 插入子巡回 5 4 3 7 8 1 9 2 6 隨機(jī)選擇一個(gè)城市 5 4 3 9 8 1 7 6 2 插入到一個(gè)隨機(jī)位置 5 4 3 9 8 2 1 7 6 23 圖 38 易位變異的說(shuō)明 k— 交換變異 k— 交換變異是解決 VSP 的一種局域?qū)?yōu)技術(shù)，即對(duì)初始可行路線的 k 條邊（或?。┻M(jìn)行交換，在初始可行解的鄰域內(nèi)逐步改進(jìn)方案，直到在鄰域內(nèi)不能改進(jìn)為止。說(shuō)明如圖 36所示。變異在遺傳算法中的作用是第二位的 ［３］［５］ 。 圖 34 基于位置交叉運(yùn)算的說(shuō)明 基于順序的交叉 是基于位置交叉的變型，其中一個(gè)雙親選定位置上的城市的順序強(qiáng)制被另一雙親相應(yīng)城市所代替。 順序交叉 (ox ) Step l：從第一雙親中隨機(jī)選擇一個(gè)子串； Step 2：將子串復(fù)制到一個(gè)空子串的相應(yīng)位置，產(chǎn)生一個(gè)原始后代； Step 3：刪去第二雙親子串已有的城市，得到原始后代需要的其他城市的順序； Step 4：按照這個(gè)城市順序，從左到右將這些城市定位到后代的空缺位置上。在 交叉算子之前需首先配對(duì)，目前采用的是隨機(jī)配對(duì)。適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的復(fù)制方法，它也叫輪盤(pán)賭復(fù)制法或蒙特卡羅復(fù)制，其具體步驟如下： Step l：對(duì)各個(gè)染色體 kv 計(jì)算適應(yīng)度 kf ； Step 2：計(jì)算種群中 n個(gè)染色體適應(yīng)度的和 ???nk kfF 1； Step 3：對(duì)各染色體 kv ，計(jì)算選擇概率 Ffp kk /? nk ,2,1 ?? ； Step 4：對(duì)各染色體 kv 計(jì)算累計(jì)概率 ???nj jk pq 1nk ,2,1 ?? 復(fù)制過(guò)程類似旋轉(zhuǎn)轉(zhuǎn)輪 n次，每次按如下方式選出一個(gè)染色體來(lái)構(gòu)造新的種群，具體過(guò)程為：在 ? ?1,0 區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù) r，若： 1qr? ，則選擇第一個(gè)染色體 1v ；否則選擇第 k個(gè)染色體 ? ?nkvk ?,2? ，使得 kk qrq ???1 成立。 級(jí)數(shù)定標(biāo) 將原來(lái)適應(yīng)度函數(shù)值以接近 1的次方來(lái)擴(kuò)大各個(gè)個(gè)體間的差異。 這種對(duì)適應(yīng)度的縮放調(diào)整稱為適應(yīng)度函數(shù)的定標(biāo)。在這種情況下，應(yīng)該縮小這個(gè)個(gè)體的適應(yīng)度，以降低這些超級(jí)個(gè)體的競(jìng)爭(zhēng)力，防止過(guò)早收斂。為了保證適應(yīng)度函數(shù)為非負(fù)，可以采用如下的轉(zhuǎn)化形式： ? ? ? ?轉(zhuǎn)換前轉(zhuǎn)換后 kkk fff /?? 適應(yīng)度定標(biāo) 在設(shè)計(jì)遺傳算法時(shí)，群體的規(guī)模一般在幾十至幾百，與實(shí)際物種的規(guī)模相差很遠(yuǎn)。 目前所出現(xiàn)最大的目標(biāo)函數(shù)值。改變?nèi)后w內(nèi)部結(jié)構(gòu)的操作都是通過(guò)適應(yīng)度加以控制。因此 n,3,2,1 ? 的全排列 ? ?n??? , 21 ? 就可以作為 TSP 的染色體。這樣，可以直接在解的表現(xiàn)型上操作，從而便于引入與問(wèn)題領(lǐng)域相關(guān)的啟發(fā)式信息，增加遺傳算法的搜索能力。 Gray 編碼的方法是首先對(duì)問(wèn)題的解進(jìn)行二進(jìn)制編碼，再將二進(jìn)制編碼轉(zhuǎn)換為相應(yīng)的Gray編碼，然后進(jìn)行遺 傳操作，當(dāng)進(jìn)行適應(yīng)度計(jì)算時(shí)，再將 Gray編碼轉(zhuǎn)換為相應(yīng)的二進(jìn)制編碼。若在一開(kāi)始就選取較高的精度，則串長(zhǎng)很大，也會(huì)降低算法的效率。二進(jìn)制編碼結(jié)構(gòu)簡(jiǎn)單，易于進(jìn)行交叉、變異等遺傳操作。設(shè)計(jì)優(yōu)良的編碼方案是遺傳算法的應(yīng)用難點(diǎn)之一。有專家斷言遺傳算法是用來(lái)解決NP完全問(wèn)題和 NP難題的趨勢(shì) ［８］ 。 近些年來(lái)，人們?cè)谟眠z傳算法解決現(xiàn)實(shí)中的各種組合優(yōu)化問(wèn)題上進(jìn)行了探索，如在生產(chǎn)調(diào)度問(wèn)題中的應(yīng)用、對(duì)一般 TSP (Traveling Salesman Problem,旅行商問(wèn)題 )問(wèn)題的求解都取得了一些成果 (Oliver和 Smith, 1989:Fogel, 1993 )。遺傳算法從其開(kāi)始就與機(jī)器學(xué)習(xí)有著密切的聯(lián)系。對(duì)于復(fù)雜的函數(shù)優(yōu)化問(wèn)題 (如非線性、不連續(xù)、多峰 值函數(shù)的優(yōu)化等 )和組合優(yōu)化問(wèn)題 (如 VSP, TSP,01 背包問(wèn)題、工作計(jì)劃問(wèn)題 確定表示問(wèn)題解答的染色體（編碼） 初始化染色體種群 計(jì)算每個(gè)染色體的適應(yīng)度 滿足終止條件？ 根據(jù)適應(yīng)度選擇串進(jìn)行復(fù)制 交叉 變異 輸出最優(yōu)解 否 是 14 制定等 )都有廣闊的發(fā)展前景。子代的產(chǎn)生是一個(gè)生殖過(guò)程，它產(chǎn)生了一個(gè)新解；最后是變異，新解產(chǎn)生過(guò)程中可能產(chǎn)生基因變異，變異使某些解的編碼發(fā)生變化，使解具有更大的遍歷性。適應(yīng)度函數(shù)基本上依據(jù)問(wèn)題的目標(biāo)函數(shù)而定，是反映染色體優(yōu)劣的 唯一指標(biāo)，遺傳算法就是要尋得適應(yīng)度最大的染色體。實(shí)際問(wèn)題的染色體有多種編碼方式，染色體編碼方式的選取應(yīng)盡可能的符合問(wèn)題約束，否則將影響計(jì)算效率。復(fù)制體現(xiàn)了向最優(yōu)解的逼近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過(guò)選擇、交叉、變異操作能迅速 排除與最優(yōu)解相差極大的染色體。 遺傳算法在求解時(shí)只使用適應(yīng)度函數(shù)的信息，而不使用導(dǎo)數(shù)及其他輔助信息。 遺傳算法是從初始群體開(kāi)始搜索的，而不是從單點(diǎn)開(kāi)始搜索的。 行程安排 (Scheduling)問(wèn)題 一般車輛優(yōu)化調(diào)度問(wèn)題再加入時(shí)間窗約束，則必須考慮到達(dá)各顧客的先后順序，也就是行程安排問(wèn)題。在實(shí)際的物流配送中，配送車輛如果能在最佳時(shí)段 (如圖 23 中的 ? ?le, 內(nèi)將貨物送到顧客處，則不處罰；若在圖 23 中的（ ? ?ea, 或 ? ?bl, ）時(shí)段內(nèi)才送達(dá)，則顧客的滿意度降低 (轉(zhuǎn)化為懲罰函數(shù) )，而且顧客不接受上述兩個(gè)時(shí)段以外的時(shí)間 （ ? ?a,?? 或 ? ??,b ）收貨。 Desrochers (1988)曾指出硬時(shí)間窗寬度會(huì)影響尋優(yōu)程序，并提出時(shí)間窗寬度評(píng)價(jià)指標(biāo)，時(shí)間窗越寬則 VSPTW 問(wèn)題越接近路線安排 (Routing)問(wèn)題，越窄則越近似行程安排(Scheduling)問(wèn)題。 研究的范圍 由于有時(shí)間窗約束的車輛優(yōu)化調(diào)度問(wèn)題所牽涉的因素相當(dāng)多，本研究?jī)H針對(duì)具有普遍性的物流中心予以探討，就研究范圍與假設(shè)界定如下： 僅考慮區(qū)位己知的單一物流配送中心和供應(yīng)商； 物流配送中心無(wú)缺貨的可能，而且商品種類單一； 物流配送中心已知顧客的基本配送資料 (需求量、地理位置、時(shí)間窗約束等 )； 8 物流配送中心擁有足夠數(shù)量的同類型配送車輛，即每輛車的載重量、時(shí)速相同。由于消費(fèi)者需求趨于多樣化，對(duì)送貨時(shí)間的要求日趨嚴(yán)格，尤其是運(yùn)送有時(shí)效性的商品，例如海鮮、花卉、蔬菜、水果等講究新鮮度的貨物，除了因缺貨造成的機(jī)會(huì)成本的損失外，由于配送不及時(shí)也會(huì)造成貨物價(jià)值的大大降低。根據(jù)任務(wù)特征可分為以下兩類： （ 1）集貨或送貨的車輛優(yōu)化調(diào)度 載貨車輛由車場(chǎng)出發(fā)到幾個(gè)集貨點(diǎn)裝貨后返回車場(chǎng)（僅有裝貨），或是車輛出發(fā)到幾個(gè)送貨點(diǎn)卸貨（僅有卸貨）后返回車場(chǎng)。該類問(wèn)題根據(jù)任務(wù)特征又分 為以下兩類： （ 1）集貨或送貨的車輛優(yōu)化調(diào)度 所有任務(wù)全是集貨點(diǎn)或全是送貨點(diǎn)，車輛空車從車場(chǎng)出發(fā)，去各貨主處裝滿貨后返回車場(chǎng)。 （ 4）改進(jìn)算法 (Improvement Algorithm) 從一個(gè)初始解開(kāi)始，通過(guò)對(duì)當(dāng)前的解進(jìn)行反復(fù)地局部擾亂 (Perturbations)以達(dá)到較好的解。一般第一階段常用構(gòu)造算法，在第二階段常用的改進(jìn)技術(shù)有 2opt(Lin，1965)、 3opt(Lin Kernighan， 1973)和 Oropt(Or， 1976)交換法，這是一種在解的鄰域中搜索，對(duì)初始解進(jìn)行某種程度優(yōu)化的算法，以改進(jìn)初始解。目前已提 6 出的啟發(fā)式算法很多，按 Cesar Rego 的分類法有以下四類： （ 1）算法 (Constructive Algorithm) 根據(jù)一些準(zhǔn)則，每一次將一個(gè)不在線路上的點(diǎn)增加進(jìn)線路，直到所有的點(diǎn)都被安排進(jìn)線路為止。 精確解法 (Exact procedures ) 精確解法指可求出最優(yōu)解的算法，精確解法主要有： 分枝界定法 (Branch and Bound Approach)、割平面法 (Cutting Planes Approach)、網(wǎng)絡(luò)流算法 (Network Flow Approach)、動(dòng)態(tài)規(guī)劃方法 (Dynamic Programming Approach)。 常用的基本問(wèn)題有：旅行商問(wèn)題、分派問(wèn)題、運(yùn)輸問(wèn)題、背包問(wèn)題最短路問(wèn)題、最小費(fèi)用流問(wèn)題、中國(guó)郵路問(wèn)題等。 按車輛對(duì)車場(chǎng)的所屬關(guān)系分，有車輛開(kāi)放問(wèn)題 (車輛可以不返回其發(fā)出車場(chǎng) )和車輛封閉問(wèn)題 (車輛必須返回其發(fā)出車場(chǎng) )。 按任務(wù)性質(zhì)分，有對(duì)弧服務(wù)問(wèn)題 (如中國(guó)郵遞員問(wèn)題 )和對(duì)點(diǎn)服務(wù)問(wèn)題 (如旅行商問(wèn)題 )以及混合服務(wù)問(wèn)題 (如交通車線路安排問(wèn)題 )。蔡延光等 (1998)應(yīng)用并行表搜索法和模擬退火法針對(duì)簡(jiǎn)單情形對(duì)滿載問(wèn)題進(jìn)行了求解 ［３］［５］ 。 國(guó)內(nèi)對(duì)物流配送車輛優(yōu)化調(diào)度問(wèn)題的研究相當(dāng)少，主要研究對(duì)象是旅行商問(wèn)題(Traveling Salesman Problem，簡(jiǎn)稱 TSP)、中國(guó)郵遞員問(wèn)題 (Chinese Postman Problem ,簡(jiǎn)稱 CPP)、有向中國(guó)郵遞員問(wèn)題 (Directed Chinese Postman Problem，簡(jiǎn)稱 DCPP)等，系統(tǒng)性研究還尚未見(jiàn)到。各學(xué)科專家對(duì)該問(wèn)題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，取得了很大的進(jìn)展。 3B 2B 1B 用戶 工廠 1A 2A 3A 進(jìn)貨 送貨 集貨 存儲(chǔ) 配貨 車輛 配裝 3 圖 12 傳統(tǒng)的物流配送模式 物流中心配送作