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

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

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

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

4、理系統(tǒng)的設(shè)計(jì)中。物流信息管理系統(tǒng)實(shí)現(xiàn)了貨物托運(yù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è)計(jì)的基本步驟- 5 -</p><p>　　2.1.2 數(shù)據(jù)庫設(shè)計(jì)的原則- 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)化與計(jì)算復(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最少費(fèi)用流問題- 25 -</p><p>　　5.3.1 概述- 25 -</p><p>　　5.3.2 最少費(fèi)用流問題算法描述- 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é)約法計(jì)算實(shí)例- 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é)約算法的多車種分送式運(yùn)輸模型- 38 -</p><p>　　6.5.1 問題描述- 38 -</p><p

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

20、p>　　7 車輛調(diào)度算法應(yīng)用——物流管理系統(tǒng)- 45 -</p><p>　　7.1 系統(tǒng)目標(biāo)- 45 -</p><p>　　7.2 適用范圍- 45 -</p><p>　　7.3 運(yùn)行環(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)功能實(shí)現(xiàn)- 47 -</p><p>　　7.6.1 主界面的實(shí)現(xiàn)- 47 -</p><p>　　7.6.2 基本信息設(shè)置模塊的實(shí)現(xiàn)- 48 -</

22、p><p>　　7.6.3 貨物管理模塊的實(shí)現(xiàn)- 49 -</p><p>　　7.6.4 信息查詢模塊的實(shí)現(xiàn)- 50 -</p><p>　　7.6.5 系統(tǒng)管理模塊的實(shí)現(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>　　致 謝錯(cuò)誤!未定義書簽。</p><p>　　參考文獻(xiàn)- 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）。這是一類具有重要研究價(jià)值的問題。一方面，它代表了一類典型的組合優(yōu)化問題，具有深遠(yuǎn)的理論意義；另一方面，它是

25、一類重要的物流運(yùn)輸問題，直接影響著相關(guān)企業(yè)的運(yùn)轉(zhuǎn)效率，具有廣泛的實(shí)踐意義。半個(gè)世紀(jì)以來，許多的專家學(xué)者對該問題進(jìn)行了廣泛而深入的研究，并將這類問題統(tǒng)稱為車輛路徑調(diào)度問題（Vehicle Routing Problem，簡稱為VRP 問題）。他們從基本問題出發(fā)，根據(jù)不同的約束和目標(biāo)，構(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ù)以及計(jì)算機(jī)網(wǎng)絡(luò)和信息處理技術(shù)的快速發(fā)展，車輛優(yōu)化調(diào)度問題作為智能交通系統(tǒng)的一個(gè)重要組成部分，在很多國家受到關(guān)注。80年代以來，隨著ITS研究領(lǐng)域和內(nèi)容的不斷深入發(fā)展，逐漸形成了美國、歐洲和日本三大智能交通體系，且三大體系研究方面各有側(cè)重。目前，某些常用且較成熟的算法并已被人們運(yùn)用的有實(shí)際的動態(tài)車輛調(diào)度系統(tǒng)，美國利用最短路徑算法、啟發(fā)式算法開發(fā)計(jì)算機(jī)配送

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

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

29、，現(xiàn)代物流已被公認(rèn)為是企業(yè)在降低物質(zhì)消耗、提高勞動生產(chǎn)率以外創(chuàng)造利潤的第三個(gè)重要源泉，也是企業(yè)降低生產(chǎn)經(jīng)營成本，提高產(chǎn)品市場競爭力的重要途徑。配送是物流系統(tǒng)中的一個(gè)重要環(huán)節(jié)，它是指按客戶的訂貨要求，在物流中心進(jìn)行分貨、配貨工作，并將配好的貨物及時(shí)送交收貨人的物流活動。在配送業(yè)務(wù)中，配送車輛調(diào)度問題的涉及面較廣，需要考慮的因素較多，對配送企業(yè)提高服務(wù)質(zhì)量、降低物流成本、增加經(jīng)濟(jì)效益的影響也較大。該問題包括集貨線路優(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提出后，很快便引起運(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)實(shí)生產(chǎn)和生活中，郵政投遞問題、車船調(diào)度問題、電力調(diào)度問題、管道鋪設(shè)問題、計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)問題等都可以抽象為配送車輛調(diào)度問題。可見，研究配送車輛調(diào)度問題具有重要的理論和現(xiàn)實(shí)意義。</p><p>

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

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

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

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

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

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

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

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

40、的就是數(shù)據(jù)庫的設(shè)計(jì)。數(shù)據(jù)庫設(shè)計(jì)是指對于一個(gè)給定的應(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)重要，它將影響整個(gè)系統(tǒng)的運(yùn)作。下面對數(shù)據(jù)庫的設(shè)計(jì)做下簡單的介紹。</p><p>　　2.1.1 數(shù)據(jù)庫設(shè)計(jì)的基本步驟</p><p><b>　?。?）需求分析階段</b></p>

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

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

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

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

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

46、B語言</b></p><p>　　Visual Basic是一種由微軟公司開發(fā)的包含協(xié)助開發(fā)環(huán)境的事件驅(qū)動編程語言。從任何標(biāo)準(zhǔn)來說，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提供的組件快速建立一個(gè)應(yīng)用程序。</p><p>　　Visual Basic語言特性：</p><p>　?、?VB的中心思想就是要便于程序員使用，無論是新手或者專家。VB使用了可以簡單建立應(yīng)用程序的GUI系統(tǒng)，但是又可以開發(fā)相當(dāng)復(fù)雜的程序。VB的程序是一種基于窗體的可視化組件安排的聯(lián)合，并且增加代碼來指定組件的屬性和方法。因?yàn)槟J(rèn)的屬性和方法已經(jīng)有一部分定義在了組件內(nèi)，所

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

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

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

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

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

54、有效的算法。</p><p>　　VRP問題一般可定義為：對一系列的裝貨點(diǎn)或卸貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(貨物需求量、發(fā)送量、車輛容量限制、行駛里程限制、時(shí)間限制)下，達(dá)到一定的目標(biāo)(路程最短、時(shí)間最小、費(fèi)用最省、車輛數(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)的信息，這些信息與時(shí)間變換無關(guān)。一旦調(diào)度開始之后，認(rèn)為這些信息不再改變。</p><p>　　動態(tài)車輛調(diào)度問題更符合實(shí)際生活中的情況，它指的是：假設(shè)在優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

76、零售商店等。客戶的屬性包括需求（或供應(yīng)）貨物的數(shù)量、需求（或供應(yīng)）貨物的時(shí)間、需求（或供應(yīng)）貨物的次數(shù)及需求（或供應(yīng)）貨物的滿足程度等。</p><p>　　在某個(gè)配送系統(tǒng)中，某個(gè)客戶的需求（或供應(yīng)）貨物的數(shù)量可能大于車輛的最大裝載量，也可能小于車輛的最大裝載量；而該系統(tǒng)全部客戶的貨物需求（或供應(yīng)）總量可能超過全部車輛的總裝載量，也可能低于全部車輛的總裝載量。</p><p>　　某客戶的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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