【正文】 2選題的目的物流已被認(rèn)為是繼降低原材料消耗和提高勞動生產(chǎn)率之后的“第三利潤源”。通過優(yōu)化物流系統(tǒng),可以降低物流成本,從而增強(qiáng)企業(yè)的市場競爭能力。因此,研究物流系統(tǒng)中的優(yōu)化問題,具有十分重要的意義,是國內(nèi)外研究的一個熱點(diǎn)。 庫存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據(jù)了很大的比例。如果能降低庫存成本與配送成本,就能有效地降低物流成本。 遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法,本文對遺傳算法進(jìn)行了分析研究,針對遺傳算法的一些缺陷提出了相應(yīng)的改進(jìn)方法。在上述研究基礎(chǔ)上,本文基于遺傳算法,研究了物流系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。本文將庫存仿真優(yōu)化問題與車輛路徑問題都看作是組合優(yōu)化問題,并應(yīng)用遺傳算法進(jìn)行求解。 本文的主要研究工作及貢獻(xiàn)可歸納如下: (1)對隨機(jī)庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計算機(jī)仿真模型。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時,其難點(diǎn)之一在于仿真的優(yōu)化。為此,本文將計算機(jī)仿真技術(shù)和遺傳算法相結(jié)合,應(yīng)用遺傳算法來優(yōu)化模型的控制參數(shù),即獲得最優(yōu)的庫存控制策略。針對隨機(jī)系統(tǒng)的特點(diǎn),設(shè)計了候選解收集器,它能夠收集在仿真優(yōu)化過程中產(chǎn)生的Pareto解。提出了M精英選擇算子,用于保護(hù)潛在的最優(yōu)個體,使它們在交叉、變異算子中不被破壞。針對兩種常用的庫存控制策略進(jìn)行了仿真優(yōu)化的實(shí)驗(yàn),結(jié)果表明本文提出的仿真優(yōu)化方法是有效的。 (2)旅行商問題(TSP)是車輛路徑問題的子問題。為了求解TSP問題,研究了常用于TSP問題的三種交叉算子的優(yōu)化效果,提出了一種求解TSP問題的高效混合遺傳算法HGATSP。在該算法中以變形的OX算子作為交叉算子,以2opt算法作為遺傳算法的變異算子。提出了K近鄰點(diǎn)集的概念以縮減搜索空間并提高算法的時間效率。 (3)將單配送中心,多輛運(yùn)輸車且無約束的車輛路徑問題建模成具有總路徑長度最短、子路徑長度均衡性好這兩個目標(biāo)的雙目標(biāo)多旅行商問題(MTSP),并基于HGATSP算法,研究了三種求解上述問題的解決方案。 (4)對于帶能力約束的車輛路徑問題(CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。雙層染色體編碼方案不需要預(yù)先知道最優(yōu)解所需要的車輛數(shù),并能確保染色體不違反能力約束,這更適合求解實(shí)際物流配送系統(tǒng)中的車輛路徑問題。此外,相對于常用的單層染色體編碼方案,該編碼方案還能降低搜索空間的大小,從而提高搜索效率并降低計算時間。子路徑交換算法可以有效提高遺傳算法的求解精度?；谏鲜鲭p層染色體編碼方案和子路徑交換算法,設(shè)計了兩種求解CVRP問題的混合遺傳算法,分別是HGACVRP算法和HGASECVRP算法。 (5)對于帶時間窗約束的車輛路徑問題(VRPTW,首先改進(jìn)了雙層染色體編碼方案,以便在編程實(shí)現(xiàn)時更方便地進(jìn)行子路徑的處理。然后研究了遺傳算法與鄰域搜索算法的結(jié)合方式,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。最后提出了一種求解VRPTW問題的新型混合遺傳算法HGAVRPTW。 (6)綜合應(yīng)用了面向?qū)ο蠓治雠c設(shè)計、多線程、UML等先進(jìn)的軟件開發(fā)方法與技術(shù),設(shè)計并開發(fā)了VRP仿真實(shí)驗(yàn)室,這是一個用于研究車輛路徑問題的軟件包,具有使用簡便、界面美觀的特點(diǎn)。VRP仿真實(shí)驗(yàn)室在本文的研究中發(fā)揮了重要的作用,是研究車輛路徑問題的有力工具。本文對大量的基準(zhǔn)測試實(shí)例(Benchmark)進(jìn)行了仿真計算,計算結(jié)果表明,本文所提出的一系列算法能有效求解物流系統(tǒng)中的庫存優(yōu)化問題與車輛路徑問題。3 問題描述車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個車隊負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時間最少等目的。 由此定義不難看出，旅行商問題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery。已證明TSP問題是NP難題，因此，VRP也屬于NP難題。 車輛路線問題自1959年提出以來，一直是網(wǎng)絡(luò)優(yōu)化問題中最基本的問題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價值，一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。車輛路線問題可以描述如下（如圖1）： 圖1 路徑問題描述設(shè)有一場站（depot），共有M 輛貨車，車輛容量為Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場站出發(fā)對客戶進(jìn)行配送服務(wù)最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實(shí)際問題包括配送中心配送、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。 車輛路徑問題的類型一般而言車輛路線問題大致可以分為以下三種類型（Ballou，1992）： 相異的單一起點(diǎn)和單一終點(diǎn)。 相同的單一起點(diǎn)和終點(diǎn)。 多個起點(diǎn)和終點(diǎn)。 車輛路線問題研究現(xiàn)狀經(jīng)過幾十年的研究發(fā)展，車輛路線問題研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個方面介紹車輛路線問題的研究現(xiàn)狀。在基本車輛路線問題（VRP）的基礎(chǔ)上，車輛路線問題在學(xué)術(shù)研究和實(shí)際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括時窗限制車輛路線問題（vehicle routing problems with time windows，VRPTW）、追求最佳服務(wù)時間的車輛路線問題（VRPDT）、多車種車輛路線問題（fleet size and mix vehicle routing problems，F(xiàn)SVRP）、車輛多次使用的車輛路線問題（vehicle routingproblems with multiple use of vehicle，VRPM）、考慮收集的車輛路線問題（vehicle routingproblems with backhauls，VRPB）、隨機(jī)需求車輛路線問題（vehicle routing problem with stochastic demand，VRPSD）等。 求解方法演進(jìn) 綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻殖民算法等。1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個階段。第一階段是從1960年到1970年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（Greedy）等；第二階段是從1970年到1980年，屬于一種以數(shù)學(xué)規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開始至今，屬于較新的方法，包括利用嚴(yán)謹(jǐn)啟發(fā)式方法、人工智能方法等。 啟發(fā)式算法 由于VRP是NPhard問題，難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運(yùn)輸問題的主要方法，多年來許多學(xué)者對車輛運(yùn)輸問題進(jìn)行了研究，提出了各種各樣的啟發(fā)式方法。車輛運(yùn)輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 簡單啟發(fā)式方法包括節(jié)省法或插入法、路線內(nèi)/間節(jié)點(diǎn)交換法、貪婪法和局部搜索法等方法。節(jié)省法或插入法（savings or insertion）是在求解過程中使用節(jié)省成本最大的可行方式構(gòu)造路線，直到無法節(jié)省為止。交換法則是依賴其他方法產(chǎn)生一個起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。1960