【正文】 足約束條件1：式中：K為所有車輛的集合， ；G為所有客戶的集合， ， ，其中{0}代表配送中心； 為由車輛k服務(wù)的客戶的集合； 為車輛到達(dá)客戶i的時(shí)間；為懲罰函數(shù)，車輛在時(shí)間 到達(dá)客戶i時(shí)所對(duì)應(yīng)的懲罰成本；為車輛從客戶i到客戶j的所有運(yùn)輸成本；為車輛從客戶i到客戶j的行車時(shí)間；為客戶i的需求量；Q為車輛k的最大裝載量；為車輛在客戶i處的停留的時(shí)間。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。這5個(gè)要素構(gòu)成了遺傳算法的核心內(nèi)容。 遺傳算法是具有“生成+檢測(cè)”(generateandtest)的迭代過(guò)程的搜索算法。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問(wèn)題，可廣泛用于組合優(yōu)化、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。當(dāng)時(shí)，其主要目的是說(shuō)明自然和人工系統(tǒng)的自適應(yīng)過(guò)程。它是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。 總結(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長(zhǎng)，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的發(fā)展前途的方法；SA算法求解速度非常快，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問(wèn)題上具有較好效果。Ombuk提出了用遺傳算法進(jìn)行路線分組，然后用禁忌搜索方法進(jìn)行路線優(yōu)化的混合算法。遺傳算法具有求解組合優(yōu)化問(wèn)題的良好特性，Holland首先采用遺傳算法（GA）編碼解決VRPTW 問(wèn)題。西南交通大學(xué)的袁慶達(dá)等設(shè)計(jì)了考慮時(shí)間窗口和不同車輛類型的禁忌算法，這種算法主要采用GENIUS方法產(chǎn)生初始解，然后禁忌算法對(duì)初始解優(yōu)化。 1990年以來(lái)，人工智能方法在解決組合優(yōu)化問(wèn)題上顯示出強(qiáng)大功能，在各個(gè)領(lǐng)域得到充分應(yīng)用，很多學(xué)者也將人工智能引入車輛路線問(wèn)題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法。 兩階段方法包括先分組后定路線（clusterfirstroute second）和先定路線后分組（routefirstcluster second）兩種啟發(fā)式策略。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來(lái)建立車隊(duì)配送路線。節(jié)省法或插入法（savings or insertion）是在求解過(guò)程中使用節(jié)省成本最大的可行方式構(gòu)造路線，直到無(wú)法節(jié)省為止。車輛運(yùn)輸問(wèn)題的啟發(fā)式方法可以分為簡(jiǎn)單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。第一階段是從1960年到1970年，屬于簡(jiǎn)單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（Greedy）等；第二階段是從1970年到1980年，屬于一種以數(shù)學(xué)規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開(kāi)始至今，屬于較新的方法，包括利用嚴(yán)謹(jǐn)啟發(fā)式方法、人工智能方法等。 求解方法演進(jìn) 綜合過(guò)去有關(guān)車輛路線問(wèn)題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻殖民算法等。下面從車輛路線問(wèn)題的現(xiàn)有研究型態(tài)和求解方法兩個(gè)方面介紹車輛路線問(wèn)題的研究現(xiàn)狀。 多個(gè)起點(diǎn)和終點(diǎn)。 車輛路徑問(wèn)題的類型一般而言車輛路線問(wèn)題大致可以分為以下三種類型（Ballou，1992）： 相異的單一起點(diǎn)和單一終點(diǎn)。車輛從場(chǎng)站出發(fā)對(duì)客戶進(jìn)行配送服務(wù)最后返回場(chǎng)站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。 車輛路線問(wèn)題自1959年提出以來(lái)，一直是網(wǎng)絡(luò)優(yōu)化問(wèn)題中最基本的問(wèn)題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，一直受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。 由此定義不難看出，旅行商問(wèn)題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery。本文對(duì)大量的基準(zhǔn)測(cè)試實(shí)例(Benchmark)進(jìn)行了仿真計(jì)算,計(jì)算結(jié)果表明,本文所提出的一系列算法能有效求解物流系統(tǒng)中的庫(kù)存優(yōu)化問(wèn)題與車輛路徑問(wèn)題。 (6)綜合應(yīng)用了面向?qū)ο蠓治雠c設(shè)計(jì)、多線程、UML等先進(jìn)的軟件開(kāi)發(fā)方法與技術(shù),設(shè)計(jì)并開(kāi)發(fā)了VRP仿真實(shí)驗(yàn)室,這是一個(gè)用于研究車輛路徑問(wèn)題的軟件包,具有使用簡(jiǎn)便、界面美觀的特點(diǎn)。然后研究了遺傳算法與鄰域搜索算法的結(jié)合方式,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。基于上述雙層染色體編碼方案和子路徑交換算法,設(shè)計(jì)了兩種求解CVRP問(wèn)題的混合遺傳算法,分別是HGACVRP算法和HGASECVRP算法。此外,相對(duì)于常用的單層染色體編碼方案,該編碼方案還能降低搜索空間的大小,從而提高搜索效率并降低計(jì)算時(shí)間。 (4)對(duì)于帶能力約束的車輛路徑問(wèn)題(CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。提出了K近鄰點(diǎn)集的概念以縮減搜索空間并提高算法的時(shí)間效率。為了求解TSP問(wèn)題,研究了常用于TSP問(wèn)題的三種交叉算子的優(yōu)化效果,提出了一種求解TSP問(wèn)題的高效混合遺傳算法HGATSP。針對(duì)兩種常用的庫(kù)存控制策略進(jìn)行了仿真優(yōu)化的實(shí)驗(yàn),結(jié)果表明本文提出的仿真優(yōu)化方法是有效的。針對(duì)隨機(jī)系統(tǒng)的特點(diǎn),設(shè)計(jì)了候選解收集器,它能夠收集在仿真優(yōu)化過(guò)程中產(chǎn)生的Pareto解。用系統(tǒng)仿真方法求解最優(yōu)庫(kù)存策略時(shí),其難點(diǎn)之一在于仿真的優(yōu)化。本文將庫(kù)存仿真優(yōu)化問(wèn)題與車輛路徑問(wèn)題都看作是組合優(yōu)化問(wèn)題,并應(yīng)用遺傳算法進(jìn)行求解。 遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法,本文對(duì)遺傳算法進(jìn)行了分析研究,針對(duì)遺傳算法的一些缺陷提出了相應(yīng)的改進(jìn)方法。 庫(kù)存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據(jù)了很大的比例。通過(guò)優(yōu)化物流系統(tǒng),可以降低物流成本,從而增強(qiáng)企業(yè)的市場(chǎng)競(jìng)爭(zhēng)能力。CVRP 要求滿足以下條件及假設(shè)：（1）所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心；（2）每條配送路徑上各客戶點(diǎn)的需求量之和不超過(guò)車輛的負(fù)載量；（3）每個(gè)客戶點(diǎn)的需求僅由一輛車一次滿足。有容量約束的車輛路徑問(wèn)題（Capacitated Vehicle routing problem，CVRP）是由一個(gè)服務(wù)中心（或車場(chǎng)）的若干車輛向多個(gè)客戶點(diǎn)進(jìn)行配送服務(wù)，在已知待服務(wù)客戶點(diǎn)和出發(fā)點(diǎn)的位置、客戶需求及車輛最大負(fù)載的前提下，設(shè)計(jì)車輛配送路徑，規(guī)劃設(shè)計(jì)方案，使運(yùn)輸成本最小化，即總代價(jià)最?。ㄊ褂密囕v盡量少，行車總距離盡量短）。研究車輛路徑問(wèn)題的特點(diǎn)及算法具有重要的實(shí)際意義。VRP 最早由Dantzig 和Ramser 于1959 年提出，引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科研究人員的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)問(wèn)題。在分組編碼遺傳算法中提出路徑調(diào)整思想，設(shè)計(jì)出一種多策略分組編碼遺傳算法。 本文首先介紹了遺傳算法在解決簡(jiǎn)單約束車輛路徑問(wèn)題上的應(yīng)用，改進(jìn)了交叉算子，為研究有時(shí)間窗裝卸問(wèn)題的遺傳算法作了充分準(zhǔn)備。 sweep method。 掃描法。最后論文在對(duì)動(dòng)態(tài)行駛時(shí)間車輛路徑問(wèn)題進(jìn)行建模的基