物流配送路徑優(yōu)化策略物流配送路徑存在的問題路徑分析物流配送路徑現(xiàn)狀分析配送路徑優(yōu)化問題的分類

1、高效率合理的配送是物流系統(tǒng)順利運(yùn)行的保證，配送線路安排的合理與否對(duì)配送速度、成本、效益影響很大。所以正確合理地安排車輛的配送線路，實(shí)現(xiàn)合理的線路運(yùn)輸可以使企業(yè)達(dá)到科學(xué)化的物流管理，這也是企業(yè)提高自身競(jìng)爭(zhēng)力的有效途徑之一。本文以帝峰模具有限公司的配送方案為例，對(duì)其配送現(xiàn)狀中存在的問題進(jìn)行分析，并運(yùn)用節(jié)約算法、掃描算法以及改進(jìn)后的最近插入法對(duì)配送線路進(jìn)行優(yōu)化，提出物流配送線路優(yōu)化的方案，并且得到了相對(duì)滿意的結(jié)果。優(yōu)化后的配送線路有效提高了帝峰模具有限公司的作業(yè)效率，降低物流成本，從而提升企業(yè)的經(jīng)濟(jì)效益，并讓公司能夠在激烈的競(jìng)爭(zhēng)市場(chǎng)立足，同時(shí)，也可以給同類企業(yè)提供參考。關(guān)鍵詞:帝峰模具配送路徑優(yōu)化最

2、近插入法掃描法節(jié)約算法AbstractReasonableandefficientdistributionistheinsuranceofasmoothrunninglogisticssystem,distributionlinearrangementisreasonableornothasagreatinfluenceonthespeedofdelivery,costsandbenefits.Therefore,toarrangeareasonableandcorrectdeliverylineforvehicleandachieveareasonabletransportlinecanen

3、ableenterprisestoachievescientificlogisticsmanagement,whichisoneoftheeffectivewayforanenterprisetoimproveitscompetitiveness.ThispapertakeDifengMoldCo,Ltd.distributionasanexampletoanalysisoftheproblemsexistinginthestatusofitsdistribution,throughthesavingalgorithm,theimprovedinsertmethodandscanningmet

4、hodofthesethreemethodsareoptimizedfordistributionlines,logisticsdistributionrouteoptimizationschemeisputforward,andarelativelysatisfactoryresultsareobtained.Optimizeddistributionlineseffectivelyimprovethegravelslogisticscompany'sefficiency,reducelogisticscosts,therebyimproveenterpriseeconomicben

5、efits,andgravelscaninthefiercemarketcompetition,atthesametime,alsocanprovideareferenceforsimilarenterprises.KeywordsDifengMoldCo,LtdDistributionrouteoptimizationscanningmethodtheimprovedinsertmethodthesavingalgorithm目錄TOCo"1-3"hzu第1章緒論1.1 研究背景61.2 國(guó)內(nèi)外研究現(xiàn)狀71.2.1 國(guó)外研究現(xiàn)狀71.2.2 國(guó)內(nèi)研究現(xiàn)狀91.3 研究目的

6、、意義和方法111.3.1 研究目的111.3.2 研究意義111.3.3 研究方法121.4 本文研究?jī)?nèi)容12第2章相關(guān)理論概述2.1 物流配送142.1.1 物流配送的概念142.1.2 物流配送的功能142.1.3 物流配送的要素152.2 配送路徑優(yōu)化問題162.2.1 配送路徑優(yōu)化的目標(biāo)162.2.2 配送路徑優(yōu)化問題的分類182.2.3 配送路徑優(yōu)化問題的解法分類192.3 本文配送路徑優(yōu)化方法202.3.1 建立VRP模型202.3.2 最近插入法212.3.3 掃描法222.3.4 節(jié)約算法23節(jié)約里程算法主要步驟：24第3章帝峰模具公司物流配送路徑現(xiàn)狀分析3.1 公司簡(jiǎn)介25

7、3.2 公司物流配送路徑現(xiàn)狀253.3 公司物流配送路徑存在的問題路徑分析283.3.1 路徑迂回283.3.2 對(duì)流運(yùn)輸293.3.3 經(jīng)驗(yàn)化操作過多30第4章帝峰模具公司物流配送路徑優(yōu)化策略4.1 建立VRP模型優(yōu)化配送路徑314.2 公司物流配送路徑的優(yōu)化314.3.1運(yùn)用最近插入法優(yōu)化314.3.2運(yùn)用掃描法法優(yōu)化354.2.3運(yùn)用節(jié)約算法優(yōu)化394.4三種優(yōu)化方案比較分析44結(jié)論致謝參考文獻(xiàn)第1章緒論1.1 研究背景物流是為了滿足消費(fèi)者需要而進(jìn)行的從供應(yīng)地到接收地的原材料、中間產(chǎn)品、最終產(chǎn)品及相關(guān)信息的有效流動(dòng)和儲(chǔ)存計(jì)劃、實(shí)施和控制的管理過程。其功能是通過運(yùn)輸、倉(cāng)儲(chǔ)、裝卸搬運(yùn)、包裝、

8、流通加工、配送、信息處理等活動(dòng)過程有機(jī)結(jié)合起來(lái)實(shí)現(xiàn)的。其中配送對(duì)于物流的運(yùn)行和發(fā)展有著深刻的社會(huì)根源和歷史背景。在市場(chǎng)經(jīng)濟(jì)體系中，物流配送猶如人體的血管，把國(guó)民經(jīng)濟(jì)各個(gè)部分緊密地聯(lián)系在一起。物流配送是物流的基本功能，作為直接面向最終客戶提供的物流服務(wù)，在滿足現(xiàn)代化的物流需求方面發(fā)揮著極其重要的作用。如果沒有配送就會(huì)影響物流的經(jīng)濟(jì)效益和社會(huì)效益,可以說物流成果主要是通過配送來(lái)實(shí)現(xiàn)的。著名管理大師彼得德魯克說“美國(guó)人花費(fèi)的每美元中，大概有美分是花在產(chǎn)品制成以后的活動(dòng)上，即在產(chǎn)品己經(jīng)完工的以后從經(jīng)濟(jì)學(xué)角度看，配送是將事物的物質(zhì)特性轉(zhuǎn)換成經(jīng)濟(jì)價(jià)值的過程，它為產(chǎn)品帶來(lái)了客戶?！庇煽梢娕渌突顒?dòng)及配送管理的

9、重要性。物流配送一般處于物流末，是直接面向用戶提供服務(wù)的環(huán)節(jié)，它具有提高物流經(jīng)濟(jì)效益，優(yōu)化、完善物流系統(tǒng)，改善物流服務(wù)，降低物流成本等功能，在物流系統(tǒng)中占有重要的地位。隨著市場(chǎng)經(jīng)濟(jì)的繁榮，企業(yè)業(yè)務(wù)規(guī)模日益擴(kuò)大，物流配送作為現(xiàn)在現(xiàn)代企業(yè)一個(gè)重要環(huán)節(jié)，其效率高低直接影響企業(yè)的服務(wù)質(zhì)量、配送成本，而配送路徑優(yōu)是物流配送的核心問題，因此物流配送路徑優(yōu)化問題是成為當(dāng)前物流研究中的一個(gè)重要課題，所以它是一項(xiàng)特殊的、綜合性的物流運(yùn)動(dòng)，其主要包括集貨作業(yè)、配貨作業(yè)、車載貨物的配裝、配送線路的確定1配送實(shí)際上是一個(gè)局部物流，是大物流在小范圍內(nèi)的運(yùn)作，配送是物流系統(tǒng)的終端。是否具備及時(shí)的配送時(shí)間影響服務(wù)水平的高低

10、，這需要對(duì)車輛配送路徑的合理優(yōu)化和配送時(shí)間的掌控?，F(xiàn)代物流己成為世界經(jīng)濟(jì)發(fā)展的研究重點(diǎn)，我國(guó)政府也對(duì)物流產(chǎn)業(yè)的發(fā)展和監(jiān)管非常重視。但是目前，由于我國(guó)的物流產(chǎn)業(yè)起步晚，尚存在著許多問題。如何改變這種局面，使物流行業(yè)健康穩(wěn)步發(fā)展，是國(guó)民生產(chǎn)力發(fā)展急需解決的難題，當(dāng)前主要可從提高物流配送服務(wù)質(zhì)量入手。在現(xiàn)代物流系統(tǒng)中，配送是一個(gè)重要環(huán)節(jié)，而在配送業(yè)務(wù)中，能否將貨物及時(shí)送交收貨人手中是物流系統(tǒng)優(yōu)化的關(guān)，配送的質(zhì)量好壞決定服務(wù)水平的高低，同時(shí)影響到客戶對(duì)整個(gè)物流服務(wù)的滿意程度。然而物流車輛在配送過程中，會(huì)涉及到車輛路徑優(yōu)化問題。由此說明，物流車輛路徑優(yōu)化問題是物流運(yùn)作管理面臨的重點(diǎn)問題，在交通和物流規(guī)劃

11、中具有舉足輕重的地位。武漢帝峰模具是一家集設(shè)計(jì)、生產(chǎn)、銷售、配送于一體的經(jīng)營(yíng)五金模具和塑膠模具的有限責(zé)任公司。作為一家以生產(chǎn)為主的企業(yè)，其在配送運(yùn)輸方面存在一定的不足之處，配送工作效率較低，配送成本較高。從車輛路徑優(yōu)化方面考慮配送優(yōu)化，對(duì)運(yùn)輸路線進(jìn)行合理規(guī)劃，尋找一條符合實(shí)際情況的優(yōu)化路徑，這樣才能從實(shí)際上節(jié)省配送費(fèi)用，緩解交通的壓力，使配送工作順利進(jìn)行，從而節(jié)省配送過程中運(yùn)輸費(fèi)用耗費(fèi)，而且使配送服務(wù)水平提高，并提高用戶的滿意度，以致提高工作效率，減少運(yùn)營(yíng)成本。1.2 國(guó)內(nèi)外研究現(xiàn)狀1.2.1 國(guó)外研究現(xiàn)狀很多國(guó)外學(xué)者對(duì)倉(cāng)儲(chǔ)貨位優(yōu)化的問題進(jìn)行了研究，比如以下幾位：Clarke和Wright(1

12、964)對(duì)Dantzig和Ramser提出VRP問題模型的求解算法進(jìn)行了改進(jìn)，提出了更為有效的啟發(fā)式算法Clarke-Wright節(jié)約法，后來(lái)該算法成功的用于求解車輛路徑優(yōu)化問題2；Miller&Gillet(1974)提出掃描法(SweepMethod),目的在于求解車輛調(diào)度問題，并針對(duì)當(dāng)時(shí)幾個(gè)求解相似問題的算法進(jìn)行比較，證明該算法所求得的解較優(yōu)于其它的方法3；wialldr(1989)首先將禁忌搜尋法應(yīng)用于車輛路線問題上，設(shè)計(jì)重復(fù)的虛擬物流中心，將車輛路線問題轉(zhuǎn)換成旅行商問題(TSP),利用2-opt或3-opt方法求解車輛路線；Dorigo,Maniezzo和Colorni(19

13、91)等意大利人將蟻群算法用于求解旅行商問題，并取得了很好的效果，后來(lái)，Dorigo在基本蟻群系統(tǒng)的模型的基礎(chǔ)上又提出螞蟻群系統(tǒng)(AntColonySystem,ACS)模型，該模型改進(jìn)了螞蟻系統(tǒng)模型的信息素更新方法和路徑選擇方式，并使用了一種隨機(jī)選擇和最優(yōu)選擇混合的路徑選擇方式，而信息素更新采用全局更新和局部更新的方式，提高了算法的全局收斂能力，相比于螞蟻系統(tǒng)模型的性能有較大的提高，收斂速度明顯加快。后來(lái)很多學(xué)者對(duì)基本的蟻群算法進(jìn)行改進(jìn)，求解不同的問題模型；Gendreau,HertZandL即orte(1994)使用插入法求解旅行商問題，再用貪婪法(GreedyMethod)進(jìn)行路線切割，

14、從而產(chǎn)生初始解；Kennedy和Eberhart(1995)等美國(guó)博士，提出了粒子群算法，Eberhart博士等人對(duì)基本粒子群算法進(jìn)行了改進(jìn)，該算法被成功的用于求解物流路徑規(guī)劃問題；Renaud(1995)等意大利博洛尼亞大學(xué)的博士對(duì)多配送中心的車輛路徑規(guī)劃問題(MultipleDepotVehicleRoutingProblem,MDVRP)進(jìn)行了研究，MDVRP比一般的VRP問題模型更為復(fù)雜，配送車輛的參考點(diǎn)有多個(gè)配送中心，每個(gè)配送中心都有車輛參與網(wǎng)點(diǎn)的配送任務(wù)，這樣路徑規(guī)劃問題非常復(fù)雜，但多配送中心的車輛路徑規(guī)劃問題是目前物流業(yè)迅速發(fā)展的一種趨勢(shì)。美國(guó)的G.B.Dantzig在1947年

15、提出線性規(guī)劃、美國(guó)的B.Jackowski等人1985年提出隱式枚舉算法、以及美國(guó)的J.Culberson在1992年提出了迭代的貪心算法后來(lái)都成功的被用來(lái)求解小規(guī)模數(shù)據(jù)網(wǎng)點(diǎn)的物流路徑規(guī)劃問題，這是一類精確式算法，在求解小規(guī)模網(wǎng)點(diǎn)的物流路徑規(guī)劃問題具有計(jì)算速度快、求解精確的特點(diǎn)4;Babraroosglu&Ogzur(1999)利用禁忌搜尋法為土耳其某物流公司構(gòu)建一套決定貨車配送點(diǎn)順序的方法DETABA,以二種亂數(shù)選取節(jié)點(diǎn)的方法產(chǎn)生初始解，找到其中最佳的解作為初始解，再以插入法(InsertinoProcdeuer)作為搜尋鄰近解的移步方法，最后以2一opt改善方法找到最優(yōu)解的值；su

16、&chen(1999)成功地將自組織影射網(wǎng)絡(luò)應(yīng)用在車輛配送區(qū)域及路線規(guī)劃問題的求解上，其算法的主要概念是利用類神經(jīng)網(wǎng)絡(luò)快速運(yùn)算、自我組織與平行處理的特性，配合M個(gè)一維環(huán)狀網(wǎng)絡(luò)拓?fù)鋪?lái)表現(xiàn)車輛路線配送問題；T.Ralphs(2003)等美國(guó)利哈伊大學(xué)的研究者對(duì)CVRP問題模型進(jìn)行了研究，CVRP是相對(duì)VRP問題提出的，表示參與配送任務(wù)的每一輛車都有自身的約束條件，如載重量、最大行駛里程等等，在滿足這些約束條件的前提下，完成所有網(wǎng)點(diǎn)訂單任務(wù)的配送，目標(biāo)是總成本最少的路徑規(guī)劃問題，后來(lái)有很多研究者在CVRP問題模型的基礎(chǔ)上提出了帶有時(shí)間窗約束的CVRP問題模型，本文的研究的物流路徑規(guī)劃問題帶有

17、多個(gè)時(shí)間窗約束5。在這些論文相繼發(fā)表之后由于該問題無(wú)論在理論上還是應(yīng)用上都具有代表性，它是典型的物流配送優(yōu)化問題，引起更多學(xué)者對(duì)許多相關(guān)學(xué)科的研究，導(dǎo)致該問題變成運(yùn)籌學(xué)研究的焦點(diǎn)。1.2.2國(guó)內(nèi)研究現(xiàn)狀通過查閱相關(guān)文獻(xiàn)資料了解到目前國(guó)內(nèi)學(xué)者在企業(yè)的物流路徑優(yōu)化問題的研究起步較晚，有些學(xué)者在研究這方面課題時(shí)也提出過一些有建設(shè)性的思路6:楊寶石（2013）把城市快遞配送路徑問題看作是簡(jiǎn)單的旅行商問題（TravelSalesmanProblem,TSP）,針對(duì)該問題模型除了考慮了一般性的約束之外，僅僅只額外考慮了容量約束。當(dāng)問題規(guī)模不大時(shí)，可以得到全局最優(yōu)解。丁潔（2012）則將城市快遞配送路徑問題

18、轉(zhuǎn)化為多重旅行商問題（MultiTravelSalesmanProblem,MTSP）,同時(shí)考慮到MTSP問題求解難度較大，故先將其轉(zhuǎn)化為TSP問題，接著結(jié)合最小生成樹的深度優(yōu)先搜索算法來(lái)確定快遞員最終的行車路線，以求得到該問題的近似最優(yōu)解；何俊生（2013）針對(duì)同城快遞配送路徑問題，提出了兩個(gè)模型，一個(gè)不考慮時(shí)間窗約束僅考慮容量約束，另一個(gè)同時(shí)考慮，采用Dijkstra遺傳優(yōu)化算法求解并進(jìn)行了比較對(duì)比分析。姜艷和關(guān)雪（2008）提出了一個(gè)線性混合整數(shù)規(guī)劃模型，該模型主要考慮時(shí)間窗約束和單車快件數(shù)目上限約束；楊從平（2014）針對(duì)快遞物流配送車輛路徑問題，考慮了容量約束和單車最大行程距離約束，

19、采用蟻群算法對(duì)桂林市某快遞網(wǎng)絡(luò)的配送路徑進(jìn)行了優(yōu)化。李炳會(huì)（2008）則用超時(shí)懲罰對(duì)時(shí)間約束進(jìn)行了替代，即快遞超過預(yù)定時(shí)間需要賠償以進(jìn)行懲罰；張迅和劉海東（2013）根據(jù)快遞配送的特點(diǎn)，研究了采用快件遞送和攬收同時(shí)服務(wù)的配送策略的車輛路徑問題。他們假設(shè)車輛在配送中心與客戶點(diǎn)之間或客戶點(diǎn)之間行駛的時(shí)間服從正態(tài)分布，各客戶點(diǎn)均帶有有軟時(shí)間窗約束，以及快件攬收數(shù)量服從泊松分布，依此建立一個(gè)線性混合整數(shù)規(guī)劃的多目標(biāo)模型，目標(biāo)函數(shù)包括：行駛路程最短，時(shí)間懲罰值最小和快件攬收數(shù)量最大。同時(shí)他們提出了一種遺傳算法：該遺傳算法采取種群個(gè)體適應(yīng)度值排序和最佳個(gè)體保留的選擇策略，以及通過參數(shù)控制自適應(yīng)交叉概率來(lái)保

20、證所求結(jié)果的優(yōu)良性，通過設(shè)計(jì)算例并采用Matlab軟件進(jìn)行編程運(yùn)算，實(shí)驗(yàn)結(jié)果證明了該遺傳算法的可行性；陳敏（2009）研究了如何快速響應(yīng)動(dòng)態(tài)信息的車輛調(diào)度問題，并將其描述成是一個(gè)實(shí)時(shí)帶時(shí)間窗車輛路徑問題（Real-timeVehicleRoutingProblemwithTimeWindows,RT-VRPTW）。針對(duì)實(shí)際調(diào)度問題的規(guī)模、復(fù)雜度和特性，將動(dòng)態(tài)問題轉(zhuǎn)化成靜態(tài)問題，提出了一種混合禁忌搜索算法，該算法分為兩個(gè)階段：第一階段，首先采用插入法生成初始方案；第二階段，引入改進(jìn)的禁忌啟發(fā)式搜索算法對(duì)全局進(jìn)行優(yōu)化，實(shí)驗(yàn)結(jié)果表明該算法行之有效；胡明偉和唐浩（2010）則研究了快遞服務(wù)相關(guān)的動(dòng)態(tài)車

21、輛路徑問題，并將其描述成帶時(shí)間窗的動(dòng)態(tài)旅行修理員問題（DynamicTravelingRepairmanProblemwithTimeWindows,DTRPTW),建立多目標(biāo)優(yōu)化模型，該模型包括服務(wù)客戶數(shù)量最大、客戶等待時(shí)間最小以及總運(yùn)行時(shí)間最短三重優(yōu)化目標(biāo)。他們采用基于詞典式的排序方法，同時(shí)改進(jìn)了Or-opt局部搜索算法。根據(jù)仿真實(shí)驗(yàn)結(jié)果顯示，與單目標(biāo)模型相比，多目標(biāo)優(yōu)化模型能夠明顯降低被拒絕服務(wù)的客戶數(shù)量和客戶等待時(shí)間，同時(shí)總運(yùn)營(yíng)時(shí)間未發(fā)生明顯增長(zhǎng)；吳海東(2011)針對(duì)城市快遞服務(wù)問題，重點(diǎn)研究了服務(wù)質(zhì)量相似性和快遞車輛交接行為這兩大新的快遞服務(wù)趨勢(shì)，同時(shí)建立兩階段模型，在滿足隨機(jī)客戶

22、需求的條件下，還能夠保證快遞配送的路徑得到最優(yōu)。目前國(guó)內(nèi)對(duì)VRP問題的研究很多都停留在理論研究階段，實(shí)驗(yàn)成果并沒用廣泛的進(jìn)行實(shí)際應(yīng)用，而且研究的問題模型都有一定的條件約束，約束條件不同，則對(duì)應(yīng)的問題模型也不一樣，求解的算法也不太一樣，這樣算法就有一定的局限性。1.3研究目的、意義和方法1.3.1 研究目的為了提高物流配送系統(tǒng)的服務(wù)質(zhì)量和節(jié)省配送費(fèi)用，對(duì)物流車輛配送路徑的優(yōu)化和行程時(shí)間的預(yù)測(cè)所進(jìn)行的研究，本文通過制定較為合理化、人性化的物流車輛配送路徑，滿足實(shí)際的物流配送要求，從而能將貨物迅速、安全地送到客戶手中，達(dá)到提高服務(wù)水平的要求；與此同時(shí)，加快物流系統(tǒng)對(duì)客戶需求的物流配送路徑優(yōu)化和行程時(shí)

23、間預(yù)測(cè)響應(yīng)速度，提高服務(wù)質(zhì)量，增強(qiáng)客戶對(duì)物流環(huán)節(jié)的滿意度，降低服務(wù)商的運(yùn)作成本使整體的服務(wù)水平提高7。1.3.2 研究意義第一，本文結(jié)合實(shí)際的配送情況，對(duì)配送車輛路徑優(yōu)化理論與方法進(jìn)行系統(tǒng)研究是物流集約化發(fā)展、建立現(xiàn)代調(diào)度指揮系統(tǒng)、發(fā)展智能交通運(yùn)輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)。同時(shí)，優(yōu)化后的物流配送路徑，有利于緩解交通壓力；第二，規(guī)劃好物流配送的行進(jìn)路線，有利于節(jié)省配送費(fèi)用，而對(duì)行程時(shí)問精確的預(yù)測(cè)反過來(lái)有利于指導(dǎo)物流規(guī)劃的行進(jìn)路線，引導(dǎo)車輛沿途配送物資；第三，物流配送路徑優(yōu)化，是物流配送優(yōu)化中關(guān)鍵的一環(huán)。對(duì)貨運(yùn)車輛進(jìn)行路徑優(yōu)化，可以提高物流經(jīng)濟(jì)效益、社會(huì)效益、實(shí)現(xiàn)物流科學(xué)化8;第四，優(yōu)化配送路徑問

24、題對(duì)提高物流企業(yè)配送效率，降低物流配送成本，促進(jìn)經(jīng)濟(jì)的快速發(fā)展都具有重要的作用，從而對(duì)物流配送路徑規(guī)劃的研究具有非常高的應(yīng)用價(jià)值。1.3.3 研究方法(1)文獻(xiàn)參考：本文主要是通過對(duì)互聯(lián)網(wǎng)上的相關(guān)文獻(xiàn)、資料以及圖書進(jìn)行詳細(xì)的閱讀和思考，并參考其中相關(guān)有用的文字以及解決問題的思路及方法。(2)實(shí)地考察：在武漢帝峰模具有限公司實(shí)習(xí)期間，將搜集的資料進(jìn)行大致的提煉，對(duì)于物流配送路徑的各項(xiàng)考慮因素進(jìn)行主次分類，并帶著這些疑問在公司實(shí)習(xí)之余對(duì)配送路徑方案進(jìn)行大致的理解與總結(jié)。(3)定量分析法：依據(jù)近三個(gè)月物流單據(jù)結(jié)合運(yùn)籌學(xué)相關(guān)知識(shí)，運(yùn)用節(jié)約算法、掃描法和改進(jìn)的最近插入法進(jìn)行必要的分析與運(yùn)算，并比較三種方

25、法的結(jié)果以得到較優(yōu)路徑的設(shè)計(jì)方案。1.4本文研究?jī)?nèi)容本文以武漢帝峰模具有限公司為例，在對(duì)物流配送業(yè)務(wù)進(jìn)行研究的基礎(chǔ)上，針對(duì)物流配送中對(duì)成本影響較大的車輛路徑問題(VRP)進(jìn)行集中研究，在車輛載重限制、時(shí)間限制、客戶需求量限制和指定地點(diǎn)的條件下建立了VRP數(shù)學(xué)模型，并利用啟發(fā)式算法中的三種方法優(yōu)化配送路徑，并選出較優(yōu)方案9。本文的研究?jī)?nèi)容如下：第一章闡述本文的研究背景，國(guó)內(nèi)外研究現(xiàn)狀，研究意義、目的和方法；第二章對(duì)物流配送和配送路徑優(yōu)化問題進(jìn)行了相關(guān)理論的概述，并介紹了節(jié)約算法、掃描法和最近插入法的原理及步驟；第三章主要介紹了本人實(shí)習(xí)所在公司，描述了其在物流配送路徑方面的現(xiàn)狀以及存在的問題；第四

26、章是本文的重點(diǎn)部分，首先介紹了關(guān)于改進(jìn)公司配送路徑的基本思路，其次運(yùn)用節(jié)約算法、掃描法以及改進(jìn)的最近插入法優(yōu)化配送路徑，然后比較三者得出的結(jié)論并選出較優(yōu)方案。PAGE45第2章相關(guān)理論概述2.1 物流配送2.1.1 物流配送的概念物流的含義是：依照客戶的訂單要求，在物流中心組織分貨、配貨，然后把分配完畢的物品以合適的數(shù)量在規(guī)定的時(shí)間內(nèi)，以現(xiàn)代化的運(yùn)送形式，運(yùn)送到客戶手中，以實(shí)現(xiàn)資源的優(yōu)化配置。配送(distribution)起源于“送貨上門”。20世紀(jì)60年代初期，生產(chǎn)企業(yè)或中轉(zhuǎn)倉(cāng)庫(kù)根據(jù)客戶的需求，將貨物準(zhǔn)確的運(yùn)送到客戶手中，形成了配送的雛形一一“普通送貨。隨著客戶對(duì)產(chǎn)品多樣化和差異化的要求，

27、為了滿足客戶的需求，原始的普通送貨開始轉(zhuǎn)向分揀、配貨、送貨一體化。因此產(chǎn)生了配送。按照國(guó)家質(zhì)量技術(shù)監(jiān)督局發(fā)布的中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)“物流術(shù)語(yǔ)”(GB/T18354-2001),配送是指在經(jīng)濟(jì)合理區(qū)域范圍內(nèi)根據(jù)用戶要求，對(duì)物品進(jìn)行揀選、加工、包裝、分割、組配等作業(yè)，并按時(shí)送達(dá)指定地點(diǎn)的物流活動(dòng)。我們可以將物流配送抽象的理解為一種共同化的服務(wù)模式，共同化可涵蓋以下幾個(gè)方面：各類資源共同使用；設(shè)施共同采用；管理過程的共同進(jìn)行。具體來(lái)說，物流配送是物流活動(dòng)的一種獨(dú)特的業(yè)務(wù)形態(tài)，其獨(dú)特之處在于它不是單獨(dú)存在的，而是與資金流、物流、信息流進(jìn)行了有機(jī)結(jié)合，這些資源的流動(dòng)均存在于物流配送的整個(gè)過程中，可以毫

28、不夸張的說，物流配送可以包含物流活動(dòng)的必要因素。從表面上看，配送是從運(yùn)輸衍生而來(lái)的功能，實(shí)際上，物流配送基本能夠涵蓋物流的所有職能，是一個(gè)完整的過程。物流配送在很大程度上容易被外部環(huán)境所影響，隨機(jī)性很強(qiáng)，因此，需要建立起完整的管理與控制，并需要強(qiáng)有力的理論與技術(shù)支持。2.1.2 物流配送的功能(1)配送完善和優(yōu)化了物流系統(tǒng)。第二次世界大戰(zhàn)后，高水平的干線運(yùn)輸呼喚支線運(yùn)輸和小搬運(yùn)配套，但支線運(yùn)輸和小搬運(yùn)在適應(yīng)性、靈活性、服務(wù)性上的欠缺，致使運(yùn)力不合理、運(yùn)輸成本過高，配送的出現(xiàn)使干線運(yùn)輸、支線運(yùn)輸及小搬運(yùn)統(tǒng)一，輸送過程得以優(yōu)化和完善。(2)配送提高了末端物流的效益。配送通過大批量進(jìn)貨，集中發(fā)貨，以

29、及將多個(gè)小批量集中一起大批量發(fā)貨，都能有效的節(jié)省運(yùn)力，實(shí)現(xiàn)經(jīng)濟(jì)運(yùn)輸，降低成本，使末端的物流經(jīng)濟(jì)效益得到提高。(3)配送通過集中庫(kù)存使企業(yè)實(shí)現(xiàn)低庫(kù)存或零庫(kù)存。采取準(zhǔn)時(shí)制配送方式之后，生產(chǎn)企業(yè)完全可以依靠配送中心的準(zhǔn)時(shí)配送而不需保持自己的庫(kù)存或保持少量安全庫(kù)存而不必留有經(jīng)常庫(kù)存。(4)配送簡(jiǎn)化事物，方便客服。采用配送的方式，客戶只需向一處訂購(gòu)，或一個(gè)進(jìn)貨單位聯(lián)系就可以訂購(gòu)到以往需要去許多地方才能頂?shù)降呢浳铮虼舜蟠蟮臏p輕了客戶的工作量和負(fù)擔(dān)，也節(jié)省了事務(wù)的開支。(5)配送可以降低整個(gè)社會(huì)物資的庫(kù)存水平。發(fā)展配送，實(shí)行集中庫(kù)存，整個(gè)社會(huì)物資的庫(kù)存總量必然低于各企業(yè)分散的庫(kù)存總量。同時(shí)，配送有利于靈活

30、高度，有利于發(fā)揮物資的作用。止匕外，集中庫(kù)存可以發(fā)揮規(guī)模經(jīng)濟(jì)優(yōu)勢(shì)，降低庫(kù)存成本10。2.1.3物流配送的要素(1)備貨。該環(huán)節(jié)是配送工作的最基礎(chǔ)環(huán)節(jié)，主要包括以下幾項(xiàng)任務(wù)：尋貨源；購(gòu)貨物；貨物統(tǒng)計(jì)匯總；日常質(zhì)量檢驗(yàn)；會(huì)計(jì)核算；日常交接工作等。物流企業(yè)應(yīng)該定期對(duì)客戶需求進(jìn)行預(yù)測(cè)，并進(jìn)行定量的貨物儲(chǔ)備，以備不時(shí)之需。備貨環(huán)節(jié)是配送的起始環(huán)節(jié)，在一定程度上影響了整個(gè)配送的成敗，因此，在這個(gè)環(huán)節(jié)，應(yīng)該努力降低成本，提高配送效益。(2)存儲(chǔ)。可以分為儲(chǔ)備與暫存這兩種主要形態(tài)。儲(chǔ)備的含義是根據(jù)某一時(shí)期制定的配送經(jīng)營(yíng)目標(biāo)及要求，建立起的資源保障以保障配送目標(biāo)得以實(shí)現(xiàn)。一般情況下，該種情況下的儲(chǔ)備數(shù)量很大，并

31、且結(jié)構(gòu)也相對(duì)較為完善，根據(jù)貨源多少及到貨量，有計(jì)劃的制定儲(chǔ)備方案。暫存的含義是在配送當(dāng)天，依照分揀配貨的具體要求，在理貨場(chǎng)所進(jìn)行的少量應(yīng)急準(zhǔn)備。(3)分揀與配貨。這一點(diǎn)是物流配送區(qū)別于其他物流形式的功能要素，另外它也是一項(xiàng)特別重要的支持性工作，在一定程度上決定了物流配送的成敗。它是提升送貨質(zhì)量和檔次的必然要求，也是企業(yè)提高自身服務(wù)水平的重要方式。(4)配裝。在電子商務(wù)環(huán)境下，客戶訂單一般較小，也較為頻繁，這樣就存在貨物的裝配問題，如何能夠集合不同類型的貨物，最大程度的提高貨車運(yùn)力，是需要考慮的重要問題。(5)運(yùn)輸。電子商務(wù)環(huán)境下的終端運(yùn)輸一般屬于短途、較小規(guī)模的運(yùn)輸，相比于干線運(yùn)輸，物流配送的

32、運(yùn)輸面臨著路徑選擇的問題。在顧客分布分散、數(shù)量較多的情況下，如何能夠?qū)⒀b配和線路進(jìn)行有效的搭配，是一個(gè)難度很大的工作。(6)送達(dá)服務(wù)。在貨物送到顧客面前以后，應(yīng)該做好交接工作，完成相關(guān)手續(xù)的辦理及業(yè)務(wù)結(jié)算，并且按照顧客的要求進(jìn)行卸貨。(7)配送加工。配送加工能夠提升顧客的滿意度，與普通流通加工有所不同，配送加工主要是為了滿足客戶的基本需求。2.2 配送路徑優(yōu)化問題物流路徑優(yōu)化問題通?？梢赃@樣描述：由多輛車將貨物從一個(gè)或多個(gè)配送中心送到多個(gè)地理位置上分散的客戶，在滿足一定的約束條件(貨物的需求量、發(fā)送量、交貨時(shí)間、車輛負(fù)載量限制、行駛路程限制、時(shí)間限制等)下，如何安排車輛及其行駛路線使得總的配送

33、費(fèi)用最小。這是物流配送的一個(gè)核心問題11。2.2.1 配送路徑優(yōu)化的目標(biāo)配送路徑合理與否對(duì)配送速度、成本、效益影響頗大，因此，采用科學(xué)的合理的方法確定配送路線是配送活動(dòng)中非常重要的一項(xiàng)工作。確定配送路線可以采取各種數(shù)學(xué)方法和在數(shù)學(xué)方法基礎(chǔ)上發(fā)展和演變出來(lái)的經(jīng)驗(yàn)方法。無(wú)論采取何種優(yōu)化方法，我們首先都要明確物流配送路徑的優(yōu)化目標(biāo)，才能有效地針對(duì)目標(biāo)進(jìn)行優(yōu)化。目標(biāo)的選擇根據(jù)配送的具體要求、配送中心的水平、實(shí)力及客觀條件而定，可以有以下多種選擇：(1)效益最高：在選擇以效益為目標(biāo)時(shí)，通常以企業(yè)當(dāng)前的效益為主要考慮因素，同時(shí)兼顧長(zhǎng)遠(yuǎn)的效益。效益是企業(yè)整體經(jīng)營(yíng)活動(dòng)的綜合體現(xiàn)，可以用利潤(rùn)來(lái)表示。因此在計(jì)算時(shí)

34、是以利潤(rùn)數(shù)值最大化為目標(biāo)值。但由于效益是綜合的反映，在擬定數(shù)學(xué)模型時(shí)很難與配送路線之間建立函數(shù)關(guān)系，所以一般很少采用這一目標(biāo)。(2)成本最低：計(jì)算成本比較困難，但和以效益為目標(biāo)相比有所簡(jiǎn)化，在成本和配送路線之間有密切關(guān)系、且成本對(duì)最終效益起決定作用的情況下，采用以成本最低為目標(biāo)實(shí)際上等于選擇了以效益為目標(biāo)，比較實(shí)用可行。(3)路程最短：如果成本和路程相關(guān)性較強(qiáng)，而和其他因素是微相關(guān)時(shí)，則可以選擇路程最短為目標(biāo)，這樣可以避免許多不易計(jì)算的影響因素，大大簡(jiǎn)化算。但需要注意的是有時(shí)候路程最短并不意味著成本最低，如果道路條件、道路收費(fèi)影響了成本，單以最短路程為最優(yōu)解則不合適了。(4)噸公里最?。菏情L(zhǎng)途

35、運(yùn)輸中常作為選擇目標(biāo)，在多個(gè)發(fā)貨站、多個(gè)收費(fèi)站、整車發(fā)到的情況下，選擇噸公里最低為目標(biāo)可以取得滿意結(jié)果。在配送路線選擇中，以噸公里最小為目標(biāo)在一般情況下并不適用，但在采取共同配送方式時(shí)，也可以作為目標(biāo)(5)準(zhǔn)時(shí)性最高：準(zhǔn)時(shí)性是配送中重要的服務(wù)指標(biāo)，以準(zhǔn)時(shí)性為目標(biāo)確定配送路線就是要將各客戶的時(shí)間要求和到達(dá)各客戶點(diǎn)的先后順序進(jìn)行協(xié)調(diào)安排，這樣有時(shí)難以顧及成本問題，甚至需要犧牲成本來(lái)滿足準(zhǔn)時(shí)性要求。但對(duì)準(zhǔn)時(shí)性的要求必須建立在控制成本的基礎(chǔ)上。(6)運(yùn)力利用最合理：在運(yùn)力非常緊張、運(yùn)力與成本或效益有一定相關(guān)的情況下，為了節(jié)約運(yùn)力、充分運(yùn)用現(xiàn)有運(yùn)力，而不需外租或新購(gòu)車輛，也可以運(yùn)力安排為目標(biāo)，確定配送路

36、線。針對(duì)不同的物流配送問題，要根據(jù)具體情況選擇優(yōu)化目標(biāo)。本文研究的物流配送問題根據(jù)帝峰模具公司物流系統(tǒng)的特點(diǎn)，將優(yōu)化目標(biāo)設(shè)定為路程短、準(zhǔn)時(shí)性高、運(yùn)力利用合理。2.2.2 配送路徑優(yōu)化問題的分類物流路徑優(yōu)化問題按照各種因素的不同形成了不同的種類，如表2-1。表2-1不同分類依據(jù)下的路徑優(yōu)化問題類型122.2.3 配送路徑優(yōu)化問題的解法分類針對(duì)早期與現(xiàn)今的車輛路徑問題模型，已有相當(dāng)多的文獻(xiàn)提出求解方法，可分為以下五大類13:(1)系統(tǒng)仿真法(Simulation)此方法最早由Golden和Skiscim于1986年提出，主要應(yīng)用于行車線路與物流配送中心區(qū)位的選擇。優(yōu)點(diǎn)在于可直接觀察系統(tǒng)安排的效率與

37、效果，但由于問題的實(shí)際情況多變且具有不確定性，很難將要實(shí)現(xiàn)的配送情形系統(tǒng)邏輯化為仿真程序；(2)人機(jī)互動(dòng)法人機(jī)互動(dòng)法是一種結(jié)合使用者的直覺、經(jīng)驗(yàn)、以及專業(yè)能力，納入求解過程的一L.種方法，這種方法可以讓決策者在電腦上產(chǎn)生途徑的中間階段。此方法結(jié)合人類決策與計(jì)算機(jī)計(jì)算能力，在求解的過程中，通過高度的人機(jī)交互模式，結(jié)合專家的決策信息計(jì)算出結(jié)果。該方法的優(yōu)點(diǎn)是尋優(yōu)的過程中，決策者可以很清楚地看到各約束條件之間的替代關(guān)系以及參數(shù)變化可能導(dǎo)致的成本變化；(3)精確解法(ExactProcedures)精確解法一般應(yīng)用于線性規(guī)劃(包括經(jīng)過了專門處理的分枝定界法、割平面法和標(biāo)號(hào)法)和非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù)

38、，以便求得問題的最優(yōu)解。在VRP問題研究的早期，主要是單源點(diǎn)(One-Point)(即配送中心、車場(chǎng)等)派車，研究如何用最短路線(或最短時(shí)間內(nèi))對(duì)一定數(shù)量的需求點(diǎn)(即用戶)進(jìn)行車輛調(diào)度，因此主要運(yùn)用精確算法求出問題的最優(yōu)解。精確式算法一般有以下幾種方法：分枝定界法(BranchandBoundApproach)、割平面法(CuttingPlanesApproach)、網(wǎng)絡(luò)流算法(NetworkFlowApproach)和動(dòng)態(tài)規(guī)劃方法(DynamicProgrammingApproach)等；(4)啟發(fā)式算法(Heuristics)由于上述三種方法的求解效率較差，所以大部分的學(xué)者都致力于啟發(fā)式解

39、法的發(fā)展。該方法在解題時(shí)可減少搜尋的次數(shù)，所以是一種容易且快速求解困難問題的算法。車輛路徑問題的啟發(fā)式解法，包括節(jié)約法(Savingmethod)、最鄰近法(Nearestneighbor)、插入法(Insertion)及掃描法(Sweeping)等；(5)智能算法(現(xiàn)代啟發(fā)式算法)進(jìn)入20世紀(jì)80年代，一些新穎的優(yōu)化算法，如人工神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、模擬退火算法、禁忌算法、混沌等，通過模擬或揭示自然現(xiàn)象或過程得到發(fā)展，其思想涉及數(shù)學(xué)、物理、生物進(jìn)化、人工智能等各方面，為解決復(fù)雜問題提供了新的思路和手段。在優(yōu)化領(lǐng)域，由于這些算法構(gòu)造的直觀性與自然機(jī)理，因而被稱為智能優(yōu)化算法(intellig

40、entoptimizationalgorithms)或現(xiàn)代啟發(fā)式算法(meta-heuristicalgorithms)。就目前的情況來(lái)看，智能算法應(yīng)用于VRP的研究還不深入，一般都只考慮比較簡(jiǎn)單的約束(容量約束、時(shí)間窗約束)，與實(shí)際應(yīng)用還有相當(dāng)大的距離。但是，用智能優(yōu)化算法解決VRP問題已經(jīng)得到了人們的重視，相當(dāng)多的學(xué)者致力于這方面的研究，發(fā)展勢(shì)頭很強(qiáng)勁，是進(jìn)行VRP研究的一個(gè)熱點(diǎn)方向。相對(duì)于傳統(tǒng)啟發(fā)式算法，現(xiàn)代啟發(fā)式算法不要求在每次迭代中均沿目標(biāo)值下降方向，而允許在算法中適當(dāng)接受目標(biāo)值有所上升甚至不可行的解，其目的是能夠跳出局部搜索鄰域。2.3 本文配送路徑優(yōu)化方法在配送路徑優(yōu)化問題的諸多

41、解法當(dāng)中，本文選擇啟發(fā)式算法當(dāng)中的三種最常被運(yùn)用到的方法進(jìn)行方案的優(yōu)化。2.3.1 建立VRP模型多回路運(yùn)輸問題(VRP)是現(xiàn)實(shí)中十分普遍的一種調(diào)配問題，此類調(diào)配的核心問題是如何對(duì)車輛進(jìn)行調(diào)度。因此，VRP(VehicleRoutingProblem)模型應(yīng)運(yùn)而生，并成為解決多回路問題的一個(gè)相當(dāng)成功的模型。該問題研究目標(biāo)是：對(duì)一系列顧客需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下(如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等)，達(dá)到一定的優(yōu)化目標(biāo)(如里程最短，費(fèi)用最小，時(shí)間盡量少等)。它涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑確定兩方面問題。一個(gè)典型的VRP模型可以

42、如下表述：(1)基本條件：現(xiàn)有m輛相同的車輛停在一個(gè)共同的源點(diǎn)v0,它需給n個(gè)客戶提供貨物，顧客為v1、v2,，vn,兩點(diǎn)之間路線為cij14。(2)模型目標(biāo)：確定所需的車輛數(shù)N,并指派這些車輛到一個(gè)回路中，同時(shí)包括回路內(nèi)的路徑安排和調(diào)度，使總費(fèi)用最小。(3)限制條件：N不大于m；每一個(gè)訂單都要完成；每輛車完成任務(wù)后都要回到源點(diǎn)v0;車輛的容量不能超過一定限制值；配送路線上所有配送點(diǎn)的配送需求量總和不能大于配送車輛的最大載重量；從配送中心出發(fā)到配送結(jié)束并返回配送中心的路程不能大于配送車輛的最大行駛距離；每條配送路線必須由一輛配送車輛配送，且要滿足路線上所有需求點(diǎn)的要求，特殊問題還需考慮時(shí)窗限制

43、、運(yùn)輸規(guī)章限制15。2.3.2 最近插入法最近插入法是一種解決旅行商問題的啟發(fā)式算法，其結(jié)合最鄰近法與節(jié)省法的觀念，依序?qū)㈩櫜迦肼窂街幸詷?gòu)建配送路線16。該方法首先以起點(diǎn)最近的點(diǎn)作為路線的種子點(diǎn)，再根據(jù)最鄰近點(diǎn)插入法的概念，以插入值最小者作為下一個(gè)插入點(diǎn)，最后再用一般化節(jié)省值公式，以其中節(jié)省值最大者決定插入的位置，重復(fù)進(jìn)行選取與插入的步驟，為了使物流配送的時(shí)間最少、距離最短、費(fèi)用最低，并使合并后的總運(yùn)輸距離節(jié)約的里程最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一條路線的優(yōu)化17?？忘c(diǎn)需求最近插入法由四步完成18:（1）找到c0i最小的節(jié)點(diǎn)vi,形成一個(gè)子回路，T=v0,vk,v0;（2）在剩下的

44、節(jié)點(diǎn)中，尋找一個(gè)離子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)vk,若此時(shí)回路的總貨運(yùn)量未超過車的載重限制，則繼續(xù)步驟（3）,否則，轉(zhuǎn)（1）尋找新的一條回路；（3）路徑優(yōu)化過程對(duì)每條路徑進(jìn)行局部搜索，調(diào)整路徑內(nèi)或路徑間節(jié)點(diǎn)訪問順序，改善路徑的質(zhì)量，在子回路中找到一條?。╥,j）,使得cik+ckj-cij最小，然后將節(jié)點(diǎn)vi插入到節(jié)點(diǎn)vi,vj之間，用兩條新的弧（i,k）,（k,j）代替原來(lái)的?。╥,j）,并將節(jié)點(diǎn)vk加入到子回路中。若此時(shí)該回路的總路程為未超過車輛的行程限制，則繼續(xù)步驟（4）,否則轉(zhuǎn)步驟（1）,尋找新的一條回路；（4）重復(fù)步驟（2）和（3）,直到每一個(gè)節(jié)點(diǎn)都被歸入某一個(gè)子回路中。2.3.3 掃

45、描法掃描法是用于求解車輛數(shù)目不限制的VRP問題的算法，它采用“先分組后路線”的過程，所謂分組就是派給每輛車一組客戶點(diǎn)。一種簡(jiǎn)單的分組方法是將以配送中心為原點(diǎn)的坐標(biāo)平面劃分為多個(gè)扇形區(qū)域，并初步將每個(gè)扇形區(qū)域的點(diǎn)分派給一輛車，然后擴(kuò)充路線，如果在進(jìn)行了一次“分組-路線”的路線構(gòu)造后，還存在未分配點(diǎn)，則再進(jìn)行“分組-路線”程序。如此反復(fù)，直到所有的點(diǎn)均已分配為止19。掃描算法的主要步驟：（1）以起點(diǎn)0點(diǎn)作為極坐標(biāo)系的原點(diǎn)，并一連通圖中的任意一顧客點(diǎn)和原點(diǎn)的連線定義為角度零，建立極坐標(biāo)系；然后對(duì)所有的顧客所在的位置，進(jìn)行極坐標(biāo)變換；（2）從最小角度的顧客開始建立一個(gè)組，按逆時(shí)針方向，將顧客逐個(gè)加入到

46、組中，直到顧客的需求總量超出了負(fù)載的限制。然后繼續(xù)建立一個(gè)新的組，繼續(xù)按逆時(shí)針方向，將客戶加入組中；（3）重復(fù)（2）中的過程，直到所有客戶都被分類為止；（4）對(duì)各個(gè)組內(nèi)的單回路進(jìn)行路徑優(yōu)化。2.3.4 節(jié)約算法節(jié)約算法是目前用來(lái)解決運(yùn)輸車輛數(shù)目不確定的VRP模型的最有名的啟發(fā)式算法,其思想在于按節(jié)約值（較短路徑與原路徑之差）由大至小排序，在車輛容量限制下，依序?qū)?duì)應(yīng)的兩客戶點(diǎn)排入路徑中，直至所有客戶都被排入路徑為止。關(guān)鍵在于當(dāng)節(jié)約值較大的兩顧客點(diǎn)被排入路徑時(shí)，除需考慮車輛容量限制方面采用“量力而為”的策略外，更需要考慮到時(shí)間的限制，此方法的優(yōu)點(diǎn)是提高車輛的利用率20。節(jié)約算法的核心思想是將運(yùn)輸

47、問題中存在的兩個(gè)回路（0,，i,0）和（0,j,，0）合并成一個(gè)回路（0,，i,j,，0）,在上面的合并操作中，整個(gè)運(yùn)輸問題的總運(yùn)輸距離會(huì)發(fā)生變化，如果變化后總運(yùn)輸距離下降，則稱節(jié)約了運(yùn)輸距離21。其中cio代表從顧客i至起點(diǎn)的距離，coj代表從起點(diǎn)至顧客j的距離，cji則代表從顧客j至顧客i的距離，相應(yīng)的變化值叫做節(jié)約距離QUOTE*MERGEFORMAT工ij。計(jì)算兩結(jié)點(diǎn)i與j間的節(jié)約值QUOTE*MERGEFORMATzCij時(shí)，應(yīng)先計(jì)算原路徑中各往返路徑的總和，再與較短路的總路徑和相比較。兩結(jié)點(diǎn)間的節(jié)約值的計(jì)算公式與意義如式（1）所示。（1）兩結(jié)點(diǎn)的原路徑與較短路的調(diào)整過程如圖2-1所

48、示。i00i調(diào)整前調(diào)整后圖2-1節(jié)約算法的圖像描述節(jié)約里程算法主要步驟：（1）設(shè)需求點(diǎn)集NR=1,2,n,各點(diǎn)需求量Ri,各點(diǎn)間最短距離cij;（2）確定各車輛配送點(diǎn)集I1,I2,1Im令上j,j=1,2,in（先采取單點(diǎn)配送）;(3)計(jì)算所有點(diǎn)對(duì)的節(jié)約度QUOTE*MERGEFORMATz2Cij,然后對(duì)計(jì)算結(jié)果進(jìn)行升序排列。(4)從升序排列的節(jié)約度序列中的最上面的值開始，直到節(jié)約里程Cij的隊(duì)列空為止，重復(fù)下列步驟：按照節(jié)約里程Cij隊(duì)列從大到小的順序，分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過2),將i,j連接起來(lái),即可令I(lǐng)"=IiU

49、Ij;？，如果不是這樣，則從節(jié)約里程隊(duì)列中去除當(dāng)前的節(jié)約里程，分析下一個(gè)客戶對(duì)22。第3章帝峰模具公司物流配送路徑現(xiàn)狀分析1.1 公司簡(jiǎn)介武漢帝峰模具有限公司成立于2012年，位于武漢市江夏開發(fā)區(qū)大橋新區(qū)107國(guó)道旁。它是以五金模具與塑膠模具的研發(fā)與制造、提供銷售配送服務(wù)為一體的實(shí)體企業(yè)。公司擁有專業(yè)技術(shù)人才二十余名和各種機(jī)械加工設(shè)備，下設(shè)設(shè)計(jì)部門，生產(chǎn)部門，營(yíng)銷部門，物流部門等職能部門，各部門通力協(xié)作，為社會(huì)奉獻(xiàn)優(yōu)質(zhì)高效的各類模具，為客戶提供專業(yè)專心的技術(shù)支持和服務(wù)，武漢帝峰模具有限公司自成立以來(lái)，堅(jiān)持“以誠(chéng)為本，以信為根”，“用科技創(chuàng)造綠色生活”的經(jīng)營(yíng)理念，立志成為模具新技術(shù)的領(lǐng)航者的企業(yè)

50、愿景，扎實(shí)走科技與生產(chǎn)相結(jié)合的產(chǎn)業(yè)化道路，專業(yè)生產(chǎn)各種模具產(chǎn)品。目前公司產(chǎn)品涵蓋湖北省各市縣并以優(yōu)厚的實(shí)力、合理的價(jià)格、優(yōu)良的服務(wù)與多家企業(yè)建立了合作關(guān)系。1.2 公司物流配送路徑現(xiàn)狀公司的客戶主要位于其所在地的周邊縣市，共有9個(gè)縣市，如孝感市、天門市、荊州市等，編號(hào)如表3-1,地區(qū)分布如圖3-1所示,但需求較小，公司為推廣產(chǎn)品，采用每月專車送貨上門服務(wù)。公司現(xiàn)擁有4輛40噸的貨車，若車輛使用欠缺時(shí)，可租賃車輛。表3-1客戶所在城市編號(hào)圖3-1帝峰模具公司配送地區(qū)基礎(chǔ)圖已知武漢帝峰模具有限公司位置為0點(diǎn)，分別向周圍編號(hào)為1、2、3、4、5、6、7、8、9共9個(gè)小客戶點(diǎn)配送本期新型五金模具，其擁

51、有2輛40噸的車40噸卡車最大載量為12套模具。各點(diǎn)需求量為Ri,每輛車的行駛里程為L(zhǎng)i,Li<700公里，客戶點(diǎn)1,2,，9。各縣市每月需求模具的基本數(shù)據(jù)如圖3-2所示。圖3-2各客戶點(diǎn)的需求量圖3-3各客戶點(diǎn)的配送距離（資料來(lái)源：帝峰模具公司信息系統(tǒng)）|目前，對(duì)小客戶公司采用的配送線路如圖3-2所示。圖3-2公司現(xiàn)有配送路線各配送線路的里程，所需司機(jī)數(shù)量的基本情況如表3-2所示。表3-2配送信息表（資料來(lái)源：帝峰模具公司信息系統(tǒng)）由上表可知，公司每月需40噸貨車4車次配送，司機(jī)5人次，所需工資2500元，運(yùn)輸總里程為1549.5千米，消耗柴油697.28升，所需燃油費(fèi)3625.86元

52、，一共花費(fèi)6125.86元。1.3 公司物流配送路徑存在的問題分析在物流車輛配送中，公司其往往需向幾個(gè)不同顧客的運(yùn)送貨物，每個(gè)用戶又會(huì)對(duì)貨物有不同的需求，這將造成配送復(fù)雜性。雖然公司對(duì)物流部門的大力支持，物流部門快速發(fā)展，物流部門的交通設(shè)施改善很多，物流配送成本也降低了很多，但相比于同行業(yè)其他企業(yè)，公司目前配送線路的弊端在于：配送路線的回路過多，存在對(duì)流運(yùn)輸?shù)默F(xiàn)象，經(jīng)驗(yàn)化操作過多，優(yōu)化不徹底，導(dǎo)致總運(yùn)距過長(zhǎng)，消耗作業(yè)時(shí)間偏多，不能充分利用車輛配載容積，浪費(fèi)較多人力和物力資源，物流成本的花費(fèi)還是很高，影響公司盈利22。1.3.1 回路總數(shù)過多在公司現(xiàn)有路徑的圖中，9個(gè)客戶點(diǎn)設(shè)置4條回路，平均每條

53、回路有2.25個(gè)客戶3.67套；由于每條點(diǎn)；9個(gè)客戶點(diǎn)總需求量為33套模具，平均每個(gè)客戶點(diǎn)需求量約回路中有一輛配送車輛，故每輛車平均裝載約8.26套模具。而公司的40噸貨車可裝載12套模具，所以平均每輛車?yán)寐蕿?8.9%,計(jì)算結(jié)果偏低，導(dǎo)致車輛非滿載運(yùn)輸，運(yùn)力利用不充分，造成車輛，人力，資金上的浪費(fèi)。對(duì)于此種情況來(lái)說，關(guān)鍵因素在于路徑回路總個(gè)數(shù)，所以最有效的方法是通過減少總會(huì)路個(gè)數(shù)，充分利用車輛配載容積，提高車輛利用率，進(jìn)而節(jié)約車輛與人力上的成本。1.3.2 對(duì)流運(yùn)輸對(duì)流運(yùn)輸亦稱相向運(yùn)輸、交錯(cuò)運(yùn)輸，是指同一種貨物，或彼此間可以互相代用而又不影響管理、技術(shù)及效益的貨物，在同一線路上或平行線路上

54、作相對(duì)方向的運(yùn)送，而與對(duì)方運(yùn)程的全部或一部分發(fā)生重迭交錯(cuò)的運(yùn)輸稱對(duì)流運(yùn)輸。已經(jīng)制定了合理流向圖的產(chǎn)品，一般必須按合理流向的方向運(yùn)輸，如果與合理流向圖指定的方向相反，也屬對(duì)流運(yùn)輸。如圖3-5中，從4號(hào)地區(qū)回到起點(diǎn)的路線與從起點(diǎn)到5號(hào)地區(qū)的路線（圖中用圓圈畫出）雖然不是一條回路中的配送路徑，但是它在平行線路上作相對(duì)方向的運(yùn)送，屬于對(duì)流運(yùn)輸?shù)那闆r，同樣情況的還有2-0與0-5（圖中用斜線畫出），2一0與0一3（圖中用菱形畫出）兩對(duì)路線，這種現(xiàn)象會(huì)導(dǎo)致人力、物力等資源的浪費(fèi)。4圖3-3現(xiàn)有路徑中的對(duì)流運(yùn)輸現(xiàn)象1.3.3 經(jīng)驗(yàn)化操作經(jīng)調(diào)查，由于企業(yè)建立時(shí)招聘的人員大多具有多年物流經(jīng)驗(yàn)，不免會(huì)根據(jù)以往的工

55、作經(jīng)驗(yàn)進(jìn)行工作，其設(shè)計(jì)的運(yùn)輸配送路徑經(jīng)驗(yàn)化操作過多，從而導(dǎo)致企業(yè)增加目標(biāo)地區(qū)之后，他們不會(huì)積極地重新去計(jì)算和安排配送的運(yùn)輸路徑，而是憑以往經(jīng)驗(yàn)操作此過程。如圖3-6中，客戶點(diǎn)3和客戶點(diǎn)4是最近與公司合作的客戶，距離公司膠原且兩點(diǎn)相離較近，物流部門便僅把兩點(diǎn)歸于一條回路當(dāng)中，并沒有將九個(gè)客戶點(diǎn)放在一起重新計(jì)算作合理安排。圖3-4經(jīng)驗(yàn)化操作下的一條回路第4章帝峰模具公司物流配送路徑優(yōu)化策略4.1 建立VRP模型優(yōu)化配送路徑對(duì)帝峰模具有限公司的配送系統(tǒng)建立VRP模型。基本條件：帝峰模具有限公司需給9個(gè)客戶送貨，客戶依次為1,2,日，現(xiàn)有3輛40噸的貨車(每百公里油耗45L),司機(jī)每天工資500元，柴

56、油每升5.20元。模型目標(biāo)：確定所需要的車輛的數(shù)目N、車輛類型、司機(jī)數(shù)量以及各車行走的路徑，并指派這些車輛到一個(gè)回路中，同時(shí)包括回路內(nèi)的路徑安排和調(diào)度，使得運(yùn)輸總費(fèi)用最小。限制條件：(1)全程的總時(shí)間不超過駕駛員每天最大工作時(shí)，以避免疲勞駕駛23,所以基于人性化與安全的考慮，當(dāng)運(yùn)輸里程超過350公里時(shí)，需配備兩名司機(jī)，為防止突發(fā)運(yùn)輸事件，車輛必須當(dāng)天回到公司，減去由于裝卸貨等影響因素，各車最大運(yùn)輸距離為650公里。(2)每輛車完成任務(wù)之后都要回到源點(diǎn)0處。(3)不能超過車輛的容量限制。40噸的貨車最多可裝12套模具。4.2 公司物流配送路徑的優(yōu)化4.2.1 運(yùn)用最近插入法優(yōu)化第一條路徑：令丁=

57、0川=0,1,2,9,比較表4-1中從0出發(fā)的所有路徑大小。因?yàn)閙inc0i|iCN,1<i<9=c01=61.4km,所以就有顧客點(diǎn)0,1構(gòu)成一個(gè)子回路，T1=0,1,0,此時(shí)M=5,L1=122.8km。然后在剩余客戶點(diǎn)(2,3,4,5,6,7,8,9)中尋找到0和1中某一點(diǎn)的最小距離，minc0i,c1iiCN,14i9且iW1=c08=77km,r8=2,因?yàn)閞1=r1+r8=7v12,所以在子回路T1=0,1,0插入點(diǎn)8。由于對(duì)稱性，無(wú)論將8插入到0和1之間往返路徑中，結(jié)果都是一樣的，這樣，構(gòu)成了一個(gè)新的子回路T1=0,1,8,0,r1=7,L1=275.1km。再次尋找剩余客戶點(diǎn)到0,1,8中某一點(diǎn)的最小距離：可知最小距離為c78=41.4km。此時(shí)，r7=4,因?yàn)閞1+r7=7+4=11<12,所以在子回路T1=0,1,8,0插入點(diǎn)7。將點(diǎn)7分別插入(0,1),(1,8),(8,0)中：(1)插入到(0,1)之間，A=c07+c71-c01=100.4+159-