物流配送車輛畢業(yè)論文

1、<p>　　物流配送車輛路徑優(yōu)化方法研究</p><p><b>　　摘 要</b></p><p>　　目前，國際物流業(yè)正朝著高度專業(yè)化和社會(huì)化的方向發(fā)展。近年來，雖然我國物流業(yè)取得了很大的發(fā)展，但與國外發(fā)達(dá)國家相比，仍有較大的差距。在物流各環(huán)節(jié)中，物流配送對(duì)物流企業(yè)增加利潤起著關(guān)鍵作用，車輛路徑問題(VRP)作為解決物流配送問題技術(shù)的一部分，得到越來越多

2、研究學(xué)者和物流企業(yè)的重視。</p><p>　　VRP是一個(gè)典型的NP-hard問題，即使在客戶規(guī)模比較小的情況下，求解也比較困難。因此，研究求解各種條件下 VRP的有效算法顯得尤為重要。從目前的研究狀況來看，雖然對(duì)VRP的研究得到了重視，但是仍沒有對(duì)實(shí)際VRP而臨的各種情況進(jìn)行深入的探討，而且成果比較分散，無論是研究的深度和廣度，都不能滿足當(dāng)今物流業(yè)迅速發(fā)展的需要。</p><p>　　

3、針對(duì)上述問題，本文在車輛調(diào)度問題現(xiàn)有的理論成果基礎(chǔ)上，運(yùn)用智能方法對(duì)各種靜態(tài)非滿載車輛調(diào)度問題作了比較系統(tǒng)的研究。首先通過相關(guān)文獻(xiàn)的總結(jié)提煉，較為全面地總結(jié)了國內(nèi)外車輛調(diào)度問題的研究現(xiàn)狀和研究過程中所存在的不足。然后運(yùn)用遺傳算法對(duì)單車場(chǎng)容量約束情況下的車輛調(diào)度問題進(jìn)行優(yōu)化，并且針對(duì)具體情況下不同智能算法的特點(diǎn)進(jìn)行改進(jìn)，尋求優(yōu)化車輛調(diào)度問題性能最好的智能算法。最后應(yīng)用健壯性最好的智能方法對(duì)各種靜態(tài)情況下的車輛調(diào)度問題進(jìn)行研究，這些情況主要

4、包括:單車場(chǎng)VRP，多車場(chǎng)VRP，集送一體化VRP，開放式VRP等。</p><p>　　本文對(duì)各種靜態(tài)情況下的車輛調(diào)度問題都進(jìn)行了試驗(yàn)并且給出了代表性的算例，通過與同類文獻(xiàn)的比較，顯示了本文所提出的智能方法對(duì)優(yōu)化車輛調(diào)度問題的有效性和可行性。</p><p>　　關(guān)鍵字: 物流配送 車輛調(diào)度 遺傳算法 數(shù)學(xué)模型 分支切割算法</p><p>　　Study

5、 on Logistics Distribution Vehicle Routing Problem</p><p><b>　　ABSTRACT</b></p><p>　　In recent years, China's logistics industry has achieved great development, but as compared w

6、ith foreign developed countries, there are still large gaps. In all the links of logistics, logistics distribution plays a key role in increasing profits of logistics enterprises. As part of solutions to the technical pr

7、oblem of logistics distribution,vehicle routing problem(VRP) is getting more and more attention in academics and enterprises.</p><p>　　VRP is a typical NP-hard problem. Even in the relatively small size of t

8、he customers, getting the solution also is difficult. Therefore, studying under all conditions for the effective VRP algorithm appears to be particularly important. Judging from the current situation of the study, althou

9、gh the study on VRP has got much attention, but still not on the actual situation facing the VRP-depth study. The VRP research results are rather scattered, the depth and breadth of which are unable to meet t</p>

10、<p>　　To realize the problem, in this paper, the deployment of various static VRP with non-full load is studied systematically based on current theoretical methods. In order to find the best suitable algorithm, a su

11、mmary of concerning references is liven and the current insufficiencies of domestic and foreign researches of VRP are reviewed. Then this paper uses improved genetic algorithm At last, an intelligent method is liven to s

12、tudy on various static VRP. These conditions include single-depot VRP w</p><p>　　In this paper, many representational examples are liven .Compared with the results attained by some other references, the expe

13、riments indicate the validity and feasibility of the intelligent method to the VRP.</p><p>　　KEY WORDS: Logistics of distribution; Vehicle Scheduling; Genetic algorithm;</p><p>　　Mathematic Mode

14、l; Branch cutting algorithm</p><p><b>　　目　錄</b></p><p><b>　　前　言1</b></p><p>　　第1章 ××××××2</p><p>　　1.1 ×

15、15;××××2</p><p>　　1.1.1 ××××××2</p><p>　　1.1.2 ××××××2</p><p>　　1.1.3 ××××

16、5;×2</p><p>　　第2章 ××××××4</p><p>　　2.1 ××××××4</p><p>　　2.1.1 ××××××4</p>&

17、lt;p>　　2.1.2 ××××××4</p><p>　　2.2 ××××××5</p><p>　　2.2.1 ××××××5</p><p>　　第3章 ×&

18、#215;××××6</p><p>　　3.1 ××××××6</p><p>　　3.1.1 ××××××6</p><p>　　3.1.2 ××××

19、5;×6</p><p>　　3.2 ××××××6</p><p>　　第4章 ××××××7</p><p>　　4.1 ××××××7</p><

20、;p>　　4.1.1 ××××××7</p><p>　　4.1.2 ××××××7</p><p>　　4.2 ××××××7</p><p>　　第5章 ×

21、15;××××8</p><p>　　5.1 ××××××8</p><p>　　5.1.1 ××××××8</p><p>　　5.1.2 ×××××

22、×8</p><p>　　5.2 ××××××8</p><p>　　5.2.1 ××××××8</p><p>　　5.2.2 ××××××8</p>&

23、lt;p><b>　　結(jié)　論9</b></p><p><b>　　謝 辭10</b></p><p><b>　　參考文獻(xiàn)11</b></p><p><b>　　附　錄13</b></p><p><b>　　外文資料翻譯14

24、</b></p><p><b>　　前　言</b></p><p>　　隨著社會(huì)主義市場(chǎng)經(jīng)濟(jì)的不斷發(fā)展，作為“第三利潤源泉”的物流對(duì)經(jīng)濟(jì)活動(dòng)的影響日益明顯，引起了人們?cè)絹碓蕉嗟闹匾暎蔀楫?dāng)前“最重要的競(jìng)爭(zhēng)領(lǐng)域”。配送是現(xiàn)代物流的一個(gè)重要環(huán)節(jié)，隨著物流的全球化、信息化及一體化,配送在整個(gè)物流系統(tǒng)中的作用變得越來越重要。配送是連接生產(chǎn)與消費(fèi)之間的一種中介服務(wù)

25、。它是指按客戶(包括零售商店、用戶等)的訂貨要求(包括貨物種類、數(shù)量和時(shí)間等方面的要求)，在物流中心(包括配送中心、倉庫、車站、港口等)進(jìn)行分貨、配貨工作，并將配好的貨物及時(shí)送交收貨人的物流活動(dòng)。</p><p>　　配送不是單純的運(yùn)輸或送貨，而是運(yùn)輸與其他活動(dòng)（集貨，分貨，配貨）的組合，是“配”與“送”的有機(jī)結(jié)合。因此對(duì)于配送問題的研究可分為對(duì) “配”和“送”兩方面的研究。“配”主要為配送中心選址問題，“送”包

26、括旅行商問題(TSP)、車輛路線優(yōu)化問題(VRP)。由于選址的外部因素（經(jīng)濟(jì)，基礎(chǔ)設(shè)施，環(huán)境等）及內(nèi)部因素（企業(yè)戰(zhàn)略，勞動(dòng)力成本和素質(zhì)等）的影響，單純考慮距離問題的選址是不合理的，因此在本文中不對(duì)“配”進(jìn)行研究，主要對(duì)“送”進(jìn)行研究。</p><p>　　配送路線的優(yōu)化，是配送優(yōu)化中的一個(gè)關(guān)鍵環(huán)節(jié)。在配送過程中，配送線路合理與否對(duì)配送速度、成本、效益影響很大。設(shè)計(jì)合理、高效的配送路線方案，不僅可以減少配送時(shí)間，降

27、低作業(yè)成本，提高企業(yè)的效益，而且可以更好地為客戶服務(wù)，提高客戶的滿意度，維護(hù)企業(yè)良好的形象。</p><p>　　配送線路優(yōu)化是指對(duì)一系列的發(fā)貨點(diǎn)和收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€使車輛有序的通過它們，在滿足一定的約束條件下（貨物需求量與發(fā)送量，車輛容量限制，行駛里程限制），力爭(zhēng)實(shí)現(xiàn)一定的目標(biāo)（行駛里程最短，使用車輛盡可能少）。但配送作業(yè)情況復(fù)雜多變，不僅存在配送點(diǎn)多、貨物種類多、道路網(wǎng)復(fù)雜、路況多變等情況，而且運(yùn)輸服

28、務(wù)地區(qū)內(nèi)需求網(wǎng)點(diǎn)分布也不均勻，使得線路優(yōu)化問題是一個(gè)無確定解多項(xiàng)式難題，需要遺傳算法算法去求得近似最優(yōu)解。</p><p>　　本文將以當(dāng)前的配送線路的優(yōu)化問題作為研究對(duì)象，對(duì)各客戶需求量及運(yùn)距進(jìn)行分析計(jì)算，建立VRP數(shù)學(xué)模型，運(yùn)用分支切割算法和以及改進(jìn)的遺傳算法法對(duì)建立的模型進(jìn)行求解，對(duì)物流配送路線進(jìn)行優(yōu)化。最后對(duì)兩種種方法求得的結(jié)果進(jìn)行比較分析，從而提出較合理的配送方案，以期減少配送里程，降低物流運(yùn)輸成本，提

29、高物流運(yùn)作效率，客戶服務(wù)質(zhì)量和整體競(jìng)爭(zhēng)力。</p><p><b>　　第1章 緒論</b></p><p>　　1.1 研究背景及意義</p><p>　　1.1.1 研究背景</p><p>　　自從18世紀(jì)工業(yè)革命在西方發(fā)初以來，人類便以為自己尋到了自我發(fā)展的終極密碼，隨著滾滾的車輪與隆隆的機(jī)器轟鳴，一番無邊無際、

30、無限無量的樂觀發(fā)展前景被反復(fù)展示。但這種樂觀最終被現(xiàn)實(shí)擊碎，“無限發(fā)展觀”一步步淪陷。在西方發(fā)達(dá)國家的經(jīng)濟(jì)發(fā)展過程中，最初企業(yè)是把降低材料的成本當(dāng)作是擴(kuò)大利潤的一個(gè)最重要的來源，所以這時(shí)候把降低材料費(fèi)用作為第一利潤源泉。當(dāng)材料成本降低到一定幅度以后，可能的空間就不大了，這時(shí)候發(fā)現(xiàn)通過降低人工成本可以獲取更多的利潤，于是實(shí)現(xiàn)了工廠作業(yè)的自動(dòng)化，所以把這種途徑稱為第二利潤源泉。同樣，隨著市場(chǎng)競(jìng)爭(zhēng)日益激烈，企業(yè)人工費(fèi)用的降低也是有一定限度的，

31、達(dá)到一定限度的時(shí)候，企業(yè)的發(fā)展受到很大的限制。后來人們發(fā)現(xiàn)如果能有效地降低在成本中占據(jù)相當(dāng)高比例的物流費(fèi)用，就等于提高了利潤，這時(shí)候人們開始把物流稱為第三利潤源泉。</p><p>　　盡管物流活動(dòng)自古有之，但直到1915年，“物流”這一名詞才第一次出現(xiàn)在阿齊.肖的《市場(chǎng)流通中的若千問題》一書中，經(jīng)過數(shù)十年的理論研究和實(shí)際運(yùn)作，人們?cè)絹碓秸J(rèn)識(shí)到物流的重要性。雖然人們對(duì)物流的認(rèn)識(shí)有了長(zhǎng)足的進(jìn)步，但是這個(gè)領(lǐng)域未知的東

32、西還很多，理論和實(shí)踐皆不成熟。著名的管理學(xué)權(quán)威PE德魯克曾經(jīng)講過，“流通是經(jīng)濟(jì)領(lǐng)域里的黑暗大陸”。日本早稻田大學(xué)西澤修教授在研究物流成本時(shí)發(fā)現(xiàn)，現(xiàn)行的財(cái)務(wù)會(huì)計(jì)制度和會(huì)計(jì)核算方法都不可能掌握物流費(fèi)用的實(shí)際情況，因而人們對(duì)物流費(fèi)用的了解是一片空白，甚至有很大的虛假性，他把這種情況比作“物流冰山”。冰山的特點(diǎn)，是最大部分沉在水而之下，而露出水而的僅是冰山的一角。物流就是一座冰山，其中沉在水而以下的是我們看不到的黑色領(lǐng)域，而我們看到的不過是物流

33、的一部分。事實(shí)證明，物流領(lǐng)域的方方而而對(duì)我們而言還是不清楚的，在黑大陸中和冰山的水下部分正是物流尚待開發(fā)的領(lǐng)域，也正是物流的潛力所在。隨著信息技術(shù)的發(fā)展尤其是因特網(wǎng)的出現(xiàn)和普及，使電子商務(wù)得到了迅速的發(fā)展，商務(wù)活動(dòng)所必需的信息流、資金流都可以在網(wǎng)上瞬間實(shí)現(xiàn)，這是電子商務(wù)成為可能條件之一，大大縮短了商品交易活動(dòng)的時(shí)間和空間，這使傳</p><p><b>　　1.1.2研究意義</b><

34、/p><p>　　一、我國發(fā)展現(xiàn)代物流的意義</p><p>　　1.現(xiàn)代物流產(chǎn)業(yè)的發(fā)展，是降低企業(yè)成本，促進(jìn)我國經(jīng)濟(jì)發(fā)展的需要</p><p>　　1）現(xiàn)代物流產(chǎn)業(yè)的發(fā)展，可以大大降低高昂的物流費(fèi)用</p><p>　　有資料顯示，目前我國工業(yè)企業(yè)生產(chǎn)中，直接勞動(dòng)成本占總成本的比重不到10%，物流費(fèi)用占商品總成本的比重高達(dá)40%。全社會(huì)物流費(fèi)用

35、占GDP的比重約為20%，而美國不足10%。如果我國能達(dá)到同一水平，按照2006年的GDP水平，全社會(huì)可節(jié)約2萬億元的物流成本，或者說可以多產(chǎn)生近2萬億元的利潤。</p><p>　　2)現(xiàn)代物流產(chǎn)業(yè)的發(fā)展，能極大的減少庫存占?jí)嘿Y金</p><p>　　由于物流速度緩慢，加之企業(yè)業(yè)務(wù)流程以傳統(tǒng)模式為主，目前全國長(zhǎng)年積累的庫存商品高達(dá)4萬億元左右。落后的物流和巨大的庫存占?jí)嘿Y金，使我國眾多企

36、業(yè)資本周轉(zhuǎn)極其緩慢。目前，我國國有獨(dú)立核算工業(yè)企業(yè)流動(dòng)資本年平均周轉(zhuǎn)速度為1.2次，國有商業(yè)流動(dòng)資本年平均周轉(zhuǎn)2.3次，而現(xiàn)代物流體系發(fā)達(dá)的日本企業(yè)流動(dòng)資金年平均周轉(zhuǎn)15至18次，沃爾瑪、麥德龍、家樂福等跨國連鎖流通企業(yè)資金的年周轉(zhuǎn)速度則高達(dá)20至30次。</p><p>　　現(xiàn)代物流產(chǎn)業(yè)的發(fā)展，將減少低水平、條塊分割的物流方式造成的巨大物耗我國傳統(tǒng)物流采取的是“大而全”、“小而全”的經(jīng)營方式，各種物流方式互不關(guān)

37、聯(lián)，物流過程中的物耗驚人。據(jù)估算，全國一年蔬菜損失價(jià)值達(dá)1354億元，糧食損失價(jià)值35.7億元，鋼材銹蝕損失價(jià)值1000億元。在傳統(tǒng)的物流模式下，一件商品從生產(chǎn)環(huán)節(jié)到最終的消費(fèi)環(huán)節(jié)，至少要搬運(yùn)十幾次，如果實(shí)行社會(huì)化的多式聯(lián)運(yùn)、一單到底，物流過程中的物耗可以大大減少。</p><p>　　2. 現(xiàn)代物流產(chǎn)業(yè)的發(fā)展，是經(jīng)濟(jì)全球化的需要</p><p>　　經(jīng)濟(jì)全球化的加強(qiáng)是當(dāng)前世界經(jīng)濟(jì)的一個(gè)重

38、要特征，其含義是指商品、資本、技術(shù)、勞動(dòng)力等資源配置己超出一個(gè)國家的范圍，是在地區(qū)甚至在全球范圍內(nèi)實(shí)現(xiàn)最優(yōu)配置的過程，其實(shí)質(zhì)是一場(chǎng)以發(fā)達(dá)國家為主導(dǎo)，跨國公司為推動(dòng)力，通過交叉投資、兼并收購為主要方式進(jìn)行的世界范圍內(nèi)產(chǎn)業(yè)結(jié)構(gòu)的調(diào)整。它的產(chǎn)生意味著“無國界經(jīng)濟(jì)”及“地球村”等現(xiàn)象的顯現(xiàn)，表明世界經(jīng)濟(jì)中各國經(jīng)濟(jì)開放度不斷提高及相互依存關(guān)系的加深。</p><p>　　經(jīng)濟(jì)全球化的加強(qiáng)迫使國內(nèi)外工商企業(yè)為參與市場(chǎng)競(jìng)爭(zhēng)，越

39、來越注重集中精力發(fā)展主業(yè)，培育在技術(shù)、管理、采購、營銷等上的核心競(jìng)爭(zhēng)力，一般把非核心的如在運(yùn)輸、倉儲(chǔ)、配送等物流業(yè)務(wù)作為整體供應(yīng)鏈的一部分外包給專業(yè)的物流公司，這是現(xiàn)代物流產(chǎn)生的重要?jiǎng)右?。而目前我國第三方物流市?chǎng)的特征之一是“兩頭在外”(物流的需求方和供應(yīng)商多為跨國公司)，現(xiàn)代物流服務(wù)作為傳統(tǒng)貨運(yùn)服務(wù)的替代品，前者同后者的區(qū)別主要表現(xiàn)在其功能的集成和基于合同為基礎(chǔ)的客戶合作伙伴關(guān)系，由此導(dǎo)致現(xiàn)代物流服務(wù)的發(fā)展?jié)摿薮蟆?lt;/p>

40、;<p><b>　　二、物流配送的意義</b></p><p>　　配送本質(zhì)上是運(yùn)輸，因此創(chuàng)造空間效用自然是它的主要功能。但配送又不同于運(yùn)輸，它是運(yùn)輸在功能上的延伸。物流配送的發(fā)展對(duì)物流的重要意義可歸納為以下幾個(gè)方面：</p><p>　　1.能促進(jìn)物流設(shè)施和裝備的技術(shù)進(jìn)步</p><p>　　現(xiàn)代大載重量的運(yùn)輸工具，固然可以提

41、高效率，降低運(yùn)輸成本，但是只適用于干線運(yùn)輸。支線運(yùn)輸一般是小批量，使用載重量大的運(yùn)輸工具則是一種浪費(fèi)。支線小批量運(yùn)輸頻次高、服務(wù)性強(qiáng)，要求比干線運(yùn)輸具有更高的靈活性和適應(yīng)性，而配送通過其他的物流環(huán)節(jié)的配合，可實(shí)現(xiàn)定制化服務(wù)，能滿足這種要求。發(fā)展物流配送有利于促進(jìn)物流設(shè)施和裝備的技術(shù)進(jìn)步，具體表現(xiàn)在三個(gè)方而:一是促進(jìn)信息處理技術(shù)的進(jìn)步。隨著配送業(yè)務(wù)的開展，處理的信息量將越來越多，原始手工的信息處理速度慢且容易出錯(cuò)，己經(jīng)適應(yīng)不了配送工作的要

42、求，必然大量應(yīng)用電子計(jì)算機(jī)這一現(xiàn)代化的信息處理技術(shù);第二是促進(jìn)物流處理技術(shù)的進(jìn)步，從而提高物流速度，縮短物流時(shí)間，降低物流成本，減少物流損耗，提高物流服務(wù)質(zhì)量。配送業(yè)務(wù)的發(fā)展，必然伴隨著自動(dòng)化立體倉庫、自動(dòng)化分揀裝置、無人搬運(yùn)車、托盤化、集裝箱化等現(xiàn)代物流技術(shù)的應(yīng)用;</p><p>　　第三是推動(dòng)物流規(guī)劃技術(shù)的開發(fā)與應(yīng)用。配送業(yè)務(wù)的開展，配送貨主越來越多，隨之而來的就是產(chǎn)生一個(gè)配送路線的合理選擇、配送中心選址、

43、配送車輛的配置和配送效益的技術(shù)經(jīng)濟(jì)核算等問題，對(duì)于這些問題的研究解決，能促進(jìn)我國物流技術(shù)的發(fā)展，并使之達(dá)到一個(gè)新階段。</p><p><b>　　2.能消除交叉運(yùn)輸</b></p><p>　　在沒有配送中心的情況下，由生產(chǎn)企業(yè)直接運(yùn)送貨物到用戶，即使采取直接配送方式，交叉運(yùn)輸也是普遍存在的。由于交叉運(yùn)輸?shù)拇嬖?，使輸送路線長(zhǎng)，規(guī)模效益差，運(yùn)輸成本高。如果在生產(chǎn)企業(yè)與

44、客戶之間設(shè)置配送中心，采取配送方式，則可消除交叉運(yùn)輸。因?yàn)樵O(shè)置配送中心以后，將原來直接由各生產(chǎn)企業(yè)送至各客戶的零散貨物通過配送中心進(jìn)行整合再實(shí)施配送，緩解了交叉輸送，使輸送距離縮短，成本降低。用大型卡車成批量的送到消費(fèi)者的配送中心，再用小型車從配送中心運(yùn)給用戶的方法，可以從總體上節(jié)省費(fèi)用。集中配送有利于集中庫存，維持合理的庫存水平，消除了分散庫存造成的各種浪費(fèi);同時(shí)還能減少不必要的中轉(zhuǎn)環(huán)節(jié)，縮短物流周轉(zhuǎn)時(shí)間，減少物品的損耗，對(duì)提高物流綜

45、合經(jīng)濟(jì)效益有利。</p><p><b>　　3.能改變倉儲(chǔ)職能</b></p><p>　　配送通過集中庫存，在同樣的需求滿足水平上，可使系統(tǒng)總庫存水平降低，既降低了存儲(chǔ)成本，也節(jié)約了運(yùn)力和其它物流費(fèi)用。尤其是采用準(zhǔn)時(shí)制配送方式后，生產(chǎn)可以根據(jù)配送中心準(zhǔn)時(shí)送貨而無須保持自己的庫存，或者只需保持少量的保險(xiǎn)庫存，這就可以實(shí)現(xiàn)生產(chǎn)企業(yè)的“零庫存”或低庫存，減少資金占用，改

46、善企業(yè)的財(cái)務(wù)狀況。開展配送業(yè)務(wù)后，現(xiàn)代倉儲(chǔ)的作用己由儲(chǔ)存、保管物品的使用價(jià)值向著集散、分送貨物，加速物品流通速度的方向發(fā)展。倉儲(chǔ)業(yè)將從儲(chǔ)存、保管的靜態(tài)儲(chǔ)存轉(zhuǎn)向以保管儲(chǔ)存、流通加工、分類、揀選、物品輸送等聯(lián)為一體的動(dòng)態(tài)儲(chǔ)存。建立配送中心后，倉儲(chǔ)業(yè)的經(jīng)營活動(dòng)將由原來的儲(chǔ)備型轉(zhuǎn)為流通型，不僅要保證物品的使用價(jià)值完好無損，而且要做到貨源充足，品種齊全，供應(yīng)及時(shí)，送貨上門，其經(jīng)營方式將從等客上門向主動(dòng)了解用戶的需求狀況，以滿足用戶的各種要求的方向

47、轉(zhuǎn)變。</p><p>　　4.提高保證供應(yīng)速度、方便用戶</p><p>　　采用配送方式，配送中心比任何單獨(dú)供貨企業(yè)有更強(qiáng)的物流能力，可使用戶減少缺貨風(fēng)險(xiǎn)。由于配送可提供全方位的物流服務(wù)，采用配送方式后，用戶只需向配送供應(yīng)商進(jìn)行一次委托，就可以得到全過程、多功能的物流服務(wù)，從而簡(jiǎn)化了委托手續(xù)和工作量，節(jié)省了開支。</p><p>　　三、VRP的研究意義<

48、/p><p>　　VRP問題作為解決物流配送核心技術(shù)的一部分，越來越得到研究學(xué)者和物流企業(yè)的重視。VRP問題主要解決的問題為:如何有效地使用載運(yùn)工具來運(yùn)送各站點(diǎn)間的旅客和貨物，要求確定哪些旅客和貨物該由何車輛、按何順序、在何時(shí)運(yùn)送，才能在滿足諸如車輛裝載能力和運(yùn)送時(shí)間等限制條件下，使總費(fèi)用為最小。V RP的研究意義主要表現(xiàn)在以下幾個(gè)方面。</p><p>　　1.能提高物流經(jīng)濟(jì)效益</p

49、><p>　　針對(duì)具體的V RP問題，通過對(duì)實(shí)際情況分析，可以將VRP相關(guān)的前提條件和各項(xiàng)成本進(jìn)行量化，明確VRP的目標(biāo)和約束，對(duì)資源進(jìn)行優(yōu)化整合與配置，通過優(yōu)化配送路徑、開展“計(jì)劃配送”、“共同配送”等形式，消除迂回運(yùn)輸、重復(fù)運(yùn)輸、交叉運(yùn)輸、空載運(yùn)輸?shù)炔缓侠憩F(xiàn)象，減少物流配送成本，提高企業(yè)的物流經(jīng)濟(jì)效益。據(jù)統(tǒng)計(jì)[fll，我國的汽車空駛率高達(dá)37%，如按照現(xiàn)代物流要求合理設(shè)計(jì)流程，可使空駛率降低到5%}能極大減少運(yùn)載

50、成本。</p><p>　　2.能提高物流管理的科學(xué)化水平</p><p>　　VRP不僅能解決車輛調(diào)度的優(yōu)化問題，同時(shí)也是提高物流管理水平的一種手段。一方而，通過對(duì)具體VRP問題進(jìn)行分析，能夠得出在現(xiàn)有條件下極大的減小物流成本、提高服務(wù)水平的物流配送方案。例如確定配送車輛對(duì)客戶的服務(wù)時(shí)間窗范圍、優(yōu)先順序和服務(wù)水平等。同時(shí)，對(duì)于一些突發(fā)事件，能夠采取有效的候選方案，減小不確定事件對(duì)企業(yè)和客

51、戶的影響;另一方而，由VRP優(yōu)化方案實(shí)施后反饋的數(shù)據(jù)，也能對(duì)企業(yè)員工的工作效率和工作質(zhì)量進(jìn)行監(jiān)督與控制，提高企業(yè)管理水平。例如，能夠根據(jù)預(yù)先制定的優(yōu)化方案與客戶反饋的信息與進(jìn)行對(duì)比，對(duì)員工的表現(xiàn)進(jìn)行評(píng)價(jià)，制定相應(yīng)的激勵(lì)機(jī)制，提高物流管理的科學(xué)化水平。</p><p>　　3.能夠促進(jìn)VRP相關(guān)領(lǐng)域的發(fā)展</p><p>　　雖然VRP最初是以物流配送為背景提出來的，但其應(yīng)用范圍早己超出了物

52、流配送領(lǐng)域。在國外，VRP己經(jīng)廣泛的運(yùn)用于生產(chǎn)、生活的各個(gè)方而，如報(bào)紙投遞及線路的優(yōu)化、牛奶配送及送達(dá)線路的優(yōu)化、電話預(yù)定貨物的車輛載貨和線路的設(shè)計(jì)、垃圾車的線路優(yōu)化及垃圾站選址的優(yōu)化、連鎖商店的送貨及線路優(yōu)化等。隨著VRP研究的加深和應(yīng)用的擴(kuò)展，該問題的應(yīng)用不僅僅局限在物流配送領(lǐng)域，還被拓展到倉庫貨位、揀貨優(yōu)化、電路設(shè)計(jì)、電網(wǎng)布局等領(lǐng)域。</p><p>　　1.2 VRP相關(guān)理論研究綜述</p>

53、<p>　　物流配送車輛優(yōu)化調(diào)度問題最早是由Dantzig和Ramser于1959年首次提出，他們描述了一個(gè)將汽油送往各加油站的實(shí)際問題，并提出了相應(yīng)的數(shù)學(xué)規(guī)劃模型及其求解算法Ell. Bodin, Golden等人在他們的綜述文章中對(duì)一般的車輛優(yōu)化調(diào)度問題做了詳盡的論述。隨著研究的深入發(fā)展，如何使研究的理論模型更貼近現(xiàn)實(shí)中的運(yùn)輸調(diào)度問題開始成為研究焦點(diǎn)。</p><p>　　Laporte和Nobe

54、rt等人(1985年)主要研究了帶容量和距離限制的車輛優(yōu)化調(diào)度問題，Solomon和Desrosiers等人(1987年)考慮將時(shí)M約束加入到一般的車輛優(yōu)化調(diào)度問題中，最早對(duì)帶時(shí)間約束的車輛優(yōu)化調(diào)度問題進(jìn)行了研究。 90年代以后車輛優(yōu)化調(diào)度問題引起了運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科的專家與運(yùn)輸計(jì)劃制定者和管理者的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點(diǎn)問題。隨著現(xiàn)代物流的不斷發(fā)展，多車場(chǎng)車

55、輛優(yōu)化調(diào)度問題、隨機(jī)車輛優(yōu)化調(diào)度問題、裝卸混合車輛優(yōu)化調(diào)度問題等更加復(fù)雜的路徑問題被不斷的提出和研究。</p><p>　　目前國內(nèi)外用于解決該問題的現(xiàn)代數(shù)學(xué)方法主要分為以下幾類:精確優(yōu)化方法、啟發(fā)式方法、模擬方法、交互式優(yōu)化方法。以往廣泛采用的是第一種方法，另外三種方法則代表了較近的研究思想。尤其是啟發(fā)式方法，作為一種逐次逼近的算法，雖然不一定得到最優(yōu)解，但可以高效地得到具有較高精度的解，而且也易于考慮各種各樣

56、的實(shí)際問題，因此，現(xiàn)己成為解決物流配送問題的重要方法。</p><p>　　隨著人工智能技術(shù)的引入和不斷發(fā)展，模擬退火算法和遺傳算法等新的方法以及人工神經(jīng)網(wǎng)絡(luò)和專家系統(tǒng)等新技術(shù)，為解決大規(guī)模、多目標(biāo)車輛優(yōu)化調(diào)度問題提供了新的輔助手段。目前，算法研究集中在對(duì)啟發(fā)式規(guī)則和搜索方法的改進(jìn)，以便提高搜索速度和質(zhì)量。主要有混合遺傳算法、部分自適應(yīng)遺傳算法先聚類分析再優(yōu)化的兩階段法、蟻群算法、免疫算法、粒子隨著高性能計(jì)算機(jī)的

57、迅速發(fā)展，國外應(yīng)用計(jì)算機(jī)及現(xiàn)代數(shù)學(xué)方法調(diào)度車輛以優(yōu)化運(yùn)輸管理效果的研究工作正在較大范圍內(nèi)展開，在車輛調(diào)度的形式、構(gòu)造、分析以及求解方法的實(shí)現(xiàn)上都有了許多突破。并且某些常用且比較成熟的算法已被人們運(yùn)用于實(shí)際配送調(diào)度系統(tǒng)，如美國IBM以最短路算法和啟發(fā)式算法為核心算法的VSPX系統(tǒng)，日本以節(jié)約法為主要算法的VSS系統(tǒng)，美國美孚利用掃描法調(diào)度車輛的HPCAD系統(tǒng)等。 </p><p>　　另外，與先進(jìn)技術(shù)的結(jié)合也

58、是物流配送車輛優(yōu)化調(diào)度問題的一個(gè)突破。例如在國外一些國家將地理信息系統(tǒng)、全球定位系統(tǒng)、智能交通系統(tǒng)等技術(shù)應(yīng)用于物流配送車輛優(yōu)化調(diào)度問題中，更加有助于直觀的、實(shí)時(shí)的反映配送狀況，使得該系統(tǒng)更加智能化。群算法等算法在車輛路徑優(yōu)化問題中的應(yīng)用。 </p><p>　　第2章 車輛路徑問題及其求解算法基本理論</p><p>　　2.1 車輛路徑問題及組成要素</p><p&

59、gt;　　VRP問題可描述為:給定一系列的客戶點(diǎn)和車場(chǎng)，車輛從車場(chǎng)出發(fā)，在滿足一定的約束條件下，有序的通過這些客戶點(diǎn)完成配送任務(wù)，最后返回指定位置，使總費(fèi)用最小。VRP問題涉及的要素很多，本節(jié)從VRP的目標(biāo)和約束兩個(gè)方而分別闡述。</p><p><b>　　2.1.1 目標(biāo)</b></p><p>　　VRP問題的目標(biāo)主要有以下幾種：</p><

60、p>　　1) 最小化總運(yùn)輸成本，運(yùn)輸成本包括車輛折舊費(fèi)用、油費(fèi)，司機(jī)工資等；</p><p>　　2) 最小化配送車輛總配送里程，即所有配送車輛的總配送距離最小化；</p><p>　　3) 最小化配送車輛數(shù)，即對(duì)于同一配送任務(wù)，需要的配送車輛數(shù)最小化；</p><p>　　4)最大化客戶服務(wù)水平，將對(duì)客戶的服務(wù)水平進(jìn)行量化，最大化服務(wù)水平；</p>

61、;<p>　　5)其它目標(biāo)，如最小化配送車輛空載里程，最小化違約時(shí)間等。</p><p><b>　　2.1.2 約束</b></p><p>　　VRP問題的約束主要有以下幾種:</p><p>　　1)車輛能力約束。配送車輛都有容量大小，達(dá)到容量上限后必須要返回指定位置，這種約束稱為車輛能力約束。</p><

62、;p>　　2)配送里程約束。即配送車輛的最大配送距離約束，達(dá)到這個(gè)最大距離需要返回指定位置。</p><p>　　3)任務(wù)時(shí)間窗約束。設(shè)完成任務(wù)1需要的時(shí)間(裝貨或卸貨)表示為Ti，又設(shè)任務(wù)i的開始時(shí)間需要在一定的時(shí)間范圍[ETi，LTi]內(nèi)，其中ETi為任務(wù)i的允許最早開始時(shí)間，LTi為任務(wù)i的允許最遲開始時(shí)間。如果車輛到達(dá)i的時(shí)間早于ETi車輛需在i處等待。如果車輛到達(dá)i的時(shí)間晚于LTi，任務(wù)i要延遲進(jìn)

63、行。時(shí)間窗約束可分為軟時(shí)間窗約束和硬時(shí)間窗約束兩種。</p><p>　　4)車輛發(fā)車時(shí)間約束。在一個(gè)車場(chǎng)中，當(dāng)接到一項(xiàng)運(yùn)輸任務(wù)，并不一定當(dāng)時(shí)就有足夠的車輛派出執(zhí)行任務(wù)。例如可能有的車輛還在執(zhí)行上一項(xiàng)任務(wù)，還需一段時(shí)間才能回到車場(chǎng);有的車輛還在維修過程中，還需一段時(shí)間才能修復(fù)；司機(jī)也并不是全都能在一個(gè)時(shí)間上班發(fā)車。在這種情況下，就要考慮發(fā)車時(shí)間的影響，即車輛發(fā)車時(shí)間約束。</p><p>

64、　　5)配送順序約束。有的配送任務(wù)需要考慮配送順序，必須先到特定的客戶完成配送任務(wù)，才能完成后續(xù)的配送任務(wù)，這種約束在集送一體化VRP中出現(xiàn)較多。</p><p>　　6)車輛總數(shù)約束。車場(chǎng)的車輛不是無限供應(yīng)的，有一定的數(shù)量限制。</p><p>　　7)車型約束。物流配送公司大都有一種以上的貨運(yùn)車輛，由于不同的貨物有不同的比重和外形特征，可能有不同的包裝方法，運(yùn)輸車輛的載重量和車箱尺寸各

65、異，以及道路條件的限制等等，使得多車型運(yùn)輸組織比單車型復(fù)雜得多。當(dāng)有多種車型可用時(shí)，對(duì)同一項(xiàng)運(yùn)輸業(yè)務(wù)來說，使用不同車型的車時(shí)、可載量常不一樣，所需的空車數(shù)也不相同。</p><p>　　8)發(fā)車、回車車場(chǎng)約束。配送任務(wù)或者配送車輛限定了發(fā)車或回車車場(chǎng)的約束。</p><p>　　9)集送類型約束。分為單送貨、單集貨和集送一體化三種。配送任務(wù)只有送貨或只有集貨的稱為單送貨或單集貨VRP，一般

66、把這兩種作為一種類型處理。如果配送任務(wù)不僅需要送貨，也需要集貨，則稱為集送一體化VRP。</p><p>　　10)客戶貨物類型約束。即單個(gè)客戶配送量的大小、類型約束。</p><p>　　2.2 車輛路徑問題分類</p><p>　　VRP問題的分類法很多，為方便對(duì)該問題進(jìn)行系統(tǒng)研究，本文VRP問題進(jìn)行如下分類:</p><p>　　1.按

67、VRP前提條件和約束確定性來分，可分為靜態(tài)VRP和動(dòng)態(tài)VRP。靜態(tài)VRP的前提條件和約束都是確定的，即在進(jìn)行優(yōu)化調(diào)度之前所有情況己經(jīng)確定并且不會(huì)改變。動(dòng)態(tài)VRP,即前提條件和約束隨時(shí)間的改變而發(fā)生變化的情況。</p><p>　　2.按VRP涉及車場(chǎng)的數(shù)量來分，VRP可分為單車場(chǎng)或多車場(chǎng)兩種類型。</p><p>　　單車場(chǎng)VRP表示配送車輛發(fā)車或回車只有一個(gè)車場(chǎng);多車場(chǎng)VRP的配送車輛則

68、有多個(gè)車場(chǎng)可供選擇。如下圖2-1，2-2所示。</p><p>　　圖 2-1 單車場(chǎng)VRP問題</p><p>　　圖 2-2 多車場(chǎng)VRP問題</p><p>　　3.按車輛完成配送任務(wù)后是否回到原發(fā)車車場(chǎng)分，VRP可分為封閉式VRP,開放式VRP和半開放式VRP。封閉式VRP表示配送車輛的發(fā)車車場(chǎng)和回車車場(chǎng)一致;開放式VRP的配送車輛不一定回到原發(fā)車車場(chǎng)，回車

69、車場(chǎng)可以是指定的多個(gè)車場(chǎng)之一，也可以以完成最后一個(gè)配送任務(wù)為配送結(jié)束標(biāo)志，不用回到車場(chǎng);半封閉式V RP發(fā)車車場(chǎng)與回車車場(chǎng)不同，但回車車場(chǎng)固定。封閉式VRP見圖2-1, 2-2。開放式V RP，半開放式VRP如下圖2-3, 2-4所示。</p><p>　　圖 2-3 開放式VRP</p><p>　　圖2-4半開放式VRP</p><p>　　按VRP集送類型

70、分，VRP可分為單送貨/單集貨VRP和集送一體化VRP。單送貨/單集貨VRP中配送車輛只送貨或只集貨;集送一體化VRP則既送貨又集貨。圖2-1, 2-2, 2-3, 2-4都是單送貨/單集貨VRP,集送一體化VRP如下圖2-5所示。</p><p>　　圖2-5集送一體化VRP</p><p>　　5.按客戶貨物大小來分，分為滿載VRP和非滿載VRP。滿載VRP指配送任務(wù)中有客戶的配送任務(wù)

71、大于車輛的容量上限。非滿載VRP指配送任務(wù)中客戶的貨物量均小于車輛能力約束。</p><p>　　6.按VRP約束類型來分，可分為能力約束VRP，時(shí)間窗約束VRP，里程約束VRP等多種類型。這些VRP類型都是根據(jù)其約束條件的特點(diǎn)來進(jìn)行劃分的。</p><p>　　上述劃分只是針對(duì)VRP的某種特性進(jìn)行的劃分，實(shí)際上VRP的類型是上述劃分的各種組合。本文VRP的研究是按靜態(tài)/動(dòng)態(tài)一單車場(chǎng)/多車

72、場(chǎng)一封閉式/開方式一其它各種約束的層次進(jìn)行分類的，以后的各章節(jié)中，將會(huì)對(duì)以上分類的多種組合進(jìn)行研究。</p><p>　　2.3 物流配送車輛路徑問題復(fù)雜度分析</p><p>　　2.3.1 計(jì)算的復(fù)雜度</p><p>　　一．算法的復(fù)雜性與有效性</p><p>　　優(yōu)化組合問題算法的有效性可以用執(zhí)行該算法的各種計(jì)算資源來度量，其中最重

73、要的、最典型的兩個(gè)資源是所需的運(yùn)行時(shí)間和存儲(chǔ)空間，不過人們一般把最快的算法與最有效的算法等同起來，因?yàn)檫\(yùn)算時(shí)間常常是決定某一特定算法在實(shí)際中的實(shí)用性和有效性的主要因素。為了更具一般性，人們常常把問題規(guī)模n的函數(shù)來表示計(jì)算的復(fù)雜性，比如旅行商問題的城市數(shù)、背包問題的物品數(shù)。不同的算法具有不同的時(shí)間復(fù)雜性，那么什么樣的算法是好的、可以接受的呢?人們通常認(rèn)為，僅當(dāng)算法的時(shí)間復(fù)雜性函數(shù)是關(guān)于n的多項(xiàng)式函數(shù)時(shí)，才認(rèn)為這個(gè)算法是有效的，實(shí)用的。&l

74、t;/p><p>　　二．以算法復(fù)雜性為基礎(chǔ)的算法分類</p><p>　　以算法復(fù)雜性為基礎(chǔ)，可以把算法分為兩類:一類是多項(xiàng)式算法，即存在某個(gè)以n為變量的多項(xiàng)式P（n），使其時(shí)間復(fù)雜度函數(shù)為O（P（n））的算法;另一類是指數(shù)時(shí)間算法，n是作為指數(shù)出現(xiàn)在時(shí)間復(fù)雜度里而的。例如搜索2分法的時(shí)間復(fù)雜性是O(log n)，它是多項(xiàng)式算法，用動(dòng)態(tài)規(guī)劃方法解TSP問題，它的時(shí)間復(fù)雜性為O(n22n),它

75、是指數(shù)時(shí)間算法。</p><p>　　三．P問題、NP問題、NP完全問題、NP難題</p><p>　　1.P問題。如果一個(gè)問題有求解它的多項(xiàng)式算法，這個(gè)問題稱為P問題；</p><p>　　2. NP問題。若存在一個(gè)多項(xiàng)式函數(shù)g(x)和一個(gè)驗(yàn)證算法H，對(duì)一類判定問題A的任何一個(gè)“是”的判定實(shí)例I都存在一個(gè)字符串S是I的“是”回答，滿足其輸入長(zhǎng)度d(s)不超過g(d

76、(I))，其中d(I>為I的輸入長(zhǎng)度，且驗(yàn)證算法驗(yàn)證s為I的“是”回答的計(jì)算時(shí)間不超過g(d(I))，則稱判定問題A為多項(xiàng)式非確定性問題，簡(jiǎn)稱NP問題。</p><p>　　3.判定問題P到Q的歸約:是指存在一個(gè)轉(zhuǎn)換函數(shù)F，它可以把問題P的輸入x轉(zhuǎn)換為問題Q的輸入F(x)，使得問題P對(duì)于輸入x得到正確結(jié)果當(dāng)且僅當(dāng)問題Q對(duì)于輸入F(x)得到正確結(jié)果。多項(xiàng)式歸約是用來建立兩個(gè)為題P和Q之間的復(fù)雜程度的比較關(guān)系，

77、實(shí)際上就是通過轉(zhuǎn)換函數(shù)F(x)把求解問題P轉(zhuǎn)化為對(duì)問題Q的求解。</p><p>　　4. NP-C問題。也稱NP完全問題，如果判定問題AE NP且NP中任何一個(gè)問題可多項(xiàng)式歸約為問題A，則A為NP-C問題；</p><p>　　5. NP-hard問題。也稱NP難題，NP中任何一個(gè)問題可多項(xiàng)式歸約為問題A，但不確定是否ANP，稱問題A為NP-hard。NP-C能多項(xiàng)式歸約為NP-hard

78、，反推不成立。</p><p>　　P問題、NP問題、NP完全問題、NP難題的關(guān)系如下圖2-6所示。</p><p>　　圖2-6 P≠NP時(shí)，P，NP，NP-C，NP-hard的關(guān)系</p><p>　　2.3.2車輛路徑問題的復(fù)雜度</p><p>　　VRP被提出來后，對(duì)其求解算法的研究一直是研究的重點(diǎn)和難點(diǎn)。在對(duì)其求解算法進(jìn)行研究的同

79、時(shí)，不少學(xué)者也對(duì)它的計(jì)算復(fù)雜性進(jìn)行了研究，為確定求解算法的研究方向奠定了基礎(chǔ)。Lenstra證明了容量約束VRP是NP-hard問題;Hassin, Shlomi Rubinstein證明了kVRP問題在k等于3或4時(shí)，kVRP問題能找到多項(xiàng)式時(shí)間算法，但是當(dāng)k大于4時(shí)，只存在求解該問題的指數(shù)時(shí)間算法。AkioImai, ETSuko Nishimura等證明了多車型VRP屬于NP-hardo Solomon指出帶時(shí)間窗的V RP比一

80、般的VRP更復(fù)雜。Hideki Hashimoto, Toshihide Ibaraki等證明了軟時(shí)‘間窗VRP屬于NP-hard。Savelsbergh提出不僅帶時(shí)間窗的VRP本身是NP-hard問題，而且當(dāng)車隊(duì)大小(可用車輛數(shù))固定時(shí)，甚至要得到一個(gè)問題的可行解都是一個(gè)NP一難問題。Lenstra和Rinnooy Kan在對(duì)VRP的計(jì)算復(fù)雜性進(jìn)行綜述和分析的基礎(chǔ)上，證明了幾乎所有類型的VRP均為NP-hard問題。 <

81、;/p><p>　　2．4物流配送車輛路徑問題算法基本理論 </p><p>　　求解車輛路徑問題的算法包括精確算法和近似算法兩大類。本節(jié)主要介紹精確算法中分支切割法和近似算法中的遺傳算法。</p><p>　　2.4.1分支切割算法基本理論</p><p>　　分支切割法是在割平面法基礎(chǔ)上發(fā)展起來

82、的。1958年R. E. Gormory首先提出的，故又稱為Gomory割平面法。割平面法對(duì)整數(shù)規(guī)劃的發(fā)展非常重要，它是解整數(shù)規(guī)劃的第一種方法，而且可以證明通過有限迭代便收斂到最優(yōu)解。構(gòu)造割平面的不同，相應(yīng)的切割算法也不同。</p><p>　　割平面算法的基本思路是:在松弛問題中逐次增加一個(gè)新約束(即割平而)，它能割去原松弛問題可行域中一塊不含整數(shù)解的區(qū)域，逐次切割下去，直到最終所得松弛可行域的一個(gè)最優(yōu)極點(diǎn)為整

83、數(shù)解為止。</p><p>　　分支定界(branch and bound算法是一種在問題的解空間樹上搜索問題的解的方法，該算法的基本思想是:首先確定目標(biāo)值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。分支定界算法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法搜索解空間樹，并且在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。利用分支定界算法對(duì)問題的解空間樹進(jìn)行搜索，它的搜索策略是:</p><

84、p>　　1.產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有孩子結(jié)點(diǎn);</p><p>　　2.在產(chǎn)生的孩子結(jié)點(diǎn)中，拋棄那些不可能產(chǎn)生可行解(或最優(yōu)解)的結(jié)點(diǎn)；</p><p>　　3.將其余的孩子結(jié)點(diǎn)加入活結(jié)點(diǎn)表;</p><p>　　4.從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)。</p><p>　　如此循環(huán)，直到找到問題的可行解(最優(yōu)解)或活結(jié)點(diǎn)表為空

85、。</p><p>　　從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)，根據(jù)選擇方式的不同，分支定界算法通?？梢苑譃閮煞N形式。</p><p>　　FIFO (First In First Out)分支定界算法:按照先進(jìn)先出原則選擇下一個(gè)活結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，即從活結(jié)點(diǎn)表中取出結(jié)點(diǎn)的順序與加入結(jié)點(diǎn)的順序相同。</p><p>　　2.最小耗費(fèi)或最大收益分支定界算法:在這

86、種情況下，每個(gè)結(jié)點(diǎn)都有一個(gè)耗費(fèi)或收益。如果要查找一個(gè)具有最小耗費(fèi)的解，那么要選擇的下一個(gè)擴(kuò)展結(jié)點(diǎn)就是活結(jié)點(diǎn)表中具有最小耗費(fèi)的活結(jié)點(diǎn);如果要查找一個(gè)具有最大收益的解，那么要選擇的下一個(gè)擴(kuò)展結(jié)點(diǎn)就是活結(jié)點(diǎn)表中具有最大收益的活結(jié)點(diǎn)。</p><p>　　在用割平而法或分支定界法解整數(shù)規(guī)劃時(shí)，常會(huì)遇到收斂很慢的情形，因此，在使用時(shí)，往往割平而法和分支定界法配合使用，稱為分支切割算法。</p><p&g

87、t;　　2.4.2遺傳算法基本理論</p><p>　　遺傳算法(genetic algorithms，簡(jiǎn)稱GA)是J. Holland于1975年受生物進(jìn)化論的啟發(fā)而提出的。GA是基于適者生存的一種高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法，它將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進(jìn)化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求的問題的最優(yōu)解或滿意解。GA時(shí)一種通

88、用的優(yōu)化算法，其編碼技術(shù)和遺傳操作比較簡(jiǎn)單，優(yōu)化不受限制性條件的約束，而其兩個(gè)顯著的特點(diǎn)則是隱含并行性和全局解空間搜索。目前，隨著計(jì)算機(jī)技術(shù)的發(fā)展，GA愈來愈受到人們的重視，并在機(jī)器學(xué)習(xí)、模式識(shí)別、圖像處理、神經(jīng)網(wǎng)絡(luò)、優(yōu)化控制、組合優(yōu)化、遺傳學(xué)等領(lǐng)域得到了成功的應(yīng)用。</p><p>　　一、遺傳算法的基本流程</p><p>　　遺傳算法是一類隨機(jī)優(yōu)化算法，但它不是簡(jiǎn)單的隨機(jī)比較搜索，而

89、是通過對(duì)染色體的評(píng)價(jià)和對(duì)染色體基因的作用，有效的利用己有的信息來指導(dǎo)搜索最有希望改善優(yōu)化質(zhì)量的狀態(tài)。標(biāo)準(zhǔn)遺傳算法的主要步驟可描述如下。</p><p>　　1.隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始群體，并評(píng)價(jià)每一個(gè)體的適應(yīng)度(fitness value)。</p><p>　　2.判斷算法收斂準(zhǔn)則是否滿足。若滿足則輸出搜索結(jié)果，否則執(zhí)行以下步驟。</p><p>　　3.根

90、據(jù)適應(yīng)度大小以一定的方式執(zhí)行復(fù)制操作。</p><p>　　4.按交叉概率Pc執(zhí)行交叉操作。</p><p>　　5.按變異概率Pm執(zhí)行變異操作。</p><p><b>　　6.返回步驟2。</b></p><p>　　上述算法中，適應(yīng)度值是對(duì)染色體進(jìn)行評(píng)價(jià)的一種指針，是GA進(jìn)行優(yōu)化所用的主要信息，它與個(gè)體的目標(biāo)值存在

91、一種對(duì)應(yīng)關(guān)系;復(fù)制操作通常采用比例復(fù)制，即復(fù)制概率正比于個(gè)體的適應(yīng)值;交叉操作通過交換兩父代個(gè)體的部分信息構(gòu)成后代個(gè)體，使得后代繼承父代的有效模式，從而有助于增加種群的多樣性，避免早熟收斂。</p><p>　　遺傳算法利用生物進(jìn)化和遺傳的思想實(shí)現(xiàn)優(yōu)化過程，區(qū)別于傳統(tǒng)優(yōu)化算法，它具有以下的特點(diǎn):</p><p>　　1.GA對(duì)問題參數(shù)編碼成“染色體”后進(jìn)行進(jìn)化操作，而不是針對(duì)參數(shù)本身，這使

92、得GA不受函數(shù)約束條件的限制，如連續(xù)性、可導(dǎo)性。</p><p>　　2.GA的搜索過程是從問題解的一個(gè)集合開始的，而不是從單個(gè)個(gè)體開始的，具有隱含并行搜索特性，從而大大減少了陷入局部最優(yōu)解的可能。</p><p>　　3.GA使用的遺傳操作均是隨機(jī)操作，同時(shí)GA根據(jù)個(gè)體的適應(yīng)度信息進(jìn)行搜索，無需其它信息，如導(dǎo)數(shù)信息等。</p><p>　　4.GA具有全局搜索能力

93、，最善于搜索復(fù)雜問題和非線性問題。</p><p>　　遺傳算法的優(yōu)越性主要表現(xiàn)在:</p><p>　　1.算法進(jìn)行全空間并行搜索，并將搜索重點(diǎn)集中于性能高的部分，從而能夠提高效率且不易陷入局部極小。</p><p>　　2.算法具有固有的并行性，通過對(duì)種群的遺傳處理可處理大量的模式，并且容易并行實(shí)現(xiàn)。</p><p>　　二、遺傳算法的關(guān)

94、鍵參數(shù)與操作設(shè)計(jì)</p><p>　　通常，遺傳算法的設(shè)計(jì)是按以下步驟進(jìn)行的:</p><p>　　1.確定問題的編碼方案。</p><p>　　2.確定適應(yīng)度函數(shù)。</p><p>　　3.遺傳操作數(shù)的設(shè)計(jì)。</p><p>　　4.算法參數(shù)的選擇，主要包括種群數(shù)目、交叉與變異概率、進(jìn)化代數(shù)等等。</p>

95、<p>　　5.確定算法的終止條件。</p><p>　　下面對(duì)關(guān)鍵參數(shù)與操作的設(shè)計(jì)做簡(jiǎn)單的介紹。</p><p><b>　　1.編碼</b></p><p>　　將問題的解用一種碼來表示，從而將問題的狀態(tài)空間與GA的碼空間相對(duì)應(yīng)，這很大程度上依賴于問題的性質(zhì)，并將影響遺傳操作的設(shè)計(jì)。由于GA的優(yōu)化過程不是直接作用在問題參數(shù)的本

96、身，而是在一定編碼機(jī)制對(duì)應(yīng)的碼空間上進(jìn)行的，因此編碼的選擇是影響算法性能與效率的重要因素。函數(shù)優(yōu)化中，不同的碼長(zhǎng)和碼制，對(duì)問題求解的精度與效率有很大的影響。二進(jìn)制編碼將問題的解用一個(gè)二進(jìn)制串來表示，十進(jìn)制編碼將問題的借用一個(gè)十進(jìn)制串來表示，顯然，碼長(zhǎng)將影響算法的精度，而且算法將付出較大的存儲(chǔ)量。實(shí)數(shù)編碼將問題的解用一個(gè)實(shí)數(shù)來表示，解決了編碼對(duì)算法精度和存儲(chǔ)量的影響，也便利于優(yōu)化中引入問題的相關(guān)信息，它在高維復(fù)雜優(yōu)化問題中得到廣泛的應(yīng)用。

97、</p><p>　　組合優(yōu)化中，由于問題本身的性質(zhì)，編碼要根據(jù)實(shí)際情況編制。</p><p><b>　　2.適應(yīng)度函數(shù)</b></p><p>　　適應(yīng)度函數(shù)用于對(duì)個(gè)體進(jìn)行評(píng)價(jià)，也是優(yōu)化過程發(fā)展的依據(jù)。在簡(jiǎn)單問題的優(yōu)化時(shí)，通?？梢灾苯永媚繕?biāo)函數(shù)變換成適應(yīng)度函數(shù)，而在復(fù)雜問題優(yōu)化時(shí)，往往需要構(gòu)造合適的評(píng)價(jià)函數(shù)，使其適應(yīng)GA進(jìn)行優(yōu)化。<

98、/p><p><b>　　3.算法參數(shù)</b></p><p>　　種群數(shù)目是影響算法優(yōu)化性能和效率的因素之一。通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法的優(yōu)化性能較差，甚至的不到問題的可行解;種群太大時(shí)盡管可增加優(yōu)化信息以阻}卜早熟收斂的發(fā)生，但是無疑會(huì)增加計(jì)算量，從而使收斂時(shí)間太長(zhǎng)。</p><p>　　交叉概率用于控制交叉操作的頻率。概率

99、太大，種群中串的更新很快，進(jìn)而會(huì)使高適應(yīng)度的個(gè)體會(huì)被很快破壞;概率太小，交叉操作很少進(jìn)行，使搜索停滯不前。</p><p>　　變異概率是加大種群多樣性的重要因素。概率太大會(huì)使GA稱為隨機(jī)搜索，概率太小則不會(huì)產(chǎn)生新個(gè)體。</p><p>　　確定最優(yōu)參數(shù)是一個(gè)極其復(fù)雜的優(yōu)化問題，要從理論上嚴(yán)格解決這個(gè)問題是十分困難的，因此很多場(chǎng)合都是根據(jù)具體實(shí)驗(yàn)情況調(diào)整的。</p><

100、p><b>　　4.算法的終止條件</b></p><p>　　GA的收斂理論說明了GA以概率1收斂的極限性質(zhì)，因此我們要追求的提高算法的收斂速度，這與算法操作設(shè)計(jì)和參數(shù)選取有關(guān)。然而。實(shí)際應(yīng)用中不允許讓它無停止的發(fā)展下去的，而且通常問題的最優(yōu)解也未必知道，因此需要有一定的條件來終止算法的進(jìn)程。最常用的終止條件就是事先給定一個(gè)最大進(jìn)化步數(shù)，或者是判斷最佳優(yōu)化值是否連續(xù)若干步?jīng)]有明顯變化

101、等。</p><p>　　GA是一個(gè)復(fù)雜的非線性智能計(jì)算模型，純粹用數(shù)學(xué)方法來預(yù)測(cè)其運(yùn)算結(jié)果很難，而且這方而的工作還遠(yuǎn)遠(yuǎn)不夠。目前，為了兼顧優(yōu)化質(zhì)量與效率，實(shí)際應(yīng)用GA時(shí)許多環(huán)節(jié)還只是憑經(jīng)驗(yàn)來解決，這方而還有待更深入的研究與發(fā)展。</p><p><b>　　2. 5本章小結(jié)</b></p><p>　　本章首先從目標(biāo)和約束兩個(gè)方而對(duì)VRP的組

102、成要素進(jìn)行分析，然后根據(jù)不同的分類方法對(duì)VRP問題進(jìn)行了分類，最后分析了VRP的復(fù)雜度和求解VRP的常用算法理論進(jìn)行了簡(jiǎn)單介紹。本章是后而各章節(jié)的總括，是全文的理論基礎(chǔ)。</p><p>　　物流配送靜態(tài)車輛路徑問題的精確算法研究</p><p>　　本章將應(yīng)用分支切割算法對(duì)靜態(tài)車輛路徑問題的最基本的類型一一能力約束車輛調(diào)度問題(Capacitated VRP，簡(jiǎn)稱CVRP)進(jìn)行研究。&l

103、t;/p><p>　　3. 1問題的描述和數(shù)學(xué)模型</p><p>　　3.1.1問題的描述</p><p>　　CVRP可描述為:考慮貨物需求量、發(fā)送量和車輛容量三種約束的條件下運(yùn)輸車輛的路徑優(yōu)化問題。它可以描述為:物流配送渠道由1個(gè)車場(chǎng)、n個(gè)送貨點(diǎn)(城市)組成，送貨的車輛從車場(chǎng)出發(fā)，到各送貨點(diǎn)送貨，每個(gè)送貨點(diǎn)的需求貨物重量為gr，每個(gè)客戶只能被服務(wù)一次，每輛車限定容

104、量為qA屯，每輛車達(dá)到各送貨點(diǎn)把貨物卸載完之后返回車場(chǎng)。費(fèi)用函數(shù)為總路程數(shù)，目標(biāo)為使總路程數(shù)最小。</p><p>　　3. 1 .2數(shù)學(xué)模型</p><p>　　設(shè)G=(V，A)為一個(gè)完備圖，其中V=｛0，1，．．．，n｝，為圖中頂點(diǎn)的集合，車場(chǎng)由0表示，客戶由1，2．．．n表示；每個(gè)客戶的配送量為ｑｉ；Vc = V/{0}表示客戶集合。集合SVc ，；δ(S)表示G中有且僅有一個(gè)端點(diǎn)在

105、S中的弧的集合；E(S)表示G中兩個(gè)端點(diǎn)都在S中的弧的集合；l(S)表示S中客戶最少需要的配送車輛數(shù)；Xij表示配送車輛在兩個(gè)客戶點(diǎn)i， j間的運(yùn)行次數(shù)；Cij表示配送車輛在兩個(gè)客戶點(diǎn)i， j間的配送費(fèi)用；K 表示總共配送車輛數(shù)。則CVRP的整數(shù)規(guī)劃模型可表示如下：</p><p><b>　　(3-1)</b></p><p>　　s.t x (δ({i}))=2

106、 (i=1,...,n) (3-2)</p><p>　　x( (S))≥ 2l(S) (SV，S≥2) (3-3)</p><p>　　x (δ({0}))=2K (3-4)</p><p>　　xi,j {0,1}

107、 (1≤i?j≤n) (3-5)</p><p>　　x0,i {0,1,2} (i=1,...,n) (3-6)</p><p>　　模型中公式（3-2）為度約束等式，用來約束每個(gè)客戶恰好被服務(wù)一次；不等式（3-3）為連接不等式。對(duì)車輛的能力進(jìn)行了約束，同時(shí)也保證了路徑是相連的;等式(3-4）為車輛約束不等式

108、。對(duì)總共的配送車輛數(shù)進(jìn)行了限制，保證所用的車輛恰好等于K。(3-5)，(3-6)為整數(shù)約束，當(dāng)iVc，jVc時(shí)，xi，j只能為0或1，意義為要么配送車輛在兩客戶i，j之間的路徑旅行一次，要么不旅行。當(dāng)i=0, jVc時(shí)，xi，j除了可以取0，1外，還能取2，其意義為路徑中僅包含一個(gè)客戶和車場(chǎng)。</p><p>　　由于上述數(shù)學(xué)模型不好直接用線形規(guī)劃進(jìn)行求解，去除連接不等式和整數(shù)約束不等式之后，得到CVRP的線形

109、松弛模型，如下所示：</p><p><b>　　（3-7）</b></p><p>　　s.t x (δ({i}))=2 (i=1,...,n) (3-8)</p><p>　　x (δ({0}))=2K (3-9)</p>&l

110、t;p>　　xi,j ≤ 1 (1≤i?j≤n) (3-10)</p><p>　　xi,j ≥ 1 (1≤i?j≤n) (3-11)</p><p>　　x0,i ≤ 2 (i=1,...,n) (3-12)<

111、/p><p>　　x0,i ≥ 0 (i=1,...,n) (3-13)</p><p>　　3. 2單車場(chǎng)能力約束車輛路徑問題的分支切割法設(shè)計(jì)</p><p>　　3. 2. 1切割面的產(chǎn)生</p><p>　　由公式(3-7)至(3-13)可知，初始線形松弛模型只包含度約束不等式、車輛約