并行工程在車身設(shè)計的應(yīng)用(共37頁)

1、學(xué) 號 M201470547課 程 論 文題 目現(xiàn)代運籌學(xué)算法在物流配送中的應(yīng)用學(xué) 院機械學(xué)院專 業(yè)工業(yè)工程班 級機碩1407姓 名楊勇指導(dǎo)教師李新宇副教授2014年12月29日摘要(zhiyo) 配送是物流活動中直接與消費者相連的環(huán)節(jié)。配送成本占物流的各項成本的比例相當高。配送線路合理與否影響到配送速度、成本和效益，特別是多用戶配送線路的確定(qudng)是一項復(fù)雜的系統(tǒng)工程。因此，物流車輛路線問題(VRP)成為國內(nèi)研究的熱點。 運籌學(xué)，用定量化方法了解和解釋運行系統(tǒng)(xtng)、為管理決策提供科學(xué)依據(jù)的學(xué)科。它把有關(guān)的運行系統(tǒng)首先歸結(jié)成數(shù)學(xué)模型，然后用數(shù)學(xué)方法進行定量分析和比較，求得合理運

2、用人力、物力和財力的系統(tǒng)運行最優(yōu)方案。運籌學(xué)有廣闊的應(yīng)用領(lǐng)域，是軟科學(xué)中“硬度”較大的一門學(xué)科，兼有邏輯的數(shù)學(xué)和數(shù)學(xué)的邏輯的性質(zhì)，是系統(tǒng)工程學(xué)和現(xiàn)代管理科學(xué)中的一種基礎(chǔ)理論和不可缺少的方法、手段和工具。在運籌學(xué)中有解決物流配送問題的有效方法。本文主要介紹了節(jié)約法、遺傳算法并用這些方法解決實際物流配送問題。關(guān)鍵詞：物流配送，節(jié)約法，遺傳算法Abstract Distribution logistics activities directly connected with the consumer segment. The costs of logistics and distribution c

3、osts account for a very high proportion. Distribution line is reasonable or not affect the distribution of speed, cost and efficiency, especially multi-user distribution lines to determine is a complex system engineering. Therefore, the logistics vehicle routing problem (VRP) has become a hot domest

4、ic research. Operations research, using quantitative methods to understand and explain the operating system, to provide a scientific basis for management decisions disciplines. It related to the operation of the system is due to a mathematical model first, and then use mathematical methods for quant

5、itative analysis and comparison, and seek the rational use of human, material and financial resources of the system to run the optimal solution. Operations research has broad applications, the soft science of hardness of the larger one discipline, the nature of the logic of both mathematics and math

6、ematical logic, is a basic theory of system engineering and modern management science and not lack of methods, means and tools.There are effective ways to solve the logistics problems in operations research. This paper describes the conservation law, scanning method, tabu search, genetic algorithm a

7、nd use these methods to solve practical problems of logistics and distribution.Keywords: logistics, saving, scanning method, tabu search, genetic algorithm目錄(ml)TOC o 1-3 h u HYPERLINK l _Toc1319 1緒論(xln) 現(xiàn)代運籌學(xué)算法(sun f)在物流配送中的應(yīng)用1緒論(xln)1.1發(fā)達國家(f d u ji)和地區(qū)物流配送現(xiàn)狀 理解物流配送概念離不開對物流概念的分析。物流概念最早是在美國形成的，被稱為

8、“physiealDistribution”(即Pn)，譯成漢語是“實物分配”或“貨物配送”。1963年被引入日本，物流被定義為“在連接生產(chǎn)和消費間對物資履行保管、運輸、裝卸、包裝、加工等功能，以及作為控制這類功能后援的信息功能,，在物資銷售中起了橋梁作用”。因此，現(xiàn)代物流是以滿足消費者的需求為目標，把制造、運輸、銷售等市場情況統(tǒng)一起來思考的一個產(chǎn)業(yè)概念。配送是物流系統(tǒng)的核心環(huán)節(jié)之一，配送在英語中的原語是“delivery”，是交貨送貨的意思。在日本工業(yè)標準Jis中，將配送定義為“將貨物從物流結(jié)點送交收貨人”強調(diào)了送貨的含義。可以說，物流配送是連接生產(chǎn)與消費之間的一種中介服務(wù)，是物資供應(yīng)的種重

9、要形式。配送是“配”和“送”有機結(jié)合的形式，它利用有效的分揀、配貨等理貨工作，使送貨達到一定的規(guī)模，以利用規(guī)模優(yōu)勢取得較低的送貨成本。 推行配送制有利于合理配置資源。由于實施配送可以做到以配送企業(yè)的庫存取代社會上千家萬戶的零散庫存，或者說，可以使庫存相對集中，因此，有條件也有可能按照統(tǒng)一計劃合理分配和使用資源，做到物盡其用。推行配送制可以降低物流成本，促進生產(chǎn)快速發(fā)展。這是因為各種流通要素相對集中，有益于開展規(guī)模經(jīng)營活動；流通的物質(zhì)要素相對集中，也便于合理安排各環(huán)節(jié)上的物流活動，使總體運動協(xié)調(diào)一致，最終會減少物流領(lǐng)域內(nèi)的勞動消耗和費用支出。推行配送制能夠充分發(fā)揮專業(yè)流通組織的綜合優(yōu)勢。推行配送

10、很容易使不同的流通組織聯(lián)系在一起，從而構(gòu)成多功能的、一體化的物流運動。這種以配送作為媒介而形成的一體化運作較之各個專業(yè)企業(yè)獨立運作更能發(fā)揮流通組織的整體優(yōu)勢和綜合優(yōu)勢。 從20世紀60年代起，商品配送的合理化在美國普遍得到重視。為了在流通領(lǐng)域產(chǎn)生效益，美國企業(yè)采取了以下措施：一是將老式的倉庫改為配送中心；二是引進電腦管理網(wǎng)絡(luò)，對裝卸、搬運、保管實行標準化操作，提高作業(yè)效率；三是連鎖店共同組建配送中心，促進連鎖店效益的增長。美國連鎖店的配送中心有多種，主要有批發(fā)型、零售型和倉儲型三種類型。首先是批發(fā)型。該類型配送中心主要靠計算機管理。業(yè)務(wù)部通過計算機獲取會員店的訂貨信息，及時向生產(chǎn)廠家和儲運部發(fā)

11、出訂貨指示單。其次是零售型。以美國沃爾瑪商品公司的配送中心為典型。該類型配送中心一般為某零售商獨資興建，專為本公司的連鎖店按時提供商品，確保各店穩(wěn)定經(jīng)營。第三是倉儲型。美國福來明公司的食品配送中心是典型的倉儲式配送中心。它的主要任務(wù)是接受獨立雜貨商聯(lián)盟的委托業(yè)務(wù)，為該聯(lián)盟在該地區(qū)的若干家加盟店負責商品配送。 在日本，零售業(yè)是首先建立先進物流系統(tǒng)的行業(yè)之一。便利店作為一種新的零售業(yè)態(tài)迅速成長，現(xiàn)己遍及日本，正影響著日本其他的零售商業(yè)形式。這種新的零售商業(yè)業(yè)態(tài)需要利用新的物流技術(shù)，以保證店內(nèi)各種商品的供應(yīng)順暢。因此，日本的物流配送具有以下特點；第一，分銷渠道發(fā)達。許多日本批發(fā)商過去常常把自己定位為

12、某特定制造商的專門代理商， 只允許經(jīng)營一家制造商的產(chǎn)品。為了保證有效地供應(yīng)商品,日本許多物流公司不得不對原有的分銷渠道進行合理化改造,更好地做到與上游或下游公司的分銷一體化。第二，頻繁、小批量進貨。日本的物流配送企業(yè)的很大一部分服務(wù)需求來自便利店，便利店依靠的是小批量的頻繁進貨，只有利用先進的物流系統(tǒng)才有可能發(fā)展連鎖便利店，因為它使小批量的頻繁進貨得以實現(xiàn)。第三，物流配送體現(xiàn)出共同化、混載化的趨勢。共同化、混載化的商品配送使原來按照不同生產(chǎn)廠、不同商品種類劃分(hu fn)開來的分散的商品物流轉(zhuǎn)變?yōu)閷⒉煌瑥S家的產(chǎn)品和不同種類的商品混合起來運送的聚合的商品物流，從而得以發(fā)揮商品物流的批量效益，大

13、大提高了運貨車輛的裝載率。第四,合作型物流配送。在日本,生產(chǎn)企業(yè)、零售企業(yè)與綜合商社、綜合物流公司之間基本上都存在一種長期的物流合作關(guān)系。并且，這種合作關(guān)系還隨著日本工業(yè)生產(chǎn)的國際化延伸到國外。第五，政府規(guī)劃在現(xiàn)代物流配送發(fā)展過程中具有重要作用。1.2我國的物流配送發(fā)展(fzhn)現(xiàn)狀 物流配送是現(xiàn)代流通的重要組成部分。近年來，我國物流配送發(fā)展(fzhn)出現(xiàn)了積極趨勢，主要體現(xiàn)在以下幾個方面： 各級政府部門采取措施積極推動物流配送的發(fā)展。不少省市己經(jīng)把發(fā)展現(xiàn)代物流列入了日程，例如，上海、天津、深圳都把物流作為支柱產(chǎn)業(yè)。還有許多省市開始制定物流規(guī)劃。國家有關(guān)部門對商品物流和配送采取了積極鼓勵和

14、支持的政策，在我國流通領(lǐng)域?qū)ν忾_放政策中，鼓勵國外資本投資于物流和配送設(shè)施等。目前國內(nèi)物流和配送服務(wù)己有較快的發(fā)展，物流配送己經(jīng)成為許多企業(yè)降低成本，提高競爭力的重要手段。例如，相當多實行連鎖經(jīng)營的零售企業(yè)建立了自己的配送中心，為企業(yè)內(nèi)部的連鎖網(wǎng)點提供物流配送服務(wù)，一些連鎖企業(yè)配送商品比例己經(jīng)超過企業(yè)經(jīng)營品種的50%。 在生活資料領(lǐng)域和生產(chǎn)資料領(lǐng)域出現(xiàn)了各具特色的不同類型的現(xiàn)代物流企業(yè)。一些傳統(tǒng)的流通企業(yè)，包括運輸和倉儲業(yè)通過改造成為物流企業(yè)，如中遠集團、中外運集團和中儲集團等；一些國有商業(yè)批發(fā)企業(yè)和大型零售企業(yè)正在積極探索和嘗試開展社會化物流配送服務(wù)；一些生產(chǎn)企業(yè)開始介入現(xiàn)代物流，如青島海爾

15、集團；一批專業(yè)化的物流企業(yè)得到較快發(fā)展，物流配送的社會化、專業(yè)化發(fā)展趨勢日益明顯，如深圳中海物流都是比較成功的第三方物流公司。外資在物流配送服務(wù)領(lǐng)域的發(fā)展也十分迅速，如中國儲運總公司與日本崗谷鋼機株式會社合資組建了天津崗谷物流公司，是集配送、加工、倉儲、寄售、租賃、修理、展銷和技術(shù)咨詢?yōu)橐惑w的新型流通組織。像這樣的合資物流公司，在北京、天津、上海等地已有10家之多，它們主要是為在中國投資的跨國公司提供物流配送服務(wù)。這些企業(yè)根據(jù)各自特點，發(fā)揮特長優(yōu)勢，積極開拓物流服務(wù)領(lǐng)域，形成了服務(wù)模式多樣、多種經(jīng)濟成份并存的現(xiàn)代物流企業(yè)群體。連鎖企業(yè)內(nèi)部的配送中心在硬件設(shè)施、管理水平、管理信息系統(tǒng)等方面的建設(shè)

16、，獲得較大發(fā)展，有些己經(jīng)達到較先進的水平。 現(xiàn)代物流技術(shù)的開發(fā)研究取得一定進展。一些物流配送企業(yè)在研究開發(fā)物流信息技術(shù)和物流配送管理技術(shù)上取得了許多成果，對于推動我國現(xiàn)代物流發(fā)展發(fā)揮了積極作用。目前已有相當多的物流和配送技術(shù)開始進入中國，并在企業(yè)中得到越來越廣泛的應(yīng)用，例如條形碼技術(shù)、計算機支持的信息管理技術(shù)、EDI、MRP等。 盡管我國物流配送業(yè)近幾年發(fā)展很快，但與發(fā)達國家相比還處在起步階段，不可避免地會遇到這樣或那樣的問題。當前，主要存在以下幾個方面的問題： （1）物流配送市場化程度低，第三方物流配送發(fā)展滯后。目前我國大多數(shù)物流配送企業(yè)技術(shù)裝備和管理手段比較落后，服務(wù)網(wǎng)絡(luò)和信息系統(tǒng)不健全，

17、物流配送市場化程度低，影響了物流服務(wù)的準確性與時效性。其主要表現(xiàn)是：?。ㄎ锪髋渌推髽I(yè)數(shù)量小，經(jīng)營規(guī)模小)、少(物流配送市場份額少、服務(wù)功能少，大多數(shù)企業(yè)還只是被動地按照用戶的要求，從事單一功能的運輸、倉儲和配送，很少能提供物流策劃、組織及深入到供應(yīng)鏈的全過程管理，物流增值少)、散(網(wǎng)絡(luò)分割、經(jīng)營秩序不規(guī)范，不能為客戶提供包括(boku)物流網(wǎng)絡(luò)設(shè)計、預(yù)測、訂貨管理、存貨管理等系統(tǒng)物流服務(wù))、弱(競爭力弱和發(fā)展滯后，專業(yè)化、信息化、標準化還沒跟上，還沒有真正了解國際物流企業(yè)的運作方式和真正意義上的“第三方物流”)。 （2）物流基礎(chǔ)設(shè)施落后，物流配送的整體功能低。一是交通運輸設(shè)施建設(shè)與物流配送的需

18、要(xyo)不相適應(yīng)，即交通運輸能力仍不能滿足運輸需求，主要運輸通道供需矛盾依然突出：二是技術(shù)裝備水平落后；三是物流系統(tǒng)標準化程度低。 （3）物流配送管理體制和相關(guān)制度不完善。一方面，市場競爭機制和市場管理法規(guī)不健全，發(fā)展物流配送所需的產(chǎn)業(yè)政策和產(chǎn)業(yè)規(guī)劃尚未出臺(ch ti)，物流市場的進入與退出、競爭規(guī)則基本上無統(tǒng)一法律法規(guī)可循，對社會性的物流缺乏有效的外部約束，致使不正當競爭較為嚴重。另一方面，物流配送市場至今仍被人為地按照部門、地區(qū)和行業(yè)的行政壁壘分割，物流配送市場管理和行業(yè)管理還沒有理順，各地商委、經(jīng)貿(mào)委、交通局、鐵路局、外經(jīng)貿(mào)委等都各自承擔了一部分物流管理職能，各部門間分工又有交叉，

19、造成了物流管理中條塊分割、重復(fù)建設(shè)等問題，統(tǒng)一、競爭、有序的物流配送市場沒有建立起來，嚴重影響了物流配送渠道的暢通和高效運轉(zhuǎn),使物流配送很難達到規(guī)模經(jīng)濟和預(yù)期回報。 （4）專業(yè)的物流配送管理和技術(shù)人才短缺。1.3發(fā)展物流配送的意義 隨著經(jīng)濟全球化和網(wǎng)絡(luò)信息技術(shù)發(fā)展的加快，物流及配送業(yè)作為一個新的經(jīng)濟增長點引起了國人的注意。上海、天津、北京等城市紛紛將物流產(chǎn)業(yè)作為支柱產(chǎn)業(yè)，中儲、中遠、中外運等大型企業(yè)都把現(xiàn)代物流作為重點發(fā)展領(lǐng)域。我國證券市場己經(jīng)形成了由幾十家企業(yè)構(gòu)成的“物流板塊”，許多商貿(mào)流通部門紛紛介入現(xiàn)代物流配送業(yè)務(wù)中，物流及配送業(yè)的發(fā)展在全國方興未艾。 2011年我國社會物流總費用為8.

20、4萬億元，從構(gòu)成情況看，運輸費用4.4萬億元，占社會物流總費用的比重為52.4%，保管費用2.9萬億元，占社會物流總費用的比重是34.5%，管理費用1萬億元，占社會物流總費用的比重為11.9%。運輸成本占物流成本的50%左右，是影響物流總費用的主要因素，調(diào)查顯示，美國的運輸成本僅占到其GDP的不到6%，日本也僅為6.5%。而我國運輸成本占到GDP 的11%。中國倉儲協(xié)會對146家生產(chǎn)企業(yè)的調(diào)查結(jié)果表明，運輸費用占整個物流費用的比例分別為：生產(chǎn)企業(yè)原材料物流中運輸費用占到58%，生產(chǎn)企業(yè)成品物流中運輸費用占到73%，商業(yè)物流中運輸費用占到 52%。 由以上數(shù)據(jù)可以看出運輸費用在總物流費用中所占比

21、重最大，因此節(jié)約運輸費用可以極大的降低物流成本。在物流活動中，配送是很重要的一個環(huán)節(jié)，運輸成本在配送成本中占有很大的一部分，因此在配送管理中，有效的使用車輛并確定配送車輛經(jīng)濟行駛路線，在最短的時間內(nèi)把商品送到顧客手中，提高顧客的滿意度，是配送作業(yè)的重點。顯然，為了實現(xiàn)以上幾點目標，必須對配送過程進行合理規(guī)劃，這一點可以通過改進運輸方式、進行線路規(guī)劃等來實現(xiàn)。近年來，配送車輛路線的確定問題是物流配送領(lǐng)域的重點研究對象，它是指利用科學(xué)的、合理的手段來制定配送線路，對其進行研究可以提高配送效益、有利于實現(xiàn)配送科學(xué)化。 為實現(xiàn)運輸成本的降低，必須對運輸?shù)倪M行(jnxng)合理規(guī)劃。運輸?shù)暮侠硪?guī)劃涉及到

22、時間、財務(wù)、環(huán)境三方面的因素，首先從時間要考慮準時性、快速響應(yīng)；財務(wù)上要考慮運輸涉及的各種開支(車輛購置成本和消耗、司機薪酬、油耗等)；環(huán)境上要盡可能減少不必要的行駛,避免交通擁擠、空氣以及噪音等污染。這些可以通過改進運輸方式、線路規(guī)劃等交通管理來加以改善。其中運輸方式屬于“硬”技術(shù)的問題。是可以通過設(shè)施的完善和提高運輸?shù)男?降低相應(yīng)成本。運輸?shù)木€路規(guī)劃主要是利用各種先進的信息技術(shù)對車輛及其路線進行規(guī)劃，實現(xiàn)對車輛合理有效的利用，從而節(jié)省大量的時間和成本。而物流中心配送作業(yè)的重點就是如何將車輛有效的使用并決定其最經(jīng)濟的行駛(xngsh)路線圖，使商品能在最短的時間內(nèi)送到顧客的手中。該問題為；

23、從配送中心(物流據(jù)點)用多輛車向多個需求點(顧客)送貨，每個需求點的位置和需求量一定,每輛車的載重量一定，要求合理安排車輛路線，使總運距最短，并滿足以下條件：(1)每條配送路徑上各需求點的需求量之和不超過車輛載重量；(2)每條配送路徑的長度不超過車輛一次配送的最大行駛距離；(3)每個需求點必須滿足,且只能由一輛車送貨。達到一定的目標(如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等)。此即為VRP問題。 通過科學(xué)合理的手段制定配送路線，在配送活動中是很重要的一個環(huán)節(jié)。合理的選擇配送路線，對于社會和企業(yè)具有重要意義。對于企業(yè)，配送路線的優(yōu)化，可以簡化配送程序、提高配送效率，充分利用配送車輛運

24、力、降低空載率、減少配送次數(shù)、盡量使配送成本降低；同時優(yōu)化配送路線可以加快企業(yè)對客戶需求的響應(yīng)速度，準時、快速的把物品送達客戶，提高客戶滿意程度。對于社會，配送路線優(yōu)化可以節(jié)省作業(yè)車輛，進而緩解交通擁堵狀況，減少噪聲、尾氣的排放，為保護生態(tài)環(huán)境(shn ti hun jn)做出貢獻。所以研究配送車輛路線優(yōu)化問題及算法具有重要的現(xiàn)實意義。1.4物流配送路線優(yōu)化現(xiàn)狀 國內(nèi)外相關(guān)領(lǐng)域?qū)RP問題的研究始于50年代，在理論研究和實際應(yīng)用兩方面都已取得了非常顯著的成果。隨著研究的深入發(fā)展,如何使研究的理論模型更貼近現(xiàn)實中的運輸規(guī)劃問題開始成為研究者們關(guān)注的焦點。車輛路線問題(VRP問題)是組合優(yōu)化領(lǐng)域中

25、著名的NP難題，近二十年來，無論在國內(nèi)還是國外，VRP問題都是一個非?；钴S的研究領(lǐng)域。目前國內(nèi)外用于解決該問題的現(xiàn)代數(shù)學(xué)方法主要分為以下幾類： （1）精確算法 精確算法是采用嚴密的數(shù)學(xué)手段進行計算的方法，在能夠求得可行解的情況下，其求得的結(jié)果一般要好于啟發(fā)算法。常見的精確算法有以下幾種：分枝定界法、割平面法、動態(tài)規(guī)劃法等。 分支定界法是一種應(yīng)用范圍很廣的搜索算法，它的基本思想是把給定問題分解為若干個較小的子問題，每個子問題又可繼續(xù)分解，直到子問題不能再分解或不能產(chǎn)生最優(yōu)解。根據(jù)問題的特點和不同的策略，把問題分解為子問題的過程稱之為分支。在分支過程，為每一子問題估算其對應(yīng)的目標值的界限稱之為定界

26、。定界的目的是為了測定界的趨勢，留下有價值的或尚不能判定的分支。刪除肯定不存在的最優(yōu)解的分支，稱之為剪支，以達到加速收斂、簡化運算的目的。對為題進行分解，確定子問題的解值界限，減去非優(yōu)的子問題，在進行新的分支，這樣一個分支到定界到剪支再到分支等反復(fù)的過程是分支定界法的基本算法步驟。不同的分支規(guī)則與定界方法，形成了同一問題的不同分支定界方法。 割平面法是由高莫瑞1958年提出的，故又稱為Gomory的割平面法。它的基本思想是：不斷增加線性約束條件（幾何術(shù)語稱為割平面）將原規(guī)劃問題的可行域切割掉一部分，使其切割掉的部分只包含非整數(shù)(zhngsh)解，沒有切割掉任何整數(shù)可行解，直到切割后得到的可行域

27、有一個整數(shù)坐標的極點恰好是問題的最優(yōu)解為止。針對求解的決策變量是全部取整還是部分取整問題，割平面算法中就分成了兩種計算方法，前者稱為分數(shù)算法，后者稱為混合整數(shù)算法。 動態(tài)(dngti)規(guī)劃法是20世紀50年代由貝爾曼（R. Bellman）等人提出,用來解決多階段決策過程問題的一種最優(yōu)化方法。所謂多階段決策過程,就是把研究問題分成若干個相互聯(lián)系的階段,由每個階段都作出決策,從而使整個過程達到最優(yōu)化。許多實際問題利用動態(tài)規(guī)劃法處理,常比線性規(guī)劃法更為有效,特別是對于那些離散型問題。實際上,動態(tài)規(guī)劃法就是分多階段進行決策,其基本思路是：按時空特點將復(fù)雜問題劃分為相互聯(lián)系的若干個階段,在選定系統(tǒng)行進

28、方向之后,逆著這個行進方向,從終點向始點計算,逐次對每個階段尋找某種決策,使整個過程達到最優(yōu),故又稱為逆序決策過程。 精確式算法領(lǐng)域的研究主要是針對某一特定問題而設(shè)計，實際應(yīng)用范圍有限，基本是在傳統(tǒng)物流配送模式下來考慮問題、改進模型和設(shè)計算法。該方法不能保證所得出的最終解是最優(yōu)整數(shù)解，但其一定是非常接近最優(yōu)解的。隨著車輛運輸調(diào)度系統(tǒng)的復(fù)雜化和調(diào)度目標的增加，問題的數(shù)據(jù)量會變得越來越大，利用精確算法求解問題就會變得十分困難，于是研究者們開始考慮利用啟發(fā)算法來解決這類問題。啟發(fā)方法是指人們根據(jù)經(jīng)驗規(guī)則來發(fā)現(xiàn)問題的滿意(mny)解的方法。用啟發(fā)式方法求解問題時往往注重求得滿意解而非最優(yōu)解。啟發(fā)式算法

29、分為傳統(tǒng)啟發(fā)式算法和現(xiàn)代啟發(fā)式算法兩種。 （2）傳統(tǒng)啟發(fā)式算法 傳統(tǒng)的啟發(fā)式算法主要有節(jié)約法、掃描法等。 節(jié)約里程法又稱節(jié)約算法或 HYPERLINK /doc/5379092.html t /doc/_blank 節(jié)約法，是指用 HYPERLINK /doc/4332348.html t /doc/_blank 來解決運輸車輛數(shù)目不確定的 HYPERLINK /doc/6783977.html t /doc/_blank VRP問題的最有名的 HYPERLINK /doc/6658906.html t /doc/_blank 啟發(fā)式算法。節(jié)約里程法基本規(guī)定， HYPERLINK /doc/2

30、519078.html 利用節(jié)約法確定配送路線的主要出發(fā)點是，根據(jù) HYPERLINK /doc/199749.html t /doc/_blank 配送中心的 HYPERLINK /doc/5687912.html t /doc/_blank 運輸能力和配送中心到各個用戶以及各個用戶之間的距離來制定使總的車輛運輸?shù)膰嵐飻?shù)最小的 HYPERLINK /doc/199749.html t /doc/_blank 配送方案。另還需滿足以下條件；1）所有用戶的要求；2）不使任何一輛車超載；3）每輛車每天的總 HYPERLINK /doc/4101580.html t /doc/_blank 運行時

31、間或行駛里程不超過規(guī)定的上限；4）用戶到貨時間要求?；舅枷?HYPERLINK /doc/2519078.html 是，為達到高效率的配送，使配送的時間最小距離最短成本最低，而尋找的最佳配送路線。近年來，由于小批量、多批次的及時配送方式的發(fā)展,運輸費用正在逐年提升，許多企業(yè)的運費己經(jīng)超越了庫存費用。選擇有效的配送路線，己成為控制物流成本的主要措施。那么如何選擇有效的配送路線呢？現(xiàn)代企業(yè)已經(jīng)普遍接受了一種觀點，即有效的配送路線實際上是在保證商品準時到達客戶指定點的前提下，盡可能地減少運輸?shù)能嚧魏瓦\輸?shù)目偮烦獭Ｔ谶@種思想的指導(dǎo)下，節(jié)約法已成為選擇配送路線的主要方法，并受到國內(nèi)外物流界的青睞。 掃

32、描法是Gillett和Miller于1974年所提出的求解車輛路線問題（Vehicle Routing Problem,VRP）的方法，此方法屬于先分群再排路線的方式。該方法采用極坐標來表示各需求點的區(qū)位，然后任取一需求點為起始點，定其角度為零度，以順時鐘或 HYPERLINK /sowiki/%E9%80%86%E6%97%B6%E9%92%9F?prd=content_doc_search o 逆時鐘 逆時鐘方向，以車容量為限制條件進行服務(wù)區(qū)域之分割，再借由Lin與Kernighan的交換法進行需求點的排序，建構(gòu)車輛排程路線。一般情況下，制定從一個物流中心向多個用戶運送貨物的配送計劃時，必

33、須考慮每輛車的運載能力和行駛距離及時間等的限制。其中掃描法是一種能較好地解決配送路線問題的有效方法，它的基本思路是采用逐次逼近的方法來解決問題。 （3）現(xiàn)代(xindi)啟發(fā)式算法 現(xiàn)代啟發(fā)式算法主要有禁忌搜索算法、遺傳算法、蟻群算法、粒子群算法等。用現(xiàn)代啟發(fā)算法對問題的求解(qi ji)是通過大規(guī)模的迭代來實現(xiàn)的，現(xiàn)代啟發(fā)算法自身具有一套獨特的搜索規(guī)則。為了求得滿意解，算法在迭代中要不斷采納和分析新信息，必要情況下需要變更原來的策略，建立新的搜索規(guī)則，同時要注意從失敗的搜索中取得經(jīng)驗教訓(xùn)，逐漸減小搜索的范圍。隨后從多個可行解中找出滿意解。 1）禁忌(jnj)搜索法 Gendreaut 等人（

34、1991）最先將禁忌搜索法應(yīng)用于車輛路徑優(yōu)化問題。先構(gòu)造一系列的解，然后對所得到的結(jié)果不斷地改進。該算法所得到的解不一定是可行解，它們對可行性的偏離程度體現(xiàn)在目標函數(shù)里的懲罰函數(shù)值的大小。禁忌搜索法是針對車輛路線優(yōu)化問題的較好的現(xiàn)代啟發(fā)式算法，在許多經(jīng)典的車輛路線優(yōu)化問題的求解中都已經(jīng)被成功地運用。 2）遺傳算法 近年來，一類基于生物學(xué),物理學(xué)和人工智能的具有全局優(yōu)化能力、魯棒性強、通用性強且適于并行處理的現(xiàn)代啟發(fā)式算法得到了發(fā)展。因其高效的優(yōu)化性能、無需問題特殊信息等優(yōu)點，廣泛用于計算機科學(xué)、優(yōu)化調(diào)度、運輸問題、組合優(yōu)化、工程優(yōu)化等領(lǐng)域。遺傳算法是其中具有代表性的一種現(xiàn)代啟發(fā)式方法。 3）蟻

35、群算法 蟻群算法蟻群算法（ant colony optimization,，ACO）又稱螞蟻算法，是一種用來尋找最優(yōu)解決方案的機率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。螞蟻在路徑上前進時會根據(jù)前邊走過的螞蟻所留下的分泌物選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強度成正比。因此，由大量螞蟻組成的群體的集體行為實際上構(gòu)成一種學(xué)習(xí)信息的正反饋現(xiàn)象：某一條路徑走過的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個體間通過這種信息的交流尋求通向食物的最短路徑。蟻群算法就是根據(jù)這一特點，通過模仿螞蟻的行為

36、，從而實現(xiàn)尋優(yōu)。這種算法有別于傳統(tǒng)編程模式，其優(yōu)勢在于，避免了冗長的編程和籌劃，程序本身是基于一定規(guī)則的隨機運行來尋找最佳配置。也就是說，當程序最開始找到目標的時候，路徑幾乎不可能是最優(yōu)的，甚至可能是包含了無數(shù)錯誤的選擇而極度冗長的。但是，程序可以通過螞蟻尋找食物的時候的信息素原理，不斷地去修正原來的路線，使整個路線越來越短，也就是說，程序執(zhí)行的時間越長，所獲得的路徑就越可能接近最優(yōu)路徑。這看起來很類似與我們所見的由無數(shù)例子進行歸納概括形成最佳路徑的過程。實際上好似是程序的一個自我學(xué)習(xí)的過程。 4）粒子群算法 Kennedy 和 Eberhart 在 1995 年首次提出了粒子群算法，該算法基

37、于對鳥類飛行覓食行為的模擬，群體達到最優(yōu)目標是通過鳥群個體之間的協(xié)作行為實現(xiàn)的。粒子群算法與遺傳算法類似，它們的共同點是運算方式基于群體的迭代，但粒子群算法沒有變異、交叉和算子的復(fù)制，群體在解可行域中追逐最優(yōu)粒子不斷搜索直到找到滿意解。粒子群算法的優(yōu)點為：個體數(shù)量少、計算簡單、魯棒性好、容易實現(xiàn)，并有著深刻的智能背景，適合于科學(xué)研究及工程應(yīng)用。粒子群算法源于對鳥群捕食行為的研究。鳥群捕食場景為：鳥群在一片固定區(qū)域內(nèi)尋找食物，但在這個區(qū)域內(nèi)食物只有一塊，群內(nèi)的每一只鳥的搜索行為都具有隨機性。鳥群中的所有個體都不清楚在哪里可以找到食物，但個體知道自身位置與食物間的距離。對于這個群體來說尋找食物的最

38、簡單有效的策略就是搜尋目前離食物最近的個體周圍的區(qū)域，粒子群算法正是基于上述方式解決優(yōu)化問題的。粒子群算法求解優(yōu)化問題時，每一個潛在解可以被看做是空間中進行搜索的一只鳥，我們將之稱為“粒子”。所有的粒子與相關(guān)優(yōu)化函數(shù)之間都有適應(yīng)值，這個適應(yīng)值由優(yōu)化函數(shù)決定，粒子自身具有速度，粒子的速度決定粒子本身的飛行距離和方向。所有的粒子追隨目前的最優(yōu)粒子在可行區(qū)域內(nèi)搜尋最優(yōu)解。粒子群算法隨機初始化一定數(shù)量的粒子，它尋找最優(yōu)解的方式是通過多次迭代。每次迭代粒子追逐個體極值及全局極值來更新自己。2理論(lln)基礎(chǔ)2.1物流配送問題的基本(jbn)理論2.1.1配送(pi sn)路線問題模型采用科學(xué)的、合理的

39、方法來確定配送線路，成為提高物流配送車輛效益、實現(xiàn)物流配送科學(xué)化的重要途徑。在滿足客戶配送需求的前提下，如何選擇配送路線，是一項很重要的工作。配送作業(yè)的時效性和高效性主要受車輛路線的安排與調(diào)度方案優(yōu)化情況的影響。配送路線優(yōu)化問題由來已久，其可以描述如下，見圖 2-1。客戶點配送中心圖2-1 配送路線優(yōu)化問題原理圖 有一個(y )（或者多個）配送中心，共有配送車輛 K 輛（一種或者多種車型），車輛載重量為Q1，Q2，Qk共有(n yu) I 位客戶等待被服務(wù)，每位客戶都有各自需求量G1，G2，Gi。從配送中心出發(fā)的配送車輛對等待服務(wù)的客戶進行配送，以滿足客戶的要求（物品品種、數(shù)量、規(guī)格的要求，配

40、送時間的要求），最后返回配送中心。要求所有客戶都被服務(wù)到，同時配送車輛不能超載。最終(zu zhn)求出車輛配送路線方案，并達到一定的優(yōu)化目標（如路程最短、費用最少、時間盡量少等）。車輛路線優(yōu)化問題是 NP 難題。自從它被提出以來，由于其應(yīng)用的廣泛性和在經(jīng)濟上的價值，一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。配送路線優(yōu)化問題的主要構(gòu)成要素為：配送車輛、貨物、客戶、配送中心、路網(wǎng)。各要素具體說明如下。 （1）車輛，其主要屬性有：車輛類型、裝載量、最大行駛距離、配送開始前與完成后所在的配送中心。 （2）貨物，其主要屬性有：重量、送達時間和送達地點等。貨物能否裝在同一配送車輛上取決于貨物屬性。 （3）客戶，其主

41、要屬性有：需求(或供應(yīng))貨物的種類、接受服務(wù)的時間等。 （4）配送中心，其主要是用來進行集貨、分貨、配貨、送貨等物流作業(yè)，在不同的路線優(yōu)化問題中，配送中心的個數(shù)為一個或者多個。 （5）運輸網(wǎng)絡(luò)，其組成部分有配送中心、客戶點和車輛行駛路線等。2.1.2物流配送路線的優(yōu)化目標 對車輛配送路線問題進行優(yōu)化時，必須要有明確的目標和遵循的基本原則。配送路線優(yōu)化問題的優(yōu)化目標可以從以下幾個方面考慮： （1）配送效益最高或配送成本最低。 物流企業(yè)是以追求效益為主要目標的，通常用企業(yè)利潤來表示，即企業(yè)通常以利潤的最大化作為自身經(jīng)營的目的。配送成本對物流企業(yè)利潤有直接的影響，以成本最低作為優(yōu)化目標與物流企業(yè)利潤

42、的最大化有直接的聯(lián)系。當與成本及利潤相關(guān)的數(shù)據(jù)容易得到和計算時，就可以用利潤最大或以成本最低作為優(yōu)化目標。 （2）配送里程最短。 當配送成本與配送里程具有較強的相關(guān)特性，與除此之外的其它因素相關(guān)特性較弱時，配送里程最短就近似等同于配送成本最低。這時可以考慮用配送里程最短作為優(yōu)化目標，這樣就可以大大簡化配送路線優(yōu)化方法。當配送成本與配送里程的相關(guān)性不明顯優(yōu)于其它因素的時候，如考慮車輛載重情況、道路運行條件等因素，單以路線最短作為優(yōu)化目標就變得不適宜。 （3）配送服務(wù)水平最優(yōu)。 當準時性成為配送的第一要求，或當出現(xiàn)某些特殊情況需要確保服務(wù)水平而忽略配送成本時，則應(yīng)盡量在成本不出現(xiàn)失控的情況下，以服

43、務(wù)水平最優(yōu)為優(yōu)化目標。優(yōu)質(zhì)的服務(wù)可以采用較高的服務(wù)價格，從而保證企業(yè)的合理利潤。 （4）配送(pi sn)勞動的消耗最小。 它是以物化勞動和活勞動消耗最小為優(yōu)化目標，在許多情況下，如人員緊張、燃料緊張、車輛(chling)設(shè)備緊張等，限制了配送作業(yè)，這時就可以考慮以配送所需要的人員、車輛或其它相關(guān)資源消耗最小作為優(yōu)化目標。實際上，配送路線優(yōu)化問題的優(yōu)化目標是多元的，但是考慮到優(yōu)化目標的目標值應(yīng)當符合實際情況，一般要盡可能取得實用性較強的目標值。因此，本文采用成本最低作為優(yōu)化目標。2.1.3配送(pi sn)車輛路線優(yōu)化問題的約束條件 現(xiàn)實中，配送車輛路線優(yōu)化問題存在著很多方面的約束條件，這些約

44、束條件使得該問題在研究和應(yīng)用上產(chǎn)生了許多不同的方向和型態(tài)，基于前文所述的分類標準，一些最重要的約束條件包括： （1）容量約束。任意配送車輛所搭載的貨物總量不能超過該車輛的載重能力。 （2）配送中心數(shù)目約束。配送中心有一個或者多個。 （3）優(yōu)先約束。客戶之間服務(wù)的次序存在著限制。 （4）車型約束。不同客戶的配送要求需要由不同車型來滿足。 （5）時間窗約束。包括硬時間窗約束和軟時間窗約束。 （6）隨機約束?？蛻魯?shù)量、配送需求、行駛路線等隨機出現(xiàn)。 （7）車速約束。車速是否穩(wěn)定。 （8）相容性約束?？蛻羰欠窨梢员徊煌渌蛙囕v（配送中心）服務(wù)。 通過以上分析，本文所要研究的配送車輛路線優(yōu)化問題所采用的

45、約束條件為：每個客戶只能被一輛車服務(wù)，每個被服務(wù)客戶沒有優(yōu)先次序，配送車輛的載重情況不超過自身的載重能力，每個客戶對其被服務(wù)的時間窗的要求為軟時間窗模式。2.1.4配送路線優(yōu)化問題的分類 對配送車輛路線問題類型分析是進一步對問題進行建模和求解的基礎(chǔ)。現(xiàn)有的對配送路線優(yōu)化問題的分類大致有以下八種:分類依據(jù)分類具體分類說明按任務(wù)特征分只送貨問題只送貨問題的特征為：配送車輛僅考慮從配送中心向客戶送貨；只取貨問題的特征為：配送車輛僅考慮從各客戶處把供應(yīng)的貨物取到配送中心；取送貨混合問題的特征為：既考慮將客戶需求的貨物從配送中心送到各個客戶只取貨問題混合問題按配送中心數(shù)目分單一車場問題單一車場問題的特征

46、為：配送系統(tǒng)中只有一個車場、貨場或配送中心；多個車場問題的特征為：配送系統(tǒng)中有多個車場、貨場或配送中心多個車場問題按配送車輛類型數(shù)目分單一車型問題單一車型問題的特征為：配送作業(yè)所用車輛都是同一類型，即車輛的參數(shù)如：載重能力、最長行駛時間和單次作業(yè)的最大行駛距離等相同；反之多種車型問題的特征為配送作業(yè)所用的車輛類型不完全相同多個車型問題按配送車輛路線分車輛開放問題車輛封閉問題車輛開放問題的特征為：車輛完成其配送任務(wù)后可以不返回出發(fā)點；車輛封閉問題的特征為：車輛完成其配送任務(wù)后必須返回出發(fā)點按配送車輛卸載狀況分滿載問題滿載問題是指當客戶的需求量或提供量大于或者等于配送車輛的載重能力時，需要用一輛或

47、者多輛車來完成一項配送作業(yè)，其中大多數(shù)配送車輛要滿載運行；非滿載問題是指當客戶的需求量或提供量小于配送車輛的載重能力時，多個客戶的配送需求都可以由同一配送車輛來滿足，整個配送過程中配送車輛處于非滿載狀態(tài)；滿載和非滿載混合問題是指當一部分客戶的需求量或提供量大于或者等于配送車輛的載重能力，而一部分客戶的需求量或提供量小于配送車輛的載重能力時非滿載問題混合問題按客戶時間需求分無時間窗問題無時間窗問題的特點是客戶對服務(wù)時間無具體要求；有時間窗問題的特點是客戶要求配送車輛必須在規(guī)定的時間范圍內(nèi)將貨物送達或取走。有時間窗問題又可以分為硬時窗問題和軟間窗問題，其中硬時窗是指，客戶要求必須在指定的時間范圍內(nèi)

48、進行配送作業(yè)，不能提前也不能拖后否則需要等待或者不能為其服務(wù)，軟時窗是指，客戶要求配送車輛盡可能在規(guī)定的時間范圍為其服務(wù)但也可以提前或拖后，只是要受到一定的懲罰，如交罰金有時間床問題按優(yōu)化目標數(shù)分單目標問題單目標問題是指選擇某一最優(yōu)或較優(yōu)指標作為優(yōu)化目標，如配送路線最短。多目標問題則是指同時選擇多個最優(yōu)或較優(yōu)的指標作為優(yōu)化目標，如同時要求配送路線最短和成本最低。路線優(yōu)化模型的指標一般包括：配送時間最短、配送路線最短、成本最低。一般情況下這三個目標是統(tǒng)一的：距離最短，也就意味著時間最短，成本也最低，但是很多情況下，也有出現(xiàn)多目標不統(tǒng)一、甚至互相矛盾的可能多目標問題按客戶和路網(wǎng)特點分靜態(tài)問題靜態(tài)問

49、題的特征為：客戶的位置、數(shù)目、需求，以及天氣、路況等因素是確定的和已知的；動態(tài)問題的特征為：客戶的位置數(shù)目、需求，以及天氣、路況等因素是隨機變化的。動態(tài)問題表2-12.2典型配送(pi sn)車輛路線優(yōu)化問題的數(shù)學(xué)模型 本文此處以經(jīng)典的帶時間窗配送車輛路線優(yōu)化問題為例，來說明配送車輛路線優(yōu)化問題的一般模型(mxng)及表達方式。帶時間窗配送車輛路線優(yōu)化問題的一般描述為：有一個配送中心（含車場），擁有的配送車輛數(shù)為 K 輛，容量分別為 Qk（k=1，2，K）。有 I 個客戶點需要被服務(wù)，客戶點 i 的作業(yè)量為 Gi，配送車輛 k 到達客戶點 i 的時刻為kis ，并且客戶點 i 的配送作業(yè)需要在

50、規(guī)定的時間窗ETi，LTi內(nèi)完成，其中 ETi表示客戶點 i 允許配送作業(yè)開始的最早時間，LTi表示客戶點 i 允許配送作業(yè)開始的最遲時間。如果配送車輛到達客戶點 i 的時間早于 ETi，則配送車輛需要在客戶點 i 處等待(dngdi)，如果配送車輛到達客戶點 i 的時間晚于 LTi，則客戶點 i 的配送作業(yè)將被延遲進行，同時配送車輛需要接受處罰。 一般情況下帶時間窗路線優(yōu)化問題需要考慮以下幾個約束條件： （1）各客戶點只可以(ky)由一輛車配送且只能被配送一次，不考慮多輛車同時為一個客戶點服務(wù)的情況； （2）配送(pi sn)中心（或車場）只有一個，所有車輛從配送中心出發(fā)，車輛在完成所有作業(yè)

51、之后需要回到配送中心； （3）各配送(pi sn)線路上客戶點的作業(yè)總量不應(yīng)大于該線路上作業(yè)車輛的載重量； （4）每個客戶點的配送作業(yè)量必須小于為其服務(wù)的車輛的最大載重量，即只需一臺配送車輛即可滿足該客戶點的配送作業(yè)需求。對模型參數(shù)定義如下：客戶i由k車來服務(wù)其他車輛k由i到j(luò)其他表示客戶點 i 到客戶點 j 的運輸成本；表示配送車輛由于等待失去的機會成本；表示配送車輛由于遲到需要支付的罰金。在僅考慮裝載約束和時間窗約束的條件下，帶時間窗的配送車輛路線優(yōu)化模型可以表示為： 任意的k i=1，2，I j=1，2，I，任意的k i=1，2，I，任意(rny)的k=0或1i，j=1，2，,I，任意(

52、rny)的k=0或1 i=1，2，I，任意(rny)的k 其中式中的目標函數(shù)，表示為各客戶點配送的目標是使配送成本最小。目標函數(shù)由兩部分組成，前半部分為車輛在線路上進行配送時所消耗的運輸成本，后半部分為車輛在為各個客戶點進行配送的過程中，由早到所損失的機會成本及遲到所支付的罰金之和。這一目標函數(shù)的具體意義為：要在滿足配送路線最短的條件下，盡量考慮車輛配送的時間窗約束，以使得配送車輛運輸成本及時間成本兩者所代表的配送成本最低。該模型的不足是忽略了配送車輛載重情況及道路等級情況對車輛運輸成本的影響。3現(xiàn)代運籌學(xué)方法在物流配送路線優(yōu)化中的實際應(yīng)用3.1傳統(tǒng)啟發(fā)式節(jié)約法及其應(yīng)用3.1.1節(jié)約法描述 利

53、用里程節(jié)約法確定配送路線的主要出發(fā)點是，根據(jù)配送方的運輸能力及其到客戶之間的距離和各客戶之間的相對距離來制定使配送車輛總的周轉(zhuǎn)量達到或接近最小的配送方案。假設(shè)條件： （1）配送的是同一種或相類似的貨物； （2）各用戶的位置及需求量已知； （3）配送方有足夠的運輸能力； （4）設(shè)狀態(tài)參數(shù)為tij, tij是這樣定義的： tij=1,表示客戶I，J在同一送貨路線上；0，表示客戶I，J不在同一送貨線路上。 t0j =2表示由送貨點p0向客戶J單獨派車送貨。 且所有狀態(tài)參數(shù)應(yīng)滿足下式： 式中：N客戶數(shù) 利用節(jié)約法制定出的配送方案除了使總的周轉(zhuǎn)量最小外，還應(yīng)滿足： （1）方案能滿足所有客戶的到貨時間要求

54、； （2）不使車輛超載； （3）每輛車每天的總運行時間及里程滿足規(guī)定的要求。 如圖3-1所示，設(shè)p0為配送中心，分別(fnbi)向用戶pi和pj送貨。p0到pi和pj的距離(jl)分別為d0i和d0j，兩個(lin )用戶pi和pj之間的距離為dij，送貨方案只有兩種即配送中心p0向用戶pi, pj分別送貨和配送中心p0向用戶pi, pj同時送貨，如圖11-7a)和b)。比較兩種配送方案： 方案a）的配送路線為p0pip0pjp0,配送距離為da=d0i+d0j 方案b)配送路線p0pipjp0,配送距離為db=. d0i+d0j+dij 顯然，da不等于db，我們用sij表示里程節(jié)約量，即方

55、案b)比方案a)節(jié)約的配送里程： 根據(jù)節(jié)約法的基本思想，如果一個配送中心p0分別向N個客戶pj(j=1.2n)配送貨物，在汽車載重能力允許的前提下，每輛汽車的配送線路上經(jīng)過的客戶個數(shù)越多，里程節(jié)約量越大，配送線路越合理。圖3-13.1.2節(jié)約法應(yīng)用 例：某一配送中心p0向10個客戶pj(j=1,2,10)配送貨物，其配送網(wǎng)絡(luò)如圖3-2所示。圖中括號內(nèi)的數(shù)字表示客戶的需求量（T），線路上的數(shù)字表示兩節(jié)點之間的距離。配送中心有2t和4t兩種車輛可供使用，試制定最優(yōu)的配送方案。 圖3-2解：第一步：計算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計算配送中心與客戶(k h)及客戶之間的最短距離，結(jié)果見表3-

56、3。 P010P194P2795P3814105P48181496P58181715137P6313121011106P74141311121282P810111517181817119P97481315151510118P10表3-3 第二步：計算節(jié)約(jiyu)里程sij,結(jié)果(ji gu)見表3-4。P115P2811P34710P403610P500039P6000015P70000045P894000125P91381000009P10表3-4 第三步：將節(jié)約(jiyu)sij,進行(jnxng)分類，按從大到小的順序排列，得表3-5。節(jié)約里程(lchng)項目分類表序號路線節(jié)約里程

57、序號路線節(jié)約里程1p1p21513p6p752p1p101313p7p853p2p31113p8p954p3p41016p1p444p4p51016p2p946p1p9916p6p846p5p6919p2p536p9p10919p4p639p1p3821p7p929p2p10822p3p10111p2p4722p5p7112p3p6622p6p91表3-5 第四步：確定配送線路。從分類表中，按節(jié)約里程大小順序，組成線路圖。 （1）初始方案：對每一客戶分別單獨派車送貨，結(jié)果如圖3-6。圖3-6 初始(ch sh)方案 初始方案(fng n)：配送線路10條 配送(pi sn)距離：S0：148k

58、m 配送車輛：2t10（2）對方案進行修正1）按節(jié)約里程sij由達到小的順序，連接p1和p2, p1和p10，p2和p3,得修正方案1。配送線路：10條 配送距離：S1：109km 配送車輛：2t6+4t1 2）在剩余的Sij中，最大的是S3，4和S4，5，此時p4和p5都有可能并入線路A中，但考慮到車輛的載重量及線路均衡問題，連接p4和p5形成一個新的線路B，得修正方案2。 配送線路：6條 配送距離：S2：99km 配送車輛：2t5+4t1 3）接下來最大的Sij是S1，9和S5，6，由于此時p1已屬于線路A，若將p9并入線路A，車輛會超載，故只將p6點并入線路B，得修正方案3。 配送線路：

59、5條 配送距離：S3：90km 配送車輛：2t3+4t2 4）再繼續(xù)按Sij由大到小排出S9，10、S1，3、S2，10、S2，4、S3，6，由于與其相應(yīng)的用戶均已包含在已完成的線路里，故不予考慮。把S6，7對應(yīng)p7點并入線路B中，得修正方案4。 配送線路：4條 配送距離：S4：85km 配送車輛：2t2+4t2 （3）最終(zu zhn)方案：剩下的是S7，8，考慮到配送距離的平衡(pnghng)和載重量的限制，不將p8點并入(bn r)到線路B中，而是連接p8 和 p9 ，組成新的線路C，得到最終方案，這樣配送方案已確定：共存在3條配送線路，總的配送距離為80 km，需要的配送車輛為2t車

60、一輛，4t車3輛。3條配送線路分別為： 第一條配送線路A：p0p3p2 p1p10p0使用一輛4t車。 第二條配送線路B： p0p4p5 p6p7p0，使用一輛4t車。 第三條配送線路C： p0p8p9p0，使用一輛2t車。 最終方案： 配送線路：3條 配送距離：S4：80km 配送車輛：2t1+4t2 圖3-7 最終方案3.1.3節(jié)約法的優(yōu)缺點分析 （1）節(jié)約法的優(yōu)點 節(jié)約法一方面體現(xiàn)出優(yōu)化運輸過程，與一般方法相比縮短了運輸路程；另一方面，它也體現(xiàn)了物流配送網(wǎng)絡(luò)的優(yōu)勢，實現(xiàn)了企業(yè)物流活動的整合，而且思路簡單、清晰，便于執(zhí)行。正是如此，它受到國內(nèi)外物流配送業(yè)的青睞。 （2）節(jié)約法的缺點 第一，