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