基于CW算法的海王星辰連鎖藥店市內(nèi)配送優(yōu)化物流管理專業(yè)

1、題題 目目基于 CW 算法的海王星辰連鎖藥店市內(nèi)配送優(yōu)化社會化分工日益精細(xì)化，使得供應(yīng)與生產(chǎn)、生產(chǎn)與消費(fèi)在時間和空間上出現(xiàn)了矛盾，促使物流在社會生產(chǎn)和生活中扮演著越來越重要的作用，物流的運(yùn)營水平關(guān)系著一個國家經(jīng)濟(jì)發(fā)展的水平，各國政府都正大力發(fā)展本國物流。配送是物流運(yùn)作中的一個重要環(huán)節(jié)，車輛路徑問題是物流運(yùn)輸系統(tǒng)的核心組件，研究車輛路徑問題有助于企業(yè)降低物流成本、提高運(yùn)作效率、提高客戶滿意度。車輛路徑問題將運(yùn)籌學(xué)理論與管理實(shí)踐緊密地結(jié)合在一起，是近半個世紀(jì)以來運(yùn)籌學(xué)領(lǐng)域最成功的研究之一。 本文主要結(jié)合海王星辰在寧波市內(nèi)的配送路徑優(yōu)化實(shí)例，簡單介紹了城市物流的一些基本特征及發(fā)展的意義、國內(nèi)外對車輛

2、路徑的研究現(xiàn)狀、車輛路徑優(yōu)化問題，因本文采取節(jié)約算法作為路徑優(yōu)化的工具，故并著重介紹了節(jié)約算法的概念及其算法過程，最后詳細(xì)的介紹了海王星辰路徑優(yōu)化的方案過程及其得出的結(jié)果。關(guān)鍵字：物流；車輛路徑問題；配送路徑優(yōu)化；節(jié)約算法Abstractwith more and more refined distribution of social labor, the supply、the production and the consumption hardly work well in time and space any longer, which resulted in an increasing

3、ly important role of the production and the logistics in the social life. The countrys economic development is mainly contributed by logistics operators, so governments are making great efforts to develop logistics. Distribution is an important part of logistics, Vehicle routing problem is the main

4、problem in the field of logistics transportation system, research on vehicle routing problems will help enterprises to reduce logistical cost, improve operation efficiency, and enhance customer satisfaction comprehensively. Since vehicle routing problems tightly connect theory of Operation Research

5、with practice of management, which was named as one of the most successful areas in Operation Research in the past half century. This paper mainly with the Nepstar distribution path optimization instance in Ningbo City, brief introduction to some basic features and significance of the development of

6、 urban logistics, the research status of the vehicle path in china and abroad, vehicle routing problem. For this article to take to save algorithm as a tool in path optimization, so it focuses on the concept of saving algorithm described in detail, and last detailed the Nepstar path optimization sol

7、ution process and the results.Key words: logistics；Vehicle routing problem；distribution route optimization；saving algorithm目錄1 選題背景和研究意義.12 城市物流特征及發(fā)展城市物流意義.22.1 城市物流配送.22.2 城市物流的特征.22.3 城市配送的現(xiàn)狀.32.4 發(fā)展城市物流的意義.43 車輛路徑優(yōu)化問題.63.1 車輛路徑優(yōu)化的定義.63.2 國內(nèi)外車輛路徑問題研究動態(tài).73.2.1 國外車輛路徑問題研究現(xiàn)狀.73.2.2 國內(nèi)車輛路徑問題研究現(xiàn)狀.83.3

8、車輛路徑問題的分類.93.4 車輛路徑問題算法分類.123.4.1 精確算法.123.4.2 啟發(fā)式算法.123.4.3 智能算法.134 節(jié)約算法的理論基礎(chǔ)及算法設(shè)計(jì).164.1 CW 節(jié)約算法提出.164.2 CW 節(jié)約算法原理及特點(diǎn).164.2.1 CW 節(jié)約算法的基本原理.164.2.2 CW 節(jié)約算法對車輛進(jìn)行優(yōu)化調(diào)度的步驟.174.2.3 CW 節(jié)約算法的特點(diǎn).174.3 節(jié)約算法設(shè)計(jì).174.3.1 模型的數(shù)學(xué)描述.174.3.2 數(shù)學(xué)模型的建立.185 案例分析.195.1 案例背景.195.2 案例數(shù)據(jù)分析.205.2.1 供應(yīng)門店選擇及分布 .205.2.2 供應(yīng)門店需求量

9、.225.2.3 配送車輛選擇.245.2.4 配送距離的確定 .245.2.5 算法程序設(shè)計(jì).255.3 結(jié)果分析與算法改進(jìn) .275.3.1 結(jié)果分析及得出的改進(jìn)方案.275.3.2 改進(jìn)方案的設(shè)計(jì).285.4 改進(jìn)算法得出的運(yùn)行結(jié)果與分析 .295.4.1 運(yùn)行結(jié)果.295.4.2 結(jié)果分析與確定.315.5 案例分析總結(jié) .32致謝.34參考文獻(xiàn).35附錄.36附錄 1 配送距離和時間原始數(shù)據(jù).36附錄 2 配送路徑距離表.45附錄 3 節(jié)約里程表.46附錄 4 初始算法程序代碼.47附錄 5 方案一算法主要程序代碼.55附錄 6 方案二算法主要程序代碼.6111 選題背景和研究意義當(dāng)

10、今，世界經(jīng)濟(jì)發(fā)展日益趨于全球化，市場競爭也異常激烈，在此背景下產(chǎn)生了一個新興行業(yè)物流業(yè)。物流是社會經(jīng)濟(jì)和商品流通發(fā)展到一定階段的必然產(chǎn)物，為了滿足社會生產(chǎn)和消費(fèi)需求，對運(yùn)輸、倉儲、裝卸搬運(yùn)、包裝、流通加工、配送、信息處理等物流環(huán)節(jié)進(jìn)行現(xiàn)代化管理、控制及信息化作業(yè)的經(jīng)濟(jì)活動。隨著世界貿(mào)易的高速發(fā)展和信息網(wǎng)絡(luò)技術(shù)的日益完善，全球經(jīng)濟(jì)一體化步伐的加快，特別是我國加入 WTO 以后，物流業(yè)作為國民經(jīng)濟(jì)中一個新興的產(chǎn)業(yè)，將會成為我國 21 世紀(jì)經(jīng)濟(jì)發(fā)展的重要產(chǎn)業(yè)和新的經(jīng)濟(jì)增長點(diǎn)。作為“第三利潤源泉”的物流對經(jīng)濟(jì)活動的影響日益明顯，越來越得到了人們的重視，成為當(dāng)前“最重要的競爭領(lǐng)域” ，未來市場競爭，物流

11、將起著舉足輕重的作用，而配送是物流中一個重要的直接與消費(fèi)者相連的環(huán)節(jié)， 物流術(shù)語中對配送的定義為：物品從供應(yīng)地向接收地的實(shí)體流動過程，根據(jù)實(shí)際需要，將運(yùn)輸、儲存、裝卸搬運(yùn)、流通加工、配送、信息處理等基本功能，實(shí)施有機(jī)結(jié)合。配送的核心部分是配送車輛的集貨、貨物分揀及送貨過程，而車輛配送路徑的合理優(yōu)化，對于整個物流運(yùn)輸速度、成本、效益影響至關(guān)重要。但是目前，由于我國的物流產(chǎn)業(yè)起步晚，尚存在著許多問題。如何改變這種局面，使物流行業(yè)健康穩(wěn)步發(fā)展，是國民生產(chǎn)力發(fā)展急需解決的難題，當(dāng)前主要可從提高物流配送服務(wù)質(zhì)量入手。在現(xiàn)代物流系統(tǒng)中，配送是一個重要環(huán)節(jié)，而在配送業(yè)務(wù)中，能否將貨物及時送交收貨人手中是物流

12、系統(tǒng)優(yōu)化的關(guān)鍵，配送的質(zhì)量好壞決定服務(wù)水平的高低，同時影響到客戶對整個物流服務(wù)的滿意程度。然而物流車輛在配送過程中，會涉及到車輛路徑優(yōu)化的問題。因此結(jié)合實(shí)際的配送情況，規(guī)劃好物流配送的行進(jìn)路線，有利于節(jié)省配送費(fèi)用和提高配送服務(wù)質(zhì)量。同時，優(yōu)化后的物流配送路徑，有利于緩解交通壓力。由此說明，物流車輛路徑優(yōu)化問題在交通和物流規(guī)劃中具有舉足輕重的地位。選取恰當(dāng)?shù)能囕v路徑，可以加快物流系統(tǒng)對客戶需求的響應(yīng)速度，提高服務(wù)質(zhì)量，增強(qiáng)客戶對物流環(huán)節(jié)的滿意度，降低服務(wù)商的運(yùn)作成本。另外，由于在車輛配送過程中，有個別客戶對物流配送時間提出高要求，為了提高服務(wù)質(zhì)量和滿意度，所以必須對于配送時間要求嚴(yán)格掌控?？偟膩?/p>

13、說，本文是為了提高物流配送系統(tǒng)的服務(wù)質(zhì)量和節(jié)省配送費(fèi)用，對物流車輛配送路徑的優(yōu)化進(jìn)行的研究。為了更加形象的分析問題，本文將選取寧波市區(qū)海王星辰藥店的藥品配送為例，對中小型城市內(nèi)的車輛路徑優(yōu)化進(jìn)行研究。22 城市物流特征及發(fā)展城市物流意義2.1 城市物流配送 所謂物流配送就是按照用戶的貨物( 商品) 訂貨要求和物流配送計(jì)劃，在物流配送節(jié)點(diǎn)( 倉庫、商店、貨運(yùn)站、物流配送中心等) 進(jìn)行存儲、分揀、加工和配貨等作業(yè)后，將配好的貨物送交收貨人的過程。而城市物流配送是指在城市范圍內(nèi)進(jìn)行的物流配送業(yè)務(wù)活。 所謂城市物流是指為城市服務(wù)的物流，它服務(wù)與城市經(jīng)濟(jì)發(fā)展的需要，指物品在城市內(nèi)部的實(shí)體流動，城市與外部

14、區(qū)域的貨物集散以及城市廢棄物清理的過程，并存在不同的模式、體系和存在形態(tài)，和其他形式的物流有一定的區(qū)別。城市物流配送系統(tǒng)的服務(wù)對象可歸類為：政府、工業(yè)、商業(yè)、農(nóng)業(yè)、大眾客戶。即電子商務(wù)中所描述的B to G，B to B，B to C。城市物流配送已隨客戶需求變化從“少品種、大批量、少批次、長周期”向“多品種、小批量、多批次、短周期”轉(zhuǎn)變。由于城市范圍一般處于汽車運(yùn)輸?shù)慕?jīng)濟(jì)里程。因而這種物流配送往往采用汽車實(shí)現(xiàn)。城市物流是城市經(jīng)濟(jì)發(fā)展的產(chǎn)物，同時，城市物流又服務(wù)于城市經(jīng)濟(jì)發(fā)展的需要，并且是城市經(jīng)濟(jì)的一個有機(jī)組成部分。不論城市地域范圍大小，物流活動都具有共同的屬性。城市物流所包含的范疇可以有兩種

15、理解：一種理解是城市物流僅僅是城市內(nèi)部范疇的物流，而城市的輸入物流及城市的輸出物流是發(fā)生在若干城市之間的物流，已經(jīng)屬于區(qū)域物流的范疇，這是對城市物流俠義的理解；另一種理解是包括城市內(nèi)部的物流以及以城市為主體的城市外部物流，例如，城市的輸入物流及城市的輸出物流，這是對城市物流廣義的理解。2.2 城市物流的特征 城市物流師連接企業(yè)物流和區(qū)域物流之間的紐帶，即服務(wù)與城市經(jīng)濟(jì)發(fā)展的需要，也服務(wù)于區(qū)域經(jīng)濟(jì)發(fā)展的需要。城市聚集了大量的人口、政府機(jī)構(gòu)、工商企業(yè)、商品、文化教育機(jī)構(gòu)，分布著大量的航空、鐵路、公路等交通運(yùn)輸網(wǎng)絡(luò)和樞紐站點(diǎn)，在政治、經(jīng)濟(jì)、文化生活中起著重要的作用，具有較強(qiáng)的吸引力、輻射力和綜合服務(wù)

16、能力，對周邊地區(qū)經(jīng)濟(jì)發(fā)展能起到滲透、帶動作用。城市經(jīng)濟(jì)和區(qū)域經(jīng)濟(jì)的形成是城市物流產(chǎn)生的條件，城市商品和服務(wù)市場的繁榮為城市物流的發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)。城市物流的發(fā)展又為城市的發(fā)展起到有力的支撐作用，因此城市物流與城市經(jīng)濟(jì)涉及的范圍是一致的，從這個意義上說城市物流可以理解為是以城市為依托的區(qū)域物流，因此，有關(guān)區(qū)域物流的理論與政策、區(qū)域物流的規(guī)劃原則與方法、區(qū)域物流發(fā)展對策等等也適用于城市物流。城市物流的主要特點(diǎn)有：（1） 與以承載大宗貨物為主的區(qū)域物流相比，城市物流的密度大、承載的貨物種類繁3多，且這種情況與城市的規(guī)模成正比，因此城市物流的管理難度也更大。但是從另一方面來講，城市物流的主要特點(diǎn)是

17、城市主體的一元化，所有的城市都具有統(tǒng)一的政府組織，城市行政組織可以統(tǒng)籌和管理物流，因此，城市物流又具有非常強(qiáng)的可控性。（2） 與以長途運(yùn)輸為主的區(qū)域物流相比，城市物流采用的大多是以公路為主的短途運(yùn)輸方式。受城市范圍的制約，城市物流的短程性非常突出，再大的城市，城市的最大直徑無非在百公里以內(nèi)，城市中心物流密度再大的部位，也要遠(yuǎn)遠(yuǎn)低于這個數(shù)字。由于城市消費(fèi)需求的多樣化，城市分布的商業(yè)網(wǎng)點(diǎn)大多靠近消費(fèi)者居住地，因此在貨物到達(dá)城市后就需要以各種小型車輛分裝運(yùn)送，運(yùn)送的載體幾乎都是以公路為主。同時以多批次、少批量、多用戶物流為主要的物流形式，更強(qiáng)調(diào)物流服務(wù)，而很難有效的降低物流成本。（3） 除了以上兩點(diǎn)

18、特點(diǎn)之外，城市物流還具有精益化的運(yùn)作模式。城市是一個國家經(jīng)濟(jì)水平最高的地區(qū)，有進(jìn)行精益化運(yùn)作的需求和條件。更重要的是，城市交通條件的制約和生態(tài)的脆弱性，不允許進(jìn)行粗放的物流活動。因此，低噪音、低排放、小噸位、封閉型的物流車輛是城市物流的主要工具，執(zhí)行的是準(zhǔn)時、準(zhǔn)確的物流方式。這種精益的運(yùn)作，是城市物流的重要特點(diǎn)。2.3 城市配送的現(xiàn)狀 隨著經(jīng)濟(jì)的發(fā)展，物流業(yè)在我國城市有了一定的基礎(chǔ)。但是，城市物流在發(fā)展過程中，也暴露出了許多問題。（1） 涉及面廣，協(xié)調(diào)管理難城市物流配送管理涉及到城市交通警察局、運(yùn)管局（處）、城管、規(guī)劃等部門以及眾多的工商企業(yè)，涉及面廣，協(xié)調(diào)管理難度較大。各個主體根據(jù)部門相關(guān)職

19、責(zé)，從城市物流配送不同的角度，對城市物流配送進(jìn)行管理。在一個完整的城市物流配送活動中，往往受到不同部門的監(jiān)督與管理，過多部門的涉入，造成了職能的交叉，管理內(nèi)容繁雜，交叉管理多。（2） 基礎(chǔ)設(shè)施落后，機(jī)械化和信息化的配送設(shè)備更少我國大部分城市貨運(yùn)基礎(chǔ)設(shè)施多年來投入嚴(yán)重不足，極少具有上規(guī)模的貨運(yùn)站場和倉儲設(shè)施，且仍然大量使用手工整理、手工票據(jù)、人工裝卸作業(yè)，信息系統(tǒng)比較落后，不能及時跟蹤貨物和獲得配送信息。而國外的現(xiàn)代物流企業(yè)早已普遍應(yīng)用電子數(shù)據(jù)交換、電子自動訂貨、配送需求計(jì)劃、貨物跟蹤查詢服務(wù)等業(yè)務(wù)。我國城市物流企業(yè)構(gòu)建的信息系統(tǒng)，對數(shù)據(jù)的采集、統(tǒng)計(jì)、分析、預(yù)計(jì)能力還很不夠，沒有一套基于全程供應(yīng)

20、鏈管理的信息系統(tǒng)，與實(shí)物流、資金流的同步謝姐能力差，很難形成客戶“門到門”的物流管理。隨著新的城市規(guī)劃的實(shí)施和城市經(jīng)濟(jì)的增長，這些物流基礎(chǔ)設(shè)施和信息化必須跟上經(jīng)濟(jì)發(fā)展腳步，否則城市物流將成為城市經(jīng)濟(jì)發(fā)展的瓶頸問題。4（3） 經(jīng)營模式小，難以形成規(guī)?；某鞘形锪饔捎诔鞘袃?nèi)眾多的企業(yè)都自辦物流，經(jīng)營規(guī)模小，市場份額少，服務(wù)功能少，競爭力、融資能力弱，貨物不穩(wěn)定且結(jié)構(gòu)單一、缺乏網(wǎng)絡(luò)或網(wǎng)絡(luò)分散、經(jīng)營秩序不規(guī)范，難以形成規(guī)模經(jīng)營，缺乏網(wǎng)絡(luò)化運(yùn)作，導(dǎo)致信息溝通不通暢。由此造成了城市物流資源嚴(yán)重浪費(fèi)、企業(yè)物流成本難以降低、物流服務(wù)難以提高問題。所以如何將城市內(nèi)企業(yè)物流進(jìn)行整合，或者發(fā)展第三方物流企業(yè)，實(shí)現(xiàn)共

21、同配送，使城市物流更專業(yè)化、信息化、功能化，政府應(yīng)該予以重視。（4） 缺少城市物流配送通道，設(shè)置不合理調(diào)查發(fā)現(xiàn)，城市物流配送中有很多道路通行限制現(xiàn)行，在重要物流節(jié)點(diǎn)和大學(xué)的商業(yè)聚集區(qū)，配送擁堵現(xiàn)行突出，配送運(yùn)輸通道不通暢。同時，城市對于貨車的行駛的時間及車型限制，對于降低配送成本和及時完成配送產(chǎn)生了一定的影響。而且，在很多地方?jīng)]有根據(jù)土地利用情況來設(shè)置不同的配送通道區(qū)域，只是簡單地按照城市中心區(qū)與非中心區(qū)的劃分來標(biāo)定路段，限制車輛通行。（5） 供應(yīng)鏈管理提高了企業(yè)對城市物流配送的重視程度供應(yīng)鏈管理的實(shí)施，使企業(yè)更注重交付效率與效果。雖然大量干線運(yùn)輸與配載效率再提升的空間很小，但最為最后一公里的

22、配送由于直接面對客戶，直接影響到產(chǎn)品服務(wù)與配送時間效率，也就直接關(guān)系到企業(yè)的市場發(fā)展和企業(yè)效益。所以，企業(yè)對城市物流配送的城市成都需要得到很大的提高。2.4 發(fā)展城市物流的意義隨著城市經(jīng)濟(jì)發(fā)展的加快，城市物流的作用越來越大，建立一個高效率的城市物流體系就顯得越來越有必要，城市物流對整個城市的發(fā)展促進(jìn)作用非常明顯，主要體現(xiàn)在：（1）促進(jìn)優(yōu)化區(qū)域產(chǎn)業(yè)結(jié)構(gòu)。通常來說，城市是商品集散和加工的中心，并且物流設(shè)施和基礎(chǔ)建設(shè)相對比較齊全，消費(fèi)比較集中且需求量大，交通與信息發(fā)達(dá)，城市水平己成為物流業(yè)發(fā)展的一個重要條件。而物流產(chǎn)業(yè)發(fā)展帶來的商流、資金流、信息流、技術(shù)流的集聚，以及交通運(yùn)輸業(yè)、商貿(mào)業(yè)、金融業(yè)、信息

23、業(yè)和旅游等多種產(chǎn)業(yè)的發(fā)展，又有助于城市產(chǎn)業(yè)結(jié)構(gòu)的合理化。此外，由于物流是對分散的貨物流動進(jìn)行集中處理，必然要求利用現(xiàn)代化的物流設(shè)施、先進(jìn)的信息網(wǎng)絡(luò)進(jìn)行協(xié)調(diào)和管理，真正的現(xiàn)代物流屬于技術(shù)密集型和高附加值的高科技產(chǎn)業(yè)，具有資產(chǎn)結(jié)構(gòu)高度化、技術(shù)結(jié)構(gòu)高度化、勞動力高度化等特征。從這個角度來說，建立城市物流體系，發(fā)展城市物流，將有利于城市產(chǎn)業(yè)結(jié)構(gòu)向高度化方向發(fā)展。（2）推動區(qū)域經(jīng)濟(jì)的快速增長。加強(qiáng)城市物流基礎(chǔ)設(shè)施的建設(shè)，提高物流技術(shù)水平，加快物流速度，無疑對區(qū)域經(jīng)濟(jì)的發(fā)展具有極為重要的意義?，F(xiàn)代物流的實(shí)質(zhì)是一種供應(yīng)鏈管理，中心城市發(fā)展現(xiàn)代物流，很大程度上是一個組織和理順供應(yīng)鏈關(guān)系的問題。只有建立高效運(yùn)作

24、的物流系統(tǒng)，理順各種供應(yīng)鏈關(guān)系，才能解決好5城市積聚的貨物快捷地發(fā)運(yùn)到周邊地區(qū)乃至更遠(yuǎn)的地方，使中心城市對周邊地區(qū)的輻射功能和在經(jīng)濟(jì)上的龍頭帶動作用才能真正得以發(fā)揮。最近十幾年，上海、深圳、廈門、寧波等城市在發(fā)展物流的過程中通過對基礎(chǔ)設(shè)施的投資，對當(dāng)?shù)氐慕?jīng)濟(jì)拉動非常的明顯。上海市的物流業(yè)以每年213的速度增長，為傳統(tǒng)制造業(yè)、信息產(chǎn)業(yè)和全融業(yè)的快速增長奠定了堅(jiān)實(shí)的基礎(chǔ)，為上海經(jīng)濟(jì)的發(fā)展做出了巨大的貢獻(xiàn)。（3）增強(qiáng)城市的綜合競爭力。如提升城市功能，改善城市國民經(jīng)濟(jì)運(yùn)行效率，提高全社會經(jīng)濟(jì)效益，擴(kuò)大吸引外資，增加就業(yè)機(jī)會，改善城市投資環(huán)境。（4）促進(jìn)城市的現(xiàn)代化。現(xiàn)在很多城市人流、物流混雜，交通、倉

25、儲、流通加工等都集中在城區(qū)，城市污染嚴(yán)重。發(fā)展現(xiàn)代物流，改造城市的物流系統(tǒng)可以降低物耗和節(jié)約能源。有效控制車輛污染，合理使用土地，及時處理廢棄物，美化城市環(huán)境。國外在城市建設(shè)中，都把物流系統(tǒng)重新規(guī)劃、重新改造。例如日本就把城區(qū)里的流通加工、倉庫等等重新設(shè)計(jì)、規(guī)劃，放到郊區(qū)交通發(fā)達(dá)的地方，建立物流中心。所以，建立合理的城市物流系統(tǒng)是城市現(xiàn)代化的需要。63 車輛路徑優(yōu)化問題3.1 車輛路徑優(yōu)化的定義 車輛路徑問題最早由學(xué)者Dantzig和Ramser于1959年提出，一般可定義為：對于一系列裝貨點(diǎn)和（或）卸貨點(diǎn)，組織合適的行車線路，使載貨車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發(fā)送

26、量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達(dá)到一定的目標(biāo)（如路程最短，費(fèi)用最少，時間盡量少，使用車輛數(shù)量盡量少等）。車輛路徑問題的示意圖如圖3.1所示：圖3.1 車輛路徑問題示意圖車輛路徑優(yōu)化問題實(shí)際上就是從中心倉庫出發(fā)，對一系列特定位置和需求量的客戶點(diǎn)，選擇最優(yōu)的行駛路線同時調(diào)用一定數(shù)量的車輛，使車輛有序的訪問各客戶點(diǎn)的過程。車輛必須在滿足特定的約束條件(如客戶需求量，車輛載重量等)下，使得貨物盡快到達(dá)客戶點(diǎn)并且運(yùn)輸總費(fèi)用最低。從圖論的角度來說，車輛路徑問題可以描述為一個無向圖，其中,GV A，V代表頂點(diǎn)的集合， ，代表連接多個頂01,.,NVv vv( ,)|,ijijE

27、v vv vV ijE顧客配送服務(wù)中心7點(diǎn)之間線段的集合，通常稱為邊的集合。頂點(diǎn)表示配送中心的位置，其他頂點(diǎn)則表0v示有待服務(wù)的顧客的集合。通常在上定義一個非負(fù)的距離矩陣或成本矩陣，E ijDd此處代表從頂點(diǎn) 到頂點(diǎn)的距離或者成本等。ijdij 與旅行商問題（TSP）對比可以看出，車輛路徑問題（VRP）就是TSP問題中，給每個客戶添加了固定的需求量，同時每一輛車增加了一些約束量，包括時間限制，車輛的容量限制等。圖3.2所示是上圖中給每個客戶添加固定需求和一些約束條件后的VRP問題的解：圖3.2 擁有三條路線的一般的VRP的一個可行解3.2 國內(nèi)外車輛路徑問題研究動態(tài)3.2.1 國外車輛路徑問題

28、研究現(xiàn)狀由于車輛路徑問題將運(yùn)籌學(xué)理論和企業(yè)物流活動緊密聯(lián)系在一起，自提出后便引起運(yùn)籌學(xué)、圖論與網(wǎng)絡(luò)分析、應(yīng)用數(shù)學(xué)、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科的專家和管理者的重視，成為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的前沿和熱點(diǎn)問題。國外對物流配送車輛路徑問題作了大量而深入的研究，例如早在 1983 年 Bodin、Golden 等人在他們的綜述文章中就列舉了 700 余篇文獻(xiàn)。1962 年，Balinski 和 Quandt 最早使用了集分割法，在對可行解集合直接考慮的基顧客配送服務(wù)中心11（28）10（16）9（21）8（6）7（25）6（27）5（7）4（19）3（29）2（17）1（13）8礎(chǔ)上進(jìn)行優(yōu)化，并提出了最

29、簡單的 VRP 模型。1964 年，Clarke 和 Wright 提出一種較有效的啟發(fā)式算法Clarke-Wright 節(jié)約算法。Paessens 等人通過使用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，降低了它的復(fù)雜度，ClarkeWright 法隨后成為許多專家和學(xué)者研究 VRPTW 的基礎(chǔ)。隨后，Rao 等人引入了列生成方法對 VRP 進(jìn)行求解。在該方法中，原問題被轉(zhuǎn)化為簡化問題，考慮的范圍是所有可能的可行解的子集，在此基礎(chǔ)上復(fù)雜求解，從而尋找最短路徑。隨著 20 世紀(jì) 70-80 年代數(shù)學(xué)規(guī)劃和網(wǎng)絡(luò)分析的發(fā)展，人民提出了精確的數(shù)學(xué)方法解決 VRP 問題，主要有：分枝定界法、割平面法、網(wǎng)絡(luò)流算法、動態(tài)規(guī)劃法等。如

30、Lee 等為 VRP 建立了一個確定的動態(tài)規(guī)劃模型并設(shè)計(jì)了一個基于最短路徑搜索算法的精確算法。Azi 等通過首先產(chǎn)生所有非支配可行解，然后對路徑進(jìn)行選擇排序的方法，建立了一個基于帶限制最短路徑算法的求解方法。到了 90 年代，人工智能分發(fā)展促進(jìn)了對 VRP 算法的研究，人們采用了模擬退火算法、遺傳算法、例子群算法、禁忌搜索算法、蟻群優(yōu)化算法和人工神經(jīng)網(wǎng)絡(luò)算法等智能優(yōu)化算法。1994 年 Garcia 等首先將禁忌算法應(yīng)用于 VRPTW 問題。用禁忌搜索算法求解 VRP 問題，雖然能保證對不同的有效搜索途徑的探索，但由于涉及復(fù)雜的鄰域轉(zhuǎn)換和求解策略，因而在實(shí)際中不容易實(shí)現(xiàn)；Osman 于 199

31、3 年對 VRP 問題的模擬退火算法進(jìn)行了研究，提出模擬退火方法適合于解決路線分組問題；神經(jīng)網(wǎng)絡(luò)模型由McCulloch 和 Pitts 于 1943 年提出，模型主要是利用神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的協(xié)同并行計(jì)算能力來構(gòu)造的優(yōu)化算法；遺傳算法是 70 年代由美國 J.Hollan 教授和他的學(xué)生建立發(fā)展起來的，其基本思想是模擬生物進(jìn)化中“適者生存”的規(guī)律；蟻群算法是 Dorigo 提出的一種基于群體仿生的智能優(yōu)化算法；微粒群算法算法是由 Kennedy 和 Eberhart 于1995 年提出的一種基于群智能方法的演化計(jì)算技術(shù)等。3.2.2 國內(nèi)車輛路徑問題研究現(xiàn)狀國內(nèi)對 VRP 問題的研究起步比較晚

32、，大約于 20 世紀(jì) 80 年代開始。經(jīng)過 20 多年的研究，取得了一些成果，但與國外相比，目前仍處于起步狀態(tài)。在解決具體問題方面：郭耀煌、李軍是國內(nèi)第一批研究 VRP 的學(xué)者，他們用傳統(tǒng)啟發(fā)式算法解決了一些相對簡單的 VRP 問題，如送貨點(diǎn)比較少得容量約束、時間窗約束 VRP；李大衛(wèi)等以 TSP 的最近距離啟發(fā)式為基礎(chǔ)，通過設(shè)置評價函數(shù)來處理時間約束，求解了簡單的 VRP；張濤等人則是通過遺傳算法來保證搜索的全局性，用 3-OPT算法來加強(qiáng)局部搜索能力，得到針對 VRP 的混合算法；蔡延光用遺傳算法、模擬退火算法等研究重載 VRP 問題，取得了一些成績。在理論綜述方面：汪壽陽、林巖等對選址路

33、徑問題的研究進(jìn)行了分析；祝崇雋較全面的回顧了 VRP 領(lǐng)域的最新進(jìn)展；黃虹，張正雄等對車輛路徑問題進(jìn)行研究現(xiàn)狀的分析和展望；陳文蘭，戴樹貴等對車輛路徑安排問題算法做了研究綜述；謝秉磊、郭9耀煌等對動態(tài) VRP 的最新發(fā)展作了評述等。盡管國內(nèi)學(xué)者在 VRP 的研究方面已經(jīng)有了一定的成果，但是總的說來還是處在起步階段，由于該問題涉及許多要素，而且為了滿足實(shí)踐的需要，還將融合其它新的要素，仍有很多新的問題值得進(jìn)一步研究。主要表現(xiàn)在如下幾個方面：（1） 研究的問題大多是確定型問題，很少見到研究不確定條件下，特別是實(shí)時調(diào)度情況下 VRP 的文獻(xiàn)。實(shí)際中引起不確定性的因素很多且交叉影響，而目前的研究卻主要

34、集中在由單一不確定性因素（尤其是需求的不確定性）引起的 VRP，未綜合考慮車輛、客戶、路況等各種不確定性，同時對不確定性的研究也只限于單一的隨機(jī)或模糊形式的不確定性，沒有考慮更復(fù)雜的粗糙情形或者雙重不確定性等形式，與廣泛的實(shí)際應(yīng)用尚有距離。（2） 在車輛調(diào)度的中，應(yīng)根據(jù)使用者的實(shí)際制定相關(guān)的目標(biāo)，有些目標(biāo)甚至相互沖突（比如客戶滿意度的提高和運(yùn)作成本的降低就可能是一對矛盾） ，因此在決策中需要更多地考慮多目標(biāo)的情況，但 VRP 的以往研究主要集中于單一目標(biāo)問題，對多目標(biāo)問題的研究尚顯不足。（3） 研究問題的手段比較單一。目前國內(nèi)主要用智能算法對 VRP 進(jìn)行研究，在可參考的文獻(xiàn)中，還沒有見到用精

35、確算法做算例的研究成果。（4） 需要建立統(tǒng)一的算法評估體系，主要包括求解VRP算法的復(fù)雜性分析和收斂性分析（定界分析） ，通過算法的復(fù)雜性分析，可以為評定算法尋優(yōu)效率提供依據(jù)，為設(shè)計(jì)更快的算法提供理論依據(jù)；收斂性分析為評定算法搜索能力提供衡量標(biāo)準(zhǔn)，可以知道該算法可得到的最好和最差解的范圍，為使用者選擇滿足所求問題的搜索精度要求的算法提供依據(jù)。而目前只能對VRP的各種算法性能進(jìn)行經(jīng)驗(yàn)評價，而且各算法選用的測試數(shù)據(jù)不全相同，很難客觀地評定算法的優(yōu)劣，因此有必要建立統(tǒng)一的算法評估考核指標(biāo)體系。3.3 車輛路徑問題的分類根據(jù)以上國內(nèi)外研究動態(tài)的研究得出車輛路徑問題涉及到的各因素是車輛路徑問題分類的依據(jù)

36、。Bodin(1983)等人將影響車輛路徑問題的主要因素整理如表3.1所示。表 3.1 影響調(diào)度和路徑的主要因素序號因素可能的選擇1可行車隊(duì)的大小一輛；多輛2可行車隊(duì)的種類單一的（僅有一種車型） ；異質(zhì)的（多種車型） ；特殊的3車輛的出發(fā)點(diǎn)單一場站（單一物流中心）：多場站4需求的類型確定性需求；隨機(jī)性需求；允許滿足部分需求105需求的位置在顧客點(diǎn)上；在路線上；混合型6網(wǎng)絡(luò)形態(tài)間接；直接；混合；歐幾里得幾何7車輛容量限制全部一樣；不一樣；沒有容量限制8最大行車時間各繞路皆相同；不同繞路不同時間；沒有時間限制9作業(yè)只有揀貨；只有送貨；有揀貨和送貨；粉刺運(yùn)送10成本變動成本（或繞路成本） ；固定成本

37、（或車輛成本） ；一般成本（沒有服務(wù)時的成本）11目標(biāo)最小繞路成本；最小固定成本與變動成本；最小車輛使用數(shù)目；最大服務(wù)或便利效用函數(shù)；最大服務(wù)或便利效用函數(shù)；最大顧客優(yōu)先權(quán)效用函數(shù)目前已知的研究模型是對這些因素中的一種或幾種的組合同時忽略其他因素建立的。車輛路徑問題的主要模型如下： （1）按起訖點(diǎn)劃分為：一是起訖點(diǎn)不同的單一車輛路徑問題；二是多個起訖點(diǎn)的車輛路徑問題；三是起訖點(diǎn)相同的車輛路徑問題。（2）按照有無車輛容量限制分為：有能力約束的車輛路徑問題(CapacitatedVehicle Routing Problem，CVRP)和沒有能力約束的車輛路徑問題。CVRP是指任意車輛路徑的總重量

38、不能超過該車輛的重量或體積的能力負(fù)荷。（3）有時間窗約束和無時間窗約束的車輛路徑的問題。包括硬時間窗(Hard Time windows)和軟時間窗(Soft Time windows)約束。引出帶時間窗(包括硬時間窗和軟時間窗)的車輛路徑問題(Vehicle RoutingProblem withTime windows，VRPTW)。如果到達(dá)任務(wù)點(diǎn)的時間是事先規(guī)定的，則稱該問題是帶時間窗要求的車輛優(yōu)化調(diào)度問題；若到達(dá)和離開時間沒有規(guī)定，則稱該問題就是一個直接的線路安排問題。帶時間窗的VRP又可分為硬時間窗VRP和軟時間窗VRP。硬時間窗VRP 指每項(xiàng)任務(wù)必須在要求的時間內(nèi)完成，軟時間窗VR

39、P指如果某項(xiàng)任務(wù)不能在要求的時間范圍內(nèi)完成，則給予一定的懲罰。（4）滿載和非滿載的車輛路徑問題。當(dāng)每個客戶需求量小于車輛容量時，用一輛車執(zhí)行一項(xiàng)任務(wù)就存在不滿載運(yùn)行情況，調(diào)度時可安排一輛車執(zhí)行多項(xiàng)任務(wù)，即在一輛車上裝載不同貨主的貨物，這類問題稱為非滿載VRP。當(dāng)然， 這類問題有一個前提條件，即不同貨主的貨物允許混裝。當(dāng)每個客戶需求量大于車輛容量時，用一輛車執(zhí)行一項(xiàng)任務(wù)就不能滿足客戶的需求，此時需要一輛以上的車對其進(jìn)行送貨，車輛能夠滿載，該問題稱為滿載VRP。（5）單車場和多車場的車輛路徑問題(Singleand Multi-Depot Vehicle Routing Problem)。單車場車

40、輛路徑問題是指所有的車輛均從一個配送中心發(fā)出，完成各自的任務(wù)后11都返回該配送中心。多車場車輛路徑問題是指，存在著多個配送中心，車輛可以從任何一個配送中心派出，完成任務(wù)后，車輛也可以返回其中的任何一個配送中心，隨著供應(yīng)鏈的集成一體化，多車場的車輛路徑問題將越來越多、越來越重要。對于這類問題可以通過一定的方法將其轉(zhuǎn)化為單車場的車輛路徑問題。（6）按車輛類型數(shù)量分為：單車型問題(所有配送車輛的載重量相同)和多車型問題(配送車輛的載重量不完全相同) (Mixed/Heterogeneous Fleet Vehicle Routing Problem。MFVRP/ HFVRP)。（7）按車輛對車場的所

41、屬關(guān)系分為：開路車輛路徑問題(Open Vehicle RoutingProblem) （即車輛完成配送任務(wù)后可以不返回其發(fā)出車場) 和封閉車輛路徑問題(即車輛完成配送任務(wù)后必須返回其發(fā)出車場)。（8）按配送任務(wù)特征分：純送貨問題、純?nèi)∝泦栴}、取送混合問題(Vehicle Routing Problem with Pick-up andDelivery，VRPPD)。純送貨問題僅考慮從物流中心向客戶送貨，也稱為純卸問題；純?nèi)∝泦栴}僅考慮把各客戶供應(yīng)的貨物取到物流中心，也稱為純裝問題；VRPPD既考慮將客戶需求的貨物從配送中心送到各個客戶，同時考慮將客戶供應(yīng)的貨物從客戶取到物流中心，也稱為裝卸混

42、合問題或集貨和送貨一體化問題。（9）確定型需求車輛路徑問題、模糊需求車輛路徑問題(Fuzz Vehicle Routing Problem，F(xiàn)VRP)、隨機(jī)需求車輛路徑問題(VehicleRouting Problem withStochastic Demand ，VRPSD) 。隨機(jī)需求車輛路徑問題目前主要研究的是隨機(jī)客戶、隨機(jī)需求、隨機(jī)時間這三方面的內(nèi)容。隨機(jī)客戶問題在物流領(lǐng)域經(jīng)常會出現(xiàn)。隨機(jī)需求車輛路徑問題(VRPSD)，雖然知道確切的客戶，卻無法知道客戶的準(zhǔn)確需求量。模糊需求車輛路徑問題FVRP：在實(shí)際的車輛調(diào)度中，某些待服務(wù)客戶的需求信息沒有或無法給出準(zhǔn)確的描述，所以就需要將模糊概念

43、引入模型和算法來解決這類問題；另一種形式是將模糊概念引入時間窗，通常客戶需要服務(wù)的時間雖然有一個范圍，但是一個模糊量。車輛在客戶要求的范圍內(nèi)到達(dá)都是可行的，但到達(dá)的時間不同，客戶的滿意度可能不同，這類問題同時是多目標(biāo)優(yōu)化的問題。(10) 周期性的車輛路徑問題(Periodic VehicleRouting Problem，PVRP )。周期性車輛路徑問題是對VRP的擴(kuò)展，VRP研究的是對車輛的日安排，而PVRP是對車輛的一個周期內(nèi)多日的安排。在一個周期內(nèi)，每個客戶在滿足需求的前提下，最少被服務(wù)一次，也可以是多次。（11）非對稱網(wǎng)絡(luò)車輛路徑問題(Asymmetric Network Vehicl

44、e Routing Problem，AVRP)。非對稱網(wǎng)絡(luò)車輛路徑問題在現(xiàn)實(shí)生活中比較常見，如單行道或禁止左轉(zhuǎn)等交通標(biāo)識的存在，使得從甲地到乙地，和從乙地到甲地的距離(或時間)并不相同。由于非對稱網(wǎng)絡(luò)的這個特性，使得許多在VRP中成功應(yīng)用的算法不能直接用于非對稱網(wǎng)絡(luò)的求解，目前的許多求解算法都是基于非對稱TSP問題的算法而來的。12（12）按目標(biāo)多少分為：單目標(biāo)車輛路徑問題和多目標(biāo)車輛路徑問題。單目標(biāo)車輛路徑問題僅考慮一個配送目標(biāo)；多目標(biāo)車輛路徑問題同時考慮多個配送目標(biāo)，比如說同時考慮里程最短、費(fèi)用最少、時間最短等。3.4 車輛路徑問題算法分類由于VRP對節(jié)約物流成本、提高物流系統(tǒng)效率有重要的

45、意義，該問題的求解算法一直是物流和算法研究領(lǐng)域的一個熱點(diǎn)問題。早期的研究者主要構(gòu)造精確算法求解VRP。一般來說，精確算法對于客戶數(shù)小于50的VRP具有較高的性能，但是，對于更大規(guī)模的VRP，精確算法的處理時間通常就難以接受了。對于更大規(guī)模的VRP，研究者主要通過構(gòu)造啟發(fā)式算法來求解。3.4.1 精確算法 精確算法是求出最優(yōu)解的算法，主要有分枝定界法、割平面法、動態(tài)規(guī)劃法、網(wǎng)絡(luò)流算法等。（1）枝定界法。分枝定界法求解VRP問題的基本思想是，以相應(yīng)的不含整數(shù)約束的VRP問題的最優(yōu)解為出發(fā)點(diǎn)，若此解是整數(shù)解，那么這個解就是原VRP問題的最優(yōu)解，否則非整數(shù)解的相鄰整數(shù)作附加條件，形成2個分枝，即2個子

46、問題，進(jìn)行求解。若對上面2個子問題求出最優(yōu)解是整數(shù)解，則停止該子問題的分枝，否則繼續(xù)分枝求解。這種方法只能適用于求解小型VRP問題。（2）割平面法。割平面法求解VRP問題的基本思想是，在求解相應(yīng)的不含整數(shù)約束的VRP問題上，增加線性約束條件(幾何術(shù)語稱為割平面)，以將可行域切割掉一部分，使其切割掉的部分只包含非整數(shù)解，沒有切割掉任何整數(shù)可行解，直到切割后得到的可行域有一個整數(shù)坐標(biāo)的極點(diǎn)恰好是最優(yōu)解為止。由于割平面法求解時間過長，故不適用于大規(guī)模問題。（3） 動態(tài)規(guī)劃法。動態(tài)規(guī)劃法求解VRP問題的基本思路是，將VRP問題視為一個n階段的決策問題，進(jìn)而將其轉(zhuǎn)化為依次求解n個具有遞推關(guān)系的單階段的決

47、策問題，從而簡化計(jì)算過程。用這種方法可求得VRP的最優(yōu)解，但僅適用于較小規(guī)模的尋優(yōu)問題。（4）網(wǎng)絡(luò)流算法。網(wǎng)絡(luò)流算法求解VRP問題的基本思想是，首先構(gòu)建VRP問題的網(wǎng)絡(luò)模型，找到網(wǎng)絡(luò)中需調(diào)量最大的弧，然后通過調(diào)節(jié)弧流量或弧兩端節(jié)點(diǎn)上的位勢，來減少弧上的需調(diào)量，直至所有弧的需調(diào)量都等于零。由于網(wǎng)絡(luò)模型的頂點(diǎn)數(shù)目和邊的數(shù)目會顯著影響網(wǎng)絡(luò)流算法時間效率，所以這種算法只適用于小規(guī)模的VRP問題。由于精確算法在求解時引入了嚴(yán)格的數(shù)學(xué)方法(手段)，精確算法的計(jì)算量一般會隨著問題規(guī)模的增大呈指數(shù)增長，從而使該類算法只能有效求解小規(guī)模的VRP問題，如在客戶數(shù)量較少、運(yùn)輸網(wǎng)絡(luò)較簡單時，才能求得物流配送車輛調(diào)度問

48、題的精確最優(yōu)解，在實(shí)際中其應(yīng)用范圍很有限。133.4.2 啟發(fā)式算法 啟發(fā)式算法在求解VRP問題時通常是從初始解出發(fā)，以鄰域搜索的方式實(shí)現(xiàn)解的改進(jìn)，并在較短的時間內(nèi)獲得一個可以接受的解。它包括:（1）節(jié)約算法。該算法的基本思路是，按節(jié)約值從大到小構(gòu)造路徑，在車輛容量限制下，依序?qū)?yīng)的兩客戶點(diǎn)排入路徑中，直至所有客戶都被排入路徑為止。這種算法具有運(yùn)算速度快的優(yōu)點(diǎn)，特別是在小規(guī)模的配送優(yōu)化中，節(jié)約算法的優(yōu)化精度與最優(yōu)解很接近，并且能夠很快給出結(jié)果。但在客戶規(guī)模增加后，容易出現(xiàn)不理想的優(yōu)化結(jié)果。（2）最鄰近法。算法從配送中心開始，搜索距離配送中心最近的、未訪問的節(jié)點(diǎn)作為第一個節(jié)點(diǎn)并設(shè)為已訪問，然后

49、以該點(diǎn)為中心搜索與之相鄰的、未訪問的節(jié)點(diǎn)，如果加上該點(diǎn)不會超出容量限制，則將該點(diǎn)加入到線路中并設(shè)為已訪問，否則結(jié)束該條線路。重復(fù)上述步驟，尋找距離配送中心最近的未訪問的節(jié)點(diǎn)作為新線路的第一個節(jié)點(diǎn)，生成新的線路，直到將所有的節(jié)點(diǎn)都訪問過。最鄰近法算法簡單，可以在較短時間內(nèi)求得初始解。但易早熟收斂，容易陷入局部最優(yōu)。（3）最近插入法。最近插入法的算法流程與最鄰近法基本相似。這種算法的關(guān)鍵是依序選擇最合適的未分配的節(jié)點(diǎn)在路線中進(jìn)行最佳位置的插入，以構(gòu)建配送路線，直至不存在可行插入節(jié)點(diǎn)時新增一條初始路線。用最近插入法求得的解比最鄰近法求得的解更優(yōu)，但在計(jì)算過程中，也耗費(fèi)了更多的計(jì)算量。（4）掃描法。它

50、假設(shè)車輛的路線位于一個幾何平面上，平面上所有的點(diǎn)都以極座標(biāo)來表示，配送中心為原點(diǎn)。先選定一尚未使用的車輛，在不違反車輛容量限制的前提下，從角度最小且尚未指派的節(jié)點(diǎn)開始，依順時針或逆時針的方向掃描。當(dāng)車輛容量超過時，結(jié)束該條線路。重復(fù)上述步驟，生成新的線路，直到將所有的節(jié)點(diǎn)都被排入。最后再用求解旅行商問題(TSP)的算法對每一條路線分別進(jìn)行優(yōu)化。用掃描法求解VRP問題，能在較短的時間內(nèi)求得可行的滿意解，但不一定能導(dǎo)出最優(yōu)解。3.4.3 智能算法20世紀(jì)90年代以來，由于人工智能方法在解決組合優(yōu)化問題中的強(qiáng)大功能，不少學(xué)者開始將人工智能引入車輛路線問題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算

51、法(智能化啟發(fā)式算法)。智能化啟發(fā)式算法包括:（1）禁忌搜索算法。它是一種全局逐步尋優(yōu)算法，引入了一個禁忌表，記錄下已經(jīng)搜索過的局部最優(yōu)點(diǎn)，在下一次搜索中利用禁忌表中的信息不再或者有選擇地搜索這些點(diǎn)，以此來跳出局部最優(yōu)點(diǎn)，從而實(shí)現(xiàn)全局優(yōu)化。用禁忌搜索算法求解VRP問題，雖然能保證對不同的有效搜索途徑的探索，但由于涉及復(fù)雜的鄰域轉(zhuǎn)換和求解策略，因而在實(shí)際中不容易實(shí)現(xiàn)。（2）模擬退火法。模擬退火法是是一種基于熱力學(xué)原理的隨機(jī)搜索算法。用模擬退火14法求解VRP問題時，把物理退火中原子獲得能量相當(dāng)于分配最優(yōu)節(jié)點(diǎn)，將原子振動模擬為線路尋優(yōu)空間的隨機(jī)搜索。搜索過程由執(zhí)行分配的成對交換完成，搜索初始解為配

52、送總成本。對現(xiàn)有分配情況用任意成對交換產(chǎn)生新的分配，從而對配送路線不斷進(jìn)行改進(jìn)，直至找到最優(yōu)路線。模擬退火算法適合大規(guī)模的需求固定或者隨機(jī)需求的VRP問題。從理論上講，用這種方法求解VRP問題，可以求得全局最優(yōu)解，但在實(shí)際應(yīng)用中，由于受計(jì)算時間的限制，往往只能給出一個近似的最優(yōu)解。為了使模擬退火算法求出的近似解更準(zhǔn)確，一般重復(fù)執(zhí)行模擬退火法多次，從中選取最好的解作為最終的近似最優(yōu)解。（3）神經(jīng)網(wǎng)絡(luò)算法。神經(jīng)網(wǎng)絡(luò)模型主要是利用神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的協(xié)同并行計(jì)算能力來構(gòu)造的優(yōu)化算法。它將實(shí)際問題的優(yōu)化解與神經(jīng)網(wǎng)絡(luò)的穩(wěn)定狀態(tài)相對應(yīng)，把實(shí)際問題的優(yōu)化過程映射為神經(jīng)網(wǎng)絡(luò)系統(tǒng)的演化過程。袁健和倪勤在2000年

53、曾用神經(jīng)網(wǎng)絡(luò)算法求解了隨機(jī)需求情形的VRP問題。神經(jīng)網(wǎng)絡(luò)算法求解VRP問題可能會導(dǎo)致網(wǎng)絡(luò)最終收斂于局部極小解，甚至可能收斂到問題的不可行解。此外，網(wǎng)絡(luò)最優(yōu)的最終結(jié)果很大程度依賴于網(wǎng)絡(luò)的參數(shù)，即參數(shù)魯棒性較差。（4）遺傳算法。遺傳算法是進(jìn)行局部搜索改進(jìn)的一類算法。遺傳算法求解VRP問題時，主要利用生物進(jìn)化世代性與最優(yōu)路線搜索迭代性間的共性，在全局范圍內(nèi)搜索配送路線的最優(yōu)解。如遇同一級配送節(jié)點(diǎn)分支的相同耗費(fèi)情況，則均予以考慮，分別參與下一步驟迭代，并由后續(xù)步驟逐漸淘汰，最終確定最優(yōu)配送路線；如遇同一級配送節(jié)點(diǎn)分支的不同耗費(fèi)情況，則適者幸存0，由耗費(fèi)少的配送分支獲得繼續(xù)迭代的權(quán)利，但并不能確定其最優(yōu)

54、資格，必須參與后續(xù)淘汰步驟，直至迭代結(jié)束，得到最優(yōu)配送路線。遺傳算法具有良好的魯棒性、靈活性、通用性，特別適合于大規(guī)模VRP 問題的求解。但由于算法本身還存在的一些缺陷，如易出現(xiàn)早熟收斂，局部搜索能力差，因此，不能保證最大概率收斂到全局最優(yōu)解。（5）蟻群算法。蟻群算法基本原理是模擬蟻群搜索食物的行為: 螞蟻群找到食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r，會在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個還沒有走過的路口時，就隨機(jī)地挑選一條路徑前行，并釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激素濃度越低。當(dāng)后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高

55、路徑概率就會相對較大。這樣就形成了一個正反饋，最優(yōu)路徑上的激素濃度越來越大，而其他的路徑上激素濃度卻會隨著時間的流逝而消減，最終整個蟻群會找出最優(yōu)路徑。該算法在求解VRP問題方面有良好效果，但存在如計(jì)算時間較長、容易陷入局部最優(yōu)等問題。（6）微粒群算法。PSO算法是通過模擬鳥群的捕食行為來達(dá)到優(yōu)化問題的求解。首先在解空間內(nèi)隨機(jī)初始化鳥群，鳥群中的每一只鳥稱為粒子0，這些粒子0在解空間內(nèi)以某種規(guī)律移動，經(jīng)過若干次迭代后找到最優(yōu)解。在每一次迭代中，粒子通過15跟蹤2個/極值0來更新自己。第一個是粒子本身的最優(yōu)解(Pbest0)；另一個極值是整個微粒群目前找到的最優(yōu)解(Obest0)。找到這2個極值

56、后，每個粒子根據(jù)自己的飛行速度，決定自身的走向及飛行距離。用PSO算法求解VRP問題具有收斂速度快、依賴的經(jīng)驗(yàn)參數(shù)少、簡便易行等特點(diǎn)。但與其他進(jìn)化類優(yōu)化算法一樣，存在易于陷入局部最優(yōu)的缺陷。從上述分析可知，求解VRP問題的方法有很多，但各種方法在一定時期、一定情況下都有各自的優(yōu)點(diǎn)，都具有解決某一類問題的優(yōu)越性。164 節(jié)約算法的理論基礎(chǔ)及算法設(shè)計(jì)由于本文主要研究的是基于節(jié)約算法的路徑優(yōu)化問題，所以本章詳細(xì)介紹下節(jié)約算法。4.1 CW節(jié)約算法提出CW節(jié)約算法是一類最為經(jīng)典的構(gòu)造型啟發(fā)式算法之一，1964年，Clark和Wright最早提出該算法，并被簡稱為CW節(jié)約算法。該算法的思想是：根據(jù)顧客點(diǎn)

57、之間的最短距離、最小成本或運(yùn)輸路程所用最小時間（即最大節(jié)約量）為原則，將路線外的客戶點(diǎn)依次插入到線路中，直到所有的點(diǎn)都被安排進(jìn)路線為止。4.2 CW節(jié)約算法原理及特點(diǎn)4.2.1 CW節(jié)約算法的基本原理假如由一家配送中心()向兩個用戶，送貨，配送中心到兩客戶的最短距0P1P2P離分別是和，和間的最短距離為，的貨物需求量分別是和01C02C1P2P12C1P2PaQ，且(+)小于運(yùn)輸裝載量，如圖 1 所示，如果配送中心分別送貨，那么需要bQaQbQQ兩個車次，總路程為: 10102=2SCC如果改用一輛車對兩客戶進(jìn)行巡回送貨，則只需一個車次，行走的總路程為: 2010212SCCC有三角形的性質(zhì)我

58、們知道:120102CCC所以第二次配送方案明顯優(yōu)于第一種，且行走總路程節(jié)約:010212SCCC1P2P01C02C0P0P1P2P01C02C+圖 4.1 節(jié)約里程法的基本原理17如果配送中心的供貨范圍內(nèi)還存在著 3 ，4 ，5 ，n 個用戶，在運(yùn)載車輛載重和體積都允許的情況下，可將它們按著節(jié)約路程的大小依次聯(lián)入巡回路線，直至滿載為止，余下的用戶同樣方法確定巡回路線，另外派車。4.2.2 CW 節(jié)約算法對車輛進(jìn)行優(yōu)化調(diào)度的步驟基于節(jié)約里程法的基本思路，在配送網(wǎng)絡(luò)中尋找這樣的三角形的回路：盡可能裝載多的貨物，且節(jié)約盡可能多的行駛里程。具體的步驟如下：（1） 形成初始解。初始解滿足顧客的需求，

59、而且所有的約束條件，如車輛載重量的限制、車輛總數(shù)的限制等也能得到滿足?；镜某跏冀鉃橹彼褪脚渌?， 即不考慮線路合并的一對一的配送模式，配送中心對每個客戶的送貨點(diǎn)均指派一輛車或多輛車完成配送。（2） 進(jìn)行節(jié)約度的計(jì)算。即計(jì)算出左圖中的，即兩個客戶之間010212SCCC的歷程節(jié)約度為這兩個客戶節(jié)點(diǎn)分別到配送中心的里程之和減去客戶節(jié)點(diǎn)之間的距離。（3） 對節(jié)約度從大到小進(jìn)行降序排列。（4） 進(jìn)行回路的合并。從節(jié)約度排序表找出產(chǎn)生該節(jié)約度的兩個客戶節(jié)點(diǎn) 、，并ij判斷連接 、的回路是否存在合并的可能性。如果一個回路以（，）開始，ijpj一個回路以( ， )結(jié)束，則該回路可以合并，并進(jìn)行下面的合并操作

60、：刪除ip兩個回路中的部分路徑（，）和（ ，），然后引入新的連接( ，)，pjipij得到新的回路（， ，）。pijp4.2.3 CW 節(jié)約算法的特點(diǎn)CW 節(jié)約算法是一種啟發(fā)式算法，屬于構(gòu)造式啟發(fā)式算法，與智能啟發(fā)式算法有區(qū)別，它屬于逐次逼近法的一種，該算法在求小規(guī)模運(yùn)輸配送路線，優(yōu)化車輛調(diào)度問題方面有自身的優(yōu)勢，該算法具有技術(shù)步驟簡單，易懂，計(jì)算速度快，并且易于考慮各種實(shí)際問題的優(yōu)點(diǎn)。4.3 節(jié)約算法設(shè)計(jì)4.3.1 模型的數(shù)學(xué)描述由于海王星辰的藥品配送屬于藥品零售的范疇，其突發(fā)性狀況比較小，對于時間的要求也比較小，所以配送過程只要避開城市的早晚高峰即可。本文為保證藥品能夠及時滿足各門店每日銷