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

1、中 文 摘 要物流配送車(chē)輛調(diào)度問(wèn)題是指：在給定運(yùn)輸任務(wù)的條件下，如何派車(chē)、組織循環(huán)運(yùn)輸，使空駛里程最少，運(yù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ì)遺傳算法中的交叉變異操作

2、做了詳細(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)

3、組合優(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)行研究，大大提高了物流配送效率、減少了物流配送成本。關(guān)鍵詞：物流配送；車(chē)輛調(diào)度；多目標(biāo)組合優(yōu)化；遺傳算法第一章 緒論1.1 課題背景物流(Logistics)：指在合適時(shí)間，將合適的物品以適當(dāng)?shù)臄?shù)量準(zhǔn)確地送到顧客手中，它是供應(yīng)鏈中最重要的組成部分。一般意義上是指在生產(chǎn)和生活中所涉及的各種物質(zhì)實(shí)體由供給方向需求方的物理性轉(zhuǎn)移過(guò)程。這一概念將物流定義在有用的物、供方、

4、需方等幾個(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)。配送成本直接關(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è)

5、原料物流中占58%，在生產(chǎn)企業(yè)成品物流中占73%，在商業(yè)物流中占52%。所以物流配送車(chē)輛調(diào)度方案的合理優(yōu)化，對(duì)于整個(gè)物流運(yù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)在此范圍內(nèi)價(jià)值的平均化、合理化。在社會(huì)經(jīng)濟(jì)的發(fā)展中，運(yùn)輸?shù)闹匾约航?jīng)被人們所確認(rèn)，成為國(guó)民經(jīng)濟(jì)的命脈。從物流系統(tǒng)的觀(guān)點(diǎn)來(lái)看，運(yùn)輸作業(yè)的關(guān)鍵因素包括運(yùn)輸成本和運(yùn)輸速度兩個(gè)方面。運(yùn)輸成本：是指為兩個(gè)地理位置的運(yùn)輸所支付的款

6、項(xiàng)，以及管理和維持轉(zhuǎn)移中存貨的有關(guān)費(fèi)用，應(yīng)采用能把系統(tǒng)總成本降低到最低限度的運(yùn)輸方式。運(yùn)輸速度：是指為完成特定的運(yùn)輸作業(yè)所需花費(fèi)的時(shí)間。運(yùn)輸速度和成本的關(guān)系，主要表現(xiàn)在以下兩個(gè)方面：首先，運(yùn)輸商提供的服務(wù)越快速，實(shí)際需要收取的費(fèi)用也就越高。其次，運(yùn)輸服務(wù)越快，轉(zhuǎn)移中的存貨就越少，可利用的運(yùn)輸間隔時(shí)間越短。因此在選擇最合理的運(yùn)輸方式時(shí)，至關(guān)重要的問(wèn)題就是如何平衡其服務(wù)的速度和成本。運(yùn)輸主要目的就是要以最低的時(shí)間、財(cái)務(wù)和環(huán)境資源成本，將產(chǎn)品從原產(chǎn)地轉(zhuǎn)移到規(guī)定地點(diǎn)。同時(shí)，產(chǎn)品轉(zhuǎn)移所采用的方式必須能滿(mǎn)足顧客有關(guān)交付履行和裝運(yùn)信息的可得性等方面的要求。所以在物流系統(tǒng)中，必須精確地維持運(yùn)輸成本和服務(wù)質(zhì)量之

7、間的平衡。低成本運(yùn)輸和高質(zhì)量服務(wù)是令人滿(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)輸成本最低。車(chē)輛調(diào)度是物流管理最重要的部分，正確合理的調(diào)度可以有效減少車(chē)輛的空駛率，實(shí)現(xiàn)合理路徑運(yùn)輸，從而有效減少運(yùn)輸

8、成本，節(jié)約運(yùn)輸時(shí)間，提高經(jīng)濟(jì)效益。1.2 課題研究的意義物流產(chǎn)業(yè)的發(fā)展，將從整體上改變經(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ì)的發(fā)展呼喚物流的進(jìn)一步發(fā)展，對(duì)物流的發(fā)展要求如下：(1) 降低流通成本在 GDP 中的比重：在我國(guó)目前工業(yè)企業(yè)生產(chǎn)中，直接勞動(dòng)成本占總成本的比重不到 10，而物流費(fèi)用占商品總成本的比重，從賬面反映約為40，全社會(huì)物流費(fèi)用支出約占 GDP 的 20，而其他發(fā)達(dá)國(guó)家一般在 10%左右。這反映了我國(guó)物流系統(tǒng)落后，流通成本太高，反映了我國(guó)國(guó)民經(jīng)濟(jì)運(yùn)行質(zhì)量不高。通過(guò)發(fā)展現(xiàn)代物流業(yè)來(lái)促進(jìn)物流合理化，降低流通成本在 GDP 中的比重，無(wú)疑將

9、成為我國(guó)新的經(jīng)濟(jì)增長(zhǎng)點(diǎn)?！笆濉逼陂g，如果我國(guó)物流費(fèi)用降低到占 GDP 的 15，每年將為社會(huì)直接節(jié)約 2400 億元的物流成本。(2) 減少企業(yè)流動(dòng)資金占用：我國(guó)工業(yè)企業(yè)和流通企業(yè)由于物流基礎(chǔ)設(shè)施、技術(shù)和管理的落后，原材料、半成品、成品積壓嚴(yán)重，大量流動(dòng)資金被占用，周轉(zhuǎ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 次/每年，與發(fā)達(dá)國(guó)家相比非常落后。如果工業(yè)企業(yè)把物流職能分離出來(lái)交給第三方物流企業(yè)，通過(guò)其先進(jìn)、科學(xué)的專(zhuān)業(yè)化服務(wù)，就可以

10、減少流動(dòng)資金占用，提高核心競(jìng)爭(zhēng)能力，實(shí)現(xiàn)從粗放式經(jīng)營(yíng)向集約式經(jīng)營(yíng)轉(zhuǎn)變。(3) 電子商務(wù)的發(fā)展需要物流做基礎(chǔ)：電子商務(wù)是流通領(lǐng)域的一場(chǎng)革命，它把3商品買(mǎi)賣(mài)虛擬成一個(gè)大的市場(chǎng)，使客戶(hù)在任何地點(diǎn)、任何時(shí)間都可以購(gòu)買(mǎi)商品。但是，電子商務(wù)需要將網(wǎng)上訂的貨物及時(shí)送到可能在任何地方的客戶(hù)手里，這就給物流系統(tǒng)帶來(lái)很大的挑戰(zhàn)。實(shí)際上，物流已經(jīng)成為電子商務(wù)發(fā)展的瓶頸，需要建立具有響應(yīng)性、靈活性和可視化的現(xiàn)代物流系統(tǒng)，需要第三方物流企業(yè)的服務(wù)。世界 500強(qiáng)中相當(dāng)多的企業(yè)都是通過(guò)第三方物流來(lái)解決它的供應(yīng)鏈與銷(xiāo)售問(wèn)題的，很多跨國(guó)公司在歐洲、亞洲、美洲等地分別有不同的第三方物流企業(yè)為他服務(wù)。(4) 現(xiàn)代物流產(chǎn)業(yè)的發(fā)展，

11、將減少由于低水平、條塊分割的物流方式造成的巨大物耗：在傳統(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)代物流集約化、一體化的發(fā)展中，配送是直接與消費(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)題

12、，幾十年來(lái)這一直是一個(gè)研究的熱點(diǎn)，在滿(mǎn)足和完成各任務(wù)的前提下，正確合理的安排行車(chē)路線(xiàn)、提高配送車(chē)輛的利用率就可以有效的節(jié)省時(shí)間從而減少運(yùn)輸成本。另外對(duì)出庫(kù)口車(chē)輛調(diào)度問(wèn)題的研究，將有效減少貨物裝配的時(shí)間。所以本文對(duì)物流配送車(chē)輛調(diào)度的研究具有重要意義。1.3 國(guó)內(nèi)外研究現(xiàn)狀車(chē)輛調(diào)度問(wèn)題最早是由Dantzig和Ramsert在上個(gè)世紀(jì)50年代末期提出，該問(wèn)題一般稱(chēng)之為VehicleRouting Problem(VRP)或者Vehicle Scheduling 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ò)分析、物流科

13、學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科專(zhuān)家與運(yùn)輸計(jì)劃制定者和管理者的極大重視，成為運(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的集分割，直接考慮可行解集合，在此基礎(chǔ)上進(jìn)行優(yōu)化，建立了最簡(jiǎn)單的VRP模型；1964年，Clarke和Wright提出了一種啟發(fā)式節(jié)約法來(lái)建立車(chē)隊(duì)配送路線(xiàn)；1968年，Rao等人在VRP 集分割的基礎(chǔ)上引入了列生成方法進(jìn)行求解，這種算法本質(zhì)上是最短路徑算法，同時(shí)結(jié)合了分枝定界算法；1971年，Eilon 等人提出將動(dòng)態(tài)

14、規(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ó)內(nèi),有關(guān)車(chē)輛調(diào)度問(wèn)題的研究是在20世紀(jì)90年代以后才逐漸興起的，比國(guó)外相對(duì)落后。國(guó)內(nèi)研究對(duì)象主要是旅行商問(wèn)題(Traveling Salesman Pr

15、oblem，簡(jiǎn)稱(chēng)TSP)、中國(guó)郵遞員問(wèn)題(Chinese Postman Problem，簡(jiǎn)稱(chēng)CPP)、有向中國(guó)郵遞員問(wèn)題(DirectedChinese Postman Problem，簡(jiǎn)稱(chēng)DCPP)等，系統(tǒng)性研究還很少見(jiàn)到。西南交通大學(xué)的李軍教授和郭耀煌教授對(duì)車(chē)輛優(yōu)化調(diào)度的基礎(chǔ)理論及各類(lèi)問(wèn)題進(jìn)行了系統(tǒng)的研究；李大為等以TSP的最近距離啟發(fā)式為基礎(chǔ)，通過(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ì)

16、薄弱，需要進(jìn)一步研究。1.4 本文內(nèi)容的安排本課題的研究以?xún)?nèi)蒙古蒙牛乳業(yè)股份(集團(tuán))有限公司的物流配送業(yè)務(wù)為背景，主要研究?jī)煞矫鎯?nèi)容：首先，對(duì)多車(chē)場(chǎng)多目標(biāo)開(kāi)放式物流配送車(chē)輛調(diào)度問(wèn)題做了研究，以此可以?xú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)輸成本，給蒙牛集團(tuán)帶來(lái)可觀(guān)的經(jīng)濟(jì)效益。本文研究的具體內(nèi)容如下：第一章緒論：介紹了本文研究的背景以及研究的目的與意義，并對(duì)國(guó)內(nèi)外對(duì)車(chē)輛調(diào)度問(wèn)題的研究現(xiàn)狀作了簡(jiǎn)單介紹。第二章車(chē)輛調(diào)度問(wèn)題概述：首先對(duì)物流配送車(chē)輛

17、調(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ē)場(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)

18、優(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)題概述2.1 車(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ù)奈恢谩?在配送中，也包含著其他的物流功能，是多種

19、功能的組合。 配送是物流系統(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和Ramser在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)輸計(jì)劃制定者的極大重視，同時(shí)也逐漸成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)研究問(wèn)題。由于它應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，一直受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。國(guó)外將物流配送車(chē)輛優(yōu)化調(diào)度問(wèn)題歸結(jié)為或稱(chēng)之為Vehicle Routi

20、ng Problem和Vehicle Scheduling Problem。本課題采用的是后者，也就是將車(chē)輛調(diào)度問(wèn)題歸結(jié)為VSP問(wèn)題：Vehicle Scheduling 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)

21、題一般研究的是在配送中心及用戶(hù)位置均已知、資源及運(yùn)輸能力充分、各用戶(hù)需求量己知的前提下，如何合理、高效、低成本的解決分配與運(yùn)送的問(wèn)題，也就是說(shuō)如何將貨物從配送中心按照一定的要求發(fā)送到若干個(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)輸行程最短。2.2 車(chē)輛調(diào)度問(wèn)題的構(gòu)成要素物流配送車(chē)輛調(diào)度問(wèn)題主要包括貨物、車(chē)輛、配送中心、

22、客戶(hù)、運(yùn)輸網(wǎng)絡(luò)、約束條件、和目標(biāo)函數(shù)等要素。(1) 貨物貨物是我國(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)，能否分批配送等屬性。(2) 車(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ù)完成后的停放位置等。(3) 配送中心配送中心是指接受

23、供應(yīng)者所提供的多品種、小批量的貨物，通過(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í)行計(jì)劃配送，需配送的商品有一定的庫(kù)存量，一般情況很少超越自己的經(jīng)營(yíng)范圍。配送中心的設(shè)施及工藝流程是根據(jù)配送需要專(zhuān)門(mén)設(shè)計(jì)的，所以配送能力很強(qiáng)，配送距離較遠(yuǎn)，配送的品種較多，配送數(shù)量比較大。使用配送中心配送覆蓋面寬，規(guī)模大，

24、因此，必須有一套配套的大規(guī)模實(shí)施配送的設(shè)施。本文的研究背景就是基于配送中心的物流配送中車(chē)輛調(diào)度問(wèn)題的研究。(4) 客戶(hù)客戶(hù)指的是物流配送的服務(wù)對(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(5) 運(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)用。

25、邊或弧的權(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)都有限制。(6) 約束條件物流配送車(chē)輛調(diào)度問(wèn)題應(yīng)滿(mǎn)足以下約束條件：能夠滿(mǎn)足所有客戶(hù)對(duì)貨物品種、規(guī)格、數(shù)量的要求；能夠在客戶(hù)要求或者承受的時(shí)間內(nèi)將貨物送到；運(yùn)輸車(chē)輛每天的運(yùn)行時(shí)間、運(yùn)行歷程都要有一定的限制，不能超過(guò)預(yù)定的時(shí)間或者里程；在物流配送過(guò)程中實(shí)際裝載的貨物不能超過(guò)車(chē)

26、輛的最大載重要求，也就是不能超載；當(dāng)然，客戶(hù)的需求也必須在物流中心現(xiàn)有的運(yùn)力范圍內(nèi)，也就是目前有這個(gè)能力去完成待完成的任務(wù)。(7) 目標(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ī)疲勞程度等因素。

27、因此，在眾多的目標(biāo)函數(shù)中選擇配送里程最短的目標(biāo)，在某種程度上可以直接減少運(yùn)輸成本。 配送車(chē)輛的載重量與公里數(shù)最少，這種方式的目標(biāo)是將配送距離與車(chē)輛的載重量進(jìn)行了有機(jī)結(jié)合，綜合來(lái)考慮載重量與配送距離之間的關(guān)系，以達(dá)到最優(yōu)化的配置，是比較常用的目標(biāo)之一。9 綜合費(fèi)用最低，完成最多的任務(wù)，花最少的成本，這是物流配送中的一個(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)格的要求。配送

28、任務(wù)完成的準(zhǔn)時(shí)性，很大程度上決定了配送公司在客戶(hù)心中的地位，決定了公司的信譽(yù)度。各種成本雖然是必須考慮的因素，也是最實(shí)際的因素，但是為提高配送服務(wù)質(zhì)量，按時(shí)完成用戶(hù)的需求，有時(shí)需要將準(zhǔn)時(shí)性最高作為配送路線(xiàn)的目標(biāo)。 使用的車(chē)輛數(shù)最少，該目標(biāo)考慮的是使用盡量少的車(chē)輛去完成指定的配送任務(wù)。前面的目標(biāo)敘述了各項(xiàng)指標(biāo)的要求，但是如果車(chē)輛跑的距離最短、也是按時(shí)到達(dá)的，但是使用的車(chē)輛都沒(méi)有滿(mǎn)載，這無(wú)疑也是對(duì)資源的一種浪費(fèi)，也不能是整體配送效益達(dá)到最優(yōu)，所以必須要求車(chē)輛的滿(mǎn)載率最高，以充分利用車(chē)輛的裝載能力。 勞動(dòng)消耗最低，充分考慮人的因素。也就是使用最少的司機(jī)數(shù)，這當(dāng)然和前面使用最少的車(chē)輛數(shù)是一致的，只有車(chē)

29、輛少了，司機(jī)才會(huì)少，只有車(chē)輛都裝滿(mǎn)了，才會(huì)使用最少的車(chē)輛。只有選擇的距離最短了，司機(jī)才能工作最短的時(shí)間，這些都是重要的目標(biāo)值。2.3 車(chē)輛調(diào)度問(wèn)題的分類(lèi)車(chē)輛調(diào)度問(wèn)題(Visual-Schedule Problem，VSP)被提出后，國(guó)內(nèi)外各學(xué)科的學(xué)者從不同角度對(duì)它進(jìn)行了各種研究，并各自按不同的標(biāo)準(zhǔn)對(duì)其進(jìn)行了分類(lèi)。綜合起來(lái)可分為以下幾種：(1) 按車(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è)配送中心。(2) 按配送任務(wù)特征分：分為純送貨問(wèn)題、純?nèi)∝泦?wèn)題以及取送混合問(wèn)題。其中純送貨問(wèn)題指僅僅考慮從物流中心向客戶(hù)

30、送貨，而不考慮從用戶(hù)向配送中心送貨；純?nèi)∝泦?wèn)題指單純考慮把各客戶(hù)供應(yīng)的貨物取到配送中心不考慮配送中心給客戶(hù)供貨問(wèn)題；取送混合問(wèn)題是上面兩者的有機(jī)組合，既要考慮將客戶(hù)需求的貨物從物流中心送到各個(gè)客戶(hù)，同時(shí)還考慮將客戶(hù)提供的貨物從客戶(hù)取到物流中心。(3) 按車(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ù)需求和供應(yīng)的貨物數(shù)量大于或等于車(chē)輛的載重量

31、，同時(shí)又存在另一部分客戶(hù)需求量或供應(yīng)的貨物數(shù)量小于車(chē)輛的載重量，上述情況就造成一部分配送車(chē)輛滿(mǎn)載運(yùn)行，而另一部分運(yùn)行在非滿(mǎn)載的狀態(tài)。(4) 按客戶(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í)間范圍內(nèi)送到，并且將供應(yīng)的貨物在一定的時(shí)間范圍內(nèi)取走。有時(shí)間約束問(wèn)題又分為硬時(shí)間窗問(wèn)題和軟時(shí)間窗問(wèn)題，硬時(shí)間窗問(wèn)題指的是對(duì)任務(wù)的完成有硬性的時(shí)間限制，或者說(shuō)時(shí)間要求。軟時(shí)間窗問(wèn)題指的是有一定的時(shí)間約束，但是相對(duì)比較寬松，盡量在用戶(hù)規(guī)定的時(shí)間范圍內(nèi)將貨物送到或者取走，但是如果

32、超越了規(guī)定的時(shí)間限制可能要有一定的處罰機(jī)制。(5) 按車(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ù)雜。(6) 按車(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)行的研究。(7) 按優(yōu)化目標(biāo)數(shù)分：分為單目標(biāo)問(wèn)題和多目標(biāo)問(wèn)題。單目標(biāo)問(wèn)題指的是僅考慮一個(gè)配送目標(biāo)；而多目標(biāo)問(wèn)題

33、指的是同時(shí)考慮多個(gè)配送目標(biāo)。2.4 車(chē)輛調(diào)度的相關(guān)求解算法用于解決物流配送車(chē)輛調(diào)度問(wèn)題的算法分為：精確算法和啟發(fā)式算法兩大類(lèi)，精確算法一般用于解決小規(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í)間內(nèi)獲得較滿(mǎn)意的次優(yōu)解，并且這些算法的通用性也很強(qiáng)。常見(jiàn)的啟發(fā)式算法有如下幾種：(1) C-W Savings算法C-W Savings算法采用了幾何中三角形的邊定理，即三角形的兩邊之和大于第三邊。當(dāng)路徑中有這樣的兩個(gè)邊時(shí)用第三邊來(lái)代替，以達(dá)到節(jié)約配送距離的目的。我們可以設(shè)節(jié)點(diǎn)i和

34、節(jié)點(diǎn)j之間的節(jié)約量為Sij，這兩點(diǎn)和節(jié)點(diǎn)o之間的距離為Doi和Doj，則Sij=Doi+Doj-Dij（ij, i,j=1,2,n,），算法首先求出所有Sij，并按非增順序排列。然后從最大的Sij開(kāi)始，確定是否存在兩條路徑，其中一條從弧(0,j)開(kāi)始，而另一條以(i,o)結(jié)束。如果存在，則去掉弧(0,j) 、(i,o)，引入弧(j,i)合并這兩條路徑。重復(fù)上述過(guò)程直到?jīng)]有路徑可以合并。(2) Sweep算法Sweep算法是一種“先分組后路線(xiàn)”的算法。所謂的分組就是：首先計(jì)算出要訪(fǎng)問(wèn)的顧客的位置的極坐標(biāo)，并把這些極坐標(biāo)按角度大小排序，然后在未分配到任何路徑中的顧客中從角度最小的顧客開(kāi)始，依次將顧

35、客歸并到相應(yīng)的路徑中，直到車(chē)輛的能力約束滿(mǎn)足為止，再重新選擇新的車(chē)輛，重復(fù)上述過(guò)程，直到所有的顧客都分配完畢。最后利用TSP的優(yōu)化算法對(duì)各子路經(jīng)進(jìn)行優(yōu)化。(3) Cluster and Route算法一般有兩種方法：先聚類(lèi)后排序方法(CFRS)和先排序后聚類(lèi)方法(RFCS)。CFRS最早由G.Gillett等提出，它是先用啟發(fā)式方法將節(jié)點(diǎn)分成若干路徑，然后對(duì)路徑中的點(diǎn)進(jìn)行排序。RFCS由Besley提出，它先對(duì)所有節(jié)點(diǎn)進(jìn)行TSP排序，然后將大的路徑分成若干個(gè)小路徑。(4) 遺傳算法GA遺傳算法使用群體搜索技術(shù)，借用適者生存規(guī)律進(jìn)行局部搜索改進(jìn)，它通過(guò)對(duì)當(dāng)前群體施加選擇、交叉、變異等一系列遺傳操

36、作，從而產(chǎn)生出新一代的群體，每一次進(jìn)化則對(duì)應(yīng)解的一次迭代，并逐步使群體進(jìn)化到包含或接近最優(yōu)解的狀體。當(dāng)?shù)螖?shù)達(dá)到最大次數(shù)限制或群體中的個(gè)體無(wú)顯著差異時(shí)，迭代終止。J.Lawrence最先將GA應(yīng)用于求解車(chē)輛調(diào)度問(wèn)題。(5) 禁忌搜索算法TSTS的思想由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è)合適的解。(6) 模擬退火

37、算法SA其思想最早有Metropolis 1953年提出，Osman于1993年用之解決VRP。模擬退火算法用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能模擬為目標(biāo)函數(shù)值，溫度演化成控制參數(shù)。由初始解和控制參數(shù)初值開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減控制參數(shù)值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。(7) 蟻群優(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)。

38、在用蟻群算法解決車(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等；還有的利用局部信息，適合改進(jìn)解，如SA、TS等。每種方法都各有所長(zhǎng)與不足，一般來(lái)說(shuō)，根據(jù)具體的求解問(wèn)題，采用兩種或兩種以上的混合方法，能夠得到更好的解。2.5 小結(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)題的算法。第三章 遺傳算法概述3.1 背景介紹遺傳

39、算法 (GeneticA lgorithm.G A)是由美國(guó)Michigan大學(xué)J.Holland教授和他的學(xué)生發(fā)展建立的一類(lèi)借鑒生物界的進(jìn)化規(guī)律 適者生存、優(yōu)勝劣汰遺傳機(jī)制演化而來(lái)的概率搜索算法。GA算法是近幾年發(fā)展起來(lái)的一種嶄新的全局優(yōu)化算法，遺傳算法作為一種非數(shù)值并行算法，其思想起源于生物遺傳學(xué)適者生存的自然規(guī)律，通過(guò)自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)體適應(yīng)性的提高。它是多學(xué)科結(jié)合與滲透的產(chǎn)物，已經(jīng)發(fā)展成一種自組織、自適應(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)題。特別是由于它不受

40、搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性、導(dǎo)數(shù)存在等假設(shè)，以及其固有的并行性。它是一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進(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)有很快的發(fā)展，在組合優(yōu)化、自適應(yīng)控制、機(jī)器學(xué)習(xí)等許多領(lǐng)域獲得應(yīng)用，并在電氣自動(dòng)化、計(jì)算機(jī)和通信以及人工智能的許多領(lǐng)域取得了

41、非凡的成就，尤其適合求解NP-hard問(wèn)題。3.2 遺傳算法的基本概念由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法，因而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念。這些概念如下：(1) 串(String)它是個(gè)體(Indlvidual)的形式，對(duì)應(yīng)于遺傳學(xué)中的染色體(Chromosome)。(2) 群體(Population)個(gè)體的集合稱(chēng)為群體，個(gè)體是群體的元素。(3) 群體大小(Populationsize)在群體中個(gè)體的數(shù)量稱(chēng)為群體的大小。(4) 基因(Gene)基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S=1010，則其中的1，0，1，0這4個(gè)元素分別稱(chēng)為基因。(

42、5) 基因位置(GenePosition)一個(gè)基因在串中的位置稱(chēng)為基因位置，有時(shí)也簡(jiǎn)稱(chēng)基因位?；蛭恢糜纱淖筮呄蛴矣?jì)算，如在串S=1011中，0基因位置是2?；蛭恢脤?duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus)。(6) 基因特征值(GeneFeature)在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致，如在串S=1011中，第三基因位值上的1，它的基因特征值為2；第一基因位值上的1，它的基因特征值為8。(7) 串結(jié)構(gòu)空間S在串中，基因任意組合構(gòu)成的串的集合稱(chēng)為串結(jié)構(gòu)空間?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行的。(8) 適應(yīng)度(Fitness)表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度。為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)

43、題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)適應(yīng)度函數(shù)，用于計(jì)算個(gè)體在群體中被使用的概率。(9) 選擇(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)。(10) 交叉(Crossover)就是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體隨機(jī)選取一個(gè)子串進(jìn)行交換，從而產(chǎn)生新的個(gè)體。(11) 變異(Mutation)就是在選中的個(gè)體中，隨機(jī)選擇兩點(diǎn)，將兩點(diǎn)間的子串

44、按一定的規(guī)則進(jìn)行變異。3.3 遺傳算法的工作流程遺傳算法在整個(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所示。圖3.1遺傳算法流程圖從圖3.1可以看出，遺傳算法的運(yùn)行為一個(gè)典型的迭代過(guò)程，其必須完成的工作內(nèi)容和基本步驟如下：(1) 選擇編碼策略，將解空間中的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的

45、不同組合便構(gòu)成了不同的編碼。(2) 定義適應(yīng)度函數(shù)f(x )。(3) 確定遺傳策略，包括選擇群體大小n，選擇、交叉、變異方法，以及確定交叉概率pc、變異概率pm等遺傳參數(shù)。(4) 隨機(jī)初始化生成群體P。(5) 計(jì)算群體中個(gè)體位串解碼后的適應(yīng)度f(wàn)(x)。(6) 按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體。(7) 判斷群體性能是否滿(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)題

46、的能力。3.4 遺傳算法的組成遺傳算法主要由六個(gè)部分組成：編碼方式、初始群體產(chǎn)生的方法、評(píng)價(jià)函數(shù)、遺傳操作、算法終止條件、算法參數(shù)的設(shè)置。要利用遺傳算法成功的解決物流配送車(chē)輛調(diào)度問(wèn)題，就需要對(duì)這六個(gè)步驟進(jìn)行設(shè)計(jì)。3.4.1 編碼方式在遺傳算法的運(yùn)行過(guò)程中，它不對(duì)所求解問(wèn)題的實(shí)際決策變量直接進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼施加選擇、交叉、變異等遺傳運(yùn)算，通過(guò)這種遺傳操作來(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)題的可行解從其解

47、空間轉(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)生很多在可行解集合內(nèi)無(wú)對(duì)應(yīng)可行解的個(gè)體，這些個(gè)體經(jīng)解碼處

48、理后所表示的解稱(chēng)為無(wú)效解。雖然有時(shí)產(chǎn)生一些無(wú)效解并不完全都是有害的，但大部分情況下它卻是影響遺傳算法運(yùn)行效率的主要因素之一。針對(duì)一個(gè)具體應(yīng)用問(wèn)題，如何設(shè)計(jì)一種完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)之一，也是遺傳算法的一個(gè)重要研究方向?？梢哉f(shuō)目前還沒(méi)有一套既嚴(yán)密又完整的指導(dǎo)理論及評(píng)價(jià)準(zhǔn)則能夠幫助我們?cè)O(shè)計(jì)編碼方案。作為參考，De Jong曾提出了兩條操作性較強(qiáng)的使用編碼原則：編碼原則一：應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案。編碼原則二：應(yīng)使用能使問(wèn)題得到自然表示或描述的具有最小編碼字符集的編碼方案。第一個(gè)編碼原則中，模式是指具有某些基因相似性的個(gè)體的集合，而具有短定

49、義長(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)樗鼭M(mǎn)足這條編碼原則的思想要求。事實(shí)上，理論分析表明，與其他編碼字符集相比，二進(jìn)制編碼方案能包含最大的模式數(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所

50、組成的二值符號(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所示)。圖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)，而且與

51、其所在字符串的位置有關(guān)，這樣的問(wèn)題稱(chēng)為有序問(wèn)題，用有序串編碼方法表示。這類(lèi)編碼方法較多地用在組合優(yōu)化問(wèn)題中，如二次分配問(wèn)(QuadraticAssignment problem)，旅行商問(wèn)題(Traveling Salesman Problem)我們常用的是有序串的編碼方式。基于遺傳算法的以上特點(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ī)交互方式

52、來(lái)初始化群體，這樣結(jié)合人類(lèi)智慧使算法優(yōu)化收斂速度更快。3.4.2 適應(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)程度較高的物種將有更多的繁殖機(jī)會(huì)；而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就相對(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ù)（Fitness Function）。遺傳算法的一個(gè)特點(diǎn)是它僅使用

53、所求問(wèn)題的目標(biāo)函數(shù)值就可以得到下一步的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù)值的使用是通過(guò)評(píng)價(jià)個(gè)體的適應(yīng)度來(lái)體現(xiàn)的。評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程是：(1) 對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可達(dá)到個(gè)體的表現(xiàn)型。(2) 由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。(3) 根據(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ù)值最小的

54、解為最優(yōu)解。3.4.3 選擇策略遺傳算法中的選擇策略就是用來(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à)的基礎(chǔ)之上的，選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。下面是遺傳算法中較常用到的幾種選擇策略。(1) 繁殖池(Breeding Pool)選擇繁殖池選擇首先根據(jù)當(dāng)前群體中個(gè)體的適應(yīng)值，按下式計(jì)算其相對(duì)適應(yīng)值

55、：其fi 是群體中第 i 個(gè)成員的適應(yīng)值，N是群體規(guī)模。則每個(gè)個(gè)體的繁殖量為：此處Round(x)表示與x距離最小的整數(shù)。計(jì)算出群體中每個(gè)個(gè)體的繁殖量，即可將它們分別復(fù)制N個(gè)以生成一個(gè)臨時(shí)群體，即繁殖池(Breeding pool)再通過(guò)在繁殖池中隨機(jī)地抽取成對(duì)個(gè)體進(jìn)行交配，所產(chǎn)生的后代將取代當(dāng)前群體形成下一個(gè)群體。顯然，個(gè)體復(fù)制到繁殖池的數(shù)目越大，則它被選到進(jìn)行交配的機(jī)會(huì)也就越多，而對(duì)于 Ni =0 的個(gè)體，它們將被淘汰出整個(gè)演化過(guò)程。在實(shí)現(xiàn)算法時(shí)需要注意的是，繁殖池中個(gè)體的數(shù)目不一定正好等于N。(2) 輪盤(pán)賭選擇(Roulette Wheel Selection)輪盤(pán)賭選擇是由Hollan

56、d提出的，是最知名的選擇方式之一，其基本原理是根據(jù)每個(gè)染色體適應(yīng)值的比例來(lái)確定該個(gè)體的選擇概率或生存概率。選擇的過(guò)程就是旋轉(zhuǎn)輪盤(pán)若干次（次數(shù)等于種群規(guī)模），每次為新種群選出一個(gè)個(gè)體。輪盤(pán)賭選擇策略在遺傳算法中使用的最多，它的具體選擇過(guò)程為：先計(jì)算個(gè)體的適應(yīng)值Pi ，然后根據(jù)選擇概率把輪盤(pán)分成N份，其中第 i 扇形的中心角為 2Pi。在進(jìn)行選擇時(shí)，先轉(zhuǎn)動(dòng)輪盤(pán)，若某參照點(diǎn)落入到第i個(gè)扇形內(nèi)，則選擇個(gè)體i?？梢?jiàn)，這種選擇方式非常類(lèi)似輪盤(pán)賭中的轉(zhuǎn)盤(pán)，小扇區(qū)的面積越大，骰子落入其中的概率也越大，即個(gè)體的適應(yīng)值越大，它被選擇到的機(jī)會(huì)也越大。從而，其基因結(jié)構(gòu)被遺傳到下一代的可能性也越大。(3) 錦標(biāo)賽（To

57、umament）選擇錦標(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è)體具有較大的“生存”機(jī)會(huì)。同時(shí)，由于它只使用適應(yīng)度的相對(duì)值作為選擇的標(biāo)準(zhǔn)，而無(wú)個(gè)體適應(yīng)度的算術(shù)運(yùn)算。從而它能避免超級(jí)個(gè)體的影響，在一定程度上，避免發(fā)生過(guò)早收斂現(xiàn)象和停滯現(xiàn)象。3.4.4 雜交策略交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色

58、體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。一方面它使原來(lái)群體中優(yōu)良個(gè)體的特性能夠在一定程度上被遺傳和繼承，另一方面它使算法能夠搜索新的基因空間，從而使新群體中的個(gè)體具有多樣性。交叉或基因重組是遺傳算法獲取新的優(yōu)良個(gè)體的最重要的手段。經(jīng)常采用的交叉算子有以下幾種：(1) 部分映射交叉(Partially Mapped Crossover，簡(jiǎn)稱(chēng)PMX)這種算子在構(gòu)造后代時(shí)通過(guò)從一個(gè)父體中選取一段路徑，并盡可能多的保留另一個(gè)父體中城市的次序和位置。選擇一個(gè)路徑時(shí)，首先隨機(jī)選取兩切割點(diǎn)作為交換操作的邊界。例如兩父體(兩切割點(diǎn)用“|”標(biāo)記)P1= (1 2 3 | 4 5 6 7 | 8 9) P2= (2 5 4 | 1 8 7 6 | 3 9)產(chǎn)生后代的過(guò)程如下：首先交換兩切割點(diǎn)之間的相應(yīng)段(符號(hào)“x” 表示目前未知值)，得到Q1=( x x x | 1 8 7 6 | x x ) Q2= ( x x x | 4 5 6 7 | x x)這一交換同時(shí)定義了一系列的映射：然后從各自的父體中填入無(wú)沖突的城市，得到：Q