車(chē)輛調(diào)度及優(yōu)化方案

.word.zl-

.word.zl-

中文摘要

物流配送車(chē)輛調(diào)度問(wèn)題是指：在給定運(yùn)輸任務(wù)的條件下，如何派車(chē)、組織循

環(huán)運(yùn)輸，使空駛里程最少，運(yùn)輸本錢(qián)最低。目前我國(guó)大多數(shù)的物流企業(yè)運(yùn)輸資源

分配不均、配送路線(xiàn)安排不合理、運(yùn)力資源浪費(fèi)嚴(yán)重，而缺乏完善的物流配送車(chē)

輛調(diào)度優(yōu)化方案是造成此現(xiàn)象的重要因素之一。因此對(duì)物流配送車(chē)輛調(diào)度問(wèn)題的

研究具有重要的現(xiàn)實(shí)意義。

目前對(duì)單車(chē)場(chǎng)、封閉式物流配送車(chē)輛調(diào)度問(wèn)題研究較多，而對(duì)多車(chē)場(chǎng)開(kāi)放式

物流配送車(chē)輛調(diào)度問(wèn)題研究較少，但是多車(chē)場(chǎng)開(kāi)放式物流配送車(chē)輛調(diào)度問(wèn)題有很

強(qiáng)的應(yīng)用背景。本文針對(duì)此問(wèn)題，建立了一種靈活的多目標(biāo)組合優(yōu)化模型，設(shè)計(jì)

了適合多車(chē)場(chǎng)開(kāi)放式車(chē)輛路徑問(wèn)題的通用染色體編碼方案，并對(duì)遺傳算法中的穿

插變異操作做了詳細(xì)說(shuō)明。此模型可以方便的增減優(yōu)化目標(biāo)值，并通過(guò)測(cè)試用例

驗(yàn)證了本文設(shè)計(jì)的優(yōu)化模型和遺傳算法在解決多車(chē)場(chǎng)多目標(biāo)開(kāi)放式物流配送車(chē)

輛調(diào)度問(wèn)題中的可行性。

自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端車(chē)輛調(diào)度策略的設(shè)計(jì)是物流配送車(chē)輛調(diào)度中的一個(gè)

關(guān)鍵問(wèn)題，好的調(diào)度策略可以大大縮短出庫(kù)端的配貨時(shí)間。為此本文引入動(dòng)態(tài)優(yōu)

先級(jí)理論，并利用該理論對(duì)大型AS/RS出庫(kù)口車(chē)輛調(diào)度問(wèn)題進(jìn)展了深入研究與

分析，提出了基于動(dòng)態(tài)優(yōu)先級(jí)的AS/RS出庫(kù)端車(chē)輛調(diào)度策略，并開(kāi)發(fā)了相應(yīng)的

AS/RS出庫(kù)口發(fā)貨資源監(jiān)控系統(tǒng)，即AS/RS出庫(kù)口車(chē)輛調(diào)度系統(tǒng)，優(yōu)化了

AS/RS出庫(kù)端車(chē)輛調(diào)度策略，大大提高了物流配送當(dāng)中的配貨效率。

本文建立的多目標(biāo)組合優(yōu)化模型以及設(shè)計(jì)的遺傳算法求解方案，可以有效的

縮減物流配送中的送貨時(shí)間；設(shè)計(jì)的AS/RS出庫(kù)端車(chē)輛調(diào)度優(yōu)化策略及開(kāi)發(fā)的

AS/RS出庫(kù)端車(chē)輛調(diào)度系統(tǒng)，可以有效縮減車(chē)輛在出庫(kù)端的配貨時(shí)間。本文對(duì)以

上兩種物流配送中的車(chē)輛調(diào)度問(wèn)題進(jìn)展研究，大大提高了物流配送效率、減少了

物流配送本錢(qián)。

關(guān)鍵詞：物流配送；車(chē)輛調(diào)度；多目標(biāo)組合優(yōu)化；遺傳算法

第一章緒論

課題背景

物流(Logistics)：指在適宜時(shí)間，將適宜的物品以適當(dāng)?shù)臄?shù)量準(zhǔn)確地送到顧客

手中，它是供給鏈中最重要的組成局部。一般意義上是指在生產(chǎn)和生活中所涉及

的各種物質(zhì)實(shí)體由供給方向需求方的物理性轉(zhuǎn)移過(guò)程。這一概念將物流定義在有

用的物、供方、需方等幾個(gè)根本因素之上。也就是說(shuō)，我們通常所指的物流是指

人們?cè)谏a(chǎn)和生活中發(fā)生的有意義的物流行為。整個(gè)物流過(guò)程是一個(gè)物理過(guò)程，

只改變時(shí)間和空間的狀態(tài)，不改變其使用價(jià)值。其中，時(shí)間狀態(tài)的改變稱(chēng)之為倉(cāng)

儲(chǔ)、流通加工等活動(dòng)，空間狀態(tài)的改變稱(chēng)之為運(yùn)輸、搬倒等活動(dòng)。

物流配送是物流系統(tǒng)中的一個(gè)重要環(huán)節(jié)，它是指按客戶(hù)的訂貨要求，在物流

中心進(jìn)展分貨、配工作，并將配好的貨物及時(shí)送交收貨人的物流活動(dòng)。配送本錢(qián)

直接關(guān)系到物流企業(yè)和部門(mén)的效益，目前我國(guó)的大多數(shù)的物流企業(yè)運(yùn)輸資源分配

不均、配送路線(xiàn)安排不合理、運(yùn)力資源浪費(fèi)嚴(yán)重,根據(jù)中國(guó)倉(cāng)儲(chǔ)協(xié)會(huì)對(duì)146個(gè)企

業(yè)的調(diào)查顯示，用于運(yùn)輸?shù)馁M(fèi)用占整個(gè)物流費(fèi)用的比例分別為：在生產(chǎn)企業(yè)原料

物流中占58%，在生產(chǎn)企業(yè)成品物流中占73%，在商業(yè)物流中占52%。所以物流

配送車(chē)輛調(diào)度方案的合理優(yōu)化，對(duì)于整個(gè)物流運(yùn)輸速度、本錢(qián)、效益的影響至關(guān)

重要。

運(yùn)輸是指“物〞的長(zhǎng)距離的移動(dòng)，任何跨越空間的物質(zhì)實(shí)體的流動(dòng)，都可稱(chēng)

為運(yùn)輸。運(yùn)輸是物流的中心環(huán)節(jié)之一，被稱(chēng)為國(guó)民經(jīng)濟(jì)的動(dòng)脈和現(xiàn)代產(chǎn)業(yè)的支柱，

從社會(huì)經(jīng)濟(jì)的角度講，運(yùn)輸功能的發(fā)揮，縮小了物質(zhì)交流的空間，擴(kuò)大了社會(huì)經(jīng)

濟(jì)活動(dòng)的圍并實(shí)現(xiàn)在此圍價(jià)值的平均化、合理化。在社會(huì)經(jīng)濟(jì)的開(kāi)展中，運(yùn)輸?shù)?/p>

重要性己經(jīng)被人們所確認(rèn)，成為國(guó)民經(jīng)濟(jì)的命脈。

從物流系統(tǒng)的觀(guān)點(diǎn)來(lái)看，運(yùn)輸作業(yè)的關(guān)鍵因素包括運(yùn)輸本錢(qián)和運(yùn)輸速度兩個(gè)

方面。運(yùn)輸本錢(qián)：是指為兩個(gè)地理位置的運(yùn)輸所支付的款項(xiàng)，以及管理和維持轉(zhuǎn)

移中存貨的有關(guān)費(fèi)用，應(yīng)采用能把系統(tǒng)總本錢(qián)降低到最低限度的運(yùn)輸方式。運(yùn)輸

速度：是指為完成特定的運(yùn)輸作業(yè)所需花費(fèi)的時(shí)間。運(yùn)輸速度和本錢(qián)的關(guān)系，主

要表現(xiàn)在以下兩個(gè)方面：首先，運(yùn)輸商提供的效勞越快速，實(shí)際需要收取的費(fèi)用

也就越高。其次，運(yùn)輸效勞越快，轉(zhuǎn)移中的存貨就越少，可利用的運(yùn)輸間隔時(shí)間

越短。因此在選擇最合理的運(yùn)輸方式時(shí)，至關(guān)重要的問(wèn)題就是如何平衡其效勞的

速度和本錢(qián)。運(yùn)輸主要目的就是要以最低的時(shí)間、財(cái)務(wù)和環(huán)境資源本錢(qián)，將產(chǎn)品

從原產(chǎn)地轉(zhuǎn)移到規(guī)定地點(diǎn)。同時(shí)，產(chǎn)品轉(zhuǎn)移所采用的方式必須能滿(mǎn)足顧客有關(guān)交

付履行和裝運(yùn)信息的可得性等方面的要求。所以在物流系統(tǒng)中，必須準(zhǔn)確地維持

運(yùn)輸本錢(qián)和效勞質(zhì)量之間的平衡。低本錢(qián)運(yùn)輸和高質(zhì)量效勞是令人滿(mǎn)意的。

物流配送車(chē)輛調(diào)度就是研究怎樣合理運(yùn)輸?shù)膯?wèn)題，所謂合理運(yùn)輸就是在實(shí)現(xiàn)

物資產(chǎn)品實(shí)體從物流中心至消費(fèi)地轉(zhuǎn)移的過(guò)程中，充分有效地運(yùn)用各種運(yùn)輸工具

的運(yùn)輸能力，以最少的人、財(cái)、物消耗，及時(shí)、迅速、按質(zhì)、按量和平安的完成

運(yùn)輸任務(wù)。其標(biāo)志是：運(yùn)輸距離最短、運(yùn)輸環(huán)節(jié)最少、運(yùn)輸時(shí)間最短和運(yùn)輸費(fèi)用

最省。據(jù)統(tǒng)計(jì)運(yùn)輸費(fèi)約占整個(gè)物流費(fèi)用的40%，占銷(xiāo)售收入的2.88%。物流配送

車(chē)輛調(diào)度問(wèn)題就是指在給定運(yùn)輸任務(wù)的條件下，如何派車(chē)、組織循環(huán)運(yùn)輸，使空

駛里程最少，運(yùn)輸本錢(qián)最低。車(chē)輛調(diào)度是物流管理最重要的局部，正確合理的調(diào)

度可以有效減少車(chē)輛的空駛率，實(shí)現(xiàn)合理路徑運(yùn)輸，從而有效減少運(yùn)輸本錢(qián)，節(jié)

約運(yùn)輸時(shí)間，提高經(jīng)濟(jì)效益。

課題研究的意義

物流產(chǎn)業(yè)的開(kāi)展，將從整體上改變經(jīng)濟(jì)運(yùn)行的方式，提高經(jīng)濟(jì)運(yùn)行效率，對(duì)

增強(qiáng)國(guó)際競(jìng)爭(zhēng)力將起到巨大的推動(dòng)作用。我國(guó)國(guó)民經(jīng)濟(jì)的開(kāi)展呼喚物流的進(jìn)一步

開(kāi)展，對(duì)物流的開(kāi)展要求如下：

降低流通本錢(qián)在GDP中的比重：在我國(guó)目前工業(yè)企業(yè)生產(chǎn)中，直接勞

動(dòng)本錢(qián)占總本錢(qián)的比重不到10％，而物流費(fèi)用占商品總本錢(qián)的比重，從賬面反

映約為40％，全社會(huì)物流費(fèi)用支出約占GDP的20％，而其他興旺國(guó)家一般在

10%左右。這反映了我國(guó)物流系統(tǒng)落后，流通本錢(qián)太高，反映了我國(guó)國(guó)民經(jīng)濟(jì)運(yùn)

行質(zhì)量不高。通過(guò)開(kāi)展現(xiàn)代物流業(yè)來(lái)促進(jìn)物流合理化，降低流通本錢(qián)在GDP中

的比重，無(wú)疑將成為我國(guó)新的經(jīng)濟(jì)增長(zhǎng)點(diǎn)?！笆濞暺陂g，如果我國(guó)物流費(fèi)用降

低到占GDP的15％，每年將為社會(huì)直接節(jié)約2400億元的物流本錢(qián)。

減少企業(yè)流動(dòng)資金占用：我國(guó)工業(yè)企業(yè)和流通企業(yè)由于物流根底設(shè)施、

技術(shù)和管理的落后，原材料、半成品、成品積壓嚴(yán)重，大量流動(dòng)資金被占用，周

轉(zhuǎn)速度很慢，物流本錢(qián)過(guò)高。據(jù)統(tǒng)，1992年，國(guó)有獨(dú)資、控股工業(yè)企業(yè)流動(dòng)資

金占用1萬(wàn)多億元，周轉(zhuǎn)速度為1.62次/年；1999年，國(guó)有獨(dú)資、控股工業(yè)企

業(yè)流動(dòng)資金達(dá)31000億元，周轉(zhuǎn)速度僅1.2次/每年，與興旺國(guó)家相比非常落后。

如果工業(yè)企業(yè)把物流職能別離出來(lái)交給第三方物流企業(yè)，通過(guò)其先進(jìn)、科學(xué)的專(zhuān)

業(yè)化效勞，就可以減少流動(dòng)資金占用，提高核心競(jìng)爭(zhēng)能力，實(shí)現(xiàn)從粗放式經(jīng)營(yíng)向

集約式經(jīng)營(yíng)轉(zhuǎn)變。

電子商務(wù)的開(kāi)展需要物流做根底：電子商務(wù)是流通領(lǐng)域的一場(chǎng)革命，它

把3商品買(mǎi)賣(mài)虛擬成一個(gè)大的市場(chǎng)，使客戶(hù)在任何地點(diǎn)、任何時(shí)間都可以購(gòu)置商

品。但是，電子商務(wù)需要將網(wǎng)上訂的貨物及時(shí)送到可能在任何地方的客戶(hù)手里，

這就給物流系統(tǒng)帶來(lái)很大的挑戰(zhàn)。實(shí)際上，物流已經(jīng)成為電子商務(wù)開(kāi)展的瓶頸，

需要建立具有響應(yīng)性、靈活性和可視化的現(xiàn)代物流系統(tǒng)，需要第三方物流企業(yè)的

效勞。世界500強(qiáng)中相當(dāng)多的企業(yè)都是通過(guò)第三方物流來(lái)解決它的供給鏈與銷(xiāo)

售問(wèn)題的，很多跨國(guó)公司在歐洲、亞洲、美洲等地分別有不同的第三方物流企業(yè)

為他效勞。

現(xiàn)代物流產(chǎn)業(yè)的開(kāi)展，將減少由于低水平、條塊分割的物流方式造成的

巨大物耗：在傳統(tǒng)的物流框架下，一件商品從生產(chǎn)出來(lái)到最終的消費(fèi)環(huán)節(jié)，至少

要被搬倒、裝運(yùn)十幾次。實(shí)行社會(huì)化的多式聯(lián)運(yùn)、一單到底，物流過(guò)程中的物耗

至少可以減少幾倍。我國(guó)汽車(chē)空駛率達(dá)37％左右，意味著全國(guó)每年有150多萬(wàn)

輛載重汽車(chē)無(wú)活可干，這種潛在浪費(fèi)至少也在數(shù)千億元。按現(xiàn)代物流要求，合理

的流程設(shè)計(jì)可使空駛率降低到5％以下。

在現(xiàn)代物流集約化、一體化的開(kāi)展中，配送是直接與消費(fèi)者相連的重要環(huán)節(jié)，

其核心局部為配送車(chē)輛的集約、貨物配裝及送貨過(guò)程，而配送車(chē)輛優(yōu)化調(diào)度是物

流系統(tǒng)優(yōu)化、物流科學(xué)化的關(guān)鍵一環(huán)，是貨物從配送中心送達(dá)收貨人的過(guò)程。配

送首要解決的是車(chē)輛的調(diào)度問(wèn)題，幾十年來(lái)這一直是一個(gè)研究的熱點(diǎn)，在滿(mǎn)足和

完成各任務(wù)的前提下，正確合理的安排行車(chē)路線(xiàn)、提高配送車(chē)輛的利用率就可以

有效的節(jié)省時(shí)間從而減少運(yùn)輸本錢(qián)。另外對(duì)出庫(kù)口車(chē)輛調(diào)度問(wèn)題的研究，將有效

減少貨物裝配的時(shí)間。所以本文對(duì)物流配送車(chē)輛調(diào)度的研究具有重要意義。

國(guó)外研究現(xiàn)狀

車(chē)輛調(diào)度問(wèn)題最早是由Dantzig和Ramsert在上個(gè)世紀(jì)50年代末期提出，該

問(wèn)題一般稱(chēng)之為VehicleRoutingProblem(VRP)或者VehicleScheduling

Problem(VSP)現(xiàn)在我們將車(chē)輛調(diào)度問(wèn)題一律簡(jiǎn)稱(chēng)為

VRP

VRP提出后就很快

引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等

學(xué)科專(zhuān)家與運(yùn)輸方案制定者和管理者的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的

前沿與研究熱點(diǎn)問(wèn)題。各學(xué)科的專(zhuān)家對(duì)該問(wèn)題進(jìn)展了大量的理論研究及實(shí)驗(yàn)分

析，取得了很大進(jìn)展。

國(guó)外對(duì)物流配送車(chē)輛優(yōu)化調(diào)度問(wèn)題作了大量而深入的研究，例如早在1962

年，Balinski等人首先提出VRP的集分割，直接考慮可行解集合，在此根底上進(jìn)展優(yōu)化，建立了最簡(jiǎn)單的VRP模型；1964年，Clarke和Wright提出了一種啟發(fā)

式節(jié)約法來(lái)建立車(chē)隊(duì)配送路線(xiàn)；1968年，Rao等人在VRP集分割的根底上引入了列生成方法進(jìn)展求解，這種算法本質(zhì)上是最短路徑算法，同時(shí)結(jié)合了分枝定界

算法；1971年，Eilon等人提出將動(dòng)態(tài)規(guī)劃法用于固定車(chē)輛數(shù)的VRP,通過(guò)遞歸

方法求解；1981年，針對(duì)帶能力約束、時(shí)間窗以及無(wú)停留時(shí)間的VRP，F(xiàn)isher

提出了三下標(biāo)車(chē)輛流方程；Thangiah于1991和Joe于l993分別用遺傳算法求解

VRP,但是都存在“早熟收斂〃的問(wèn)題；2001年，Tan,Lee,Du結(jié)合遺傳算法、tabu樹(shù)搜索算法的優(yōu)點(diǎn)，形成知識(shí)庫(kù)，用人工智能的方法來(lái)求解；2002年，Taranrilis,Kiranondis使用空間決策支持系統(tǒng)來(lái)解決車(chē)輛路徑問(wèn)題。

在國(guó),有關(guān)車(chē)輛調(diào)度問(wèn)題的研究是在20世紀(jì)90年代以后才逐漸興起的，比國(guó)

外相對(duì)落后。國(guó)研究對(duì)象主要是旅行商問(wèn)題(TravelingSalesmanProblem,簡(jiǎn)稱(chēng)TSPb中國(guó)郵遞員問(wèn)題(ChinesePostmanProblem簡(jiǎn)稱(chēng)CPP)、有向中國(guó)郵遞員問(wèn)題(DirectedChinesePostmanProblem簡(jiǎn)稱(chēng)DCPP)等，系統(tǒng)性研究還很少見(jiàn)到。西南交通大學(xué)的軍教授和郭耀煌教授對(duì)車(chē)輛優(yōu)化調(diào)度的根底理論及各類(lèi)問(wèn)題進(jìn)展

了系統(tǒng)的研究；大為等以TSP的最近距離啟發(fā)式為根底，通過(guò)設(shè)置評(píng)價(jià)函數(shù)來(lái)

處理時(shí)間窗約束，求解了簡(jiǎn)單的VRP。另外在利用現(xiàn)代優(yōu)化算法（如:遺傳算法、

神經(jīng)網(wǎng)絡(luò)方法、模擬退火等）對(duì)簡(jiǎn)單TSP的求解取得了一定成果。蔡延光等應(yīng)用

模擬退火法針對(duì)滿(mǎn)載問(wèn)題進(jìn)展了求解?？傮w來(lái)說(shuō)，目前我國(guó)對(duì)車(chē)輛調(diào)度問(wèn)題的理

論研究仍相對(duì)薄弱，需要進(jìn)一步研究。

本文容的安排

本課題的研究以蒙牛乳業(yè)股份（集團(tuán)）的物流配送業(yè)務(wù)為背景，主要研究?jī)煞?/p>

面容：首先，對(duì)多車(chē)場(chǎng)多目標(biāo)開(kāi)放式物流配送車(chē)輛調(diào)度問(wèn)題做了研究，以此可以

優(yōu)化對(duì)客戶(hù)的派車(chē)問(wèn)題及最正確車(chē)輛路徑的選擇問(wèn)題。其次，對(duì)AS/RS出庫(kù)端

車(chē)輛調(diào)度策略做了研究，以本文建立的策略對(duì)出庫(kù)口的車(chē)輛分配車(chē)位，可以減少

車(chē)輛的配貨時(shí)間。本文的研究將在最大程度上減少蒙牛集團(tuán)的運(yùn)輸本錢(qián)，給蒙牛

集團(tuán)帶來(lái)可觀(guān)的經(jīng)濟(jì)效益。本文研究的具體容如下：

第一章緒論：介紹了本文研究的背景以及研究的目的與意義，并對(duì)國(guó)外對(duì)車(chē)

輛調(diào)度問(wèn)題的研究現(xiàn)狀作了簡(jiǎn)單介紹。

第二章車(chē)輛調(diào)度問(wèn)題概述：首先對(duì)物流配送車(chē)輛調(diào)度問(wèn)題進(jìn)展了描述，其次

介紹了車(chē)輛調(diào)度問(wèn)題的構(gòu)成要素和車(chē)輛調(diào)度問(wèn)題的分類(lèi)，最后列舉了車(chē)輛調(diào)度的

相關(guān)求解算法。

第三章遺傳算法概述：首先對(duì)GA的背景作了簡(jiǎn)單的介紹，接著對(duì)GA算法

的根本概念、工作流程和算法的組成做了詳細(xì)描述。

第四章用遺傳算法解決多車(chē)場(chǎng)多目標(biāo)開(kāi)放式車(chē)輛調(diào)度問(wèn)題：首先介紹了兩種

求解多車(chē)場(chǎng)車(chē)輛調(diào)度的方法，然后對(duì)多車(chē)場(chǎng)多目標(biāo)開(kāi)放式車(chē)輛調(diào)度問(wèn)題的研究背

景進(jìn)展了描述，在此根底上確定了多車(chē)場(chǎng)多目標(biāo)開(kāi)放式車(chē)輛調(diào)度問(wèn)題的數(shù)學(xué)模

型，并詳細(xì)描述了用遺傳算法對(duì)多車(chē)場(chǎng)多目標(biāo)開(kāi)放式車(chē)輛調(diào)度問(wèn)題的求解過(guò)程，

最后用實(shí)例證明了用遺傳算法求解此問(wèn)題的可行性。

第五章對(duì)AS/RS出庫(kù)端車(chē)輛調(diào)度策略做了研究，提出了基于動(dòng)態(tài)優(yōu)先級(jí)的

AS/RS出庫(kù)端車(chē)輛調(diào)度策略，并開(kāi)發(fā)了相應(yīng)的AS/RS出庫(kù)端發(fā)貨資源監(jiān)控系統(tǒng)，

即AS/RS出庫(kù)口車(chē)輛調(diào)度系統(tǒng)，以此策略對(duì)出庫(kù)口的車(chē)輛分配車(chē)位,可以減少車(chē)

輛的配貨時(shí)間。

第六章總結(jié)與展望：歸納與總結(jié)了本文的創(chuàng)新之處，并提出進(jìn)一步研究車(chē)輛

調(diào)度問(wèn)題的方向。

第二章車(chē)輛調(diào)度問(wèn)題概述

車(chē)輛調(diào)度問(wèn)題的描述

“配送〞一詞是日本引進(jìn)美國(guó)物流學(xué)時(shí)，對(duì)英文單詞delivery一詞的意譯，

我國(guó)轉(zhuǎn)學(xué)于日本，也直接用了“配送〞這個(gè)詞。配送是物流系統(tǒng)中由運(yùn)輸派生出

的功能，是短距離的運(yùn)輸。具有：①配送距離較短，位于物流系統(tǒng)的最末端，處

于支線(xiàn)運(yùn)輸、二次運(yùn)輸和末端運(yùn)輸?shù)奈恢?。②在配送中，也包含著其他的物流?/p>

能，是多種功能的組合。③配送是物流系統(tǒng)的縮影，也可以說(shuō)是一個(gè)小圍的物流

系統(tǒng)。從物流來(lái)講，配送幾乎包括了所有物流的要素，車(chē)輛調(diào)度就是其中一個(gè)最

重要且有意義的要素，所以本文研究的是物流配送車(chē)輛調(diào)度問(wèn)題。

物流配送車(chē)輛調(diào)度優(yōu)化問(wèn)題最早是由Dentzing和Ramse依1959年第一次提

出的。從此，車(chē)輛調(diào)度優(yōu)化問(wèn)題很快引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與

網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科的專(zhuān)家與運(yùn)輸方案制定者的極大重視，

同時(shí)也逐漸成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)研究問(wèn)題。由于它應(yīng)用的廣泛性和

經(jīng)濟(jì)上的重大價(jià)值，一直受到國(guó)外學(xué)者的廣泛關(guān)注。國(guó)外將物流配送車(chē)輛優(yōu)化調(diào)

度問(wèn)題歸結(jié)為或稱(chēng)之為VehicleRoutingProblem^口VehicleSchedulingProblem本

課題采用的是后者，也就是將車(chē)輛調(diào)度問(wèn)題歸結(jié)為VSP問(wèn)題：VehicleScheduling

Problem。

物流配送車(chē)輛調(diào)度問(wèn)題的一般性定義是：物流配送車(chē)輛調(diào)度問(wèn)題是把一系列

的裝貨點(diǎn)和〔或〕卸貨點(diǎn)，有機(jī)的組織起來(lái)，形成一系列行車(chē)線(xiàn)路，使待調(diào)度車(chē)

輛能夠高效、節(jié)能且有序地通過(guò)這些點(diǎn)。當(dāng)然，這種組織方式是應(yīng)該在滿(mǎn)足一定

的約束條件〔例如：用戶(hù)對(duì)貨物的需求量、一次性發(fā)貨量、應(yīng)交發(fā)貨時(shí)間、單個(gè)

車(chē)場(chǎng)的車(chē)輛容量限制、路程約束、時(shí)間限制等〕，最終到達(dá)縮短里程、減少開(kāi)支

費(fèi)用、縮短運(yùn)輸時(shí)間、使用車(chē)輛數(shù)盡量少等優(yōu)化目標(biāo)。

物流配送車(chē)輛調(diào)度問(wèn)題一般研究的是在配送中心及用戶(hù)位置均、資源及運(yùn)輸

能力充分、各用戶(hù)需求量己知的前提下，如何合理、高效、低本錢(qián)的解決分配與

運(yùn)送的問(wèn)題，也就是說(shuō)如何將貨物從配送中心按照一定的要求發(fā)送到假設(shè)干個(gè)用

戶(hù)點(diǎn)。配送方案應(yīng)該包括兩個(gè)相關(guān)的環(huán)節(jié)：①有哪些用戶(hù)要被分配到一條回路上，

即有哪些用戶(hù)的貨物應(yīng)該安排在同一輛車(chē)上；②每條配送路線(xiàn)上用戶(hù)的連接順

序。物流配送車(chē)輛調(diào)度的最優(yōu)解實(shí)際上是一個(gè)效率最高的運(yùn)輸方案，它應(yīng)明確的

規(guī)定應(yīng)派出的車(chē)輛型號(hào)、車(chē)輛數(shù)以及每輛車(chē)的具體行車(chē)路線(xiàn)。實(shí)施這一配送方案，

即可以滿(mǎn)足用戶(hù)的需求，又可以使總的運(yùn)輸行程最短。

車(chē)輛調(diào)度問(wèn)題的構(gòu)成要素

物流配送車(chē)輛調(diào)度問(wèn)題主要包括貨物、車(chē)輛、配送中心、客戶(hù)、運(yùn)輸網(wǎng)絡(luò)、

約束條件、和目標(biāo)函數(shù)等要素。

貨物

貨物是我國(guó)交通運(yùn)輸領(lǐng)域中的一個(gè)特有專(zhuān)用概念，交通運(yùn)輸領(lǐng)域?qū)⑵浣?jīng)營(yíng)的

對(duì)象分為兩大類(lèi)：一類(lèi)是人，一類(lèi)是物?！拔铷曔@一類(lèi)的運(yùn)輸目標(biāo)統(tǒng)稱(chēng)為貨物。

我們這里所說(shuō)的貨物是指物流配送的對(duì)象，每批貨物都包括品名、包裝、重量、

體積、要求送到(或取走)的時(shí)間和地點(diǎn)，能否分批配送等屬性。

車(chē)輛

車(chē)輛是“車(chē)〞與車(chē)的單位“輛〞的總稱(chēng)。所謂車(chē)，是指陸地上用輪子轉(zhuǎn)動(dòng)的

交通工具；所謂輛，來(lái)源于古代對(duì)車(chē)的計(jì)量方法。本文所說(shuō)的車(chē)輛是指運(yùn)載貨物

的工具，車(chē)輛的主要屬性包括：類(lèi)型、工作時(shí)間、配送前的停放位置、載重量以

及配送任務(wù)完成后的停放位置等。

配送中心

配送中心是指承受供給者所提供的多品種、小批量的貨物，通過(guò)存儲(chǔ)、保管、

分揀、配貨以及流通加工、信息處理等作業(yè)后，將按需要者訂貨要求配齊的貨物

送交顧客的組織機(jī)構(gòu)和物流設(shè)施。本文所說(shuō)的配送中心是指從事配送業(yè)務(wù)的物流

場(chǎng)所或組織，如可以進(jìn)展貨物集中、分揀、配貨、送貨等的倉(cāng)庫(kù)、車(chē)站、港口等

固定場(chǎng)所。在物流配送系統(tǒng)中，配送中心可以只有一個(gè)，也可以同時(shí)具有多個(gè)。

配送中心專(zhuān)業(yè)性強(qiáng)，和客戶(hù)有固定的配送關(guān)系，一般實(shí)行方案配送，需配送的商

品有一定的庫(kù)存量，一般情況很少超越自己的經(jīng)營(yíng)圍。配送中心的設(shè)施及工藝流

程是根據(jù)配送需要專(zhuān)門(mén)設(shè)計(jì)的，所以配送能力很強(qiáng)，配送距離較遠(yuǎn)，配送的品種

較多，配送數(shù)量比擬大。使用配送中心配送覆蓋面寬，規(guī)模大，因此，必須有一

套配套的大規(guī)模實(shí)施配送的設(shè)施。本文的研究背景就是基于配送中心的物流配送

中車(chē)輛調(diào)度問(wèn)題的研究。

客戶(hù)

客戶(hù)指的是物流配送的效勞對(duì)象，可以是各種零售店，也可以是分倉(cāng)庫(kù)，還

可以是別的倉(cāng)庫(kù)的外調(diào)。也就是說(shuō)客戶(hù)是有配送任務(wù)的對(duì)象的統(tǒng)稱(chēng)。客戶(hù)的屬性

包括需求數(shù)量、需求時(shí)間、需求次數(shù)及目前需求的滿(mǎn)足動(dòng)態(tài)等。8

運(yùn)輸網(wǎng)絡(luò)

本文的運(yùn)輸網(wǎng)絡(luò)采用了離散數(shù)學(xué)中對(duì)網(wǎng)的介紹，配送中心、客戶(hù)、停車(chē)場(chǎng)等

構(gòu)成網(wǎng)絡(luò)的頂點(diǎn)、它們之間的交互運(yùn)輸構(gòu)成了無(wú)向邊，具體的運(yùn)輸任務(wù)被稱(chēng)為由

有向弧組成的運(yùn)輸?shù)木W(wǎng)絡(luò)。邊、弧的屬性包括方向、權(quán)值和交通流量限制等。在

運(yùn)輸網(wǎng)絡(luò)中，邊或弧具有一定的權(quán)值，該值可以表示為距離、時(shí)間或費(fèi)用。邊或

弧的權(quán)值變化具有以下幾種情況：固定不變，不隨著時(shí)間和車(chē)輛的不同而變化；

隨時(shí)間段或者車(chē)輛不同而變化；既隨著時(shí)間的不同而變化，又隨著車(chē)輛的不同而

變化。對(duì)運(yùn)輸網(wǎng)絡(luò)中的定點(diǎn)、邊或弧的交通流量要求分為以下幾種情況：無(wú)流量

限制；邊、弧限制，即每條邊、弧上同時(shí)行駛的車(chē)輛數(shù)有限；頂點(diǎn)限制，即每個(gè)

頂點(diǎn)上同時(shí)裝、卸貨的車(chē)輛數(shù)有限；邊、弧、頂點(diǎn)都有限制。

約束條件

物流配送車(chē)輛調(diào)度問(wèn)題應(yīng)滿(mǎn)足以下約束條件：能夠滿(mǎn)足所有客戶(hù)對(duì)貨物品

種、規(guī)格、數(shù)量的要求；能夠在客戶(hù)要求或者承受的時(shí)間將貨物送到；運(yùn)輸車(chē)輛

每天的運(yùn)行時(shí)間、運(yùn)行歷程都要有一定的限制，不能超過(guò)預(yù)定的時(shí)間或者里程；

在物流配送過(guò)程中實(shí)際裝載的貨物不能超過(guò)車(chē)輛的最大載重要求，也就是不能超

載；當(dāng)然，客戶(hù)的需求也必須在物流中心現(xiàn)有的運(yùn)力圍，也就是目前有這個(gè)能力

去完成待完成的任務(wù)。

目標(biāo)函數(shù)

目標(biāo)函數(shù)是指所關(guān)心的目標(biāo)(某一變量)與相關(guān)的因素(某些變量)的函數(shù)關(guān)

系。簡(jiǎn)單的說(shuō)，就是你求解后所得出的那個(gè)函數(shù)。在求解前函數(shù)是未知的，按照

你的思路將條件利用起來(lái)，去求解未知量的函數(shù)關(guān)系式，即為目標(biāo)函數(shù)。本課題研究的物流配送車(chē)輛調(diào)度問(wèn)題，可以只選用一個(gè)目標(biāo)，也可以同時(shí)選用多個(gè)目標(biāo)。

使用概率比擬多的目標(biāo)函數(shù)主要有：

①配送的距離最短，也就是在配送過(guò)程中車(chē)輛所走的路程最短。在實(shí)際的物

流配送中，配送里程直接關(guān)系到配送車(chē)輛的耗油量、磨損程度以及司機(jī)疲勞程度

等因素。因此，在眾多的目標(biāo)函數(shù)中選擇配送里程最短的目標(biāo)，在某種程度上可

以直接減少運(yùn)輸本錢(qián)。

②配送車(chē)輛的載重量與公里數(shù)最少，這種方式的目標(biāo)是將配送距離與車(chē)輛的

載重量進(jìn)展了有機(jī)結(jié)合，綜合來(lái)考慮載重量與配送距離之間的關(guān)系，以到達(dá)最優(yōu)

化的配置，是比擬常用的目標(biāo)之一。9

③綜合費(fèi)用最低，完成最多的任務(wù)，花最少的本錢(qián)，這是物流配送中的一個(gè)

根本原那么。降低各項(xiàng)開(kāi)支的綜合費(fèi)用是實(shí)現(xiàn)物流配送業(yè)務(wù)中取得良好經(jīng)濟(jì)效益

的根本要求。在物流配送中，與配送相關(guān)的費(fèi)用包括：車(chē)輛維護(hù)費(fèi)用、車(chē)輛耗油

費(fèi)用、車(chē)隊(duì)管理費(fèi)用、裝卸工所需費(fèi)用、各部門(mén)人員工資費(fèi)用等。

④準(zhǔn)時(shí)完成任務(wù)，無(wú)論是分倉(cāng)庫(kù)還是分銷(xiāo)點(diǎn)，各種用戶(hù)都對(duì)需求的交貨時(shí)間

有著嚴(yán)格的要求。配送任務(wù)完成的準(zhǔn)時(shí)性，很大程度上決定了配送公司在客戶(hù)心

中的地位，決定了公司的信譽(yù)度。各種本錢(qián)雖然是必須考慮的因素，也是最實(shí)際

的因素，但是為提高配送效勞質(zhì)量，按時(shí)完成用戶(hù)的需求，有時(shí)需要將準(zhǔn)時(shí)性最

高作為配送路線(xiàn)的目標(biāo)。

⑤使用的車(chē)輛數(shù)最少，該目標(biāo)考慮的是使用盡量少的車(chē)輛去完成指定的配送

任務(wù)。前面的目標(biāo)表達(dá)了各項(xiàng)指標(biāo)的要求，但是如果車(chē)輛跑的距離最短、也是按

時(shí)到達(dá)的，但是使用的車(chē)輛都沒(méi)有滿(mǎn)載，這無(wú)疑也是對(duì)資源的一種浪費(fèi)，也不能

是整體配送效益到達(dá)最優(yōu)，所以必須要求車(chē)輛的滿(mǎn)載率最高，以充分利用車(chē)輛的

.word.zl-

.word.zl-

. .word.zl-

裝載能力。

⑥勞動(dòng)消耗最低，充分考慮人的因素。也就是使用最少的司機(jī)數(shù)，這當(dāng)然和

前面使用最少的車(chē)輛數(shù)是一致的，只有車(chē)輛少了，司機(jī)才會(huì)少，只有車(chē)輛都裝滿(mǎn)

了，才會(huì)使用最少的車(chē)輛。只有選擇的距離最短了，司機(jī)才能工作最短的時(shí)間，

這些都是重要的目標(biāo)值。

車(chē)輛調(diào)度問(wèn)題的分類(lèi)

車(chē)輛調(diào)度問(wèn)題(Visual-ScheduleProblemVSP液提出后，國(guó)外各學(xué)科的學(xué)者從

不同角度對(duì)它進(jìn)展了各種研究，并各自按不同的標(biāo)準(zhǔn)對(duì)其進(jìn)展了分類(lèi)。綜合起來(lái)

可分為以下幾種：

按車(chē)場(chǎng)數(shù)目分：有單車(chē)場(chǎng)車(chē)輛調(diào)度問(wèn)題和多車(chē)場(chǎng)車(chē)輛調(diào)度問(wèn)題。單車(chē)場(chǎng)

問(wèn)題指配送系統(tǒng)中僅有一個(gè)配送中心，多車(chē)場(chǎng)車(chē)輛調(diào)度問(wèn)題指配送系統(tǒng)中存在多

個(gè)配送中心。

按配送任務(wù)特征分：分為純送貨問(wèn)題、純?nèi)∝泦?wèn)題以及取送混合問(wèn)題。

其中純送貨問(wèn)題指僅僅考慮從物流中心向客戶(hù)送貨，而不考慮從用戶(hù)向配送中心

送貨；純?nèi)∝泦?wèn)題指單純考慮把各客戶(hù)供給的貨物取到配送中心不考慮配送中心

給客戶(hù)供貨問(wèn)題；取送混合問(wèn)題是上面兩者的有機(jī)組合，既要考慮將客戶(hù)需求的

貨物從物流中心送到各個(gè)客戶(hù)，同時(shí)還考慮將客戶(hù)提供的貨物從客戶(hù)取到物流中

心。

按車(chē)輛載貨狀況分：分為滿(mǎn)載問(wèn)題、非滿(mǎn)載問(wèn)題以及滿(mǎn)載和非滿(mǎn)載混合

問(wèn)題。10滿(mǎn)載問(wèn)題指的是貨運(yùn)量不小于車(chē)輛容量，完成一項(xiàng)任務(wù)需要不少于一

輛車(chē)；非滿(mǎn)載問(wèn)題指的是貨運(yùn)量小于車(chē)輛容量，多項(xiàng)貨物合用一輛車(chē)，在實(shí)際的

車(chē)輛配送過(guò)程中經(jīng)常會(huì)出現(xiàn)這種處于非滿(mǎn)載的狀態(tài)；滿(mǎn)載和非滿(mǎn)載混合問(wèn)題是上

述兩者的有機(jī)組合，既存在一局部客戶(hù)需求和供給的貨物數(shù)量大于或等于車(chē)輛的

載重量，同時(shí)又存在另一局部客戶(hù)需求量或供給的貨物數(shù)量小于車(chē)輛的載重量，

上述情況就造成一局部配送車(chē)輛滿(mǎn)載運(yùn)行，而另一局部運(yùn)行在非滿(mǎn)載的狀態(tài)。

按客戶(hù)對(duì)貨物處理時(shí)間的要求分：分為無(wú)時(shí)間約束問(wèn)題和有時(shí)間約束問(wèn)

題。其中無(wú)時(shí)間約束問(wèn)題指的是客戶(hù)對(duì)貨物的取走和送到的時(shí)間沒(méi)有嚴(yán)格的要

求；有時(shí)間約束問(wèn)題指的是客戶(hù)要求將其需求的貨物在一定的時(shí)間圍送到，并且

將供給的貨物在一定的時(shí)間圍取走。有時(shí)間約束問(wèn)題又分為硬時(shí)間窗問(wèn)題和軟時(shí)

間窗問(wèn)題，硬時(shí)間窗問(wèn)題指的是對(duì)任務(wù)的完成有硬性的時(shí)間限制，或者說(shuō)時(shí)間要

求。軟時(shí)間窗問(wèn)題指的是有一定的時(shí)間約束，但是相比照擬寬松，盡量在用戶(hù)規(guī)

定的時(shí)間圍將貨物送到或者取走，但是如果超越了規(guī)定的時(shí)間限制可能要有一定

的處分機(jī)制。

按車(chē)輛類(lèi)型分：分為單車(chē)型問(wèn)題和多車(chē)型問(wèn)題。單車(chē)型問(wèn)題指所有配送

車(chē)輛類(lèi)型和容量一樣，這種情況方便統(tǒng)一管理和裝卸。多車(chē)型問(wèn)題指在執(zhí)行任務(wù)

過(guò)程中的配送車(chē)輛類(lèi)型和容量不完全一樣，這種情況處理起來(lái)比擬復(fù)雜。

按車(chē)輛對(duì)車(chē)場(chǎng)所屬關(guān)系分：分為開(kāi)放式車(chē)輛調(diào)度問(wèn)題和封閉式車(chē)輛調(diào)度

問(wèn)題。開(kāi)放式車(chē)輛調(diào)度問(wèn)題指的是車(chē)輛完成配送任務(wù)后可以不返回其原來(lái)發(fā)出車(chē)

場(chǎng)；封閉式車(chē)輛調(diào)度問(wèn)題指的是車(chē)輛完成配送任務(wù)后必須返回其原來(lái)發(fā)出車(chē)場(chǎng)。

本課題是針對(duì)開(kāi)放式車(chē)輛調(diào)度問(wèn)題進(jìn)展的研究。

按優(yōu)化目標(biāo)數(shù)分：分為單目標(biāo)問(wèn)題和多目標(biāo)問(wèn)題。單目標(biāo)問(wèn)題指的是僅

考慮一個(gè)配送目標(biāo)；而多目標(biāo)問(wèn)題指的是同時(shí)考慮多個(gè)配送目標(biāo)。

車(chē)輛調(diào)度的相關(guān)求解算法

用于解決物流配送車(chē)輛調(diào)度問(wèn)題的算法分為：準(zhǔn)確算法和啟發(fā)式算法兩大

類(lèi)，準(zhǔn)確算法一般用于解決小規(guī)模的VRP問(wèn)題，車(chē)輛調(diào)度問(wèn)題應(yīng)用最為廣泛的

算法是啟發(fā)式算法，啟發(fā)式算法并不追求問(wèn)題的最優(yōu)解，而是強(qiáng)調(diào)問(wèn)題解的滿(mǎn)意

性。所以，啟發(fā)式算法對(duì)于大規(guī)模的車(chē)輛調(diào)度問(wèn)題能在較短的時(shí)間獲得較滿(mǎn)意的

次優(yōu)解，并且這些算法的通用性也很強(qiáng)。常見(jiàn)的啟發(fā)式算法有如下幾種：

C-WSaving^法

C-WSavings算法采用了幾何中三角形的邊定理，即三角形的兩邊之和大于

第三邊。當(dāng)路徑中有這樣的兩個(gè)邊時(shí)用第三邊來(lái)代替，以到達(dá)節(jié)約配送距離的目

的。我們可以設(shè)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的節(jié)約量為Sij,這兩點(diǎn)和節(jié)點(diǎn)o之間的距離

為Doi和Doj,那么Sij=Doi+Doj-Dij〔iwj,i,j=1,2,,算汨苜先求出所有Sij,

并按非增順序排列。然后從最大的Sij開(kāi)場(chǎng)，確定是否存在兩條路徑，其中一條

從弧(0,j)開(kāi)場(chǎng)，而另一條以(i,o)完畢。如果存在，那么去掉弧(0,j)、(i,o),引入弧

(j,i)合并這兩條路徑。重復(fù)上述過(guò)程直到?jīng)]有路徑可以合并。

⑵SweepB^

Sweep?法是一種“先分組后路線(xiàn)〃的算法。所謂的分組就是：首先計(jì)算出

要訪(fǎng)問(wèn)的顧客的位置的極坐標(biāo)，并把這些極坐標(biāo)按角度大小排序，然后在未分配

到任何路徑中的顧客中從角度最小的顧客開(kāi)場(chǎng)，依次將顧客歸并到相應(yīng)的路徑

中，直到車(chē)輛的能力約束滿(mǎn)足為止，再重新選擇新的車(chē)輛，重復(fù)上述過(guò)程，直到

所有的顧客都分配完畢。最后利用TSP的優(yōu)化算法對(duì)各子路經(jīng)進(jìn)展優(yōu)化。

ClusterandRoutes法

一般有兩種方法：先聚類(lèi)后排序方法(CFRS和先排序后聚類(lèi)方法(RFCS)

CFRS最早由G.Gillett等提出，它是先用啟發(fā)式方法將節(jié)點(diǎn)分成假設(shè)干路徑，然后對(duì)路徑中的點(diǎn)進(jìn)展排序。RFCS由Besley?出，它先對(duì)所有節(jié)點(diǎn)進(jìn)展TSP排序,然后將大的路徑分成假設(shè)干個(gè)小路徑。

遺傳算法GA

遺傳算法使用群體搜索技術(shù)，借用適者生存規(guī)律進(jìn)展局部搜索改良，它通過(guò)

對(duì)當(dāng)前群體施加選擇、穿插、變異等一系列遺傳操作，從而產(chǎn)生出新一代的群體，

每一次進(jìn)化那么對(duì)應(yīng)解的一次迭代，并逐步使群體進(jìn)化到包含或接近最優(yōu)解的狀

體。當(dāng)?shù)螖?shù)到達(dá)最大次數(shù)限制或群體中的個(gè)體無(wú)顯著差異時(shí)，迭代終止。

J.Lawrencel1先將GA應(yīng)用于求解車(chē)輛調(diào)度問(wèn)題。

禁忌搜索算法TS

TS的思想由Glover最早提出，它通過(guò)對(duì)避開(kāi)一些局部最優(yōu)解，到達(dá)接納一

局部較差解，從而跳出局部搜索的目的。TS是對(duì)局部鄰域搜索的一種擴(kuò)展，是

一種全局逐步尋優(yōu)算法，是對(duì)人類(lèi)思維過(guò)程的一種模擬。禁忌搜索算法通過(guò)利用

一個(gè)禁忌表記錄已經(jīng)到達(dá)過(guò)的局部最優(yōu)點(diǎn)，并在后面的搜索中，根據(jù)某種限制循

環(huán)的規(guī)那么和禁忌表中記錄的信息在當(dāng)前搜索鄰域中取一個(gè)適宜的解。

模擬退火算法SA

其思想最早有Metropolis1953年提出，Osman于1993年用之解決VRP。模

擬退火算法用固體退火模擬組合優(yōu)化問(wèn)題，將能模擬為目標(biāo)函數(shù)值，溫度演化成

控制參數(shù)。由初始解和控制參數(shù)初值開(kāi)場(chǎng)，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解-計(jì)算目標(biāo)函數(shù)差-承受或舍棄〃的迭代，并逐步衰減控制參數(shù)值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。

蟻群優(yōu)化算法ACO

蟻群算法模擬了蟻群搜索食物的行為。螞蟻在尋找食物時(shí)，會(huì)在它所經(jīng)過(guò)的

路徑排放一種外激素(pheromone,在算法中稱(chēng)為信息素)作為標(biāo)記，排放的量那

么根據(jù)路徑長(zhǎng)度和食物的等級(jí)決定。這些外激素可以指導(dǎo)螞蟻的運(yùn)動(dòng)方向，并使

蟻群朝著外激素強(qiáng)度高的方向移動(dòng)。在用蟻群算法解決車(chē)輛調(diào)度問(wèn)題時(shí)，可根據(jù)

優(yōu)化的目標(biāo)函數(shù)個(gè)數(shù)，構(gòu)造多組相互協(xié)作的人工蟻群，使各組分別優(yōu)化其中的一

個(gè)目標(biāo)函數(shù)，并以共用解的方式建立協(xié)作關(guān)系。在以上求解VRP的算法中，有

的算法利用全局信息進(jìn)展整體搜索適合構(gòu)解，如GA等；還有的利用局部信息，

適合改良解，如SA、TS等。每種方法都各有所長(zhǎng)與缺乏，一般來(lái)說(shuō)，根據(jù)具體

的求解問(wèn)題，采用兩種或兩種以上的混合方法，能夠得到更好的解。

小結(jié)

本章從車(chē)輛調(diào)度根本理論的角度，首先介紹了車(chē)輛調(diào)度涉及到的根本概念，

包括了問(wèn)題的描述和構(gòu)成要素。其次對(duì)車(chē)輛調(diào)度問(wèn)題的分類(lèi)進(jìn)展的描述，列舉了

一些相關(guān)解決車(chē)輛調(diào)度問(wèn)題的算法。

第三章遺傳算法概述

背景介紹

遺傳算法(GeneticAIgorithm.GA)是由美國(guó)Michigan大學(xué)J.Holland教授和他

的學(xué)生開(kāi)展建立的一類(lèi)借鑒生物界的進(jìn)化規(guī)律—適者生存、優(yōu)勝劣汰遺傳機(jī)制

演化而來(lái)的概率搜索算法。GA算法是近幾年開(kāi)展起來(lái)的一種嶄新的全局優(yōu)化算

法，遺傳算法作為一種非數(shù)值并行算法，其思想起源于生物遺傳學(xué)適者生存的自

然規(guī)律，通過(guò)自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)體適應(yīng)性的提高。它

是多學(xué)科結(jié)合與滲透的產(chǎn)物，已經(jīng)開(kāi)展成一種自組織、自適應(yīng)的綜合技術(shù)，廣泛

應(yīng)用在計(jì)算機(jī)科學(xué)、工程技術(shù)和社會(huì)科學(xué)等領(lǐng)域。

GA算法是通過(guò)對(duì)自然進(jìn)化現(xiàn)象的模擬，利用簡(jiǎn)單的編碼技術(shù)和進(jìn)化機(jī)制來(lái)

解決復(fù)雜的優(yōu)化問(wèn)題。特別是由于它不受搜索空間的限制性假設(shè)的約束，不必要

.word.zl-

.word.zl-

. .word.zl-

求諸如連續(xù)性、導(dǎo)數(shù)存在等假設(shè)，以及其固有的并行性。它是一種以自然選擇和遺傳理論為根底，將生物進(jìn)化過(guò)程中適者生存規(guī)那么與同一群染色體的隨機(jī)信息

變換機(jī)制相結(jié)合的搜索算法，其通過(guò)給解向量編碼，形成初始種群，然后用變異、

穿插、重組、自然選擇等算子，進(jìn)展并行迭代求得優(yōu)化解。

由于遺傳算法具有不依賴(lài)于問(wèn)題模型采用隨機(jī)運(yùn)算，對(duì)搜索空間無(wú)特殊要

求、無(wú)需求導(dǎo)，具有全局最優(yōu)性求解能力、隱含并行性、收斂速度快以及能高效

率地解決不同非線(xiàn)性問(wèn)題的魯棒性的特點(diǎn)。因此近年來(lái)有很快的開(kāi)展，在組合優(yōu)

化、自適應(yīng)控制、機(jī)器學(xué)習(xí)等許多領(lǐng)域獲得應(yīng)用，并在電氣自動(dòng)化、計(jì)算機(jī)和通

信以及人工智能的許多領(lǐng)域取得了非凡的成就，尤其適合求解NP-hard問(wèn)題。

遺傳算法的根本概念

由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法，因而在

這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念。這些概念如下：

串(String)

它是個(gè)體(Individual)的形式，對(duì)應(yīng)于遺傳學(xué)中的染色體(Chromosome)

群體(Population)

個(gè)體的集合稱(chēng)為群體，個(gè)體是群體的元素。

(3)群體大小(Populationsize并群體中個(gè)體的數(shù)量稱(chēng)為群體的大小。

基因(Gene)

基因是用中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)用S=1010,那

么其中的1，0，1，0這4個(gè)元素分別稱(chēng)為基因。

基因位置(GenePosition)

一個(gè)基因在串中的位置稱(chēng)為基因位置，有時(shí)也簡(jiǎn)稱(chēng)基因位?；蛭恢糜纱?/p>

左邊向右計(jì)算，如在串S=1011中，0基因位置是2?；蛭恢脤?duì)應(yīng)于遺傳學(xué)中的

地點(diǎn)(Locus)。

基因特征值(GeneFeature)

在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致，如在串S=1011中，

第三基因位值上的1，它的基因特征值為2；第一基因位值上的1，它的基因特

征值為8。

串構(gòu)造空間S

在串中，基因任意組合構(gòu)成的串的集合稱(chēng)為串構(gòu)造空間。基因操作是在構(gòu)造

空間中進(jìn)展的。

適應(yīng)度(Fitness)

表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度。為了表達(dá)染色體的適應(yīng)能力，引入了對(duì)

問(wèn)題中的每一個(gè)染色體都能進(jìn)展度量的函數(shù)—適應(yīng)度函數(shù)，用于計(jì)算個(gè)體在群體

中被使用的概率。

選擇(Selection)

就是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代，

故有時(shí)也稱(chēng)這一操作為再生(Reproduction｝由于在選擇用于繁殖下一代的個(gè)體

時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度來(lái)決定其繁殖量的，故有時(shí)也稱(chēng)為非均勻再生

(Differentia1Reproduction。)

穿插(Crossover)

就是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體隨機(jī)選取一個(gè)子串

進(jìn)展交換，從而產(chǎn)生新的個(gè)體。

變異(Mutation)

就是在選中的個(gè)體中，隨機(jī)選擇兩點(diǎn)，將兩點(diǎn)間的子用按一定的規(guī)那么進(jìn)展

變異。

傳算法的工作流程

遺傳算法在整個(gè)進(jìn)化過(guò)程中的遺傳操作是隨機(jī)的，但它所呈現(xiàn)出的特性并不

是完全隨機(jī)搜索，它能有效地利用歷史信息來(lái)推測(cè)下一代期望性能有所提高的尋

優(yōu)點(diǎn)集。這樣一代代地不斷進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，求得問(wèn)

題的最優(yōu)解。遺傳算法所涉及的五大要素為：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)

度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定。其流程框圖如圖3.1所示。

評(píng)彷群體

遺化舞作

確定時(shí)間問(wèn)題參型集

(1)位串解磚卷簾數(shù)

C2J計(jì)，目齷函數(shù)

(3)函效侑f適應(yīng)值

U)適應(yīng)值調(diào)整

三個(gè)厘小黨子:

(1＞選樣

121交叉

圖3.1遺傳算法流程圖

從圖3.1可以看出，遺傳算法的運(yùn)行為一個(gè)典型的迭代過(guò)程，其必須完成的

工作容和根本步驟如下：

選擇編碼策略，將解空間中的解數(shù)據(jù)表示成遺傳空間的基因型串構(gòu)造數(shù)

據(jù)，這些串構(gòu)造數(shù)據(jù)的不同組合便構(gòu)成了不同的編碼。

定義適應(yīng)度函數(shù)f(x)。

(3)確定遺傳策略，包括選擇群體大小n,選擇、穿插、變異方法，以及確

定穿插概率pc、變異概率pm等遺傳參數(shù)。

隨機(jī)初始化生成群體P。

計(jì)算群體中個(gè)體位串解碼后的適應(yīng)度f(wàn)(x)。

按照遺傳策略，運(yùn)用選擇、穿插和變異算子作用于群體，形成下一代群

體。

判斷群體性能是否滿(mǎn)足某一指標(biāo)，或者己完成預(yù)定迭代次數(shù)，不滿(mǎn)足那

么返回步驟(6)，或者修改遺傳策略再返回步驟(6)。

在遺傳算法的應(yīng)用過(guò)程中，人們往往結(jié)合問(wèn)題的特征和領(lǐng)域知識(shí)對(duì)根本遺傳

算法進(jìn)展各種改變，形成了各種各樣具體的遺傳算法，從而使得遺傳算法具備求

解不同類(lèi)型優(yōu)化問(wèn)題的能力。

3.4遺傳算法的組成

遺傳算法主要由六個(gè)局部組成：編碼方式、初始群體產(chǎn)生的方法、評(píng)價(jià)函數(shù)、

遺傳操作、算法終止條件、算法參數(shù)的設(shè)置。要利用遺傳算法成功的解決物流配

送車(chē)輛調(diào)度問(wèn)題，就需要對(duì)這六個(gè)步驟進(jìn)展設(shè)計(jì)。

編碼方式

在遺傳算法的運(yùn)行過(guò)程中，它不對(duì)所求解問(wèn)題的實(shí)際決策變量直接進(jìn)展操

作，而是對(duì)表示可行解的個(gè)體編碼施加選擇、穿插、變異等遺傳運(yùn)算，通過(guò)這種

.word.zl-

.word.zl-

遺傳操作來(lái)到達(dá)優(yōu)化的目的，這是遺傳算法的特點(diǎn)之一。遺傳算法通過(guò)這種對(duì)個(gè)

體編碼的操作，不斷搜索出適應(yīng)度較高的個(gè)體，并在群體中逐漸增加其數(shù)量，最

終尋求出問(wèn)題的最優(yōu)解或近似最優(yōu)解。在遺傳算法中如何描述問(wèn)題的可行解，即

把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方

法就成為編碼。

編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題，也是設(shè)計(jì)遺傳算法的一個(gè)關(guān)鍵步

驟。編碼方法除了決定了個(gè)體的染色體排列形式之外，它還決定了個(gè)體從搜索空

間的基因型變換到解空間的表現(xiàn)型時(shí)的解碼方法，編碼方法也影響到穿插算子、

變異算子等遺傳算子的運(yùn)算方法。由此可見(jiàn)，編碼方法在很大程度上決定了如何

進(jìn)展群體的遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化運(yùn)算的效率。一個(gè)好的編碼方法，有可能

會(huì)使得穿插運(yùn)算、變異運(yùn)算等遺傳操作可以簡(jiǎn)單的實(shí)現(xiàn)和執(zhí)行。而一個(gè)差的編碼

方法，卻有可能會(huì)使得穿插運(yùn)算、變異運(yùn)算等遺傳操作難以實(shí)現(xiàn)，也有可能會(huì)產(chǎn)

生很多在可行解集合無(wú)對(duì)應(yīng)可行解的個(gè)體，這些個(gè)體經(jīng)解碼處理后所表示的解稱(chēng)

為無(wú)效解。雖然有時(shí)產(chǎn)生一些無(wú)效解并不完全都是有害的，但大局部情況下它卻

是影響遺傳算法運(yùn)行效率的主要因素之一。

針對(duì)一個(gè)具體應(yīng)用問(wèn)題，如何設(shè)計(jì)一種完美的編碼方案一直是遺傳算法的應(yīng)

用難點(diǎn)之一，也是遺傳算法的一個(gè)重要研究方向。可以說(shuō)目前還沒(méi)有一套既嚴(yán)密

又完整的指導(dǎo)理論及評(píng)價(jià)準(zhǔn)那么能夠幫助我們?cè)O(shè)計(jì)編碼方案。作為參考，DeJong

曾提出了兩條操作性較強(qiáng)的使用編碼原那么：

編碼原那么一：應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)

度模式的編碼方案。

編碼原那么二：應(yīng)使用能使問(wèn)題得到自然表示或描述的具有最小編碼字符集

的編碼方案。

第一個(gè)編碼原那么中，模式是指具有某些基因相似性的個(gè)體的集合，而具有短定義長(zhǎng)度、低階且適應(yīng)度較高的模式稱(chēng)為構(gòu)造優(yōu)良個(gè)體的積木塊或基因塊，這里可以把該編碼原那么理解成應(yīng)使用易于生成適應(yīng)度較高的個(gè)體的編碼方案。

第二個(gè)編碼原那么說(shuō)明了我們?yōu)楹纹珢?ài)于使用二進(jìn)制編碼方法的原因，因?yàn)?/p>

它滿(mǎn)足這條編碼原那么的思想要求。事實(shí)上，理論分析說(shuō)明，與其他編碼字符集相比，二進(jìn)制編碼方案能包含最大的模式數(shù)，從而使得遺傳算法確實(shí)定規(guī)模的群體中能夠處理最多的模式。

由于遺產(chǎn)算法應(yīng)用的廣泛性，迄今為止人們己經(jīng)提出了許多種不同的編碼方法。總的來(lái)說(shuō)，常用的編碼方法可分為三大類(lèi)：二進(jìn)制編碼方法、實(shí)數(shù)編碼方法、有序用編碼方法。二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它使用

的編碼符號(hào)集是由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集{0,1},它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)用。在二進(jìn)制編碼方式的遺傳算法中，遺傳操作是作用在編碼空間上的，操作后的二進(jìn)制用通過(guò)解碼轉(zhuǎn)換到解空間，在這里進(jìn)展評(píng)估選擇（如圖3-2所示）。

解碼

l1?:

編碼空M遺傳運(yùn)兌解空間評(píng)估與選擇

[

編碼

圖3.2編碼解碼操作

使用二進(jìn)制編碼方法，在求解高維優(yōu)化問(wèn)題時(shí)，二進(jìn)制申會(huì)很長(zhǎng)，因而算法

的搜索效率很低。為了克制二進(jìn)制編碼方法的缺點(diǎn)，對(duì)于變量是實(shí)向量的情況，

可以直接采用實(shí)數(shù)編碼方法。實(shí)數(shù)編碼表示比擬自然，較易引入相關(guān)領(lǐng)域知識(shí)，因此，實(shí)數(shù)編碼還可以使遺傳算法更接近問(wèn)題空間，防止了編碼和解碼的過(guò)程，

其使用將越來(lái)越廣泛。對(duì)很多組合優(yōu)化問(wèn)題，目標(biāo)函數(shù)的值不僅與表示解的字符

串中各字符的值有關(guān)，而且與其所在字符串的位置有關(guān)，這樣的問(wèn)題稱(chēng)為有序問(wèn)

題，用有序串編碼方法表示。這類(lèi)編碼方法較多地用在組合優(yōu)化問(wèn)題中，如二次

分配問(wèn)(QuadraticAssignmentproblem])旅行商問(wèn)題(TravelingSalesmanProblem)們常用的是有序串的編碼方式。

基于遺傳算法的以上特點(diǎn)，在本文用遺產(chǎn)算法求解物流配送車(chē)輛調(diào)度問(wèn)題

時(shí)，我們采用有序串編碼方式的染色體設(shè)計(jì)。初始化過(guò)程有很多種，在研究遺傳

算法時(shí)，常常隨機(jī)產(chǎn)生初始群體，這樣做的好處是產(chǎn)生方式不依賴(lài)于問(wèn)題，也就

是對(duì)于任何問(wèn)題，我們都可以采用這種方式來(lái)生成初始群體，由于本文是對(duì)某個(gè)

特定的非線(xiàn)性規(guī)劃問(wèn)題求解，所以我們采用人機(jī)交互方式來(lái)初始化群體，這樣結(jié)

合人類(lèi)智慧使算法優(yōu)化收斂速度更快。

適應(yīng)度函數(shù)

在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)

度量某個(gè)物種對(duì)于其生存環(huán)境的適應(yīng)度程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將

有更多的繁殖時(shí)機(jī)；而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖時(shí)機(jī)就相對(duì)較少。

與此相似，在遺傳算法中也使用適應(yīng)度這個(gè)概念來(lái)度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)

算中有可能到達(dá)或接近于或有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度較高的個(gè)體遺

傳到下一代的概率就較大，而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就相對(duì)小一

些。度量個(gè)體適應(yīng)度的函數(shù)就稱(chēng)為適應(yīng)度函數(shù)〔FitnessFunction〕。

遺傳算法的一個(gè)特點(diǎn)是它僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可以得到下一步

.word.zl-

.word.zl-

的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù)值的使用是通過(guò)評(píng)價(jià)個(gè)體的適應(yīng)度來(lái)表達(dá)的。評(píng)

價(jià)個(gè)體適應(yīng)度的一般過(guò)程是：

對(duì)個(gè)體編碼串進(jìn)展解碼處理后，可到達(dá)個(gè)體的表現(xiàn)型。

由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。

根據(jù)最優(yōu)化問(wèn)題的類(lèi)型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)那么求出個(gè)體的

適應(yīng)度。

遺傳算法中，群體的進(jìn)化過(guò)程就是以群體中各個(gè)個(gè)體的適應(yīng)度為依據(jù)，通過(guò)

一個(gè)反復(fù)迭代過(guò)程，不斷地尋求出適應(yīng)度較大的個(gè)體，最終就可以得到問(wèn)題的最

優(yōu)解或者近似最優(yōu)解。對(duì)于本課題的多車(chē)場(chǎng)多目標(biāo)開(kāi)放式車(chē)輛調(diào)度模型優(yōu)化問(wèn)

題，采用函數(shù)值來(lái)評(píng)價(jià)解的好壞，這種方法是最直接，也是最方便的方法，取函

數(shù)值最小的解為最優(yōu)解。

選擇策略

遺傳算法中的選擇策略就是用來(lái)確定如何從父代群體中按某種方法選取哪

些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算，選擇提供了遺傳算法的驅(qū)動(dòng)力。如

果驅(qū)動(dòng)力過(guò)大，遺傳搜索將過(guò)早地終止，而如果驅(qū)動(dòng)力太小，進(jìn)化過(guò)程將變得難

以承受。相對(duì)而言，較小的驅(qū)動(dòng)力一般能使群體保持足夠的多樣性，從而增大了

算法收斂到全局最優(yōu)的概率。選擇操作是建立在對(duì)個(gè)體的適應(yīng)度進(jìn)展評(píng)價(jià)的根底

之上的，選擇操作的主要目的是為了防止基因缺失、提高全局收斂性和計(jì)算效率。

下面是遺傳算法中較常用到的幾種選擇策略。

(1)繁殖池(BreedingPool選擇

繁殖池選擇首先根據(jù)當(dāng)前群體中個(gè)體的適應(yīng)值，按下式計(jì)算其相對(duì)適應(yīng)值：

Re/：=&

j-i

其fi是群體中第i個(gè)成員的適應(yīng)值，N是群體規(guī)模。那么每個(gè)個(gè)體的繁殖量為：

Ni-round(Re/xNJ

此處Round(x/示與x距離最小的整數(shù)。

計(jì)算出群體中每個(gè)個(gè)體的繁殖量，即可將它們分別復(fù)制N個(gè)以生成一個(gè)臨

時(shí)群體，即繁殖池(Breedingpool再通過(guò)在繁殖池中隨機(jī)地抽取成對(duì)個(gè)體進(jìn)展交配，所產(chǎn)生的后代將取代當(dāng)前群體形成下一個(gè)群體。顯然，個(gè)體復(fù)制到繁殖池的

數(shù)目越大，那么它被選到進(jìn)展交配的時(shí)機(jī)也就越多，而對(duì)于Ni=0的個(gè)體，它

們將被淘汰出整個(gè)演化過(guò)程。在實(shí)現(xiàn)算法時(shí)需要注意的是，繁殖池中個(gè)體的數(shù)目不一定正好等于No

(2)輪盤(pán)賭選擇(RouletteWheelSelection)

輪盤(pán)賭選擇是由Holland提出的，是最知名的選擇方式之一，其根本原理是根據(jù)每個(gè)染色體適應(yīng)值的比例來(lái)確定該個(gè)體的選擇概率或生存概率。選擇的過(guò)程

就是旋轉(zhuǎn)輪盤(pán)假設(shè)干次〔次數(shù)等于種群規(guī)?！常看螢樾路N群選出一個(gè)個(gè)體。輪盤(pán)賭選擇策略在遺傳算法中使用的最多，它的具體選擇過(guò)程為：先計(jì)算個(gè)體的適

應(yīng)值Pi,然后根據(jù)選擇概率把輪盤(pán)分成N份，其中第i扇形的中心角為2九￡在進(jìn)展選擇時(shí)，先轉(zhuǎn)動(dòng)輪盤(pán)，假設(shè)某參照點(diǎn)落入到第i個(gè)扇形，那么選擇個(gè)體i<

可見(jiàn)，這種選擇方式非常類(lèi)似輪盤(pán)賭中的轉(zhuǎn)盤(pán)，小扇區(qū)的面積越大，骰子落入其

中的概率也越大，即個(gè)體的適應(yīng)值越大，它被選擇到的時(shí)機(jī)也越大。從而，其基因構(gòu)造被遺傳到下一代的可能性也越大。

(3)錦標(biāo)賽〔ToumamenU選擇

錦標(biāo)賽選擇也是一種基于個(gè)體適應(yīng)度之間大小關(guān)系的選擇方法。在選擇時(shí)，

每次進(jìn)展適應(yīng)度大小比擬的個(gè)體數(shù)目稱(chēng)為競(jìng)賽規(guī)模，一般情況下，競(jìng)賽規(guī)模K

的取值為2。具體操作過(guò)程如下：首先，從群體中隨機(jī)選取K個(gè)個(gè)體進(jìn)展適應(yīng)度

大小的比擬，將其中適應(yīng)度最高的個(gè)體作為生成下一代的父體。其次，將上述過(guò)

程重復(fù)M次，就可得到下一代群體中的M個(gè)個(gè)體。顯然，這種選擇方式也使得

適應(yīng)度好的個(gè)體具有較大的“生存〞時(shí)機(jī)。同時(shí)，由于它只使用適應(yīng)度的相對(duì)值

作為選擇的標(biāo)準(zhǔn)，而無(wú)個(gè)體適應(yīng)度的算術(shù)運(yùn)算。從而它能防止超級(jí)個(gè)體的影響，

在一定程度上，防止發(fā)生過(guò)早收斂現(xiàn)象和停滯現(xiàn)象。

雜交策略

穿插運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其局部基因，從

而形成兩個(gè)新的個(gè)體。它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。

一方面它使原來(lái)群體中優(yōu)良個(gè)體的特性能夠在一定程度上被遺傳和繼承，另一方

面它使算法能夠搜索新的基因空間，從而使新群體中的個(gè)體具有多樣性。穿插或

基因重組是遺傳算法獲取新的優(yōu)良個(gè)體的最重要的手段。經(jīng)常采用的穿插算子有

以下幾種：

(1)局部映射穿插(PartiallyMappedCrossover簡(jiǎn)稱(chēng)PMX)

這種算子在構(gòu)造后代時(shí)通過(guò)從一個(gè)父體中選取一段路徑，并盡可能多的保存

另一個(gè)父體中城市的次序和位置。選擇一個(gè)路徑時(shí)，首先隨機(jī)選取兩切割點(diǎn)作為

交換操作的邊界。例如兩父體(兩切割點(diǎn)用“|〞標(biāo)記)

P1=(123|4567|89)P2=(254|1876|39)

產(chǎn)生后代的過(guò)程如下：首先交換兩切割點(diǎn)之間的相應(yīng)段(符號(hào)“x〞表示目

前未知值)，得到

Q1=(xxx|1876|xx)Q2=(xxx|4567|xx)

這一交換同時(shí)定義了一系列的映射：

lc48o57o6和607。

然后從各自的父體中填入無(wú)沖突的城市，得到：

Q1=(x23|1876|x9)Q2=(2xx|4567|39)

最后，后代Q1中的第一個(gè)“x根據(jù)映射4被4代替。類(lèi)似地，Q1中

的第二個(gè)“x用代替，Q2

中的兩個(gè)“x分別處和1代替。因此生成的后代為

Q1=(423|1876|59)Q2=(281|4567|39)

(2)次序穿插(OrderCrossover簡(jiǎn)稱(chēng)OX)

這一算子在構(gòu)造后代時(shí)通過(guò)從一個(gè)父體中選取一段路徑，并保持另一個(gè)父體

中城市的相對(duì)次序。例如兩父體(兩切割點(diǎn)用“|〃標(biāo))己

P1=(123|4567|89)P2=(452|1876|93)

產(chǎn)生后代的過(guò)程如下：首先，兩切割點(diǎn)之間的城市段被復(fù)制到后代中，得到:

Q1=(xxx|1876|xx)Q2=(xxx|4567|xx)

接著從一個(gè)父體的第二個(gè)切割點(diǎn)開(kāi)場(chǎng)，來(lái)自另一個(gè)父體的城市依同樣的次序被復(fù)制，省略已經(jīng)出現(xiàn)的城市。當(dāng)?shù)竭_(dá)串尾時(shí)，那么從串首繼續(xù)。那么，第二個(gè)父體從第二個(gè)切割點(diǎn)開(kāi)場(chǎng)的城市序列為：

9-3-4-5-2-1-8-7-6

移去4,5,6和7這四個(gè)在第一個(gè)后代中已出現(xiàn)的城市，得到：

9-3-2-1-8

.word.zl-

.word.zl-

. .word.zl-

依此次序從第二個(gè)切割點(diǎn)開(kāi)場(chǎng)填入第一個(gè)后代得到

Q1=(218|4567|93)

類(lèi)似地，可得到另一個(gè)后代

Q2=(345|1876|92)

OX算子開(kāi)發(fā)了路徑表示的一個(gè)特性，即重要的是城市間的相對(duì)次序，而不

是他們的特定位置。也就是，兩條路徑9-3-4-5-2-18-7-6和4-5-2-1-8-7-6-9-3實(shí)際

上是一樣的。

(3)循環(huán)穿插(CycleCrossover簡(jiǎn)稱(chēng)CX)

這種算子在構(gòu)造后代時(shí)，每個(gè)城市及其所處的位置都來(lái)自于某一個(gè)父體。循

環(huán)穿插的過(guò)程如下：兩父體

P1=(123456789)P2=(452687193)

產(chǎn)生后代時(shí)，先從第一個(gè)父體中取第一個(gè)城市作為第一個(gè)后代的起始點(diǎn)，得

到

Q1=(lxxxxxxxx)。

由于后代中的每一個(gè)城市必須取自于某個(gè)父體且保持同樣位置，所以在起始

點(diǎn)我們別無(wú)選擇。下一個(gè)考慮的城市應(yīng)該是4，因?yàn)樗荘2中位于所選城市1“下

方〞的城市，在P1中這個(gè)城市位于位置4。因此

Q1=(lxx4xxxxx)

接著是城市6，因?yàn)樗荘2中位于所選城市4“下方〞的城市。因此

Q1=(lxx4x6xxx)

按照這樣的規(guī)那么，在第一個(gè)后代中應(yīng)包括的下個(gè)城市是7。但是注意，選

擇城市7

蒙牛乳業(yè)股份自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端車(chē)輛調(diào)度問(wèn)題

摘要：自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端車(chē)輛調(diào)度策略的設(shè)計(jì)是物流配送車(chē)輛調(diào)度中的

一個(gè)關(guān)鍵問(wèn)題，好的調(diào)度策略可以大大縮短出庫(kù)端的配貨時(shí)間。為此本文引入動(dòng)

態(tài)優(yōu)先級(jí)理論，并利用該理論對(duì)大型AS/RS出庫(kù)口車(chē)輛調(diào)度問(wèn)題進(jìn)展了深入研

究與分析，提出了基于動(dòng)態(tài)優(yōu)先級(jí)的AS/RS出庫(kù)端車(chē)輛調(diào)度策略，并開(kāi)發(fā)了相

應(yīng)的AS/RS出庫(kù)口發(fā)貨資源監(jiān)控系統(tǒng)，即AS/RS出庫(kù)口車(chē)輛調(diào)度系統(tǒng)，優(yōu)化

了AS/RS出庫(kù)端車(chē)輛調(diào)度策略，大大提高了物流配送當(dāng)中的配貨效率。

本文建立的多目標(biāo)組合優(yōu)化模型以及設(shè)計(jì)的遺傳算法求解方案，可以有效的

縮減物流配送中的送貨時(shí)間；設(shè)計(jì)的AS/RS出庫(kù)端車(chē)輛調(diào)度優(yōu)化策略及開(kāi)發(fā)的

AS/RS出庫(kù)端車(chē)輛調(diào)度系統(tǒng)，可以有效縮減車(chē)輛在出庫(kù)端的配貨時(shí)間。本文對(duì)以

上兩種物流配送中的車(chē)輛調(diào)度問(wèn)題進(jìn)展研究，大大提高了物流配送效率、減少了

物流配送本錢(qián)。

關(guān)鍵詞：物流配送；車(chē)輛調(diào)度；多目標(biāo)組合優(yōu)化；

一、公司背景

蒙牛乳業(yè)，是“蒙牛乳業(yè)集團(tuán)〞的簡(jiǎn)稱(chēng)。其總部，設(shè)在呼和浩特市和林格爾

盛樂(lè)經(jīng)濟(jì)園區(qū)。前后四期工程占地面積55萬(wàn)平方米。蒙牛是一家總部位于中華

人民國(guó)的乳制品生產(chǎn)企業(yè)，蒙牛是中國(guó)大陸生產(chǎn)牛奶、酸奶和乳制品的領(lǐng)頭企業(yè)

之一，1999年成立，至2005年時(shí)已成為中國(guó)奶制品營(yíng)業(yè)額第二大的公司，其中

液態(tài)奶和冰淇淋的產(chǎn)量都居全中國(guó)第一。蒙牛主要業(yè)務(wù)是制造液體奶、冰激凌和

其他乳制品。

1999年8月，蒙牛乳業(yè)〔集團(tuán)〕股份〔簡(jiǎn)稱(chēng)蒙牛乳業(yè)集團(tuán)〕成立，總部設(shè)在

中國(guó)乳都核心區(qū)――和林格爾經(jīng)濟(jì)開(kāi)發(fā)區(qū)，擁有總資產(chǎn)100多億元，職工近3萬(wàn)

人，乳制品年生產(chǎn)能力達(dá)600萬(wàn)噸。

到目前為止，包括和林基地在，蒙牛乳業(yè)集團(tuán)已經(jīng)在全國(guó)16個(gè)省區(qū)市建立

生產(chǎn)基地20多個(gè)，擁有液態(tài)奶、酸奶、冰淇淋、奶品、奶酪五大系列400多個(gè)

品項(xiàng)，產(chǎn)品以其優(yōu)良的品質(zhì)覆蓋國(guó)市場(chǎng)，并出口到美國(guó)、加拿大、蒙古、東南亞

及港澳等多個(gè)國(guó)家和地區(qū)。

二、AS/RS出庫(kù)端車(chē)輛調(diào)度問(wèn)題的研究

問(wèn)題的提出

自動(dòng)化立體倉(cāng)庫(kù)〔AutomaticStorage＆RetrievalSystem〕：是指能自動(dòng)儲(chǔ)存

和輸出貨物的倉(cāng)庫(kù)，它采用多層貨架儲(chǔ)存單元貨物，用自動(dòng)化貨物搬運(yùn)設(shè)備進(jìn)展

貨物的入庫(kù)和出庫(kù)。它一般由自動(dòng)控制與管理系統(tǒng)、貨架、巷道式堆垛機(jī)、出入

庫(kù)輸送機(jī)等構(gòu)成，能按指令自動(dòng)完成貨物的搬運(yùn)、存取作業(yè)，并能對(duì)庫(kù)存貨物進(jìn)

展自動(dòng)管理。由于自動(dòng)化立體倉(cāng)庫(kù)具有很高的空間利用率、很強(qiáng)的入出庫(kù)能力、

采用計(jì)算機(jī)進(jìn)展控制管理便于企業(yè)實(shí)施現(xiàn)代化管理等特點(diǎn)，已成為企業(yè)物流和生

產(chǎn)管理不可缺少的倉(cāng)儲(chǔ)技術(shù)，自動(dòng)化立體倉(cāng)庫(kù)作為物流中心的重要組成局部，越

來(lái)越受到企業(yè)的重視。

現(xiàn)階段對(duì)物流配送車(chē)輛調(diào)度問(wèn)題的研究很多，但大多是對(duì)車(chē)輛調(diào)度線(xiàn)路選擇

問(wèn)題的研究，對(duì)自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端車(chē)輛調(diào)度問(wèn)題的研究較少。在物流配送中

整個(gè)配送時(shí)間應(yīng)包括兩局部：出庫(kù)端的配貨時(shí)間和裝貨完成后的送貨時(shí)間，對(duì)車(chē)

輛調(diào)度線(xiàn)路選擇問(wèn)題的研究可以有效的縮減物流配送中的送貨時(shí)間，但通過(guò)對(duì)出

庫(kù)端車(chē)輛調(diào)度問(wèn)題的研究可以有效縮減車(chē)輛在出庫(kù)端的配貨時(shí)間，對(duì)減少物流配送的時(shí)間本錢(qián)有很大的作用。

所謂自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端車(chē)輛調(diào)度，即在自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端按什么樣

的原那么給待裝貨車(chē)輛分配車(chē)位的問(wèn)題?，F(xiàn)階段出庫(kù)端車(chē)輛調(diào)度大多采用先來(lái)先

效勞的原那么，即對(duì)先到的車(chē)輛優(yōu)先分配車(chē)位，此原那么的采用可以充分表達(dá)車(chē)

輛調(diào)度的公平性，但有很多缺乏。首先當(dāng)給訂貨數(shù)量特大的訂單客戶(hù)的車(chē)輛分配

車(chē)位后，此客戶(hù)后的所有小訂貨數(shù)量客戶(hù)的車(chē)輛都需要等待很長(zhǎng)時(shí)間才能被分配

車(chē)位，減少了系統(tǒng)在一段時(shí)間處理客戶(hù)訂單的能力，并且此調(diào)度策略沒(méi)有考慮影

響出庫(kù)產(chǎn)品整體銷(xiāo)售模式的因素。所以本文對(duì)自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)口車(chē)輛調(diào)度問(wèn)

題的研究具有重要的實(shí)際意義。

問(wèn)題及相關(guān)因素描述

本文是以蒙牛乳業(yè)股份自動(dòng)化立體倉(cāng)庫(kù)出庫(kù)端車(chē)輛調(diào)度問(wèn)題為背景進(jìn)展研

究的。一個(gè)大型的立體倉(cāng)庫(kù)有多個(gè)出庫(kù)口，每一個(gè)出庫(kù)口對(duì)應(yīng)一個(gè)車(chē)位，所謂車(chē)

位就是車(chē)輛裝貨時(shí)在出貨口的位置，分為常規(guī)固定車(chē)位和雙向固定車(chē)位兩種類(lèi)

型。常規(guī)固定車(chē)位用于分配后開(kāi)門(mén)的車(chē)輛，雙向固定車(chē)位用于分配側(cè)開(kāi)門(mén)或兩端

開(kāi)門(mén)的車(chē)輛。其構(gòu)造如圖5.1所示。文章所要解決的問(wèn)題是如何調(diào)度不斷到來(lái)的

客戶(hù)車(chē)輛為其分配車(chē)位，使其能在最短的時(shí)間完成裝貨任務(wù)。車(chē)輛從進(jìn)廠(chǎng)到裝完

貨離開(kāi)的這段時(shí)間我們稱(chēng)為裝載時(shí)間，影響裝載時(shí)間的因素很多，這里我們假設(shè)

自動(dòng)化立體倉(cāng)庫(kù)有足夠大的出庫(kù)能力，即只要出庫(kù)口能夠裝完一盤(pán)貨物，自動(dòng)化

立體倉(cāng)庫(kù)有足夠的能力立即準(zhǔn)備好另一盤(pán)貨。另外假設(shè)每個(gè)車(chē)上的裝卸工的裝卸

速率都是均等的，這樣我們要研究的問(wèn)題只與對(duì)不同用戶(hù)的車(chē)輛的調(diào)度順序有

關(guān)。

.word.zl-

.word.zl-

▼環(huán)穿小午

一??,裝貨車(chē)輛

車(chē)位io:更工

“位"?友一+常規(guī)車(chē)位

自動(dòng)化立體倉(cāng)庫(kù)

車(chē)位1

埔

送

口

輸

這

U

出庫(kù)環(huán)穿

車(chē)位9

WiT|CZZ

軍位13m

圖2.1AS/RS出庫(kù)端

2.2.1銷(xiāo)售派車(chē)單

銷(xiāo)售派車(chē)單是由各事業(yè)部的運(yùn)管部根據(jù)銷(xiāo)售訂單下發(fā)，所包括的主要信息

有：出庫(kù)單號(hào)、倉(cāng)庫(kù)、數(shù)量、品名規(guī)格、訂單號(hào)、訂單類(lèi)型、車(chē)輛類(lèi)型。其他信息包括：定貨單位、收貨單位、收貨單位地址、聯(lián)系人、聯(lián)系、運(yùn)輸方式、方案

到達(dá)日期等。司機(jī)到達(dá)蒙牛六期AS/RS出庫(kù)端后應(yīng)先到儲(chǔ)運(yùn)部登記，保管員按

司機(jī)到達(dá)順序給司機(jī)帶來(lái)的銷(xiāo)售派車(chē)單據(jù)分配優(yōu)先級(jí)，分配原那么是先來(lái)先分

配。優(yōu)先級(jí)高的銷(xiāo)售派車(chē)單對(duì)應(yīng)的車(chē)輛被優(yōu)先調(diào)度，被優(yōu)先下發(fā)出庫(kù)任務(wù)。具體

流程圖如下所示：

開(kāi)始

核實(shí)

是

III

結(jié)束

圖2.2原車(chē)輛調(diào)度流程圖

2.2.2訂單的優(yōu)先級(jí)表示

為了更好的調(diào)度待裝貨車(chē)輛我們引入訂單動(dòng)態(tài)優(yōu)先級(jí)的概念，根據(jù)裝貨車(chē)輛

到達(dá)立體庫(kù)時(shí)所持銷(xiāo)售派車(chē)單的相關(guān)信息確定銷(xiāo)售派車(chē)單的優(yōu)先級(jí)，以此確定車(chē)輛調(diào)度的優(yōu)先級(jí)并為車(chē)輛分配車(chē)位。一個(gè)完整的銷(xiāo)售派車(chē)單主要信息如下:

車(chē)輛類(lèi)型〔Vehicle-Typd：分為集裝箱〔兩個(gè)側(cè)開(kāi)門(mén)或兩端開(kāi)門(mén)的車(chē)〕和常規(guī)車(chē)〔有一個(gè)后門(mén)的車(chē)〕兩類(lèi)。其中常規(guī)車(chē)分配在常規(guī)固定車(chē)位，集裝箱分配在雙向固定車(chē)位。

.word.zl-

.word.zl-

訂單類(lèi)型〔Order-Type〕：包括外部調(diào)撥訂單、部調(diào)撥訂單和銷(xiāo)售訂單。外

部調(diào)撥訂單是集團(tuán)部不同事業(yè)部之間調(diào)撥產(chǎn)品時(shí)所用到的單據(jù)；部調(diào)撥訂單是一

個(gè)事業(yè)部的部各廠(chǎng)之間調(diào)撥產(chǎn)品時(shí)所用到的單據(jù)；銷(xiāo)售訂單是客戶(hù)向本公司訂購(gòu)

產(chǎn)品時(shí)所用到的單據(jù)，三者都是立體庫(kù)出庫(kù)口進(jìn)展配貨的憑證，主要信息有：?jiǎn)?/p>

據(jù)類(lèi)型、倉(cāng)庫(kù)號(hào)、品名規(guī)格、數(shù)量等。在本文的研究背景中外部