車輛調(diào)度算法研究及其應(yīng)用【畢業(yè)設(shè)計+開題報告+文獻綜述】

1、<p>　　本科畢業(yè)設(shè)計(論文)</p><p><b>　?。ǘ?屆）</b></p><p>　　車輛調(diào)度算法研究及其應(yīng)用</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級 計算機科學(xué)與技術(shù) </p>

2、<p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p>　　摘要：隨著物流業(yè)的蓬勃發(fā)展，特別是專業(yè)物流公司的出現(xiàn)，降低物流成本正成為企業(yè)的第三利潤源，這使得人

3、們越來越關(guān)注物流成本的下降，降低運輸成本對降低物流成本有舉足輕重的作用。車輛調(diào)度問題是物流運輸研究領(lǐng)域內(nèi)一個非常重要的問題。</p><p>　　論文首先對車輛調(diào)度問題進行了簡單的描述,介紹了車輛調(diào)度算法的一些基本理論及當前相關(guān)的一些實際問題，給出了相應(yīng)的VRP解決方法,并對動態(tài)車輛調(diào)度和靜態(tài)車輛調(diào)度進行了比較。其次對最典型的啟發(fā)式算法—節(jié)約算法單獨作了介紹，最后提出了其改進算法，并將改進后的算法應(yīng)用于物流信息管

4、理系統(tǒng)的設(shè)計中。物流信息管理系統(tǒng)實現(xiàn)了貨物托運管理和信息查詢等功能。</p><p>　　關(guān)鍵詞：車輛調(diào)度；物流配送；動態(tài)車輛調(diào)度;物流信息管理系統(tǒng)</p><p>　　Vehicle Scheduling Algorithms And Its Application</p><p>　　Abstract: Reduce logistics cost is beco

5、ming the third profit source with the vigorous development of the logistics industry, especially professional logistics company's appearance. This makes people pay more and more attention to the logistics cost and to

6、 reduce the transportation cost down to reduce logistics cost a pivotal role. Vehicle scheduling problem is logistics transportation research field is a very important question.</p><p>　　In this paper, the p

7、roblems of the vehicle scheduling, some basic theories of the vehicle scheduling algorithm, and the current practical issues related were simply described firstly,the corresponding VRP solution was determined, and dynami

8、c and static vehicle scheduling were compared. Secondly, the most typical heuristic algorithm- saving algorithm was introduced separately, finally the improved algorithm was proposed and used in the design of logistics i

9、nformation management system. The functi</p><p><b>　　目 錄</b></p><p>　　1 緒論- 1 -</p><p>　　1.1 課題的研究背景- 1 -</p><p>　　1.1.1 車輛調(diào)度問題研究的歷史背景- 1 -</p>

10、<p>　　1.1.2 車輛調(diào)度問題算法的發(fā)展現(xiàn)狀- 1 -</p><p>　　1.2 課題研究的目的與意義- 2 -</p><p>　　1.3 課題的研究內(nèi)容- 2 -</p><p>　　1.4 課題的研究方法- 3 -</p><p>　　1.5 論文的組織- 3 -</p><p>　

11、　2 基礎(chǔ)知識簡介- 5 -</p><p>　　2.1 數(shù)據(jù)庫技術(shù)- 5 -</p><p>　　2.1.1 數(shù)據(jù)庫設(shè)計的基本步驟- 5 -</p><p>　　2.1.2 數(shù)據(jù)庫設(shè)計的原則- 6 -</p><p>　　2.2 VB語言- 6 -</p><p>　　3 車輛調(diào)度算法概述-

12、8 -</p><p>　　3.1 車輛調(diào)度算法的提出及其分類- 8 -</p><p>　　3.2 動態(tài)車輛調(diào)度問題和靜態(tài)車輛調(diào)度問題- 8 -</p><p>　　3.3 配送車輛調(diào)度問題的描述- 10 -</p><p>　　3.4 配送車輛調(diào)度問題的構(gòu)成要素分析- 11 -</p><p>　　3.5

13、配送車輛調(diào)度問題的分類- 13 -</p><p>　　4 車輛調(diào)度算法基本理論- 15 -</p><p>　　4.1 組合優(yōu)化與計算復(fù)雜性- 15 -</p><p>　　4.1.1 組合優(yōu)化問題- 15 -</p><p>　　4.1.2 算法及算法分析- 15 -</p><p>　　4.2 啟發(fā)式

14、算法理論- 18 -</p><p>　　5 車輛調(diào)度算法基本問題- 20 -</p><p>　　5.1 旅行商問題- 20 -</p><p>　　5.1.1 概述- 20 -</p><p>　　5.1.2 TSP的算法分析- 20 -</p><p>　　5.2最短路徑問題- 23 -</p

15、><p>　　5.2.1 概述- 23 -</p><p>　　5.2.2最短路徑問題的算法分析- 23 -</p><p>　　5.3最少費用流問題- 25 -</p><p>　　5.3.1 概述- 25 -</p><p>　　5.3.2 最少費用流問題算法描述- 25 -</p><p

16、>　　5.4中國郵遞員問題- 27 -</p><p>　　5.4.1 概述- 27 -</p><p>　　5.4.2算法描述- 28 -</p><p>　　6 節(jié)約算法在車輛調(diào)度中的應(yīng)用- 32 -</p><p>　　6.1引言- 32 -</p><p>　　6.2節(jié)約算法- 32 -&l

17、t;/p><p>　　6.2.1 節(jié)約量公式- 32 -</p><p>　　6.2.2 節(jié)約算法的思路和程序- 32 -</p><p>　　6.2.3 節(jié)約法計算實例- 33 -</p><p>　　6.3 C-W在裝配企業(yè)采購物流中的應(yīng)用- 36 -</p><p>　　6.3.1 C-W算法在配送領(lǐng)域的應(yīng)用

18、- 36 -</p><p>　　6.3.2 C-W法在采購領(lǐng)域的應(yīng)用條件- 37 -</p><p>　　6.4 C-K節(jié)約算法在配載車輛調(diào)度問題上的應(yīng)用- 37 -</p><p>　　6.5 基于節(jié)約算法的多車種分送式運輸模型- 38 -</p><p>　　6.5.1 問題描述- 38 -</p><p

19、>　　6.5.2 模型分析- 39 -</p><p>　　6.5.3 算法及求解步驟- 39 -</p><p>　　6.6 車輛路線安排的一種改進的節(jié)約算法- 41 -</p><p>　　6.6.1 改進的節(jié)約法的思路和程序- 42 -</p><p>　　6.6.2 計算實例- 42 -</p><

20、p>　　7 車輛調(diào)度算法應(yīng)用——物流管理系統(tǒng)- 45 -</p><p>　　7.1 系統(tǒng)目標- 45 -</p><p>　　7.2 適用范圍- 45 -</p><p>　　7.3 運行環(huán)境- 45 -</p><p>　　7.4 系統(tǒng)分析- 45 -</p><p>　　7.4.1 需求分析-

21、 45 -</p><p>　　7.4.2 數(shù)據(jù)流程分析- 46 -</p><p>　　7.5系統(tǒng)功能確定- 47 -</p><p>　　7.6 系統(tǒng)功能實現(xiàn)- 47 -</p><p>　　7.6.1 主界面的實現(xiàn)- 47 -</p><p>　　7.6.2 基本信息設(shè)置模塊的實現(xiàn)- 48 -</

22、p><p>　　7.6.3 貨物管理模塊的實現(xiàn)- 49 -</p><p>　　7.6.4 信息查詢模塊的實現(xiàn)- 50 -</p><p>　　7.6.5 系統(tǒng)管理模塊的實現(xiàn)- 51 -</p><p>　　7.6.5主要算法代碼- 52 -</p><p>　　8 總結(jié)及展望- 56 -</p>

23、<p>　　8.1 本文總結(jié)- 56 -</p><p>　　8.2展望- 56 -</p><p>　　致 謝錯誤!未定義書簽。</p><p>　　參考文獻- 57 -</p><p><b>　　1 緒論</b></p><p>　　1.1 課題的研究背景</p

24、><p>　　1.1.1 車輛調(diào)度問題研究的歷史背景</p><p>　　1959 年，Dantzig 等人首先從旅行商問題（Traveling Salesman Problem，簡稱TSP 問題，）得到啟發(fā)，提出了車輛分配問題TDP（Truck Dispatching Problem）。這是一類具有重要研究價值的問題。一方面，它代表了一類典型的組合優(yōu)化問題，具有深遠的理論意義；另一方面，它是

25、一類重要的物流運輸問題，直接影響著相關(guān)企業(yè)的運轉(zhuǎn)效率，具有廣泛的實踐意義。半個世紀以來，許多的專家學(xué)者對該問題進行了廣泛而深入的研究，并將這類問題統(tǒng)稱為車輛路徑調(diào)度問題（Vehicle Routing Problem，簡稱為VRP 問題）。他們從基本問題出發(fā)，根據(jù)不同的約束和目標，構(gòu)建了不同的模型，并有針對性地開發(fā)出了有效的算法[1]。</p><p>　　1.1.2 車輛調(diào)度問題算法的發(fā)展現(xiàn)狀</p>

26、;<p>　　隨著定位導(dǎo)航技術(shù)、數(shù)據(jù)通訊技術(shù)、自動控制技術(shù)、圖像分析技術(shù)以及計算機網(wǎng)絡(luò)和信息處理技術(shù)的快速發(fā)展，車輛優(yōu)化調(diào)度問題作為智能交通系統(tǒng)的一個重要組成部分，在很多國家受到關(guān)注。80年代以來，隨著ITS研究領(lǐng)域和內(nèi)容的不斷深入發(fā)展，逐漸形成了美國、歐洲和日本三大智能交通體系，且三大體系研究方面各有側(cè)重。目前，某些常用且較成熟的算法并已被人們運用的有實際的動態(tài)車輛調(diào)度系統(tǒng)，美國利用最短路徑算法、啟發(fā)式算法開發(fā)計算機配送

27、調(diào)度系統(tǒng)用來解決貨運汽車作業(yè)計劃路線優(yōu)化選擇和車輛分配等問題，使汽車里程利用率提高5%-15%，運輸成本和運輸時間也有了明顯下降。目前已經(jīng)開發(fā)并應(yīng)用于實踐的動態(tài)車輛調(diào)度系統(tǒng)有美國IBM公司開發(fā)的VIIPX系統(tǒng)，其核心算法為最短路徑算法和啟發(fā)式算法；日本富士通公司開發(fā)的VSS系統(tǒng)，以節(jié)約為核心算法；美國美孚公司開發(fā)的HOCAD系統(tǒng)，以掃描為核心算法。</p><p>　　由于該問題在交通運輸、工業(yè)生產(chǎn)管理等領(lǐng)域具有

28、廣泛而重要的應(yīng)用，因此近年來引起了人們極大的興趣，運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、網(wǎng)絡(luò)分析、圖論、計算機應(yīng)用等學(xué)科的專家與運輸計算制定者和管理者進行了大量的理論研究及實驗析，取得了很大的進展。運用這些研究成果，車輛優(yōu)化調(diào)度問題已被成功運用到郵件速遞、出租車服務(wù)、奶品配送、生產(chǎn)計劃、緊急服務(wù)等業(yè)務(wù)之中。車輛的優(yōu)化調(diào)度問題是一種具有相當廣泛實用價值的學(xué)術(shù)研究問題，在理論上屬于復(fù)雜的組合優(yōu)化問題。</p><p>　　當前

29、，現(xiàn)代物流已被公認為是企業(yè)在降低物質(zhì)消耗、提高勞動生產(chǎn)率以外創(chuàng)造利潤的第三個重要源泉，也是企業(yè)降低生產(chǎn)經(jīng)營成本，提高產(chǎn)品市場競爭力的重要途徑。配送是物流系統(tǒng)中的一個重要環(huán)節(jié)，它是指按客戶的訂貨要求，在物流中心進行分貨、配貨工作，并將配好的貨物及時送交收貨人的物流活動。在配送業(yè)務(wù)中，配送車輛調(diào)度問題的涉及面較廣，需要考慮的因素較多，對配送企業(yè)提高服務(wù)質(zhì)量、降低物流成本、增加經(jīng)濟效益的影響也較大。該問題包括集貨線路優(yōu)化、貨物配裝及送貨線路優(yōu)

30、化等，是配送系統(tǒng)優(yōu)化的關(guān)鍵[2]。</p><p>　　1.2 課題研究的目的與意義</p><p>　　國外將配送車輛調(diào)度問題歸結(jié)為VRP（Vehicle Routing Problem，即車輛路徑問題）、VSP（Vehicle Scheduling Problem，即車輛調(diào)度問題）和MTSP（Multiple Traveling Salesman Problem，即多路旅行商問題）。該

31、問題于1959年由Dantzig和Ramser提出后，很快便引起運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計算機應(yīng)用等學(xué)科的專家以及運輸計劃制定者的極大重視，并一直是運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與熱點問題。在現(xiàn)實生產(chǎn)和生活中，郵政投遞問題、車船調(diào)度問題、電力調(diào)度問題、管道鋪設(shè)問題、計算機網(wǎng)絡(luò)拓撲設(shè)計問題等都可以抽象為配送車輛調(diào)度問題?？梢姡芯颗渌蛙囕v調(diào)度問題具有重要的理論和現(xiàn)實意義。</p><p>

32、　　1.3 課題的研究內(nèi)容</p><p>　　本課題研究旨在通過應(yīng)用動態(tài)規(guī)劃思想，改進求解VRP問題的節(jié)約法，建立不斷增加節(jié)約量的動態(tài)規(guī)劃數(shù)學(xué)模型，使其能夠得到全局最優(yōu)解，并將此算法應(yīng)用于物流配送管理車輛系統(tǒng)中。具體內(nèi)容敘述如下：</p><p><b>　?、?算法研究</b></p><p>　　對多種車輛路徑優(yōu)化的算法進行簡述比較，主要

33、對節(jié)約法進行研究。簡述節(jié)約算法的原理，實現(xiàn)途徑；對節(jié)約法的優(yōu)缺點進行分析，在此基礎(chǔ)上提出節(jié)約法的改進意見，并以節(jié)約法為基礎(chǔ)，提出一個配送計劃的制定規(guī)劃及步驟，使運輸行駛總距離最短。</p><p>　　⑵ 物流配送車輛管理系統(tǒng)的研究</p><p>　　物流配送車輛管理系統(tǒng)的研究主要是提供給管理人員的一個平臺，方便管理人員對車輛的調(diào)度管理。系統(tǒng)集節(jié)約算法與數(shù)據(jù)庫管理分析于一體，進行貨物配送

34、方案的優(yōu)化，并以報表形式向用戶提供方案?？傮w內(nèi)容為：基礎(chǔ)數(shù)據(jù)庫建立、信息維護、運輸計劃制定、查詢、統(tǒng)計分析、系統(tǒng)管理。系統(tǒng)功能模塊如圖1-1所示：</p><p>　　圖1-1 物流管理系統(tǒng)功能模塊圖</p><p>　　1.4 課題的研究方法</p><p>　　由于本課題一方面是對車輛調(diào)度算法的研究，主要是通過對文獻的研究、整理來得出結(jié)論; 另一方面是對物流配

35、送車輛管理系統(tǒng)的研究，通過閱讀大量關(guān)于物流配送車輛管理的文獻，根據(jù)相關(guān)文獻，對系統(tǒng)進行需求分析和可行性分析，從而確定自己的研究方向和實現(xiàn)方法。通過數(shù)據(jù)庫設(shè)計方法使用SQLserver設(shè)計出結(jié)構(gòu)完整并適合管理的數(shù)據(jù)庫。最后運用面向?qū)ο缶幊坦ぞ遃B.NET，來完成物流配送車輛管理系統(tǒng)的開發(fā)。</p><p><b>　　1.5 論文的組織</b></p><p>　　論文

36、共有八章，其中第一章緒論，說明問題課題研究背景、課題研究意義、課題研究內(nèi)容和課題研究方法；第二章基礎(chǔ)知識簡介，對論文中用到的一些基礎(chǔ)的知識進行概括性的介紹；第三章車輛調(diào)度算法概述，說明車輛調(diào)度算法的提出及其分類，對動態(tài)車輛調(diào)度算法和靜態(tài)車輛調(diào)度算法進行分別介紹，并敘述車輛調(diào)度算法在物流中的應(yīng)用和其應(yīng)用分類；第四章車輛調(diào)度算法基本理論，介紹了組合優(yōu)化問題，車輛調(diào)度問題的算法求解；第五章車輛調(diào)度算法基本問題，介紹了旅行商問題、最短路徑問題2

37、00753225103、最小費用流問題和中國郵遞員問；第六章約算法在車輛調(diào)度中的應(yīng)用，介紹節(jié)約算法，對引用前人相對于節(jié)約算法提出的解決模型，研究改進了的節(jié)約算法，并研究分析了節(jié)約算法在物流上應(yīng)用；第七章車輛調(diào)度算法計算機實現(xiàn)——物流管理系統(tǒng)介紹，介紹物流管理系統(tǒng)的設(shè)計與實現(xiàn)；第八章總結(jié)及展望：對本文進行總結(jié)并對進一步研究做出展望。</p><p><b>　　2 基礎(chǔ)知識簡介</b><

38、;/p><p>　　2.1 數(shù)據(jù)庫技術(shù)</p><p>　　數(shù)據(jù)庫技術(shù)產(chǎn)生于20世紀60年代末70年代初,其主要目的是有效地管理和存取大量的數(shù)據(jù)資源。主要研究如何存儲,使用和管理數(shù)據(jù)。在應(yīng)用計算機進行數(shù)據(jù)處理的技術(shù)發(fā)展過程中經(jīng)歷了三個階段：程序數(shù)據(jù)處理技術(shù)、文件數(shù)據(jù)處理技術(shù)、數(shù)據(jù)庫數(shù)據(jù)處理技術(shù)。發(fā)展至今，所有的數(shù)據(jù)處理應(yīng)用系統(tǒng)都是采用數(shù)據(jù)庫數(shù)據(jù)處理技術(shù)實現(xiàn)的。</p><

39、p>　　所謂數(shù)據(jù)庫（Database），是指按照數(shù)據(jù)結(jié)構(gòu)來組織、存儲和管理數(shù)據(jù)的倉庫。它產(chǎn)生于距今五十年前，隨著信息技術(shù)和市場的發(fā)展，特別是二十世紀九十年代以后，數(shù)據(jù)管理不再僅僅是存儲和管理數(shù)據(jù)，而轉(zhuǎn)變成用戶所需要的各種數(shù)據(jù)管理的方式。數(shù)據(jù)庫有很多種類型，從最簡單的存儲各種數(shù)據(jù)的表格到能夠進行海量數(shù)據(jù)存儲的大型數(shù)據(jù)庫系統(tǒng)都在各個方面得到了廣泛的應(yīng)用[3]。</p><p>　　在開發(fā)一個系統(tǒng)之前，首先要完成

40、的就是數(shù)據(jù)庫的設(shè)計。數(shù)據(jù)庫設(shè)計是指對于一個給定的應(yīng)用環(huán)境，構(gòu)造最優(yōu)的數(shù)據(jù)庫模式，建立數(shù)據(jù)庫及其應(yīng)用系統(tǒng)，使之能夠有效地存儲數(shù)據(jù)。如何在給定的應(yīng)用環(huán)境下，構(gòu)造最優(yōu)的數(shù)據(jù)庫模型至關(guān)重要，它將影響整個系統(tǒng)的運作。下面對數(shù)據(jù)庫的設(shè)計做下簡單的介紹。</p><p>　　2.1.1 數(shù)據(jù)庫設(shè)計的基本步驟</p><p><b>　?。?）需求分析階段</b></p>

41、;<p>　　該階段的任務(wù)是準確了解和分析用戶的需求，包括數(shù)據(jù)與處理。是整個設(shè)計過程的基礎(chǔ)，也是最困難、最耗費時間的一步。</p><p>　　（2）概念結(jié)構(gòu)設(shè)計階段</p><p>　　該階段主要是通過對用戶需求進行綜合、歸納與抽象，形成一個獨立于具體DBMS的概念模型，即設(shè)計數(shù)據(jù)庫的E-R模型圖，是整個數(shù)據(jù)庫設(shè)計的關(guān)鍵。</p><p>　?。?）

42、邏輯結(jié)構(gòu)設(shè)計階段</p><p>　　該階段是將概念結(jié)構(gòu)轉(zhuǎn)換為某個DBMS所支持的數(shù)據(jù)模型。如將E-R如轉(zhuǎn)換為多張表。</p><p>　　（4）數(shù)據(jù)庫物理設(shè)計階段</p><p>　　該階段是要為邏輯數(shù)據(jù)模型選取一個最適合應(yīng)用環(huán)境的物理結(jié)構(gòu)，包括存儲結(jié)構(gòu)和存取方法。</p><p>　?。?）數(shù)據(jù)庫實施階段</p><p

43、>　　這個階段是運用DBMS提供的數(shù)據(jù)語言、工具及宿主語言，根據(jù)邏輯設(shè)計和物理設(shè)計的結(jié)果建立數(shù)據(jù)庫，編制與調(diào)試應(yīng)用程序，組織數(shù)據(jù)入庫，并進行試運行。</p><p>　?。?）數(shù)據(jù)庫運行和維護階段</p><p>　　數(shù)據(jù)庫應(yīng)用系統(tǒng)經(jīng)過試運行后即可投入正式運行，但在系統(tǒng)運行過程中必須不斷地對其進行評價、調(diào)整與修改。</p><p>　　在設(shè)計過程中要把數(shù)據(jù)庫的

44、設(shè)計和對數(shù)據(jù)庫中數(shù)據(jù)處理的設(shè)計緊密結(jié)合起來，將這兩個方面的需求分析、抽象、設(shè)計、實現(xiàn)在各個階段同時進行，相互參照，相互補充，以完善兩方面的設(shè)計。</p><p>　　2.1.2 數(shù)據(jù)庫設(shè)計的原則</p><p>　　在數(shù)據(jù)庫設(shè)計過程中，往往會出現(xiàn)一些問題，如數(shù)據(jù)冗余、更新異?；蚴潜砼c表之間的范式問題，要想減少錯誤的產(chǎn)生，避免不必要的麻煩，必須遵循數(shù)據(jù)庫設(shè)計的基本原則。原則如下：</

45、p><p>　?。?）正確反映數(shù)據(jù)與數(shù)據(jù)(信息與信息)之間的層次邏輯關(guān)系；</p><p>　?。?）對進入到數(shù)據(jù)庫中的數(shù)據(jù)有一個有效性檢查；</p><p>　?。?）對數(shù)據(jù)庫中的數(shù)據(jù)進行非邏輯操作進行相應(yīng)的錯誤處理；</p><p>　?。?）滿足系統(tǒng)對性能上的要求。</p><p><b>　　2.2 V

46、B語言</b></p><p>　　Visual Basic是一種由微軟公司開發(fā)的包含協(xié)助開發(fā)環(huán)境的事件驅(qū)動編程語言。從任何標準來說，VB都是世界上使用人數(shù)最多的語言——不僅是盛贊VB的開發(fā)者還是抱怨VB的開發(fā)者的數(shù)量。它源自于BASIC編程語言。VB擁有圖形用戶界面（GUI）和快速應(yīng)用程序開發(fā)（RAD）系統(tǒng)，可以輕易的使用DAO、RDO、ADO連接數(shù)據(jù)庫，或者輕松的創(chuàng)建ActiveX控件。程序員可以

47、輕松的使用VB提供的組件快速建立一個應(yīng)用程序。</p><p>　　Visual Basic語言特性：</p><p>　?、?VB的中心思想就是要便于程序員使用，無論是新手或者專家。VB使用了可以簡單建立應(yīng)用程序的GUI系統(tǒng)，但是又可以開發(fā)相當復(fù)雜的程序。VB的程序是一種基于窗體的可視化組件安排的聯(lián)合，并且增加代碼來指定組件的屬性和方法。因為默認的屬性和方法已經(jīng)有一部分定義在了組件內(nèi)，所

48、以程序員不用寫多少代碼就可以完成一個簡單的程序。過去的版本里面VB程序的性能問題一直被放在了桌面上，但是隨著計算機速度的飛速增加，關(guān)于性能的爭論已經(jīng)越來越少。 　　</p><p>　　⑵ 窗體控件的增加和改變可以用拖放技術(shù)實現(xiàn)。一個排列滿控件的工具箱用來顯示可用控件（比如文本框或者按鈕)。每個控件都有自己的屬性和事件。默認的屬性值會在控件創(chuàng)建的時候提供，但是程序員也可以進行更改。很多的屬性值可以在運行時候隨著用

49、戶的動作和修改進行改動，這樣就形成了一個動態(tài)的程序。舉個例子來說：窗體的大小改變事件中加入了可以改變控件位置的代碼，在運行時候每當用戶更改窗口大小，控件也會隨之改變位置。在文本框中的文字改變事件中加入相應(yīng)的代碼，程序就能夠在文字輸入的時候自動翻譯或者阻止某些字符的輸入。 　　</p><p>　　⑶ VB的程序可以包含一個或多個窗體，或者是一個主窗體和多個子窗體，類似于操作系統(tǒng)的樣子。有很少功能的對話框窗口（比如

50、沒有最大化和最小化按鈕的窗體）可以用來提供彈出功能。 　　</p><p>　?、?VB的組件既可以擁有用戶界面，也可以沒有。這樣一來服務(wù)器端程序就可以處理增加的模塊。 　　</p><p>　?、?VB使用參數(shù)計算的方法來進行垃圾收集，這個方法中包含有大量的對象，提供基本的面向?qū)ο笾С?。因為越來越多組建的出現(xiàn)，程序員可以選用自己需要的擴展庫。和有些語言不一樣，VB對大小寫不敏感，但是能自

51、動轉(zhuǎn)換關(guān)鍵詞到標準的大小寫狀態(tài)，以及強制使得符號表入口的實體的變量名稱遵循書寫規(guī)則。默認情況下字符串的比較是對大小寫敏感的，但是可以關(guān)閉這個功能。 　　</p><p>　　⑹ VB使得大量的外界控件有了自己的生存空間。大量的第三方控件針對VB提供。VB也提供了建立、使用和重用這些控件的方法，但是由于語言問題，從一個應(yīng)用程序創(chuàng)建另外一個并不簡單[3]。</p><p>　　其他本文即將用到

52、的部分算法的概念將在下文中有關(guān)論述中進行介紹。</p><p>　　3 車輛調(diào)度算法概述</p><p>　　3.1 車輛調(diào)度算法的提出及其分類</p><p>　　1959 年，Dantzig 等人首先從旅行商問題（Traveling Salesman Problem，簡稱TSP 問題）得到啟發(fā)，提出了車輛分配問題TDP（Truck Dispatching Pr

53、oblem）。這是一類具有重要研究價值的問題。一方面，它代表了一類典型的組合優(yōu)化問題，具有深遠的理論意義；另一方面，它是一類重要的物流運輸問題，直接影響著相關(guān)企業(yè)的運轉(zhuǎn)效率，具有廣泛的實踐意義。半個世紀以來，許多的專家學(xué)者對該問題進行了廣泛而深入的研究，并將這類問題統(tǒng)稱為車輛路徑調(diào)度問題（Vehicle Routing Problem，簡稱為VRP 問題）。他們從基本問題出發(fā)，根據(jù)不同的約束和目標，構(gòu)建了不同的模型，并有針對性地開發(fā)出了

54、有效的算法。</p><p>　　VRP問題一般可定義為：對一系列的裝貨點或卸貨點，組織適當?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(貨物需求量、發(fā)送量、車輛容量限制、行駛里程限制、時間限制)下，達到一定的目標(路程最短、時間最小、費用最省、車輛數(shù)目最少等)。由于該問題研究范圍非常廣，根據(jù)其網(wǎng)絡(luò)性能大致可以分為兩類：一類為靜態(tài)車輛調(diào)度(StaticVRP, SVRP)，一類為動態(tài)車輛調(diào)度 (dyna

55、mic VRP, DVRP)。</p><p>　　3.2 動態(tài)車輛調(diào)度問題和靜態(tài)車輛調(diào)度問題</p><p>　　靜態(tài)車輛調(diào)度問題（SVRP）指的是：假設(shè)在優(yōu)化調(diào)度指令執(zhí)行之前，調(diào)度中心已經(jīng)知道所以與優(yōu)化調(diào)度相關(guān)的信息，這些信息與時間變換無關(guān)。一旦調(diào)度開始之后，認為這些信息不再改變。</p><p>　　動態(tài)車輛調(diào)度問題更符合實際生活中的情況，它指的是：假設(shè)在優(yōu)化

56、調(diào)度指令執(zhí)行之前，調(diào)度中心不一定知道所有優(yōu)化調(diào)度相關(guān)信息，這些信息肯呢個隨時間變化。一旦調(diào)度指令開始執(zhí)行之后，這些信息不是一成不變的。可能有新的信息出現(xiàn)活已有信息發(fā)生改變時，就需要實時更新優(yōu)化調(diào)度結(jié)果[4]。</p><p>　　動態(tài)車輛調(diào)度問題是靜態(tài)車輛調(diào)度問題的擴展，相當于在靜態(tài)調(diào)度的基礎(chǔ)上增加了動態(tài)需求等變化而產(chǎn)生了新的調(diào)度需求和結(jié)果。由于動態(tài)需求應(yīng)盡可能在短時間內(nèi)得到服務(wù)，這就要求信息處理的時間盡可能的短

57、。</p><p>　　一般來說，調(diào)度問題嚴格而復(fù)雜，新的動態(tài)顧客插入將越復(fù)雜，例如有時間約束調(diào)度問題比無時間約束調(diào)度問題的新顧客插入更困難，而且如果找不到可行的地方插入新顧客，在線調(diào)度系統(tǒng)可能拒絕對顧客的插入。</p><p>　　傳統(tǒng)意義上的靜態(tài)車輛調(diào)度是NP難題（將在下文中進行敘述），用適當計算時間為現(xiàn)實某種規(guī)模問題找到一個滿意解不總是可行的，顯然動態(tài)車輛調(diào)度問題更屬于NP難題，它相

58、當于每接受一個服務(wù)請求時去解決一個靜態(tài)車輛調(diào)度問題。此時車輛調(diào)度問題還必須考慮立即服務(wù)請求顧客的到達時間、顧客需求和服務(wù)時間以及調(diào)度系統(tǒng)的反應(yīng)時間，因此這類問題的求解對時間要求很高[5]。</p><p>　　動態(tài)車輛調(diào)度問題有很多自身特點和研究中需要關(guān)注的地方，主要表現(xiàn)在：</p><p>　?、?時間因素至關(guān)重要</p><p>　　在靜態(tài)車輛調(diào)度問題中，不需要

59、重點考慮時間因素，但在動態(tài)車輛調(diào)度問題中就變得至關(guān)重要。調(diào)度中心需要實時地知道（至少在新的需求到來的時候）所有運輸車輛所處位置，才能對行車路線做出動態(tài)調(diào)整。</p><p>　?、?問題可能是開放的</p><p>　　靜態(tài)車輛調(diào)度問題中，時間尺度上往往是有界的，即一條行車路線開始并結(jié)束于同一個或者不同的車場。然而在動態(tài)車輛調(diào)度問題中，時間尺度往往是無界的，行車路線往往不是一條開始并結(jié)束于

60、車場的封閉路線，而是一條開放的路徑。</p><p>　　⑶ 將來的信息具有不確定性的</p><p>　　靜態(tài)車輛調(diào)度問題中所以的相關(guān)信息都被假定是已知并且不會改變的。但是在實際情況中，未來的信息不可能是確定無疑的。很多情況下未來的信息如動態(tài)顧客等是完全不知道的，當然也有可能知道某些顧客的概率信息。</p><p>　?、?近期事件應(yīng)該得到優(yōu)先考慮</p&g

61、t;<p>　　靜態(tài)車輛調(diào)度問題中由于所用的時間都是確定的并且不會隨時間改變，所以近期和遠期的事件都會被綜合在一起進行同等考慮。但是在動態(tài)車輛調(diào)度問題中，因為信息隨時都在改變，所以明智的做法是把注意力放在近期的事件上。如果根據(jù)當前掌握的不完全信息就做全局的長期優(yōu)化，那么現(xiàn)在得到的優(yōu)化結(jié)果在將來很有可能因為新的動態(tài)信息的到來而變成次優(yōu)或者甚至成為劣解。</p><p>　?、?要建立信息更新的機制&l

62、t;/p><p>　　在動態(tài)車輛調(diào)度問題中，各種輸入的信息隨時都可能發(fā)生改變，并且還不斷有新的信息到來，所以建立信息更新機制就顯得很重要。而在靜態(tài)車輛調(diào)度問題中，由于信息一經(jīng)輸入就已經(jīng)確定，所以就您沒有必要建立這種更新機制。</p><p>　?、?重新安排任務(wù)的執(zhí)行順序，重新分派運輸車輛都是可以考慮的做法。</p><p>　　動態(tài)車輛調(diào)度問題中，由于不斷有新的需求產(chǎn)

63、生，同時已經(jīng)被安排的需求也可能要求撤消服務(wù)。面對這些新的情況，調(diào)度中心有可能需要重新制定服務(wù)順序或者重新分派另外的車輛去服務(wù)某個顧客。</p><p>　?、?計劃制定者需要更快的計算速度</p><p>　　在靜態(tài)環(huán)境中，由于只需要制定一次計劃，所以計劃制定者可以花上幾個小時來得到一個高質(zhì)量的解。但是在動態(tài)車輛調(diào)度中，運輸車輛的死機需要得到計劃制定者實時的指令，這就迫使計劃制定者在很短的

64、時間，比如幾分鐘內(nèi)完成一次路線或者車輛分派的調(diào)整。因此，計劃人員需要具有更快的計算速度的軟硬件資源。</p><p>　?、?需要具有推遲服務(wù)機制</p><p>　　當某個需求的某些屬性，例如地理位置等可能對服務(wù)其他需求造成嚴重延遲時，需要建立推遲服務(wù)這個需求的機制。具體的做法可以采取時間窗約束或者懲罰函數(shù)。</p><p>　?、?優(yōu)先考慮的目標是減少顧客的等待

65、時間</p><p>　　傳統(tǒng)靜態(tài)車輛調(diào)度問題的目標往往是最小化運輸車輛行駛的總距離或者總時間等。然后在動態(tài)車輛調(diào)度中，顧客能否得到即使地服務(wù)是首要考慮因素，所以動態(tài)車輛調(diào)度的主要目的應(yīng)該是最小化顧客的平均等待時間。</p><p>　?、?時間約束需要更加輕松</p><p>　　相比靜態(tài)車輛調(diào)度，動態(tài)環(huán)境中的時間限制，如對某個需求的最晚開始服務(wù)時間等，往往定的寬

66、松。這樣做是因為在實際操作中往往更愿意一定程度上去違反時間限制來接受一個新的顧客，而不是因為違反既定的時間限制去拒絕他。</p><p>　?、?車隊車輛數(shù)量的確定性降低</p><p>　　在靜態(tài)車輛調(diào)度中往往可以控制車輛的數(shù)量來達到最游記。但是在動態(tài)環(huán)境下，由于對未來需求的不確定性，往往需要配備后備車輛，這使得自由決定車隊車輛的確定性有所降低。</p><p>

67、　?、?往往要考慮排隊模型</p><p>　　當動態(tài)顧客的增加超過車輛服務(wù)能力時，等待服務(wù)的顧客會越來越多。這時需要從排隊論的角度去考慮整個系統(tǒng)運轉(zhuǎn)是否能夠平穩(wěn)的運轉(zhuǎn)而不癱瘓。</p><p>　　3.3 配送車輛調(diào)度問題的描述</p><p>　　配送車輛調(diào)度問題可以描述為：在一個存在供求關(guān)系的系統(tǒng)中，有若干臺車輛、若干個物流中心和客戶，要求合理安排車輛的行車路

68、線和出行時間，從而在給定的約束條件下，把客戶需求的貨物從物流中心送到客戶，把客戶供應(yīng)的貨物從客戶取到物流中心，并使目標函數(shù)取得優(yōu)化。</p><p>　　配送車輛調(diào)度問題可歸結(jié)為如下的一般網(wǎng)絡(luò)模型：設(shè)G=（V，E，A）是一個連通的混合網(wǎng)絡(luò)，V是頂點集（表示物流中心、客戶、停車場等），E、A分別為無向的邊集和有向的弧集，E中的邊和A中的弧均被賦權(quán)（可以表示配送的距離、時間或費用），V’、E’、A’分別為V、E、A的

69、子集，求滿足約束條件（包括客戶的貨物需求或供應(yīng)數(shù)量約束、需求或供應(yīng)時間約束、配送車輛一次配送的最大行駛距離約束、車輛的最大載重量約束等），并包含V’、E’、A’的一些巡回路線，使目標函數(shù)取得優(yōu)化，目標函數(shù)可以取配送總里程最短、配送車輛總噸位公里數(shù)最少、配送總費用最低、配送總時間最少、使用的配送車輛數(shù)最少、配送車輛的滿載率最高等[6]。</p><p>　　3.4 配送車輛調(diào)度問題的構(gòu)成要素分析</p>

70、<p>　　配送車輛調(diào)度問題主要包括貨物、車輛、物流中心、客戶、運輸網(wǎng)絡(luò)、約束條件和目標函數(shù)等要素。</p><p>　?、?貨物。貨物是配送的對象?？蓪⒚總€客戶需求（或供應(yīng)）的貨物看成一批貨物。每批貨物都包括品名、包裝、重量、體積、要求送到（或取走）的時間和地點、能否分批配送等屬性。</p><p>　　貨物的品名和包裝，是選用配送車輛的類型以及決定該批貨物能否與其它貨物裝

71、在同一車輛內(nèi)的依據(jù)。例如，一些貨物因性質(zhì)特殊需要使用專用車輛裝運；一些貨物因性質(zhì)特殊不能與其它貨物裝在同一車輛內(nèi)；一些貨物雖然性質(zhì)特殊，但由于包裝條件很好，故也能與其它貨物裝在同一車輛內(nèi)。</p><p>　　貨物的重量和體積是進行車輛裝載決策的依據(jù)。當某個客戶需求（或供應(yīng)）貨物的重量或體積超過配送車輛的最大裝載重量或容積時，則該客戶將需要多臺車輛進行配送。</p><p>　　貨物的送到

72、（或取走）時間和地點是制定車輛的出行時間和配送路線的依據(jù)。</p><p>　　允許貨物分批配送，是指某個客戶的需求（或供應(yīng)）的貨物可以用多輛車分批送到（或取走），即使其需求（或供應(yīng)）量在一輛車的裝載量以下[7]。</p><p>　?、?車輛。車輛是貨物的運載工具。其主要屬性包括：車輛的類型、裝載量、一次配送的最大行駛距離、配送前的停放位置及完成任務(wù)后的停放位置等。</p>

73、<p>　　車輛的類型有通用車輛和專用車輛之分，通用車輛適于裝運大多數(shù)普通貨物，專用車輛適于裝運一些性質(zhì)特殊的貨物。</p><p>　　車輛的裝載量是指車輛的最大裝載重量和最大裝載容積，是進行車輛裝載決策的依據(jù)。在某配送系統(tǒng)中，車輛的裝載量可以相同，也可以不同。</p><p>　　對每臺車輛一次配送的行駛距離的要求可分為以下幾種情況：①無距離限制；②有距離限制；③有距離限制

74、，但可以不遵守，只是不遵守時需另付加班費。</p><p>　　車輛在配送前的停放位置可以在某個停車場、物流中心或客戶所在地。</p><p>　　車輛完成配送任務(wù)后，對其停放位置的要求可分為以下幾種情況：①必須返回出發(fā)點；②必須返回某停車場；③可返回到任意停車場；④可停放在任何停車場、物流中心或客戶所在地。</p><p>　?、?物流中心。也稱為物流基地、物流據(jù)

75、點，是指進行集貨、分貨、配貨、配裝、送貨作業(yè)的配送中心、倉庫、車站、港口等。</p><p>　　在某配送系統(tǒng)中，物流中心的數(shù)量可以只有一個，也可以有一個以上；物流中心的位置可以是確定的，也可以是不確定的。對于某個物流中心，其供應(yīng)的貨物可能有一種，也可能有多種；其供應(yīng)的貨物數(shù)量可能能夠滿足全部客戶的需求，也可能僅能滿足部分客戶的需求。</p><p>　?、?客戶。也稱為用戶，包括分倉庫、

76、零售商店等?？蛻舻膶傩园ㄐ枨螅ɑ蚬?yīng)）貨物的數(shù)量、需求（或供應(yīng)）貨物的時間、需求（或供應(yīng)）貨物的次數(shù)及需求（或供應(yīng)）貨物的滿足程度等。</p><p>　　在某個配送系統(tǒng)中，某個客戶的需求（或供應(yīng)）貨物的數(shù)量可能大于車輛的最大裝載量，也可能小于車輛的最大裝載量；而該系統(tǒng)全部客戶的貨物需求（或供應(yīng)）總量可能超過全部車輛的總裝載量，也可能低于全部車輛的總裝載量。</p><p>　　某客戶的

77、需求（或供應(yīng)）貨物的時間，是指要求貨物送到（或取走）的時間，對配送時間的要求可分為以下幾種情況：①無時間限制；②要求在指定的時間區(qū)間（也稱為時間窗）內(nèi)完成運輸任務(wù)；③有時間限制，但可以不遵守，只是不遵守時要給予一定的懲罰。</p><p>　　某客戶的需求（或供應(yīng)）貨物的次數(shù)可能僅有一次，即只需一次配送服務(wù)；也可能為多次，即需要多次配送服務(wù)。</p><p>　　某客戶對需求（或供應(yīng)）貨物

78、的滿足程度的要求可分為兩種情況：①要求全部滿足；②可以部分滿足，但不滿足時要受到懲罰。</p><p>　　⑸ 運輸網(wǎng)絡(luò)。運輸網(wǎng)絡(luò)是由頂點（指物流中心、客戶、停車場）、無向邊和有向弧組成的。邊、弧的屬性包括方向、權(quán)值和交通流量限制等。</p><p>　　某運輸網(wǎng)絡(luò)中可能僅有無向邊；也可能僅有有向?。贿€可能既有無向邊，又有有向弧。</p><p>　　運輸網(wǎng)絡(luò)中邊或

79、弧的權(quán)值可以表示距離、時間或費用。邊或弧的權(quán)值變化分為以下幾種情況：①固定，即不隨時間和車輛的不同而變化；②隨時間不同而變化；③隨車輛的不同而變化；④既隨時間不同而變化，又隨車輛不同而變化。對運輸網(wǎng)絡(luò)權(quán)值間的關(guān)系可以要求其滿足三角不等式，即兩邊之和大于第三邊；也可以不加限制。</p><p>　　對運輸網(wǎng)絡(luò)中頂點、邊或弧的交通流量要求分為以下幾種情況：①無流量限制；②邊、弧限制，即每條邊、弧上同時行駛的車輛數(shù)有限

80、；③頂點限制，即每個頂點上同時裝、卸貨的車輛數(shù)有限；④邊、弧、頂點都有限制。</p><p>　?、?約束條件。配送車輛調(diào)度問題應(yīng)滿足的約束條件主要包括：①滿足所有客戶對貨物品種、規(guī)格、數(shù)量的要求；②滿足客戶對貨物發(fā)到時間范圍的要求；③在允許通行的時間進行配送（如有時規(guī)定白天不能通行貨車等）；④車輛在配送過程中的實際載貨量不得超過車輛的最大允許裝載量；⑤在物流中心現(xiàn)有運力范圍內(nèi)。</p><p

81、>　?、?目標函數(shù)。對配送車輛調(diào)度問題，可以只選用一個目標，也可以選用多個目標。經(jīng)常選用的目標函數(shù)主要有：</p><p>　?、倥渌涂偫锍套疃?。配送里程與配送車輛的耗油量、磨損程度以及司機疲勞程度等直接相關(guān)，它直接決定運輸?shù)某杀?，對配送業(yè)務(wù)的經(jīng)濟效益有很大影響。由于配送里程計算簡便，它是確定配送路線時用得最多的指標。</p><p>　?、谂渌蛙囕v的噸位公里數(shù)最少。該目標將配送距離

82、與車輛的載重量結(jié)合起來考慮，即以所有配送車輛的噸位數(shù)（最大載重噸）與其行駛距離的乘積的總和最少為目標。</p><p>　?、劬C合費用最低。降低綜合費用是實現(xiàn)配送業(yè)務(wù)經(jīng)濟效益的基本要求。在配送中，與取送貨有關(guān)的費用包括：車輛維護和行駛費用、車隊管理費用、貨物裝卸費用、有關(guān)人員工資費用等。</p><p>　?、軠蕰r性最高。由于客戶對交貨時間有較嚴格的要求，為提高配送服務(wù)質(zhì)量，有時需要將準時

83、性最高作為確定配送路線的目標。</p><p>　?、葸\力利用最合理。該目標要求使用的較少的車輛完成配送任務(wù)，并使車輛的滿載率最高，以充分利用車輛的裝載能力。</p><p>　?、迍趧酉淖畹汀＜匆运緳C人數(shù)最少、司機工作時間最短為目標。</p><p>　　3.5 配送車輛調(diào)度問題的分類</p><p>　　配送車輛調(diào)度問題可按照其構(gòu)成要素

84、劃分為不同的種類。</p><p>　?。?）按物流中心的數(shù)目分，有單物流中心問題（配送系統(tǒng)中僅有一個物流中心）和多物流中心問題（配送系統(tǒng)中存在多個物流中心）。</p><p>　?。?）按車輛載貨狀況分，有滿載問題（由于客戶需求或供應(yīng)的貨物數(shù)量大于或等于車輛的載重量，故完成一項配送任務(wù)需要一輛及其以上的配送車輛，配送車輛需要滿載運行）、非滿載問題（由于客戶需求或供應(yīng)的貨物數(shù)量小于車輛載重

85、量，多項配送任務(wù)可共用一輛配送車輛，車輛在配送過程中經(jīng)常處于不滿載狀態(tài)）以及滿載和非滿載混合問題（由于一部分客戶需求或供應(yīng)的貨物數(shù)量大于或等于車輛的載重量，而另一部分客戶需求或供應(yīng)的貨物數(shù)量小于車輛的載重量，造成一些配送車輛需要滿載運行，而另一些車輛則經(jīng)常處于不滿載狀態(tài)）。</p><p>　?。?）按配送任務(wù)特征分，有純送貨問題（僅考慮從物流中心向客戶送貨，也稱為純卸問題）或純?nèi)∝泦栴}（僅考慮把各客戶供應(yīng)的貨物

86、取到物流中心，也稱為純裝問題）及取送混合問題（既考慮將客戶需求的貨物從物流中心送到各個客戶，同時考慮將客戶供應(yīng)的貨物從客戶取到物流中心，也稱為裝卸混合問題或集貨和送貨一體化問題）。為了便于敘述，本文將純送貨或純?nèi)∝浀呐渌蛙囕v調(diào)度問題稱為單向配送車輛調(diào)度問題，而將取送混合的配送車輛調(diào)度問題稱為雙向配送車輛調(diào)度問題。</p><p>　　（4）按客戶對貨物?。ㄋ停r間的要求分，有無時限問題（客戶對貨物的取走或送到的時

87、間無具體要求）和有時限問題（客戶要求將需求的貨物在規(guī)定的時間窗內(nèi)送到，將供應(yīng)的貨物在規(guī)定的時間窗內(nèi)取走，也稱為有時間窗問題）。有時限問題又可以分為硬時間窗問題（客戶要求貨物必須在規(guī)定的時間窗內(nèi)送到或取走，不能提前也不能拖后）和軟時間窗問題（客戶要求將貨物盡量在規(guī)定的時間窗內(nèi)送到或取走，但也可以提前或拖后，只不過在提前或拖后時，要對配送企業(yè)實施一定的懲罰）。</p><p>　?。?）按車輛類型數(shù)分，有單車型問題（

88、所有配送車輛的載重量相同）和多車型問題（配送車輛的載重量不完全相同）。</p><p>　?。?）按車輛對車場的所屬關(guān)系分，有車輛開放問題（即車輛完成配送任務(wù)后可以不返回其發(fā)出車場）和車輛封閉問題（車輛完成配送任務(wù)后必須返回其發(fā)出車場）。</p><p>　?。?）按優(yōu)化目標數(shù)分，有單目標問題（僅考慮一個配送目標）和多目標問題（同時考慮多個配送目標）[8]。</p><

89、p>　　以上對配送車輛調(diào)度問題的構(gòu)成要素和種類的分析是進一步對問題進行建模和求解的基礎(chǔ)。</p><p>　　4 車輛調(diào)度算法基本理論</p><p>　　4.1 組合優(yōu)化與計算復(fù)雜性</p><p>　　4.1.1 組合優(yōu)化問題</p><p>　　在有限個可行解集合中找出最優(yōu)解，這類問題稱為組合優(yōu)化問題。組合優(yōu)化問題是指在離散的、

90、有限的數(shù)學(xué)結(jié)構(gòu)上，求滿足給定約束條件的目標函數(shù)最優(yōu)值（最大值或最小值）的問題，也稱離散優(yōu)化問題，該類問題與序有關(guān)。</p><p>　　一個組合優(yōu)化問題π由三部分組成：</p><p><b>　?、?實例集D；</b></p><p>　?、?對于一個實例I∈D，有一個有限的非空集合S（I），S（I）的元素稱為I的可行解；</p>

91、<p>　?、?對于每一個可行解σ∈S（I），有一個正整數(shù)c（σ），稱為值σ。</p><p>　　當π是最小化問題（最大化問題）時，如果σ*∈S（I）使得對于所有的σ∈S（I），有</p><p>　　c（σ*）≤c（σ） （或c（σ*）≥c（σ）））</p><p>　　則稱σ*是最優(yōu)解。c（σ*）稱作I的最優(yōu)解，極為OPT（I）。<

92、/p><p>　　不失一般性，只要改變目標函數(shù)的符號，就可實現(xiàn)最小化問題和最大化問題的相互轉(zhuǎn)換。</p><p>　　在管理科學(xué)、計算機科學(xué)、電子工程、工業(yè)工程和交通運輸?shù)瓤萍碱I(lǐng)域內(nèi)，存在著大量組合優(yōu)化問題，其中不少問題隨著規(guī)模的增加，計算指數(shù)增長，他們屬于NP完全問題或NP難題[5]。</p><p>　　4.1.2 算法及算法分析</p><p&

93、gt;<b>　　⒈ 算法</b></p><p>　　算法是能被機械地執(zhí)行的動作（或稱規(guī)則、指令）的有窮集合，一個動作的一次執(zhí)行稱為一步。能夠用算法來解的和你熟或問題稱為可計算函數(shù)或可計算問題。算法有五大特征。</p><p>　　⑴ 有窮性（Finiteness）</p><p>　　算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止<

94、;/p><p>　?、?確切性(Difiniteness)</p><p>　　算法的每一步驟必須有確切的定義；</p><p>　?、?輸入項(Input)</p><p>　　一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；</p><p>　　⑷ 輸出項(Output)&l

95、t;/p><p>　　一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；</p><p>　?、?可行性(Effectiveness)</p><p>　　算法中執(zhí)行的任何計算步都是可以被分解為基本的可執(zhí)行的操作步，即每個計算步都可以在有限時間內(nèi)完成。（也稱之為有效性）</p><p>　　計算機技術(shù)的發(fā)展，促進

96、了問題的數(shù)值解法、模擬技術(shù)和信息處理技術(shù)的發(fā)展。人們普遍認為，今日的科學(xué)技術(shù)的需要已超出了現(xiàn)有計算機的能力。計算機能執(zhí)行算法，也就是說，它能準確和全面地識別和執(zhí)行一系列的指令，而這些指令是用于求解嚴格確定的可計算問題的[9]。</p><p><b>　　⒉ 算法分析</b></p><p>　　算法分析是對算法性能的討論，它的目的是對同一問題的各種可實現(xiàn)的算法進行比

97、較，對它們的性能做出定量的判斷。捅死，可確定算法是否存在什么性能上的限制，如難易程度、最好的下界、最壞情況下和平均意義下的性態(tài)等等，給算法設(shè)計提供理論上的指導(dǎo)。</p><p>　　對算法的評價有許多標準，如清晰性、可讀性、易修改、易排錯等，它們屬于結(jié)構(gòu)化程序設(shè)計的討論范疇。在算法分析中，主要是研究完成算法需要的運行時間和占用的空間。</p><p>　　問題的規(guī)模是輸入量大小的一個測度，

98、也稱為問題的大小或尺寸，它視不同的問題有不同的含義。</p><p>　　考察一個規(guī)模為n的輸入，對不同的輸入，算法的行為可能不同，把其中的最壞行為，定義為該算法關(guān)于規(guī)模為n的復(fù)雜性。故算法或問題的復(fù)雜性一般是問題規(guī)模n的函數(shù)。旅行商問題中的城市數(shù)、0-1背包問題中的物品數(shù)、圖色問題中的頂點數(shù)都是刻劃問題規(guī)模的特征數(shù)。</p><p>　　復(fù)雜性函數(shù)中，增長速度較慢的項，終將被速度很快的項

99、超過（在nlgn+5n中，當n＞1000時，nlgn＞5n）。因此，在研究算法復(fù)雜形勢，僅考慮輸入增加速度增長最快的項即可。對增長速度，有如下概念：</p><p>　　設(shè)f(n)、g(n)是定義在正整數(shù)上的正實值函數(shù)，若</p><p>　　如果存在正常數(shù)c＞0，使得當n足夠大時，有f(n) ≤cg(n)，則記f(n)= ο（g(n)）；</p><p>　　如果

100、存在正常數(shù)c＞0，使得當n足夠大時，有f(n) ≥cg(n)，則記f(n)= Ω（g(n)）；</p><p>　　如果存在正常數(shù)c,c’＞0，使得當n足夠大時，有c’g(n) ≤f(n)≤cg(n)，則記</p><p>　　f(n) =θ(g(n));</p><p>　　顯然，θ是一種等價關(guān)系，在此等價關(guān)系下，f(n)的等價類（即使得f(n) =θ(g(n))

101、得集合）稱為f(n)的增長速度。應(yīng)用這一概念，一個算法的復(fù)雜性函數(shù)的增長速度可以有上街。例如它所用時間為ο（n3）。</p><p>　　在分析問題復(fù)雜性時，可以求出算法復(fù)雜性的函數(shù)f(n)，也可以方便地用復(fù)雜性函數(shù)的階ο（f(n)）。若算法A的時間復(fù)雜性是TA(n)= ο(p(n))，p(n)是n的多項式函數(shù)，這時算法是實際有效的，如復(fù)雜性為ο（n）或ο（n3）的算法是可以接受的。有些算法其漸進復(fù)雜性自身不是多

102、項式的，但它有一個多項式的上界，這樣的算法也是可以接受的，如n2.5和nlgn等。這類算法稱為多項式算法，J.Edmonds稱之為好的算法。</p><p>　　復(fù)雜性高于多項式的算法稱為指數(shù)算法，如n!、2n2、nn、nlgn。如搜索二分法的時間復(fù)雜性是ο（logn），堆 的時間復(fù)雜性時ο（nlogn），它們是好算法。而用動態(tài)規(guī)劃解決TSP的時間復(fù)雜性是ο（n22n），用回溯法求解圖的k-著色問題的時間復(fù)雜性時

103、ο（nkn），它們都是指數(shù)時間算法。</p><p>　　當輸入規(guī)模不斷增大時，任意一個多項式算法終將變得比任一指數(shù)算法更有效。多項式算法的另一個特色是：在某種意義上它很好地利用了技術(shù)發(fā)展的優(yōu)點。另外，多項式算法有較好的“閉”性：即幾個多項式算法可以結(jié)合起來解同一個問題的某些特殊情形；一個多項式算法也可以利用另一個多項式算法作為其“子程序”，并且最后的結(jié)果仍是多項式算法[5]。</p><p&

104、gt;　　有少數(shù)最壞情況下復(fù)雜度為指數(shù)函數(shù)的算法，但在實踐中證明是有效的算法，如線性規(guī)劃中的單純形算法就是一個突出的例子，它有指數(shù)實踐復(fù)雜度，可是實踐表明其運算相當快，其奧秘在于這些算法的平均性態(tài)良好。因此，在具體選擇算法時，應(yīng)該、根據(jù)算法的時間和空間復(fù)雜度，結(jié)合具體因素（如問題大小、機器容量、平均性態(tài)等），選擇使用好的算法。</p><p><b>　?、?NP難題</b></p&g

105、t;<p>　　NP是Nondeteministic Polynomial的縮寫，即為非確定型的多項式算法的意思。</p><p>　　⑴P類問題與NP類問題</p><p>　　一個問題的判定過程可形式地描述如下：已知L?{0,1}*，對于x?{0,1}*，若x∈L，則給出答案“是”，若x≮L，則給出答案“非”。</p><p>　　{0,1}*指的

106、是由有限個0和1組成的符號串集合?！啊凇北硎静粚儆?。</p><p>　　按照判定問題的復(fù)雜性對最優(yōu)化問題進行分類。問題復(fù)雜性的形式定義可用圖靈機（Turing Machine）計算模型給出。如果一個問題有解它的多項式時間DTM（確定型圖靈機）程序，則稱該問題屬于P類。P類問題表示多項式算法所能解決的判定問題類。如果一個問題有解它的多項式時間NIM（非確定型圖靈機）程序，則稱該問題屬于NP類。NP類問題是指可在多

107、項式時間內(nèi)檢測的問題類，至今尚未找到多項式時間算法。</p><p>　　對于一個NP類問題，并不要求的它的每個實例都能用某個算法在多項式時間內(nèi)得到回答，只要求，如果x是問題的答案為“是”的實例，則存在對x的一個簡短（即其長度以x的長度的多項式為界）證明，使得能在多項式時間內(nèi)檢驗這個證明的真實性。</p><p><b>　?、?NP-完全問題</b></p&g

108、t;<p>　　NP-完全問題為NP類中難度最大的問題，具有如下性質(zhì)：</p><p>　?、偃魏我粋€NP-完全問題都不能用任何已知的多項式算法求解。</p><p>　?、谌羧魏我粋€NP-完全問題有多項式算法，則NP-完全問題都有多項式算法。</p><p>　　為了證明一個問題是NP-完全的必須證明兩個方面：</p><p>

109、;　?、?該問題是NP的；</p><p>　?、?所有其他NP問題可算法，多項式變換到該問題。</p><p>　　現(xiàn)已正面的NP-完全問題有上千個，但沒有找到任一問題的多項式算法。因此，計算科</p><p>　　學(xué)家們大都認為NP-完全問題不存在有效的多項式時間但是未能證明。</p><p><b>　　⑶ NP難題</