【正文】 析 ...................................................................... 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)，與此同時，相當部分的大型運輸、倉儲和航運企業(yè)開始轉(zhuǎn)向第三方物流經(jīng)營。本文針對客戶提出時間約束這 一配送需求，對有時間窗的物流配送車輛優(yōu)化調(diào)度問題（ VSPTW）進行數(shù)學(xué)分析，研究探索性能更強的解決 VSPTW的遺傳算法。 雖然 我國物流發(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) ”。國外將此類問題稱之為 Vehicle Scheduling Problem，簡稱為 VSP問題。 國外對物流配送車輛優(yōu)化調(diào)度問題作了大量而深入的研究，例如早在 1983 年 Bodin, Golden 等人在他們的綜述文章中就列舉了 700余篇文獻。李大為等 (1998)以 TSP的最近距離啟發(fā)式為基礎(chǔ)，通過設(shè)置評價函數(shù)來處理時間窗約束，求解了簡單的 VSP。 目前，問題的形式己有很大發(fā)展，該問題以不僅僅局限于汽車運輸領(lǐng)域，在水運、航空、通訊、電力、工業(yè)管理、計算機應(yīng)用等領(lǐng)域也有一定的應(yīng)用，其算法己用于航空乘務(wù)員輪班安排、輪船公司運送貨物經(jīng)過港口與貨物安排的優(yōu)化設(shè)計、交通車線路安排、生產(chǎn)系統(tǒng)中的計劃與控制等多種組合優(yōu)化問題。 按車輛載貨狀況分，有滿載問題 (貨運量不小于車輛容量，完成一項任 務(wù)需要不只一輛車 )和非滿載問題 (貨運量小于車輛容量，多項任務(wù)用一輛車 )。 按優(yōu)化目標數(shù)來分，有單目標問題和多目標問題。 常用的基本理論和方法有：分枝界定法、割平面法、線性規(guī)劃法、動態(tài)規(guī)劃法、匹配理論、對偶理論、組合理論、線搜索技術(shù)、列生成技術(shù)、概率分析、統(tǒng)計分析、最差情況分析、經(jīng)驗分析等。精確算法的計算量一般隨著問題規(guī)模的增大呈指數(shù)增長。該類算法的每一步，把當前的線路構(gòu)形（很可能是不可行的）跟另外的構(gòu)形（也可能是不可行的）進行比較并加以改進，后者是根據(jù)某個判別函數(shù)（例如總費用）會產(chǎn)生最大限度的節(jié)約的構(gòu)形，或是 以最小代價把一個在當前構(gòu)形上的需求對象插入進來的構(gòu)形 (Clarke和 Wright， 1964； Mole 和 Jamesson， 1976； Paessens， 1988； Altinkemer 和 Gavish， 1991；Desrochers 和 Verhoog， 1989)。 在兩階段法求解過程中，常常采用交互式優(yōu)化技術(shù)，把人的主觀能動作用結(jié)合到問題的求解過程中，其主要思想是：有經(jīng)驗的決策者具有對結(jié)果和參數(shù)的某種判斷能力，并且根據(jù)知識直感，把主觀的估計加到優(yōu)化模型中去。基于啟發(fā)式的并行算法和一些稱為亞啟發(fā)式算法 (Metaheuristics、 Laporte 和 Osman， 1996)的方法都屬于此類 (Cesar Rego， 1998； Gendrea、 Laporte 和 Potvin， 1994)［８ ］ 。這種情況下，貨運量總數(shù)不超過車輛容量的任務(wù)可用一輛車來完成。 （ 2）集貨和送貨一體化的車輛優(yōu)化調(diào)度 每一項貨運任務(wù)都有自己的集貨點和送貨點，各項任務(wù)需要的車輛數(shù)不一致，這時需要對車輛進行優(yōu)化調(diào)度，確定行車路線。因此，在配送運輸上，時間因素是十分重要的。 9 第 2 章 有時間窗的車輛優(yōu)化調(diào)度問題 (VSPTW) 時間窗的定義 VSPTW問題是傳統(tǒng)的車輛優(yōu)化調(diào)度問題加上時間窗約束，時間窗約束可分為硬時間窗、軟時間窗與混合型時間窗。 圖 21 硬時間窗約束示意圖 軟時間窗 (Soft Time Windows)：指配送車輛如果無法將貨物在特定的時段 (如圖22的 ? ?le, )內(nèi)送到顧客手中， 則必須按照違反時間的長短施以一定的罰金或其它懲罰法則。 圖 23 混合型時間窗約束示意圖 e l t ??tP M ??tP e l t M a b 11 VSPTW 問題的結(jié)構(gòu) 時間窗約束的車輛優(yōu)化調(diào)度問題是在傳統(tǒng)的車輛優(yōu)化調(diào)度問題的基礎(chǔ)上再加入顧客的時間窗約 束，所以該問題包含以下三項關(guān)鍵問題： 巡回 (Routing)問題 一般車輛優(yōu)化調(diào)度問題中的配送車輛由配送中心出發(fā)后，必須完成其所指派客戶的配送，然后回到配送中心。 有時 間窗約束的車輛優(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)解。許多傳統(tǒng)優(yōu)化方法都是從搜索空間的單點出發(fā)，通過某些轉(zhuǎn)換 規(guī)則確定下一點。對于不同類型的優(yōu)化問題，傳統(tǒng)方法需要使用不同形式的輔助信息，沒有一種優(yōu)化方法能適應(yīng)各類問題的要求。 算法具有隱含的并行性。 與傳統(tǒng)方法相比，遺傳算法的優(yōu)越性主要表現(xiàn)在：首先，在遺傳算子的作用下，遺傳算法具有很強的搜索能力，能以很大的概率找到 問題的全局最優(yōu)解：其次，由于它固有的并行性，能有效地處理大規(guī)模的優(yōu)化問題。第二是隨機產(chǎn)生初始群體。當適應(yīng)度函數(shù)確定以后，復(fù)制是以適應(yīng)度函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰。 13 遺傳算法的基本流程如圖 31所示。目前在運籌學(xué)、機械優(yōu)化設(shè)計、電網(wǎng)設(shè)計、生產(chǎn)管理等應(yīng)用學(xué)科中都嘗試著用遺傳算法解決現(xiàn)實優(yōu)化計算問題。分類器 CS1是 Halland與 Keitman實現(xiàn)的第一個基于遺傳算法的機器學(xué)習(xí)系統(tǒng)。但在 VSP中的應(yīng)用才剛剛開始，已有文獻利用遺傳算法對 VSP 進行求解 (Berthold,1995。 編碼 將問題的解編碼為染色體是用遺傳算法解決各類問題的第一步，也是關(guān)鍵一步。下面是幾種常用的編碼方法。但也存在以下缺點： （ 1）相鄰整數(shù)的二進制編碼可能具有較大的 Hamming 距離。 （ 3）在求解多維高精度優(yōu)化問題時，二進制編碼將會非常長，從而降低算法效率。 Gray 編碼可以有效的解決二進制編碼的 Hamming 懸崖缺陷，但由于長度與二進制編碼相同，因此同樣存在二進制編碼中（ 2）、（ 3）兩項缺點。 排列編碼 對于某些問題，排列是其解的一種自然的表示。 適應(yīng)度函數(shù) 在遺傳算法中，適應(yīng)度是用來區(qū)分群體中個體（問題的解）的好壞，適應(yīng)度越大的個體越好，反之，適應(yīng)度越小的個體越差。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而定。 目前操作的群體中，最大的目標函數(shù)值。因此，個體繁殖數(shù)量的調(diào)節(jié)在遺傳操作中就顯得比較重要。在另一方面，在搜索過程的后期，雖然群體中存在足夠的多樣性，但群體的平均適應(yīng) 度可能會接近群體的最優(yōu)適應(yīng)度。目前，主要的定標技術(shù)歸納成表 31。此方法在計算上的步驟上比較簡易，但 k的設(shè)定與問題的類型具有相關(guān)性。 由于染色體復(fù)制后，當前群體中最佳染色體可能喪失繁殖能力，為了提高遺傳算法的性能，可在使用輪盤賭的基礎(chǔ)上采用最佳保留策略。采用二進制編碼、實數(shù)編碼和自然數(shù)編碼時所采用的交叉策略不一樣，其中自然數(shù)編碼所采用的交叉策略有如下幾種： 部分映射交叉 (PMX ) PMX可看作二進制串的兩點或多點交叉在自然數(shù)編碼中的擴展，并應(yīng)用修復(fù)程序來解決簡單兩點交叉引起的非法性。 過程說明見圖 33，同樣步驟可用同一對雙親產(chǎn)生另一個后代 [7 9 3 4 5 6 1 2 8]。說明見圖 35。目前發(fā)展的主要變異算子如表 32所示。 雙親 1： 5 4 6 3 8 7 2 9 1 原始后代： 4 * * 1 8 9 * * * 雙親 2： 1 2 3 4 9 8 7 6 5 后代： 4 2 3 1 8 9 7 6 5 選擇位置 22 圖 36 反轉(zhuǎn)變異的說明 插入變異 隨機地選擇一個城市，并將它插入到一個隨機的位置中 。這里說明一下2— 交換和 3— 交換。為了選擇合適的群體規(guī)模 n、交叉率 cp 、變異率 mp ，許多學(xué)者進行了研究。建議的最優(yōu)參數(shù)范圍是30~20?n , ~?cp , ~?mp 。目前許多學(xué)者認識到這些參數(shù)需要隨著遺傳進程而自適應(yīng)變化，這種有自組織性能的遺傳算法具有更強的魯棒性、全局收斂性和計算效率 ［９］［１０］ 。該問題屬于組合優(yōu)化領(lǐng)域的 NP 難題 ［１１］ ，本小組嘗試使用遺傳算法求得該類問題的最優(yōu)解或近似最優(yōu)解。求滿足貨運需求和車輛載重量的費用最小的車輛行使線路。 有時間窗的 VSP 則是在一般車輛優(yōu)化調(diào)度問題的基礎(chǔ)上要求每項任務(wù) i 在時間范圍? ?ii ba, 內(nèi)完成，并可根據(jù)時間約束的嚴格與否，分為軟時間窗和硬時間窗的 VSP。為了使線路安排具有一定的彈性，可預(yù)先估計一個完成任務(wù)所需要的車輛數(shù) m： 11 ????????????????aqgmnii (41) 其中， [ ]表示不大于括號內(nèi)數(shù)字的 最大整數(shù)， ? ?10 ??aa 是對裝車或卸車的復(fù)雜性程度及約束多少的估計，一般來講，裝 (卸 )車越復(fù)雜，約束越多， a 應(yīng)越小，表示一輛車所能承載的貨物量越小。 得到車輛優(yōu)化調(diào)度數(shù)學(xué)模型如下： ? ?? ?? ?? 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 模型 設(shè)完成任務(wù) i 需要的時間 (裝貨或卸貨 )表示為 iT ，又設(shè)任務(wù) i 的開始時間需在一定的時間范圍 ? ?ii ba, 內(nèi)，其中 ia 為任務(wù) i的允許最早開始時間，為任務(wù) i的允許最遲開始時間。 以 is 表示車輛到達點 i的時間，一般應(yīng)有以下關(guān)系式： 00?s iii bsa ?? ni ,2,1 ??