車輛調度與優(yōu)化

物流配送車輛調度問題是指：在給定運輸任務的條件下，如何派車、組織循環(huán)運輸，使空駛里程最少，運輸成本最低。現在我國大多數的物流公司運輸資源分派不均、配送路線安排不合理、運力資源浪費嚴重，而缺少完善的物流配送車輛調度優(yōu)化方案是造成此現象的重要因素之一。因此對物流配送車輛調度問題的研究含有重要的現實意義?，F在對單車場、封閉式物流配送車輛調度問題研究較多，而對多車場開放式物流配送車輛調度問題研究較少，但是多車場開放式物流配送車輛調度問題有很強的應用背景。本文針對此問題，建立了一種靈活的多目的組合優(yōu)化模型，設計了適合多車場開放式車輛途徑問題的通用染色體編碼方案，并對遺傳算法中的交叉變異操作做了具體闡明。此模型能夠方便的增減優(yōu)化目的值，并通過測試用例驗證了本文設計的優(yōu)化模型和遺傳算法在解決多車場多目的開放式物流配送車輛調度問題中的可行性。自動化立體倉庫出庫端車輛調度方略的設計是物流配送車輛調度中的一種核心問題，好的調度方略能夠大大縮短出庫端的配貨時間。為此本文引入動態(tài)優(yōu)先級理論，并運用該理論對大型AS/RS出庫口車輛調度問題進行了進一步研究與分析，提出了基于動態(tài)優(yōu)先級的AS/RS出庫端車輛調度方略，并開發(fā)了對應的AS/RS出庫口發(fā)貨資源監(jiān)控系統(tǒng)，即AS/RS出庫口車輛調度系統(tǒng)，優(yōu)化了AS/RS出庫端車輛調度方略，大大提高了物流配送當中的配貨效率。本文建立的多目的組合優(yōu)化模型以及設計的遺傳算法求解方案，能夠有效的縮減物流配送中的送貨時間；設計的AS/RS出庫端車輛調度優(yōu)化方略及開發(fā)的AS/RS出庫端車輛調度系統(tǒng)，能夠有效縮減車輛在出庫端的配貨時間。本文對以上兩種物流配送中的車輛調度問題進行研究，大大提高了物流配送效率、減少了物流配送成本。核心詞：物流配送；車輛調度；多目的組合優(yōu)化；遺傳算法第一章緒論課題背景物流(Logistics)：指在適宜時間，將適宜的物品以適宜的數量精確地送到顧客手中，它是供應鏈中最重要的構成部分。普通意義上是指在生產和生活中所涉及的多個物質實體由供應方向需求方的物理性轉移過程。這一概念將物流定義在有用的物、供方、需方等幾個基本因素之上。也就是說，我們普通所指的物流是指人們在生產和生活中發(fā)生的故意義的物流行為。整個物流過程是一種物理過程，只變化時間和空間的狀態(tài)，不變化其使用價值。其中，時間狀態(tài)的變化稱之為倉儲、流通加工等活動，空間狀態(tài)的變化稱之為運輸、搬倒等活動。物流配送是物流系統(tǒng)中的一種重要環(huán)節(jié)，它是指按客戶的訂貨規(guī)定，在物流中心進行分貨、配工作，并將配好的貨品及時送交收貨人的物流活動。配送成本直接關系到物流公司和部門的效益，現在我國的大多數的物流公司運輸資源分派不均、配送路線安排不合理、運力資源浪費嚴重,根據中國倉儲協(xié)會對146個公司的調查顯示，用于運輸的費用占整個物流費用的比例分別為：在生產公司原料物流中占58%，在生產公司成品物流中占73%，在商業(yè)物流中占52%。因此物流配送車輛調度方案的合理優(yōu)化，對于整個物流運輸速度、成本、效益的影響至關重要。運輸是指“物”的長距離的移動，任何跨越空間的物質實體的流動，都可稱為運輸。運輸是物流的中心環(huán)節(jié)之一，被稱為國民經濟的動脈和當代產業(yè)的支柱，從社會經濟的角度講，運輸功效的發(fā)揮，縮小了物質交流的空間，擴大了社會經濟活動的范疇并實現在此范疇內價值的平均化、合理化。在社會經濟的發(fā)展中，運輸的重要性己經被人們所確認，成為國民經濟的命脈。從物流系統(tǒng)的觀點來看，運輸作業(yè)的核心因素涉及運輸成本和運輸速度兩個方面。運輸成本：是指為兩個地理位置的運輸所支付的款項，以及管理和維持轉移中存貨的有關費用，應采用能把系統(tǒng)總成本減少到最低程度的運輸方式。運輸速度：是指為完畢特定的運輸作業(yè)所需耗費的時間。運輸速度和成本的關系，重要體現在下列兩個方面：首先，運輸商提供的服務越快速，實際需要收取的費用也就越高。另首先，運輸服務越快，轉移中的存貨就越少，可運用的運輸間隔時間越短。因此在選擇最合理的運輸方式時，至關重要的問題就是如何平衡其服務的速度和成本。運輸重要目的就是要以最低的時間、財務和環(huán)境資源成本，將產品從原產地轉移到規(guī)定地點。同時，產品轉移所采用的方式必須能滿足顧客有關交付推行和裝運信息的可得性等方面的規(guī)定。因此在物流系統(tǒng)中，必須精確地維持運輸成本和服務質量之間的平衡。低成本運輸和高質量服務是令人滿意的。物流配送車輛調度就是研究如何合理運輸的問題，所謂合理運輸就是在實現物資產品實體從物流中心至消費地轉移的過程中，充足有效地運用多個運輸工具的運輸能力，以最少的人、財、物消耗，及時、快速、按質、按量和安全的完畢運輸任務。其標志是：運輸距離最短、運輸環(huán)節(jié)最少、運輸時間最短和運輸費用最省。據統(tǒng)計運輸費約占整個物流費用的40%，占銷售收入的%。物流配送車輛調度問題就是指在給定運輸任務的條件下，如何派車、組織循環(huán)運輸，使空駛里程最少，運輸成本最低。車輛調度是物流管理最重要的部分，對的合理的調度能夠有效減少車輛的空駛率，實現合理途徑運輸，從而有效減少運輸成本，節(jié)省運輸時間，提高經濟效益。課題研究的意義物流產業(yè)的發(fā)展，將從整體上變化經濟運行的方式，提高經濟運行效率，對增強國際競爭力將起到巨大的推動作用。我國國民經濟的發(fā)展呼喚物流的進一步發(fā)展，對物流的發(fā)展規(guī)定以下：(1)減少流通成本在GDP中的比重：在我國現在工業(yè)公司生產中，直接勞動成本占總成本的比重不到10％，而物流費用占商品總成本的比重，從賬面反映約為40％，全社會物流費用支出約占GDP的20％，而其它發(fā)達國家普通在10%左右。這反映了我國物流系統(tǒng)落后，流通成本太高，反映了我國國民經濟運行質量不高。通過發(fā)呈當代物流業(yè)來增進物流合理化，減少流通成本在GDP中的比重，無疑將成為我國新的經濟增加點?！笆濉逼陂g，如果我國物流費用減少到占GDP的15％，每年將為社會直接節(jié)省2400億元的物流成本。(2)減少公司流動資金占用：我國工業(yè)公司和流通公司由于物流基礎設施、技術和管理的落后，原材料、半成品、成品積壓嚴重，大量流動資金被占用，周轉速度很慢，物流成本過高。據統(tǒng)，1992年，國有獨資、控股工業(yè)公司流動資金占用1萬多億元，周轉速度為次/年；1999年，國有獨資、控股工業(yè)公司流動資金達31000億元，周轉速度僅次/每年，與發(fā)達國家相比非常落后。如果工業(yè)公司把物流職能分離出來交給第三方物流公司，通過其先進、科學的專業(yè)化服務，就能夠減少流動資金占用，提高核心競爭能力，實現從粗放式經營向集約式經營轉變。(3)電子商務的發(fā)展需要物流做基礎：電子商務是流通領域的一場革命，它把3商品買賣虛擬成一種大的市場，使客戶在任何地點、任何時間都能夠購置商品。但是，電子商務需要將網上訂的貨品及時送到可能在任何地方的客戶手里，這就給物流系統(tǒng)帶來很大的挑戰(zhàn)。事實上，物流已經成為電子商務發(fā)展的瓶頸，需要建立含有響應性、靈活性和可視化的當代物流系統(tǒng)，需要第三方物流公司的服務。世界500強中相稱多的公司都是通過第三方物流來解決它的供應鏈與銷售問題的，諸多跨國公司在歐洲、亞洲、美洲等地分別有不同的第三方物流公司為他服務。(4)當代物流產業(yè)的發(fā)展，將減少由于低水平、條塊分割的物流方式造成的巨大物耗：在傳統(tǒng)的物流框架下，一件商品從生產出來到最后的消費環(huán)節(jié)，最少要被搬倒、裝運十幾次。實施社會化的多式聯運、一單究竟，物流過程中的物耗最少能夠減少幾倍。我國汽車空駛率達37％左右，意味著全國每年有150多萬輛載重汽車無活可干，這種潛在浪費最少也在數千億元。按當代物流規(guī)定，合理的流程設計可使空駛率減少到5％下列。在當代物流集約化、一體化的發(fā)展中，配送是直接與消費者相連的重要環(huán)節(jié)，其核心部分為配送車輛的集約、貨品配裝及送貨過程，而配送車輛優(yōu)化調度是物流系統(tǒng)優(yōu)化、物流科學化的核心一環(huán)，是貨品從配送中心送達收貨人的過程。配送首要解決的是車輛的調度問題，幾十年來這始終是一種研究的熱點，在滿足和完畢各任務的前提下，對的合理的安排行車路線、提高配送車輛的運用率就能夠有效的節(jié)省時間從而減少運輸成本。另外對出庫口車輛調度問題的研究，將有效減少貨品裝配的時間。因此本文對物流配送車輛調度的研究含有重要意義。國內外研究現狀車輛調度問題最早是由Dantzig和Ramsert在上個世紀50年代末期提出，該問題普通稱之為VehicleRoutingProblem(VRP)或者VehicleSchedulingProblem(VSP)，現在我們將車輛調度問題一律簡稱為VRP。VRP提出后就很快引發(fā)運籌學、應用數學、組合數學、圖論與網絡分析、物流科學、計算機應用等學科專家與運輸計劃制訂者和管理者的極大重視，成為運籌學與組合優(yōu)化領域的前沿與研究熱點問題。各學科的專家對該問題進行了大量的理論研究及實驗分析，獲得了很大進展。國外對物流配送車輛優(yōu)化調度問題作了大量而進一步的研究，例如早在1962年，Balinski等人首先提出VRP的集分割，直接考慮可行解集合，在此基礎上進行優(yōu)化，建立了最簡樸的VRP模型；1964年，Clarke和Wright提出了一種啟發(fā)式節(jié)省法來建立車隊配送路線；1968年，Rao等人在VRP集分割的基礎上引入了列生成辦法進行求解，這種算法本質上是最短途徑算法，同時結合了分枝定界算法；1971年，Eilon等人提出將動態(tài)規(guī)劃法用于固定車輛數的VRP，通過遞歸辦法求解；1981年，針對帶能力約束、時間窗以及無停留時間的VRP，Fisher提出了三下標車輛流方程；Thangiah于1991和Joe于l993分別用遺傳算法求解VRP，但是都存在“早熟收斂”的問題；，Tan，Lee，Du結合遺傳算法、tabu樹搜索算法的優(yōu)點，形成知識庫，用人工智能的辦法來求解；，Taranrilis,Kiranondis使用空間決策支持系統(tǒng)來解決車輛途徑問題。在國內,有關車輛調度問題的研究是在20世紀90年代后來才逐步興起的，比國外相對落后。國內研究對象重要是旅行商問題(TravelingSalesmanProblem，簡稱TSP)、中國郵遞員問題(ChinesePostmanProblem，簡稱CPP)、有向中國郵遞員問題(DirectedChinesePostmanProblem，簡稱DCPP)等，系統(tǒng)性研究還極少見到。西南交通大學的李軍專家和郭耀煌專家對車輛優(yōu)化調度的基礎理論及各類問題進行了系統(tǒng)的研究；李大為等以TSP的近來距離啟發(fā)式為基礎，通過設立評價函數來解決時間窗約束，求解了簡樸的VRP。另外在運用當代優(yōu)化算法(如:遺傳算法、神經網絡辦法、模擬退火等)對簡樸TSP的求解獲得了一定成果。蔡延光等應用模擬退火法針對滿載問題進行了求解。總體來說，現在我國對車輛調度問題的理論研究仍相對單薄，需要進一步研究。本文內容的安排本課題的研究以內蒙古蒙牛乳業(yè)股份(集團)有限公司的物流配送業(yè)務為背景，重要研究兩方面內容：首先，對多車場多目的開放式物流配送車輛調度問題做了研究，以此能夠優(yōu)化對客戶的派車問題及最佳車輛途徑的選擇問題。另首先，對AS/RS出庫端車輛調度方略做了研究，以本文建立的方略對出庫口的車輛分派車位，能夠減少車輛的配貨時間。本文的研究將在最大程度上減少蒙牛集團的運輸成本，給蒙牛集團帶來可觀的經濟效益。本文研究的具體內容以下：第一章緒論：介紹了本文研究的背景以及研究的目的與意義，并對國內外對車輛調度問題的研究現狀作了簡樸介紹。第二章車輛調度問題概述：首先對物流配送車輛調度問題進行了描述，另首先介紹了車輛調度問題的構成要素和車輛調度問題的分類，最后列舉了車輛調度的有關求解算法。第三章遺傳算法概述：首先對GA的背景作了簡樸的介紹，接著對GA算法的基本概念、工作流程和算法的構成做了具體描述。第四章用遺傳算法解決多車場多目的開放式車輛調度問題：首先介紹了兩種求解多車場車輛調度的辦法，然后對多車場多目的開放式車輛調度問題的研究背景進行了描述，在此基礎上擬定了多車場多目的開放式車輛調度問題的數學模型，并具體描述了用遺傳算法對多車場多目的開放式車輛調度問題的求解過程，最后用實例證明了用遺傳算法求解此問題的可行性。第五章對AS/RS出庫端車輛調度方略做了研究，提出了基于動態(tài)優(yōu)先級的AS/RS出庫端車輛調度方略，并開發(fā)了對應的AS/RS出庫端發(fā)貨資源監(jiān)控系統(tǒng)，即AS/RS出庫口車輛調度系統(tǒng)，以此方略對出庫口的車輛分派車位,能夠減少車輛的配貨時間。第六章總結與展望：歸納與總結了本文的創(chuàng)新之處，并提出進一步研究車輛調度問題的方向。第二章車輛調度問題概述車輛調度問題的描述“配送”一詞是日本引進美國物流學時，對英文單詞delivery一詞的意譯，我國轉學于日本，也直接用了“配送”這個詞。配送是物流系統(tǒng)中由運輸派生出的功效，是短距離的運輸。含有：①配送距離較短，位于物流系統(tǒng)的最末端，處在支線運輸、二次運輸和末端運輸的位置。②在配送中，也包含著其它的物流功效，是多個功效的組合。③配送是物流系統(tǒng)的縮影，也能夠說是一種小范疇的物流系統(tǒng)。從物流來講，配送幾乎涉及了全部物流的要素，車輛調度就是其中一種最重要且故意義的要素，因此本文研究的是物流配送車輛調度問題。物流配送車輛調度優(yōu)化問題最早是由Dentzing和Ramser在1959年第一次提出的。從此，車輛調度優(yōu)化問題很快引發(fā)運籌學、應用數學、組合數學、圖論與網絡分析、物流科學、計算機應用等學科的專家與運輸計劃制訂者的極大重視，同時也逐步成為運籌學與組合優(yōu)化領域的熱點研究問題。由于它應用的廣泛性和經濟上的重大價值，始終受到國內外學者的廣泛關注。國外將物流配送車輛優(yōu)化調度問題歸結為或稱之為VehicleRoutingProblem和VehicleSchedulingProblem。本課題采用的是后者，也就是將車輛調度問題歸結為VSP問題：VehicleSchedulingProblem。物流配送車輛調度問題的普通性定義是：物流配送車輛調度問題是把一系列的裝貨點和（或）卸貨點，有機的組織起來，形成一系列行車線路，使待調度車輛能夠高效、節(jié)能且有序地通過這些點。固然，這種組織方式是應當在滿足一定的約束條件（例如：顧客對貨品的需求量、一次性發(fā)貨量、應交發(fā)貨時間、單個車場的車輛容量限制、路程約束、時間限制等），最后達成縮短里程、減少開支費用、縮短運輸時間、使用車輛數盡量少等優(yōu)化目的。物流配送車輛調度問題普通研究的是在配送中心及顧客位置均已知、資源及運輸能力充足、各顧客需求量己知的前提下，如何合理、高效、低成本的解決分派與運輸的問題，也就是說如何將貨品從配送中心按照一定的規(guī)定發(fā)送到若干個顧客點。配送方案應當涉及兩個有關的環(huán)節(jié)：①有哪些顧客要被分派到一條回路上，即有哪些顧客的貨品應當安排在同一輛車上；②每條配送路線上顧客的連接次序。物流配送車輛調度的最優(yōu)解事實上是一種效率最高的運輸方案，它應明確的規(guī)定應派出的車輛型號、車輛數以及每輛車的具體行車路線。實施這一配送方案，即能夠滿足顧客的需求，又能夠使總的運輸行程最短。車輛調度問題的構成要素物流配送車輛調度問題重要涉及貨品、車輛、配送中心、客戶、運輸網絡、約束條件、和目的函數等要素。(1)貨品貨品是我國交通運輸領域中的一種特有專用概念，交通運輸領域將其經營的對象分為兩大類：一類是人，一類是物?！拔铩边@一類的運輸目的統(tǒng)稱為貨品。我們這里所說的貨品是指物流配送的對象，每批貨品都涉及品名、包裝、重量、體積、規(guī)定送到(或取走)的時間和地點，能否分批配送等屬性。(2)車輛車輛是“車”與車的單位“輛”的總稱。所謂車，是指陸地上用輪子轉動的交通工具；所謂輛，來源于古代對車的計量辦法。本文所說的車輛是指運載貨品的工具，車輛的重要屬性涉及：類型、工作時間、配送前的停放位置、載重量以及配送任務完畢后的停放位置等。(3)配送中心配送中心是指接受供應者所提供的多品種、小批量的貨品，通過存儲、保管、分揀、配貨以及流通加工、信息解決等作業(yè)后，將按需要者訂貨規(guī)定配齊的貨品送交顧客的組織機構和物流設施。本文所說的配送中心是指從事配送業(yè)務的物流場合或組織，如能夠進行貨品集中、分揀、配貨、送貨等的倉庫、車站、港口等固定場合。在物流配送系統(tǒng)中，配送中心能夠只有一種，也能夠同時含有多個。配送中心專業(yè)性強，和客戶有固定的配送關系，普通實施計劃配送，需配送的商品有一定的庫存量，普通狀況極少超越自己的經營范疇。配送中心的設施及工藝流程是根據配送需要專門設計的，因此配送能力很強，配送距離較遠，配送的品種較多，配送數量比較大。使用配送中心配送覆蓋面寬，規(guī)模大，因此，必須有一套配套的大規(guī)模實施配送的設施。本文的研究背景就是基于配送中心的物流配送中車輛調度問題的研究。(4)客戶客戶指的是物流配送的服務對象，能夠是多個零售店，也能夠是分倉庫，還能夠是別的倉庫的外調。也就是說客戶是有配送任務的對象的統(tǒng)稱。客戶的屬性涉及需求數量、需求時間、需求次數及現在需求的滿足動態(tài)等。8(5)運輸網絡本文的運輸網絡采用了離散數學中對網的介紹，配送中心、客戶、停車場等構成網絡的頂點、它們之間的交互運輸構成了無向邊，具體的運輸任務被稱為由有向弧構成的運輸的網絡。邊、弧的屬性涉及方向、權值和交通流量限制等。在運輸網絡中，邊或弧含有一定的權值，該值能夠表達為距離、時間或費用。邊或弧的權值變化含有下列幾個狀況：固定不變，不隨著時間和車輛的不同而變化；隨時間段或者車輛不同而變化；既隨著時間的不同而變化，又隨著車輛的不同而變化。對運輸網絡中的定點、邊或弧的交通流量規(guī)定分為下列幾個狀況：無流量限制；邊、弧限制，即每條邊、弧上同時行駛的車輛數有限；頂點限制，即每個頂點上同時裝、卸貨的車輛數有限；邊、弧、頂點都有限制。(6)約束條件物流配送車輛調度問題應滿足下列約束條件：能夠滿足全部客戶對貨品品種、規(guī)格、數量的規(guī)定；能夠在客戶規(guī)定或者承受的時間內將貨品送到；運輸車輛每天的運行時間、運行歷程都要有一定的限制，不能超出預定的時間或者里程；在物流配送過程中實際裝載的貨品不能超出車輛的最大載重規(guī)定，也就是不能超載；固然，客戶的需求也必須在物流中心現有的運力范疇內，也就是現在有這個能力去完畢待完畢的任務。(7)目的函數目的函數是指所關心的目的(某一變量)與有關的因素(某些變量)的函數關系。簡樸的說，就是你求解后所得出的那個函數。在求解前函數是未知的，按照你的思路將已知條件運用起來，去求解未知量的函數關系式，即為目的函數。本課題研究的物流配送車輛調度問題，能夠只選用一種目的，也能夠同時選用多個目的。使用概率比較多的目的函數重要有：①配送的距離最短，也就是在配送過程中車輛所走的路程最短。在實際的物流配送中，配送里程直接關系到配送車輛的耗油量、磨損程度以及司機疲勞程度等因素。因此，在眾多的目的函數中選擇配送里程最短的目的，在某種程度上能夠直接減少運輸成本。②配送車輛的載重量與公里數最少，這種方式的目的是將配送距離與車輛的載重量進行了有機結合，綜合來考慮載重量與配送距離之間的關系，以達成最優(yōu)化的配備，是比較慣用的目的之一。9③綜合費用最低，完畢最多的任務，花最少的成本，這是物流配送中的一種根本原則。減少各項開支的綜合費用是實現物流配送業(yè)務中獲得良好經濟效益的根本規(guī)定。在物流配送中，與配送有關的費用涉及：車輛維護費用、車輛耗油費用、車隊管理費用、裝卸工所需費用、各部門人員工資費用等。④準時完畢任務，無論是分倉庫還是分銷點，多個顧客都對需求的交貨時間有著嚴格的規(guī)定。配送任務完畢的準時性，很大程度上決定了配送公司在客戶心中的地位，決定了公司的信譽度。多個成本即使是必須考慮的因素，也是最實際的因素，但是為提高配送服務質量，準時完畢顧客的需求，有時需要將準時性最高作為配送路線的目的。⑤使用的車輛數最少，該目的考慮的是使用盡量少的車輛去完畢指定的配送任務。前面的目的敘述了各項指標的規(guī)定，但是如果車輛跑的距離最短、也是準時達成的，但是使用的車輛都沒有滿載，這無疑也是對資源的一種浪費，也不能是整體配送效益達成最優(yōu)，因此必須規(guī)定車輛的滿載率最高，以充足運用車輛的裝載能力。⑥勞動消耗最低，充足考慮人的因素。也就是使用最少的司機數，這固然和前面使用最少的車輛數是一致的，只有車輛少了，司機才會少，只有車輛都裝滿了，才會使用最少的車輛。只有選擇的距離最短了，司機才干工作最短的時間，這些都是重要的目的值。車輛調度問題的分類車輛調度問題(Visual-ScheduleProblem，VSP)被提出后，國內外各學科的學者從不同角度對它進行了多個研究，并各自按不同的原則對其進行了分類。綜合起來可分為下列幾個：(1)按車場數目分：有單車場車輛調度問題和多車場車輛調度問題。單車場問題指配送系統(tǒng)中僅有一種配送中心，多車場車輛調度問題指配送系統(tǒng)中存在多個配送中心。(2)按配送任務特性分：分為純送貨問題、純取貨問題以及取送混合問題。其中純送貨問題指僅僅考慮從物流中心向客戶送貨，而不考慮從顧客向配送中心送貨；純取貨問題指單純考慮把各客戶供應的貨品取到配送中心不考慮配送中心給客戶供貨問題；取送混合問題是上面兩者的有機組合，既要考慮將客戶需求的貨品從物流中心送到各個客戶，同時還考慮將客戶提供的貨品從客戶取到物流中心。(3)按車輛載貨狀況分：分為滿載問題、非滿載問題以及滿載和非滿載混合問題。10滿載問題指的是貨運量不不大于車輛容量，完畢一項任務需要不少于一輛車；非滿載問題指的是貨運量不大于車輛容量，多項貨品合用一輛車，在實際的車輛配送過程中經常會出現這種處在非滿載的狀態(tài)；滿載和非滿載混合問題是上述兩者的有機組合，既存在一部分客戶需求和供應的貨品數量不不大于或等于車輛的載重量，同時又存在另一部分客戶需求量或供應的貨品數量不大于車輛的載重量，上述狀況就造成一部分派送車輛滿載運行，而另一部分運行在非滿載的狀態(tài)。(4)按客戶對貨品解決時間的規(guī)定分：分為無時間約束問題和有時間約束問題。其中無時間約束問題指的是客戶對貨品的取走和送到的時間沒有嚴格的規(guī)定；有時間約束問題指的是客戶規(guī)定將其需求的貨品在一定的時間范疇內送到，并且將供應的貨品在一定的時間范疇內取走。有時間約束問題又分為硬時間窗問題和軟時間窗問題，硬時間窗問題指的是對任務的完畢有硬性的時間限制，或者說時間規(guī)定。軟時間窗問題指的是有一定的時間約束，但是相對比較寬松，盡量在顧客規(guī)定的時間范疇內將貨品送到或者取走，但是如果超越了規(guī)定的時間限制可能要有一定的處分機制。(5)按車輛類型分：分為單車型問題和多車型問題。單車型問題指全部配送車輛類型和容量相似，這種狀況方便統(tǒng)一管理和裝卸。多車型問題指在執(zhí)行任務過程中的配送車輛類型和容量不完全相似，這種狀況解決起來比較復雜。(6)按車輛對車場合屬關系分：分為開放式車輛調度問題和封閉式車輛調度問題。開放式車輛調度問題指的是車輛完畢配送任務后能夠不返回其原來發(fā)出車場；封閉式車輛調度問題指的是車輛完畢配送任務后必須返回其原來發(fā)出車場。本課題是針對開放式車輛調度問題進行的研究。(7)按優(yōu)化目的數分：分為單目的問題和多目的問題。單目的問題指的是僅考慮一種配送目的；而多目的問題指的是同時考慮多個配送目的。車輛調度的有關求解算法用于解決物流配送車輛調度問題的算法分為：精確算法和啟發(fā)式算法兩大類，精確算法普通用于解決小規(guī)模的VRP問題，車輛調度問題應用最為廣泛的算法是啟發(fā)式算法，啟發(fā)式算法并不追求問題的最優(yōu)解，而是強調問題解的滿意性。因此，啟發(fā)式算法對于大規(guī)模的車輛調度問題能在較短的時間內獲得較滿意的次優(yōu)解，并且這些算法的通用性也很強。常見的啟發(fā)式算法有以下幾個：(1)C-WSavings算法C-WSavings算法采用了幾何中三角形的邊定理，即三角形的兩邊之和不不大于第三邊。當途徑中有這樣的兩個邊時用第三邊來替代，以達成節(jié)省配送距離的目的。我們能夠設節(jié)點i和節(jié)點j之間的節(jié)省量為Sij，這兩點和節(jié)點o之間的距離為Doi和Doj，則Sij=Doi+Doj-Dij（i≠j,i,j=1,2,…n,），算法首先求出全部Sij，并按非增次序排列。然后從最大的Sij開始，擬定與否存在兩條途徑，其中一條從弧(0,j)開始，而另一條以(i,o)結束。如果存在，則去掉弧(0,j)、(i,o)，引入弧(j,i)合并這兩條途徑。重復上述過程直到沒有途徑能夠合并。(2)Sweep算法Sweep算法是一種“先分組后路線”的算法。所謂的分組就是：首先計算出要訪問的顧客的位置的極坐標，并把這些極坐標按角度大小排序，然后在未分派到任何途徑中的顧客中從角度最小的顧客開始，依次將顧客歸并到對應的途徑中，直到車輛的能力約束滿足為止，再重新選擇新的車輛，重復上述過程，直到全部的顧客都分派完畢。最后運用TSP的優(yōu)化算法對各子路經進行優(yōu)化。(3)ClusterandRoute算法普通有兩種辦法：先聚類后排序辦法(CFRS)和先排序后聚類辦法(RFCS)。CFRS最早由等提出，它是先用啟發(fā)式辦法將節(jié)點分成若干途徑，然后對途徑中的點進行排序。RFCS由Besley提出，它先對全部節(jié)點進行TSP排序，然后將大的途徑分成若干個小途徑。(4)遺傳算法GA遺傳算法使用群體搜索技術，借用適者生存規(guī)律進行局部搜索改善，它通過對現在群體施加選擇、交叉、變異等一系列遺傳操作，從而產生出新一代的群體，每一次進化則對應解的一次迭代，并逐步使群體進化到包含或靠近最優(yōu)解的狀體。當迭代次數達成最大次數限制或群體中的個體無明顯差別時，迭代終止。最先將GA應用于求解車輛調度問題。(5)禁忌搜索算法TSTS的思想由Glover最早提出，它通過對避開某些局部最優(yōu)解，達成接納一部分較差解，從而跳出局部搜索的目的。TS是對局部鄰域搜索的一種擴展，是一種全局逐步尋優(yōu)算法，是對人類思維過程的一種模擬。禁忌搜索算法通過運用一種禁忌表統(tǒng)計已經達成過的局部最優(yōu)點，并在背面的搜索中，根據某種限制循環(huán)的規(guī)則和禁忌表中統(tǒng)計的信息在現在搜索鄰域中取一種適宜的解。(6)模擬退火算法SA其思想最早有Metropolis1953年提出，Osman于1993年用之解決VRP。模擬退火算法用固體退火模擬組合優(yōu)化問題，將內能模擬為目的函數值，溫度演化成控制參數。由初始解和控制參數初值開始，對現在解重復“產生新解→計算目的函數差→接受或舍棄”的迭代，并逐步衰減控制參數值，算法終止時的現在解即為所得近似最優(yōu)解。(7)蟻群優(yōu)化算法ACO蟻群算法模擬了蟻群搜索食物的行為。螞蟻在尋找食物時，會在它所通過的途徑排放一種外激素(pheromone,在算法中稱為信息素)作為標記，排放的量則根據途徑長度和食物的等級決定。這些外激素能夠指導螞蟻的運動方向，并使蟻群朝著外激素強度高的方向移動。在用蟻群算法解決車輛調度問題時，可根據優(yōu)化的目的函數個數，構造多組互相協(xié)作的人工蟻群，使各組分別優(yōu)化其中的一種目的函數，并以共用解的方式建立協(xié)作關系。在以上求解VRP的算法中，有的算法運用全局信息進行整體搜索適合構解，如GA等；尚有的運用局部信息，適合改善解，如SA、TS等。每種辦法都各有所長與局限性，普通來說，根據具體的求解問題，采用兩種或兩種以上的混合辦法，能夠得到更加好的解。小結本章從車輛調度基本理論的角度，首先介紹了車輛調度涉及到的基本概念，涉及了問題的描述和構成要素。另首先對車輛調度問題的分類進行的描述，列舉了某些有關解決車輛調度問題的算法。第三章遺傳算法概述背景介紹遺傳算法(GeneticAA)是由美國Michigan大學專家和他的學生發(fā)展建立的一類借鑒生物界的進化規(guī)律—適者生存、優(yōu)勝劣汰遺傳機制演化而來的概率搜索算法。GA算法是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，遺傳算法作為一種非數值并行算法，其思想來源于生物遺傳學適者生存的自然規(guī)律，通過自然選擇、遺傳、變異等作用機制，實現各個體適應性的提高。它是多學科結合與滲入的產物，已經發(fā)展成一種自組織、自適應的綜合技術，廣泛應用在計算機科學、工程技術和社會科學等領域。GA算法是通過對自然進化現象的模擬，運用簡樸的編碼技術和進化機制來解決復雜的優(yōu)化問題。特別是由于它不受搜索空間的限制性假設的約束，不必規(guī)定諸如持續(xù)性、導數存在等假設，以及其固有的并行性。它是一種以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規(guī)則與同一群染色體的隨機信息變換機制相結合的搜索算法，其通過給解向量編碼，形成初始種群，然后用變異、交叉、重組、自然選擇等算子，進行并行迭代求得優(yōu)化解。由于遺傳算法含有不依賴于問題模型采用隨機運算，對搜索空間無特殊規(guī)定、無需求導，含有全局最優(yōu)性求解能力、隱含并行性、收斂速度快以及能高效率地解決不同非線性問題的魯棒性的特點。因此近年來有很快的發(fā)展，在組合優(yōu)化、自適應控制、機器學習等許多領域獲得應用，并在電氣自動化、計算機和通信以及人工智能的許多領域獲得了不凡的成就，特別適合求解NP-hard問題。遺傳算法的基本概念由于遺傳算法是由進化論和遺傳學機理而產生的直接搜索優(yōu)化辦法，因而在這個算法中要用到多個進化和遺傳學的概念。這些概念以下：(1)串(String)它是個體(Indlvidual)的形式，對應于遺傳學中的染色體(Chromosome)。(2)群體(Population)個體的集合稱為群體，個體是群體的元素。(3)群體大小(Populationsize)在群體中個體的數量稱為群體的大小。(4)基因(Gene)基因是串中的元素，基因用于表達個體的特性。例如有一種串S=1010，則其中的1，0，1，0這4個元素分別稱為基因。(5)基因位置(GenePosition)一種基因在串中的位置稱為基因位置，有時也簡稱基因位?；蛭恢糜纱淖筮呄蛴矣嬎悖缭诖甋=1011中，0基因位置是2?；蛭恢脤谶z傳學中的地點(Locus)。(6)基因特性值(GeneFeature)在用串表達整數時，基因的特性值與二進制數的權一致，如在串S=1011中，第三基因位值上的1，它的基因特性值為2；第一基因位值上的1，它的基因特性值為8。(7)串構造空間S在串中，基因任意組合構成的串的集合稱為串構造空間。基因操作是在構造空間中進行的。(8)適應度(Fitness)表達某一種體對于環(huán)境的適應程度。為了體現染色體的適應能力，引入了對問題中的每一種染色體都能進行度量的函數—適應度函數，用于計算個體在群體中被使用的概率。(9)選擇(Selection)就是從群體中選擇出較適應環(huán)境的個體。這些選中的個體用于繁殖下一代，故有時也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個體時，是根據個體對環(huán)境的適應度來決定其繁殖量的，故有時也稱為非均勻再生(Differentia1Reproduction)。(10)交叉(Crossover)就是在選中用于繁殖下一代的個體中，對兩個不同的個體隨機選用一種子串進行交換，從而產生新的個體。(11)變異(Mutation)就是在選中的個體中，隨機選擇兩點，將兩點間的子串按一定的規(guī)則進行變異。遺傳算法的工作流程遺傳算法在整個進化過程中的遺傳操作是隨機的，但它所呈現出的特性并不是完全隨機搜索，它能有效地運用歷史信息來推測下一代盼望性能有所提高的尋優(yōu)點集。這樣一代代地不停進化，最后收斂到一種最適應環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算法所涉及的五大要素為：參數編碼、初始群體的設定、適應度函數的設計、遺傳操作的設計和控制參數的設定。其流程框圖如圖所示。圖遺傳算法流程圖從圖能夠看出，遺傳算法的運行為一種典型的迭代過程，其必須完畢的工作內容和基本環(huán)節(jié)以下：(1)選擇編碼方略，將解空間中的解數據表達成遺傳空間的基因型串構造數據，這些串構造數據的不同組合便構成了不同的編碼。(2)定義適應度函數f(x)。(3)擬定遺傳方略，涉及選擇群體大小n，選擇、交叉、變異辦法，以及擬定交叉概率pc、變異概率pm等遺傳參數。(4)隨機初始化生成群體P。(5)計算群體中個體位串解碼后的適應度f(x)。(6)按照遺傳方略，運用選擇、交叉和變異算子作用于群體，形成下一代群體。(7)判斷群體性能與否滿足某一指標，或者己完畢預定迭代次數，不滿足則返回環(huán)節(jié)(6)，或者修改遺傳方略再返回環(huán)節(jié)(6)。在遺傳算法的應用過程中，人們往往結合問題的特性和領域知識對基本遺傳算法進行多個變化，形成了多個各樣具體的遺傳算法，從而使得遺傳算法含有求解不同類型優(yōu)化問題的能力。遺傳算法的構成遺傳算法重要由六個部分構成：編碼方式、初始群體產生的辦法、評價函數、遺傳操作、算法終止條件、算法參數的設立。要運用遺傳算法成功的解決物流配送車輛調度問題，就需要對這六個環(huán)節(jié)進行設計。編碼方式在遺傳算法的運行過程中，它不對所求解問題的實際決策變量直接進行操作，而是對表達可行解的個體編碼施加選擇、交叉、變異等遺傳運算，通過這種遺傳操作來達成優(yōu)化的目的，這是遺傳算法的特點之一。遺傳算法通過這種對個體編碼的操作，不停搜索出適應度較高的個體，并在群體中逐步增加其數量，最后謀求出問題的最優(yōu)解或近似最優(yōu)解。在遺傳算法中如何描述問題的可行解，即把一種問題的可行解從其解空間轉換到遺傳算法所能解決的搜索空間的轉換辦法就成為編碼。編碼是應用遺傳算法時要解決的首要問題，也是設計遺傳算法的一種核心環(huán)節(jié)。編碼辦法除了決定了個體的染色體排列形式之外，它還決定了個體從搜索空間的基因型變換到解空間的體現型時的解碼辦法，編碼辦法也影響到交叉算子、變異算子等遺傳算子的運算辦法。由此可見，編碼辦法在很大程度上決定了如何進行群體的遺傳進化運算以及遺傳進化運算的效率。一種好的編碼辦法，有可能會使得交叉運算、變異運算等遺傳操作能夠簡樸的實現和執(zhí)行。而一種差的編碼辦法，卻有可能會使得交叉運算、變異運算等遺傳操作難以實現，也有可能會產生諸多在可行解集合內無對應可行解的個體，這些個體經解碼解決后所示的解稱為無效解。即使有時產生某些無效解并不完全都是有害的，但大部分狀況下它卻是影響遺傳算法運行效率的重要因素之一。針對一種具體應用問題，如何設計一種完美的編碼方案始終是遺傳算法的應用難點之一，也是遺傳算法的一種重要研究方向。能夠說現在還沒有一套既嚴密又完整的指導理論及評價準則能夠協(xié)助我們設計編碼方案。作為參考，DeJong曾提出了兩條操作性較強的使用編碼原則：編碼原則一：應使用能易于產生與所求問題有關的且含有低階、短定義長度模式的編碼方案。編碼原則二：應使用能使問題得到自然表達或描述的含有最小編碼字符集的編碼方案。第一種編碼原則中，模式是指含有某些基因相似性的個體的集合，而含有短定義長度、低階且適應度較高的模式稱為構造優(yōu)良個體的積木塊或基因塊，這里能夠把該編碼原則理解成應使用易于生成適應度較高的個體的編碼方案。第二個編碼原則闡明了我們?yōu)槭裁雌珢塾谑褂枚M制編碼辦法的因素，由于它滿足這條編碼原則的思想規(guī)定。事實上，理論分析表明，與其它編碼字符集相比，二進制編碼方案能包含最大的模式數，從而使得遺傳算法的擬定規(guī)模的群體中能夠解決最多的模式。由于遺產算法應用的廣泛性，迄今為止人們己經提出了許多個不同的編碼辦法。總的來說，慣用的編碼辦法可分為三大類：二進制編碼辦法、實數編碼辦法、有序串編碼辦法。二進制編碼辦法是遺傳算法中最慣用的一種編碼辦法，它使用的編碼符號集是由二進制符號0和1所構成的二值符號集{0，1}，它所構成的個體基因型是一種二進制編碼符號串。在二進制編碼方式的遺傳算法中，遺傳操作是作用在編碼空間上的，操作后的二進制串通過解碼轉換到解空間，在這里進行評定選擇(如圖3-2所示)。圖編碼解碼操作使用二進制編碼辦法，在求解高維優(yōu)化問題時，二進制串會很長，因而算法的搜索效率很低。為了克服二進制編碼辦法的缺點，對于變量是實向量的狀況，能夠直接采用實數編碼辦法。實數編碼表達比較自然，較易引入有關領域知識，因此，實數編碼還能夠使遺傳算法更靠近問題空間，避免了編碼和解碼的過程，其使用將越來越廣泛。對諸多組合優(yōu)化問題，目的函數的值不僅與表達解的字符串中各字符的值有關，并且與其所在字符串的位置有關，這樣的問題稱為有序問題，用有序串編碼辦法表達。這類編碼辦法較多地用在組合優(yōu)化問題中，如二次分派問(QuadraticAssignmentproblem)，旅行商問題(TravelingSalesmanProblem)我們慣用的是有序串的編碼方式。基于遺傳算法的以上特點，在本文用遺產算法求解物流配送車輛調度問題時，我們采用有序串編碼方式的染色體設計。初始化過程有諸多個，在研究遺傳算法時，經常隨機產生初始群體，這樣做的好處是產生方式不依賴于問題，也就是對于任何問題，我們都能夠采用這種方式來生成初始群體，由于本文是對某個特定的非線性規(guī)劃問題求解，因此我們采用人機交互方式來初始化群體，這樣結合人類智慧使算法優(yōu)化收斂速度更快。適應度函數在研究自然界中生物的遺傳和進化現象時，生物學家使用適應度這個術語來度量某個物種對于其生存環(huán)境的適應度程度。對生存環(huán)境適應程度較高的物種將有更多的繁殖機會；而對生存環(huán)境適應程度較低的物種，其繁殖機會就相對較少。與此相似，在遺傳算法中也使用適應度這個概念來度量群體中各個個體在優(yōu)化計算中有可能達成或靠近于或有助于找到最優(yōu)解的優(yōu)良程度。適應度較高的個體遺傳到下一代的概率就較大，而適應度較低的個體遺傳到下一代的概率就相對小某些。度量個體適應度的函數就稱為適應度函數（FitnessFunction）。遺傳算法的一種特點是它僅使用所求問題的目的函數值就能夠得到下一步的有關搜索信息。而對目的函數值的使用是通過評價個體的適應度來體現的。評價個體適應度的普通過程是：(1)對個體編碼串進行解碼解決后，可達成個體的體現型。(2)由個體的體現型可計算出對應個體的目的函數值。(3)根據最優(yōu)化問題的類型，由目的函數值按一定的轉換規(guī)則求出個體的適應度。遺傳算法中，群體的進化過程就是以群體中各個個體的適應度為根據，通過一種重復迭代過程，不停地謀求出適應度較大的個體，最后就能夠得到問題的最優(yōu)解或者近似最優(yōu)解。對于本課題的多車場多目的開放式車輛調度模型優(yōu)化問題，采用函數值來評價解的好壞，這種辦法是最直接，也是最方便的辦法，取函數值最小的解為最優(yōu)解。選擇方略遺傳算法中的選擇方略就是用來擬定如何從父代群體中按某種辦法選用哪些個體遺傳到下一代群體中的一種遺傳運算，選擇提供了遺傳算法的驅動力。如果驅動力過大，遺傳搜索將過早地終止，而如果驅動力太小，進化過程將變得難以接受。相對而言，較小的驅動力普通能使群體保持足夠的多樣性，從而增大了算法收斂到全局最優(yōu)的概率。選擇操作是建立在對個體的適應度進行評價的基礎之上的，選擇操作的重要目的是為了避免基因缺失、提高全局收斂性和計算效率。下面是遺傳算法中較慣用到的幾個選擇方略。(1)繁殖池(BreedingPool)選擇繁殖池選擇首先根據現在群體中個體的適應值，按下式計算其相對適應值：其fi是群體中第i個組員的適應值，N是群體規(guī)模。則每個個體的繁殖量為：此處Round(x)表達與x距離最小的整數。計算出群體中每個個體的繁殖量，即可將它們分別復制N個以生成一種臨時群體，即繁殖池(Breedingpool)再通過在繁殖池中隨機地抽取成對個體進行交配，所產生的后裔將取代現在群體形成下一種群體。顯然，個體復制到繁殖池的數目越大，則它被選到進行交配的機會也就越多，而對于Ni=0的個體，它們將被裁減出整個演化過程。在實現算法時需要注意的是，繁殖池中個體的數目不一定正好等于N。(2)輪盤賭選擇(RouletteWheelSelection)輪盤賭選擇是由Holland提出的，是最出名的選擇方式之一，其基本原理是根據每個染色體適應值的比例來擬定該個體的選擇概率或生存概率。選擇的過程就是旋轉輪盤若干次（次數等于種群規(guī)模），每次為新種群選出一種個體。輪盤賭選擇方略在遺傳算法中使用的最多，它的具體選擇過程為：先計算個體的適應值Pi，然后根據選擇概率把輪盤分成N份，其中第i扇形的中心角為2πPi。在進行選擇時，先轉動輪盤，若某參考點落入到第i個扇形內，則選擇個體i?？梢?，這種選擇方式非常類似輪盤賭中的轉盤，小扇區(qū)的面積越大，骰子落入其中的概率也越大，即個體的適應值越大，它被選擇到的機會也越大。從而，其基因構造被遺傳到下一代的可能性也越大。(3)錦標賽（Toumament）選擇錦標賽選擇也是一種基于個體適應度之間大小關系的選擇辦法。在選擇時，每次進行適應度大小比較的個體數目稱為競賽規(guī)模，普通狀況下，競賽規(guī)模K的取值為2。具體操作過程以下：首先，從群體中隨機選用K個個體進行適應度大小的比較，將其中適應度最高的個體作為生成下一代的父體。另首先，將上述過程重復M次，就可得到下一代群體中的M個個體。顯然，這種選擇方式也使得適應度好的個體含有較大的“生存”機會。同時，由于它只使用適應度的相對值作為選擇的原則，而無個體適應度的算術運算。從而它能避免超級個體的影響，在一定程度上，避免發(fā)生過早收斂現象和停滯現象。雜交方略交叉運算是指對兩個互相配對的染色體按某種方式互相交換其部分基因，從而形成兩個新的個體。它在遺傳算法中起著核心作用，是產生新個體的重要辦法。首先它使原來群體中優(yōu)良個體的特性能夠在一定程度上被遺傳和繼承，另首先它使算法能夠搜索新的基因空間，從而使新群體中的個體含有多樣性。交叉或基因重組是遺傳算法獲取新的優(yōu)良個體的最重要的手段。經常采用的交叉算子有下列幾個：(1)部分映射交叉(PartiallyMappedCrossover，簡稱PMX)這種算子在構造后裔時通過從一種父體中選用一段途徑，并盡量多的保存另一種父體中都市的次序和位置。選擇一種途徑時，首先隨機選用兩切割點作為交換操作的邊界。例如兩父體(兩切割點用“|”標記)P1=(123|4567|89)P2=(254|1876|39)產生后裔的過程以下：首先交換兩切割點之間的對應段(符號“x”表達現在未知值)，得到Q1=(xxx|1876|xx)Q2=(xxx|4567|xx)這一交換同時定義了一系列的映射：然后從各自的父體中填入無沖突的都市，得到：Q1=(x23|1876|x9)Q2=(2xx|4567|39)最后，后裔Q1中的第一種“x”根據映射14被4替代。類似地，Q1中的第二個“x”用5替代，Q2中的兩個“x”分別用8和1替代。因此生成的后裔為Q1=(423|1876|59)Q2=(281|4567|39)(2)次序交叉(OrderCrossover，簡稱OX)這一算子在構造后裔時通過從一種父體中選用一段途徑，并保持另一種父體中都市的相對次序。例如兩父體(兩切割點用“|”標記)P1=(123|4567|89)P2=(452|1876|93)產生后裔的過程以下：首先，兩切割點之間的都市段被復制到后裔中，得到：Q1=(xxx|1876|xx)Q2=(xxx|4567|xx)接著從一種父體的第二個切割點開始，來自另一種父體的都市依同樣的次序被復制，省略已經出現的都市。當達成串尾時，則從串首繼續(xù)。那么，第二個父體從第二個切割點開始的都市序列為：9-3-4-5-2-1-8-7-6移去4，5，6和7這四個在第一種后裔中已出現的都市，得到：9-3-2-1-8依本次序從第二個切割點開始填入第一種后裔得到Q1=(218|4567|93)類似地，可得到另一種后裔Q2=(345|1876|92)OX算子開發(fā)了途徑表達的一種特性，即重要的是都市間的相對次序，而不是他們的特定位置。也就是，兩條途徑9-3-4-5-2-18-7-6和4-5-2-事實上是相似的。(3)循環(huán)交叉(CycleCrossover，簡稱CX)這種算子在構造后裔時，每個都市及其所處的位置都來自于某一種父體。循環(huán)交叉的過程以下：兩父體P1=(123456789)P2=(452687193)產生后裔時，先從第一種父體中取第一種都市作為第一種后裔的起始點，得到Q1=(lxxxxxxxx)。由于后裔中的每一種都市必須取自于某個父體且保持同樣位置，因此在起始點我們別無選擇。下一種考慮的都市應當是4，由于它是P2中位于所選都市1“下方”的都市，在P1中這個都市位于位置4。因此Q1=(lxx4xxxxx)接著是都市6，由于它是P2中位于所選都市4“下方”的都市。因此Q1=(lxx4x6xxx)按照這樣的規(guī)則，在第一種后裔中應涉及的下個都市是7。但是注意，選擇都市7蒙牛乳業(yè)股份有限公司自動化立體倉庫出庫端車輛調度問題摘要：自動化立體倉庫出庫端車輛調度方略的設計是物流配送車輛調度中的一種核心問題，好的調度方略能夠大大縮短出庫端的配貨時間。為此本文引入動態(tài)優(yōu)先級理論，并運用該理論對大型AS/RS出庫口車輛調度問題進行了進一步研究與分析，提出了基于動態(tài)優(yōu)先級的AS/RS出庫端車輛調度方略，并開發(fā)了對應的AS/RS出庫口發(fā)貨資源監(jiān)控系統(tǒng)，即AS/RS出庫口車輛調度系統(tǒng)，優(yōu)化了AS/RS出庫端車輛調度方略，大大提高了物流配送當中的配貨效率。本文建立的多目的組合優(yōu)化模型以及設計的遺傳算法求解方案，能夠有效的縮減物流配送中的送貨時間；設計的AS/RS出庫端車輛調度優(yōu)化方略及開發(fā)的AS/RS出庫端車輛調度系統(tǒng)，能夠有效縮減車輛在出庫端的配貨時間。本文對以上兩種物流配送中的車輛調度問題進行研究，大大提高了物流配送效率、減少了物流配送成本。核心詞：物流配送；車輛調度；多目的組合優(yōu)化；一、公司背景蒙牛乳業(yè)，是“蒙牛乳業(yè)集團”的簡稱。其總部，設在呼和浩特市和林格爾盛樂經濟園區(qū)。前后四期工程占地面積55萬平方米。蒙牛是一家總部位于中華人民共和國內蒙古的乳制品生產公司，蒙牛是中國大陸生產牛奶、酸奶和乳制品的領頭公司之一，1999年成立，至時已成為中國奶制品營業(yè)額第二大的公司，其中液態(tài)奶和冰淇淋的產量都居全中國第一。蒙牛重要業(yè)務是制造液體奶、冰激凌和其它乳制品。1999年8月，內蒙古蒙牛乳業(yè)（集團）股份有限公司（簡稱蒙牛乳業(yè)集團）成立，總部設在中國乳都核心區(qū)――內蒙古和林格爾經濟開發(fā)區(qū)，擁有總資產100多億元，職工近3萬人，乳制品年生產能力達600萬噸。到現在為止，涉及和林基地在內，蒙牛乳業(yè)集團已經在全國16個省區(qū)市建立生產基地20多個，擁有液態(tài)奶、酸奶、冰淇淋、奶品、奶酪五大系列400多個品項，產品以其優(yōu)良的品質覆蓋國內市場，并出口到美國、加拿大、蒙古、東南亞及港澳等多個國家和地區(qū)。二、AS/RS出庫端車輛調度問題的研究問題的提出自動化立體倉庫（AutomaticStorage＆RetrievalSystem）：是指能自動儲存和輸出貨品的倉庫，它采用多層貨架儲存單元貨品，用自動化貨品搬運設備進行貨品的入庫和出庫。它普通由自動控制與管理系統(tǒng)、貨架、巷道式堆垛機、出入庫輸送機等構成，能按指令自動完畢貨品的搬運、存取作業(yè)，并能對庫存貨品進行自動管理。由于自動化立體倉庫含有很高的空間運用率、很強的入出庫能力、采用計算機進行控制管理便于公司實施當代化管理等特點，已成為公司物流和生產管理不可缺少的倉儲技術，自動化立體倉庫作為物流中心的重要構成部分，越來越受到公司的重視?，F階段對物流配送車輛調度問題的研究諸多，但大多是對車輛調度線路選擇問題的研究，對自動化立體倉庫出庫端車輛調度問題的研究較少。在物流配送中整個配送時間應涉及兩部分：出庫端的配貨時間和裝貨完畢后的送貨時間，對車輛調度線路選擇問題的研究能夠有效的縮減物流配送中的送貨時間，但通過對出庫端車輛調度問題的研究能夠有效縮減車輛在出庫端的配貨時間，對減少物流配送的時間成本有很大的作用。所謂自動化立體倉庫出庫端車輛調度，即在自動化立體倉庫出庫端按什么樣的原則給待裝貨車輛分派車位的問題?，F階段出庫端車輛調度大多采用先來先服務的原則，即對先到的車輛優(yōu)先分派車位，此原則的采用能夠充足體現車輛調度的公平性，但有諸多局限性。首先當給訂貨數量特大的訂單客戶的車輛分派車位后，此客戶后的全部小訂貨數量客戶的車輛都需要等待很長時間才干被分派車位，減少了系統(tǒng)在一段時間內解決客戶訂單的能力，并且此調度方略沒有考慮影響出庫產品整體銷售模式的因素。因此本文對自動化立體倉庫出庫口車輛調度問題的研究含有重要的實際意義。問題及有關因素描述本文是以內蒙古蒙牛乳業(yè)股份有限公司自動化立體倉庫出庫端車輛調度問題為背景進行研究的。一種大型的立體倉庫有多個出庫口，每一種出庫口對應一種車位，所謂車位就是車輛裝貨時在出貨口的位置，分為常規(guī)固定車位和雙向固定車位兩種類型。常規(guī)固定車位用于分派后開門的車輛，雙向固定車位用于分派側開門或兩端開門的車輛。其構造如圖所示。文章所要解決的問題是如何調度不停到來的客戶車輛為其分派車位，使其能在最短的時間內完畢裝貨任務。車輛從進廠到裝完貨離開的這段時間我們稱為裝載時間，影響裝載時間的因素諸多，這里我們假設自動化立體倉庫有足夠大的出庫能力，即只要出庫口能夠裝完一盤貨品，自動化立體倉庫有足夠的能力立刻準備好另一盤貨。另外假設每個車上的裝卸工的裝卸速率都是均等的，這樣我們要研究的問題只與對不同顧客的車輛的調度次序有關。圖AS/RS出庫端銷售派車單銷售派車單是由各事業(yè)部的運管部根據銷售訂單下發(fā)，所涉及的重要信息有：出庫單號、倉庫、數量、品名規(guī)格、訂單號、訂單類型、車輛類型。其它信息涉及：定貨單位、收貨單位、收貨單位地址、聯系人、聯系電話、運輸方式、計劃達成日期等。司機達成蒙牛六期AS/RS出庫端后應先到儲運部登記，保管員按司機達成次序給司機帶來的銷售派車單據分派優(yōu)先級，分派原則是先來先分派。優(yōu)先級高的銷售派車單對應的車輛被優(yōu)先調度，被優(yōu)先下發(fā)出庫任務。具體流程圖以下所示：圖原車輛調度流程圖訂單的優(yōu)先級表達為了更加好的調度待裝貨車輛我們引入訂單動態(tài)優(yōu)先級的概念，根據裝貨車輛達成立體庫時所持銷售派車單的有關信息擬定銷售派車單的優(yōu)先級，以此擬定車輛調度的優(yōu)先級并為車輛分派車位。一種完整的銷售派車單重要信息以下：車輛類型（Vehicle-Type）：分為集裝箱（兩個側開門或兩端開門的車）和常規(guī)車（有一種后門的車）兩類。其中常規(guī)車分派在常規(guī)固定車位，集裝箱分派在雙向固定車位。訂單類型（Order-Type）：涉及外部調撥訂單、內部調撥訂單和銷售訂單。外部調撥訂單是集團內部不同事業(yè)部之間調撥產品時所用到的單據；內部調撥訂單是一種事業(yè)部的內部各廠之間調撥產品時所用到的單據；銷售訂單是客戶向我司訂購產品時所用到的單據，三者都是立體庫出庫口進行配貨的憑證，重要信息有：單據類型、倉庫號、品名規(guī)格、數量等。在本文的研究背景中外部調撥訂單和銷售訂單的優(yōu)先級同等看待。內部調撥優(yōu)先級高于前兩者。運輸方式（Transport-Type）：選擇何種運輸方式，能夠在