【正文】 而不是確定的精確規(guī)則。 算法具有隱含的并行性。 算法具有極強(qiáng)的容錯(cuò)能力。對(duì)于不同類型的優(yōu)化問題，傳統(tǒng)方法需要使用不同形式的輔助信息，沒有一種優(yōu)化方法能適應(yīng)各類問題的要求。遺傳算法是以點(diǎn)集開始的尋優(yōu)過程，初始群體是隨機(jī)地在搜索空間中選取的，覆蓋面大，利于全局尋優(yōu)。許多傳統(tǒng)優(yōu)化方法都是從搜索空間的單點(diǎn)出發(fā)，通過某些轉(zhuǎn)換 規(guī)則確定下一點(diǎn)。遺傳算法處理的對(duì)象是染色體，因而要求把所要優(yōu)化問題的基本參數(shù)轉(zhuǎn)化成一定長度的有限符號(hào)的染色體。 有時(shí) 間窗約束的車輛優(yōu)化調(diào)度問題可以用圖 24表示： 圖 24 VSPTW問題的結(jié)構(gòu) 第 3 章 遺傳算法基本理論 遺傳算法的基本原理 遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，它由美國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ì)的旅行商問題 一般車輛優(yōu)化調(diào)度問題 有時(shí)間窗約束的車 輛優(yōu)化調(diào)度問題 加入車輛裝載能力約束 加入時(shí)間窗約束 12 個(gè)數(shù)，使適應(yīng)度越大的解存活的機(jī)會(huì)越大；也就是“適者生存”的原則來選擇隨機(jī)的值域，最后留下的就是最優(yōu)解。 裝載 (Loading)問題 因?yàn)槊恳慌渌蛙囕v都有規(guī)定負(fù)荷的載重量限制，所以在 TSP問題中加入配送車輛的裝載量限制，此時(shí)的問題成為一般車輛優(yōu)化調(diào)度問題。 圖 23 混合型時(shí)間窗約束示意圖 e l t ??tP M ??tP e l t M a b 11 VSPTW 問題的結(jié)構(gòu) 時(shí)間窗約束的車輛優(yōu)化調(diào)度問題是在傳統(tǒng)的車輛優(yōu)化調(diào)度問題的基礎(chǔ)上再加入顧客的時(shí)間窗約 束，所以該問題包含以下三項(xiàng)關(guān)鍵問題： 巡回 (Routing)問題 一般車輛優(yōu)化調(diào)度問題中的配送車輛由配送中心出發(fā)后，必須完成其所指派客戶的配送，然后回到配送中心。 t e l ??tP M 10 圖 22 軟時(shí)間窗約束示意圖 混合型時(shí)間窗 (Mixed Time Windows )：系統(tǒng)中有些顧客屬于硬時(shí)間窗，有些則屬于軟時(shí)間窗；同一顧客，往往軟、硬兩種時(shí)間窗混合使用。 圖 21 硬時(shí)間窗約束示意圖 軟時(shí)間窗 (Soft Time Windows)：指配送車輛如果無法將貨物在特定的時(shí)段 (如圖22的 ? ?le, )內(nèi)送到顧客手中， 則必須按照違反時(shí)間的長短施以一定的罰金或其它懲罰法則。圖 21為一懲罰函數(shù) (Penalty Function)當(dāng)貨品送達(dá)時(shí)間超出 ? ?le, 時(shí)，其懲罰值 ??tP 等于一個(gè)非常大的正值， 表示硬時(shí)間窗的限制。 9 第 2 章 有時(shí)間窗的車輛優(yōu)化調(diào)度問題 (VSPTW) 時(shí)間窗的定義 VSPTW問題是傳統(tǒng)的車輛優(yōu)化調(diào)度問題加上時(shí)間窗約束，時(shí)間窗約束可分為硬時(shí)間窗、軟時(shí)間窗與混合型時(shí)間窗。由于有時(shí)間窗的 VSP是典型的NP— 難題，會(huì)隨著節(jié)點(diǎn)的增加出現(xiàn)組合爆炸的現(xiàn)象，因 此求解的困難度及時(shí)效性會(huì)有影響。因此，在配送運(yùn)輸上，時(shí)間因素是十分重要的。 所謂時(shí)間窗口是指配送車輛或顧客希望服務(wù)或被服務(wù)的時(shí)間范 圍。 （ 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ōu)化調(diào)度問題 當(dāng)貨主的貨物量不小于車輛容量時(shí)，執(zhí)行每項(xiàng)任務(wù)需要的車輛可能不只一輛，車輛為完成任務(wù)，需 滿載運(yùn)行。這種情況下，貨運(yùn)量總數(shù)不超過車輛容量的任務(wù)可用一輛車來完成。 貨運(yùn)車輛優(yōu)化調(diào)度問題的分類 根據(jù)任務(wù)的性質(zhì)將貨物運(yùn)輸分成以下幾類： 非滿載車輛優(yōu)化調(diào)度問題 當(dāng)貨物量小于車輛容量時(shí)，用一輛車執(zhí)行任務(wù)，存在不滿載運(yùn)行情況，調(diào)度時(shí)可安排一 7 輛車執(zhí)行多項(xiàng)任務(wù)，即在一輛車上同時(shí)載有不同貨主的貨物?；趩l(fā)式的并行算法和一些稱為亞啟發(fā)式算法 (Metaheuristics、 Laporte 和 Osman， 1996)的方法都屬于此類 (Cesar Rego， 1998； Gendrea、 Laporte 和 Potvin， 1994)［８ ］ 。 （ 3）不完全優(yōu)化算法 (Inplete Optimization Algorithm) 以 啟發(fā)式準(zhǔn)則來代替精確算法中的決策準(zhǔn)則，以縮小解搜索的空間 (Toth、 Christofides和 Mingozzi， 1979 等 )。 在兩階段法求解過程中，常常采用交互式優(yōu)化技術(shù)，把人的主觀能動(dòng)作用結(jié)合到問題的求解過程中，其主要思想是：有經(jīng)驗(yàn)的決策者具有對(duì)結(jié)果和參數(shù)的某種判斷能力，并且根據(jù)知識(shí)直感，把主觀的估計(jì)加到優(yōu)化模型中去。 （ 2）階段法 (Twophase Algorithm) 兩階段法是： 第一階段得到一可行解，第二階段通過對(duì)點(diǎn)的調(diào)整，在始終保持解可行的情況下，力圖向最優(yōu)目標(biāo)靠近，每一步都產(chǎn)生另一個(gè)可行解以代替原來的解，使目標(biāo)函數(shù)值得以改進(jìn)，一直繼續(xù)到不能再改進(jìn)目標(biāo)函數(shù)值為止 (Gillett 和 Miller， 1974； Christofids、Mingozzi和 Toth， 1979； Fisher 和 Jaikumar， 1981； Renaud、 Boctor 和 Laporte， 1996； Bramel和 SimchiLevi， 1995)。該類算法的每一步，把當(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)來的構(gòu)形 (Clarke和 Wright， 1964； Mole 和 Jamesson， 1976； Paessens， 1988； Altinkemer 和 Gavish， 1991；Desrochers 和 Verhoog， 1989)。該方法在解題時(shí)可減少搜尋的次數(shù)，所以是一種容易且快速的求解困難問題的算法。精確算法的計(jì)算量一般隨著問題規(guī)模的增大呈指數(shù)增長。 人機(jī)互動(dòng)法 此方法結(jié)合人類決策與計(jì)算機(jī)計(jì)算能力，在求解的過程中，通過高度的人機(jī)交互模式，結(jié)合專家的決策信息，并據(jù)以計(jì)算出結(jié)果；優(yōu)點(diǎn)是尋優(yōu)的過程中，決策者可以很清楚地看到各約束條件之間的替代關(guān)系，以及 參數(shù)變化可能導(dǎo)致的成本變化。 常用的基本理論和方法有：分枝界定法、割平面法、線性規(guī)劃法、動(dòng)態(tài)規(guī)劃法、匹配理論、對(duì)偶理論、組合理論、線搜索技術(shù)、列生成技術(shù)、概率分析、統(tǒng)計(jì)分析、最差情況分析、經(jīng)驗(yàn)分析等。 基本問題與基本方法 為簡化貨運(yùn)車輛優(yōu) 化調(diào)度問題的求解，常常應(yīng)用一些技術(shù)將問題分解或轉(zhuǎn)化成一個(gè)或幾個(gè)已經(jīng)研究過的基本問題，再用相應(yīng)比較成熟的基本理論和方法，以得到原貨運(yùn)車輛優(yōu)化調(diào)度問題的最優(yōu)解或滿意解。 按優(yōu)化目標(biāo)數(shù)來分，有單目標(biāo)問題和多目標(biāo)問題。 按車輛類型數(shù)分，有單車型問題 (所有車輛容量相同 )和多車型問題 (執(zhí)行任務(wù)的車輛容 5 量不完全相同 )。 按車輛載貨狀況分，有滿載問題 (貨運(yùn)量不小于車輛容量，完成一項(xiàng)任 務(wù)需要不只一輛車 )和非滿載問題 (貨運(yùn)量小于車輛容量，多項(xiàng)任務(wù)用一輛車 )。 按任務(wù)特征分，有純裝問題或純卸題 (pure pick up or pure delivery, 車輛在所有任務(wù)點(diǎn)裝貨或卸貨，及集貨或送貨問題 ) 及裝卸混合問題 (bined pick up and delivery，每項(xiàng)任務(wù)有不同的裝貨點(diǎn)和卸貨點(diǎn)，即集貨、送貨一體化問題 )。 目前，問題的形式己有很大發(fā)展，該問題以不僅僅局限于汽車運(yùn)輸領(lǐng)域，在水運(yùn)、航空、通訊、電力、工業(yè)管理、計(jì)算機(jī)應(yīng)用等領(lǐng)域也有一定的應(yīng)用，其算法己用于航空乘務(wù)員輪班安排、輪船公司運(yùn)送貨物經(jīng)過港口與貨物安排的優(yōu)化設(shè)計(jì)、交通車線路安排、生產(chǎn)系統(tǒng)中的計(jì)劃與控制等多種組合優(yōu)化問題。遺傳算法和神經(jīng)網(wǎng)絡(luò)方法對(duì)簡單 TSP的求解取得了一定成果。李大為等 (1998)以 TSP的最近距離啟發(fā)式為基礎(chǔ)，通過設(shè)置評(píng)價(jià)函數(shù)來處理時(shí)間窗約束，求解了簡單的 VSP。該領(lǐng)域的代表人物有 Bodin， Christfids，Golden， Assad， Ball， Laporte， Rinnooy Kan， Lenstra， Desrosiers和 Desrochers等人［１］［３］ 。 國外對(duì)物流配送車輛優(yōu)化調(diào)度問題作了大量而深入的研究，例如早在 1983 年 Bodin, Golden 等人在他們的綜述文章中就列舉了 700余篇文獻(xiàn)。 圖 13 以物流中心為主的配送模式 1S 2S iS 1R 2R jR 供應(yīng)商（ S） 零售商（ R） 供應(yīng)商（ S） 零售商（ R） 1S 2S iS 1R 2R jR 物流 中心 4 物流配送車輛優(yōu)化調(diào)度的研究動(dòng)態(tài)和水平 問題的提出 物 流配送車輛優(yōu)化調(diào)度問題最早是由 Dantzig和 Ramser于 1959年首次提出，自此，很快引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科的專家與運(yùn)輸計(jì)劃制定者和管理者的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點(diǎn)問題。國外將此類問題稱之為 Vehicle Scheduling Problem，簡稱為 VSP問題。假設(shè)零售商與供應(yīng)商之間通過一個(gè)物流配送中心來配送，則只需 i+j 次配送，如圖 13所示，如此一來即可減少 (ij(i+j))的配送次數(shù)，當(dāng)供應(yīng)商與零售商數(shù)目越多，節(jié)省的配送次數(shù)也就會(huì)越多。 所謂“物流中心”，根據(jù)美國物流管理協(xié)會(huì) (The Council of Logistics Management, CLM)定義：“以適合顧客要求為目的，對(duì)原物料、在制品、制成品與其相關(guān)信息，從產(chǎn)地到消費(fèi)者的間的流程與保管，為求有效率且最小的機(jī)會(huì)成本，而進(jìn)行計(jì)劃、執(zhí)行、控制的場所(Depot) ”。但是在現(xiàn)代的配送系統(tǒng)中，零售商為了減少資金積壓及提供多樣化的商品，勢必要減少各種商品的存貨數(shù)量，而同時(shí)又必須考慮到提供最好的服務(wù)品質(zhì) (不允許缺 貨 )。配送的流程一般如下圖所示。我國國家標(biāo)準(zhǔn)《物流術(shù)語》中對(duì)配送的定義是：“在經(jīng)濟(jì)合理區(qū)域范圍內(nèi)，根據(jù)用戶要求，對(duì)物品進(jìn)行揀選、加工、包裝、分割、組配等作業(yè)，并按時(shí)送達(dá)指定地點(diǎn)的物流活動(dòng) ［７］ 。 雖然 我國物流發(fā)展 持 續(xù)加速，但與國民經(jīng)濟(jì)發(fā)展的要求 還 相差甚遠(yuǎn) ，這就要求我們對(duì)物流產(chǎn)業(yè)的各個(gè)環(huán)節(jié)進(jìn)行研究。 2 第 1 章 概 述 研究背景 隨著社會(huì)主義市場經(jīng)濟(jì)的發(fā)展， 在經(jīng)濟(jì)大循環(huán)中提高 經(jīng)濟(jì)運(yùn)作 效率 的物流對(duì)經(jīng)濟(jì)活動(dòng) 的影響日益明顯，越來越引起人們的重視。本文針對(duì)客戶提出時(shí)間約束這 一配送需求，對(duì)有時(shí)間窗的物流配送車輛優(yōu)化調(diào)度問題（ VSPTW）進(jìn)行數(shù)學(xué)分析，研究探索性能更強(qiáng)的解決 VSPTW的遺傳算法。物流配送開始在我國迅速興起發(fā)展起來，對(duì)物流配送的研究引起了國內(nèi)物流專家學(xué)者的廣泛關(guān)注。 關(guān)鍵詞 ：物流配送 車輛優(yōu)化調(diào)度 遺傳算法 時(shí)間窗 II Abstract Recent years, logistics, taken as third profit resource”, has been developing rapidly. In the developed mercial society, traditional VSP algorithm have been unable to meet the requirement that Quick Response to customer demand had brought forth, then the conception of Time Window has e into being. The vehiclescheduling problem with time window is also a NPhard problem being more plicated than VSP. This text has been researched to the vehiclescheduling problem with time window on the basis of researched to logistic vehicle scheduling problem. And it has explained the basic theory of geic algorithm. On the VSP with time window, while the restraints of capacity and time windows are changed into object restraints, a mathematic model is established. We use techn