【正文】 ........................................... 4 基本問題與基本方法 ......................................................... 5 算法 ................................................................................ 5 貨運車輛優(yōu)化調(diào)度問題的分類 ........................................... 6 研究的意義 .............................................................................. 7 研究的范圍 .............................................................................. 7 第 2 章 有時間窗的車輛優(yōu)化調(diào)度問題 (VSPTW) ...................................... 9 時間窗的定義 ........................................................................... 9 VSPTW 問題的結(jié)構(gòu) ................................................................... 11 第 3 章 遺傳算法基本理論 .................................................................. 11 遺傳算法的基本原理 ............................................................... 11 遺傳算法的特點 ............................................................. 12 遺傳算法的基本步驟和處理流程 ...................................... 12 遺傳算法的應(yīng)用 ............................................................. 13 編碼 ...................................................................................... 14 二進制編碼 .................................................................... 14 Gray 編碼 ...................................................................... 15 實數(shù)向量編碼 ................................................................. 15 排列編碼 ....................................................................... 15 IV 適應(yīng)度函數(shù) ............................................................................ 15 目標(biāo)函數(shù)映射成適應(yīng)度函數(shù) ............................................. 16 適應(yīng)度定標(biāo) .................................................................... 16 遺傳算法的基因操作 ............................................................... 17 選擇算子 ....................................................................... 17 交叉算子 ....................................................................... 18 變異算子 ....................................................................... 21 遺傳算法控制參數(shù)設(shè)定 ............................................................ 24 第 4 章 遺傳算法求解有時間窗非滿載 VSP ........................................... 25 問題描述 ................................................................................ 25 數(shù)學(xué)模型 ................................................................................ 25 一般 VSP 模型 ................................................................. 25 有時間窗 VSP 模型 .......................................................... 27 算法設(shè)計 ................................................................................ 27 算法流程圖 .................................................................... 27 染色體結(jié)構(gòu) .................................................................... 27 約束處理 ....................................................................... 30 適應(yīng)度函數(shù) .................................................................... 31 初始種群 ....................................................................... 31 遺傳算子 ....................................................................... 31 控制參數(shù)和終止條件 ....................................................... 32 算法實現(xiàn) ................................................................................ 34 實驗及結(jié)果分析 ...................................................................... 34 控制參數(shù)選定 ................................................................. 34 實例實驗 ....................................................................... 38 實例數(shù)據(jù) ....................................................................... 38 實例數(shù)據(jù)分析 ................................................................. 38 結(jié) 論 .................................................................................................. 39 參考文獻 ............................................................................................. 41 謝 辭 .................................................................................................. 42 1 引 言 隨著市場經(jīng)濟的發(fā)展，大量經(jīng)營規(guī)模較大的制造企業(yè)和商業(yè)企業(yè)紛紛建立起配送中心向商品流通效率化發(fā)起挑戰(zhàn)，與此同時，相當(dāng)部分的大型運輸、倉儲和航運企業(yè)開始轉(zhuǎn)向第三方物流經(jīng)營。 雖然 我國物流發(fā)展 持 續(xù)加速，但與國民經(jīng)濟發(fā)展的要求 還 相差甚遠 ，這就要求我們對物流產(chǎn)業(yè)的各個環(huán)節(jié)進行研究。 所謂“物流中心”，根據(jù)美國物流管理協(xié)會 (The Council of Logistics Management, CLM)定義：“以適合顧客要求為目的，對原物料、在制品、制成品與其相關(guān)信息，從產(chǎn)地到消費者的間的流程與保管，為求有效率且最小的機會成本，而進行計劃、執(zhí)行、控制的場所(Depot) ”。 國外對物流配送車輛優(yōu)化調(diào)度問題作了大量而深入的研究，例如早在 1983 年 Bodin, Golden 等人在他們的綜述文章中就列舉了 700余篇文獻。 目前，問題的形式己有很大發(fā)展，該問題以不僅僅局限于汽車運輸領(lǐng)域，在水運、航空、通訊、電力、工業(yè)管理、計算機應(yīng)用等領(lǐng)域也有一定的應(yīng)用，其算法己用于航空乘務(wù)員輪班安排、輪船公司運送貨物經(jīng)過港口與貨物安排的優(yōu)化設(shè)計、交通車線路安排、生產(chǎn)系統(tǒng)中的計劃與控制等多種組合優(yōu)化問題。 按優(yōu)化目標(biāo)數(shù)來分，有單目標(biāo)問題和多目標(biāo)問題。精確算法的計算量一般隨著問題規(guī)模的增大呈指數(shù)增長。 在兩階段法求解過程中，常常采用交互式優(yōu)化技術(shù)，把人的主觀能動作用結(jié)合到問題的求解過程中，其主要思想是：有經(jīng)驗的決策者具有對結(jié)果和參數(shù)的某種判斷能力，并且根據(jù)知識直感，把主觀的估計加到優(yōu)化模型中去。這種情況下，貨運量總數(shù)不超過車輛容量的任務(wù)可用一輛車來完成。因此，在配送運輸上，時間因素是十分重要的。 圖 21 硬時間窗約束示意圖 軟時間窗 (Soft Time Windows)：指配送車輛如果無法將貨物在特定的時段 (如圖22的 ? ?le, )內(nèi)送到顧客手中， 則必須按照違反時間的長短施以一定的罰金或其它懲罰法則。 有時 間窗約束的車輛優(yōu)化調(diào)度問題可以用圖 24表示： 圖 24 VSPTW問題的結(jié)構(gòu) 第 3 章 遺傳算法基本理論 遺傳算法的基本原理 遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，它由美國Holland教授首先在《自然結(jié)合人工智能系統(tǒng)的適應(yīng)性》一書中提出，是利用生物進化的特性所發(fā)展的方法，由一群群體 (Population)以隨機配對產(chǎn)生下一代，利用交叉 (Crossover)及變異 (Mutation)等操作進行基因的進化，并經(jīng) 由選擇 (Selection)機能決定下一代相對的旅行商問題 一般車輛優(yōu)化調(diào)度問題 有時間窗約束的車 輛優(yōu)化調(diào)度問題 加入車輛裝載能力約束 加入時間窗約束 12 個數(shù)，使適應(yīng)度越大的解存活的機會越大；也就是“適者生存”的原則來選擇隨機的值域，最后留下的就是最優(yōu)解。對于不同類型的優(yōu)化問題，傳統(tǒng)方法需要使用不同形式的輔助信息，沒有一種優(yōu)化方法能適應(yīng)各類問題的要求。 與傳統(tǒng)方法相比，遺傳算法的優(yōu)越性主要表現(xiàn)在：首先，在遺傳算子的作用下，遺傳算法具有很強的搜索能力，能以很大的概率找到 問題的全局最優(yōu)解：其次，由于它固有的并行性，能有效地處理大規(guī)模的優(yōu)化問題。當(dāng)適應(yīng)度函數(shù)確定以后，復(fù)制是以適應(yīng)度函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰。目前在運籌學(xué)、機械優(yōu)化設(shè)計、電網(wǎng)設(shè)計、生產(chǎn)管理等應(yīng)用學(xué)科中都嘗試著用遺傳算法解決現(xiàn)實優(yōu)化計算問題。但在 VSP中的應(yīng)用才剛剛開始，已有文獻利用遺傳算法對 VSP 進行求解 (Berthold,1995。下面是幾種常用的編碼方法。 （ 3）在求解多維高精度優(yōu)化問題時，二進制編碼將會非常長，從而降低算法效率。 排列編碼 對于某些問題，排列是其解的一種自然的表示。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而定。因此，個體繁殖數(shù)量的調(diào)節(jié)在遺傳操作中就顯得比較重要。目前，主要的定標(biāo)技術(shù)歸納成表 31。 由于染色體復(fù)制后，當(dāng)前群體中最佳染色體可能喪失繁殖能力，為了提高遺傳算