1、 家樂福超市物流配送路線優化 安徽工業大學 學年論文之家樂福超市物流配送路線優化專業物流工程 班級姓名學號日期摘要在物流配送業務中，合理確定配送路徑是提商服務質量，降低配送成本，增加經濟效益的重要手段。物流配送系統中最優路線的選擇問題一直都是配送中心關注的焦點，針對當前家樂福物流配送體系不完善等方面的現狀，本文從可持續發展的角度，用系統的觀念，來研究家樂福物流配送體系，優化配送路線，使配送體系合理化。通過對家樂福超市現有物流配送路徑的分析研究，發現其中存在的一些問題，并由此提出解決辦法，結合背景材料，建立了數學模型，運用遺傳算法對家樂福物流配送路線進行優化選擇，并得出結果。由此可見，家樂福超市

2、原有的物流配送路線還可以進行再優化，從而達到運輸成本最小化的目標。關鍵詞：物流配送；路徑優化；節約里程算法目錄TOC o 1-3 h z u HYPERLINK l _Toc360615011 1.緒論 .緒論1.1 選題目的和意義配送是一項特殊的、綜合性的物流運動，其運行和發展有著深刻的社會根源和歷史背景。在市場經濟體系中，物流配送如同人體的血管，把國民經濟各個部分緊密地聯系在一起。配送是物流中一個重要的直接與消費者相連的環節，是將貨物從物流結點送達收貨人的過程，是在集貨、配貨基礎上，完全按用戶要求，包括種類、品種搭配、數量、時間等方面的要求所進行的運送，是“配”和“送”的有機結合形式。其主

3、要包括集貨作業、配貨作業、車載貨物的配裝、配送線路的確定。在生活中，基于電子商務的物流配送業務量逐漸增加，如果還沿用以前的物流方法來組織配送，會產生很多問題。這些問題歸納起來，包括以下幾點:1)服務質量的下降。電子商務的特征是交易量巨大和交易速度極快，而傳統物流配送的特點是人工調度、反應時間長。信息流與物流的矛盾會導致整個電子商務客戶服務的低效。也許客戶可以在幾十秒內完成一次交易，卻要等上一個星期才能收到貨物，這樣的服務只能逐漸失掉客戶。2)物流成本控制困難。傳統的物流配送大多是由人工調度的，在交易量較小的情況下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快，配送調度就會超出人工

4、的能力范圍，會導致大量的不合理調度的出現，物流成本無法控制。3)增加城市交通的負擔。物流配送調度的不合理，會使物流配送的行車路線變長，導致在運車輛增加，從而給本已擁擠的城市交通加重負擔。要解決以上的問題，使物流配送調度滿足以下目標準時送貨。就是要客戶選擇貨物送達他們指定地點的時間，要按照每個客戶的時間要求安排物流配送。總成本最低。總行車路徑最短。當前，物流的現代化水平不僅成為反映一個國家現代化程度和綜合國力的重要標志，也成為城市經濟發展水平的體現，被喻為促進經濟發展的“加速器”。物流配送是一種先進的現代物流形式，它不但給供應者和需求者帶來降低物流成本、享受優質服務的直接效益，而且還能為社會節省

5、運輸車次、緩解交通壓力、減少運輸污染、保護生態環。而今，由于小批量、多批次的及時配送方式的發展，運輸費用正在逐年提升，許多企業的運費已經超越了庫存費用，城市交通與改善物流的矛盾也愈演愈烈，城市交通混雜、阻塞、車輛噪音、尾氣污染、車禍事故和能源浪費等現象更加嚴重，若物流路線選擇的不合理，還會使物流配送的行車路線變長，導致在運車輛增加，從而給本己擁擠的城市交通加重負擔，這就勢必要選擇合理有效的運輸路線來減少重復運輸、倒流運輸、遷回運輸、單程運輸和空駛等，這樣不僅提高配送效率，控制了物流成本，而且可限制車輛在城市中的運行時間，有效緩解城市交通負擔。物流配送系統中最優路線的選擇問題一直都是配送中心關注

6、的焦點，對于城市配送而言，由于受交通堵塞和各種交通管制的影響，導致配送路徑尋優更具復雜性。所以本文通過對具有動態的交通堵塞和交通擁擠限制信息及靜態禁止通行等限制信息的實際配送網絡的描述，提出解決兩種限制情況下配送網絡尋優的方法，建立了配送網絡圖中權重確定模型，并基于此進一步建立了城市物流配送決策系統數學模型，運用二分領域搜索算法對其尋優。針對當前家樂福物流配送體系不完善等方面的現狀，本文從可持續發展的角度，用系統的觀念，來研究家樂福物流配送體系，優化配送路線，使配送體系合理化:一方面通過建立一種快速、高效、網絡化的物流組織系統降低物流成本，增加利潤;另一方面，增強家樂福的競爭力，使其配送系統相

7、應得到優化，從而使家樂福物流取得階段性成果，因此，對家樂福物流配送體系及其路線的優化問題進行研究將具有很大的現實意義。1.2 國內外物流配送路線優化研究現狀物流配送路線優化，是物流系統優化中關鍵的一環，也是電子商務活動不可缺少的內容。對物流配送路線優化，可以提高物流經濟效益，實現物流科學化。可以說對物流配送路線優化理論與方法進行系統研究是物流集約化發展，構建綜合物流系統，建立現代調度指揮系統，發展智能交通運輸系統和開展電子商務的基礎。配送路線合理與否對配送速度，成本，效益影響很大，特別是多用戶配送線路的確定更為復雜。采用科學的，合理的方法來確定配送路線，是配送活動中非常重要的一項工作。路線優化

8、問題最早是由DANTZIG和RAMSER于1959年提出的，由于這一問題的理論涉及很多學科，很多實際問題的理論抽象都可歸結為這一類問題，應用前景廣闊，所以很快便引起運籌學，應用數學，圖論與網絡分析，物流學科，交通運輸工程，管理科學與工程，計算機應用等學科的專家，工程技術人員和管理者的極大重視，自此，一直成為運籌學與組合優化領域的前沿與研究熱點問題。 在國外，物流配送路線優化問題已廣泛應用于生產，生活的各個方面。如報紙投遞及線路的優化，牛奶配送及送達線路的優化，電話預訂貨物的車輛線路設計，垃圾車的線路優化，連鎖商店的送貨的線路優化等等。目前，研究水平已有很大發展，其理論成果除在汽車運輸領域外，在

9、水運，航空，通訊，電力，工業管理，計算機應用等領域也有一定的應用，還用于航空乘務員輪班安排，輪船公司運送貨物經過港口與貨物安排的優化設計，交通車線路安排，生產系統中的計劃與控制等多種組合優化問題。在國內，該問題的系統研究還不多見。近年來有李軍等人課題組承擔的國家自然科學基金不確定信息條件下動態車輛路徑等研究工作。紀壽文等人根據深圳市科技園的實際路網圖，采用神經網絡的方法對運輸車輛優化調度進行了試驗研究。王正彬等人在分析VRP現有啟發式算法的基礎上，建立了考慮線路安排的物流配送方案模型，并提出了求解該問題的搜索算法。2. 家樂福超市配送路線現狀2.1 家樂福超市概況成立于1959年的家樂福集團是

10、大賣場業態的首創者，是歐洲第一大零售商，世界第二大國際化零售連鎖集團。現擁有11,000多家營運零售單位，業務范圍遍及世界30個國家和地區。集團以三種主要經營業態引領市場：大型超市，超市以及折扣店。此外，家樂福還在一些國家發展了便利店和會員制量販店。2004年集團稅后銷售額增至726.68億歐元，員工總數超過43萬人。2005年，家樂福在財富雜志編排的全球500強企業中排名第22位。法國家樂福集團是大型超級市場（Hypermarket）概念的創始者，于1963年在法國開設了世界上第一家大型超市。1999年8月30日家樂福兼并普羅莫代斯組成世界第二大零售集團。如今家樂福已發展成為歐洲最大、全球第

11、二大的零售商。2004年，家樂福集團被財富雜志評為全球500強企業的第22位。家樂福于1969年開始進入國際市場，目前在世界上31個國家和地區擁有一萬多家銷售網點，涉及的零售業態包括大賣場、超級市場、折扣店、便利店、倉儲式商店與電子商務，集團的50萬名員工正致力于為20億消費者服務。家樂福集團建立了全球性的采購網絡，向不同國家和地區的供應商采購具有市場競爭力的商品。家樂福的經營理念是以低廉的價格、卓越的顧客服務和舒適的購物環境為廣大消費者提供日常生活所需的各類消費品。家樂福對顧客的承諾是在價格、商品種類、質量、服務及便利性等各方面滿足消費者的需求。家樂福力爭通過自己的努力成為當地社區最好的購物

12、場所，為消費者帶來更多的實惠和便利，并攜手和各商業伙伴為當地經濟的繁榮做出貢獻。家樂福于1995年進入中國后，采用國際先進的超市管理模式，致力于為社會各界提供價廉物美的商品和優質的服務，受到廣大消費者的青睞和肯定，其“開心購物家樂福”、“一站式購物”等理念已經深入人心。如今，家樂福已成功地進入了中國的25個城市，在北至哈爾濱、南至深圳、西至烏魯木齊、東至上海的中國廣袤土地上開設了109家大型超市，聘請3萬多名員工。在在華外資零售企業中處于領先地位。家樂福還向中國引進迪亞折扣店和冠軍食品超市兩種業態。2004年，家樂福(中國)被國內媒體評為“在華最有影響力的企業”之一。2004年約有2億多人光顧

13、了家樂福在中國的各門店，其中68%為女性，32%乘公共汽車，37%步行，15%騎自行車，9%乘坐出租車或小轎車前往家樂福購物。家樂福成為了各地居民的好鄰居。通過多年的經營，家樂福向中國的商業界輸入了大型超市經營管理方面的技能和先進經驗，并對商品采購、營銷管理、資產管理以及人力資源開發等各方面實現現代化和本地化，為當地經濟發展做了積極的貢獻。2.2 家樂福超市配送路線作業現狀2.2.1 配送距離分析(1)配送需求點坐標：現在以家樂福物流配送中心為原點(0,0),建立直角坐標系,各商店的坐標如下表所示:X(km);Y(km) 表2-1分店所在地坐標分店與配送中心間距離坐標分店與配送中心間距離坐標X

14、Y1892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083 i=1，220；(2) 現有路線是固定不變且為已知,每條線路行駛距離可由表2-3求得, 配送中心與商店之間，商店與商店之間的距離分析如下表：表2-2 配送中心與分店之間,分店與分店之間的距離(0點表示配送中心)0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.8621

15、73.61.427153.6237.113625626.41306.12136101611191614181310137.15.17.2211234.57.86.1018345131314119.2209.24.51519.25196.1422112118050145.4311281038261533171814361753039363450037452641434020253624344139153369.22.8105143708.3189.26.44.224121204.2114.5234.5717616135.4458.30269.23.65.132209.22712148.53112

16、89.22111133126182602725237.11118214161712179177191412419.29.22705.86.132189.528132013289.210163.616118436.43.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.5147.1267.11215271820382024327.1323129014245.12023249.223136.415139.2262512201118181614011119.11714108.9148.53.6104.5153

17、619.2189.57.2524110193.6125223.615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.13.6160105.1195.11711135.19.21841111416201514231712181007.12615189.267.2514394.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93

18、.6195.1158.51902.2.2 車輛數分析所需車輛數分析(家樂福配送中心一年(365天)的車輛調度):表2-3車輛調度情況車輛運用數101291110111010891011運用天數2530364246494838241386表2-4車輛運用數所占比率車輛運用數相對比率累計比率120.070.07120.080.15110.100.25100.120.37120.130.50110.130.63130.130.76100.100.86140.070.93150.040.97130.020.99110.011.00則家樂福平均每天所用車輛數為12輛。2.2.3 需求量分析表2-5 每個

19、分店（一年365天）平均每天的需求量分店12345678910需求量2324123513分店11121314151617181920需求量23421213222.2.4 商品品種分析超市以滿足消費者對基本生活用品一次性購買需要為經營宗旨，是一種經營品項較多的零售業態。下面對商品進行分類分析。一、大分類大分類是超市最粗線條的分類。大分類的主要標準是商品特征，如畜產、水產、果菜、日配加工食品、一般食品、日用雜貨、日用百貨、家用電器等。為了便于管理，超級市場的大分類一般以不超過10個為宜。二、中分類 中分類是大分類中細分出來的類別。其分類標準主要有：(1)按商品功能與用途劃分。如日配品這個大分類下，

20、可分出牛奶、豆制品、冰品、冷凍食品等中分類。(2)按商品制造方法劃分。如畜產品這個大分類下，可細分出熟肉制品的中分類，包括咸肉、熏肉、火腿、香腸等。(3)按商品產地劃分。如水果蔬菜這個大分類下，可細分出國產水果與進口水果的中分類。三、小分類 小分類是中分類中進一步細分出來的類別。主要分類標準有：(1)按功能用途劃分。如“畜產”大分類中、“豬肉”中分類下，可進一步細分出“排骨”、“肉米”、“里肌肉”等小分類。(2)按規格包裝劃分。如“一般食品”大分類中、“飲料”中分類下，可進一步細分出“聽裝飲料”、“瓶裝飲料”、“盒裝飲料”等小分類。(3)按商品成份分類。如“日用百貨”大分類中、“鞋”中分類下，

21、可進一步細分出“皮鞋”、“人造革鞋”、“布鞋”、“塑料鞋”等小分類。(4)按商品口味劃分。如“糖果餅干”大分類中、“餅干”中分類下，可進一步細分出“甜味餅干”、“咸味餅干”、“奶油餅干”、“果味餅干”等小分類。四、單品單品是商品分類中不能進一步細分的、完整獨立的商品品項。如上海申美飲料有限公司生產的“355毫升聽裝可口可樂”、“125升瓶裝可口可樂”、“2升瓶裝可口可樂”、“2升瓶裝雪碧”，就屬于四個不同單品。需要說明的是，商品分類并沒有統一固定的標準，各超市公司可根據市場和自身的實際情況對商品進行分類。但商品分類應該以方便顧客購物、方便商品組合、體現企業特點為目的。具體分類如下表所示：食品日

22、用品1.糧油1.日化產品糧食米面淀粉食用油主食熟食豆制品其他糧油2.日雜用品2.果蔬3. 家居用品新鮮蔬菜新鮮水果食用菌蔬菜制品干果|堅果果蔬深加工其他果蔬4. 清潔用品及用具3.水產5.餐具鮮活水產品粗加工水產品精加工水產品其他水產6.廚具畜產7.日用小家電鮮活畜禽鮮肉類鮮蛋類鮮奶類肉制品蛋制品乳制品蜜制品8.家用塑料制品 4.糖酒飲料9.首飾糖類酒類茶葉軟飲料沖飲品冷飲咖啡豆|可可其他糖酒飲料10.衣物5.加工食品11.箱包,袋,皮具保健食品休閑食品方便食品罐頭食品特色食品調味品其他加工食品12. 文體用品6.煙草13.日用小五金煙葉香煙其他煙草14.休閑家具7.添加劑15.個人護理用品食

23、品添加劑 添加劑發酵制品16.衛浴用品8.包裝機17.炊具加工設備食品包裝其他機械包裝制冷設備18.灶具表2-6 商品品種2.3 家樂福超市配送現有路線問題分析家樂福的配送系統和信息系統是較落后的.家樂福至今沒有在中國建立起統一的配送體系,且計算機系統的開發和建立,要落后于競爭對手沃爾瑪好幾年.家樂福這種”滯后”的配送系統與信息系統是其戰略規劃的成果,因為商品的集中配送是連鎖商業帶來的,但是目前中國連鎖商業基礎非常薄弱,只有通過大的配送系統的完善和整合才能形成規模的,高效的,社會化的物流配送系統.家樂福配送路線的分配存在以下幾方面的問題：物流公司與門店之間的分布太分散，難以形成固定的配送線路送

24、貨難以達到及時難以保證適量的庫存而不壓貨路線里程未達最短費用消耗大勞力消耗大，運力難以適當分配，難以調度車輛配送車輛噸位公里數大配送未實現自動化配送未實現網絡化配送服務未實現系列化3.配送路線優化建模與求解3.1 研究對象目標設定物流配送常考慮以最小化總運輸成本或距離最短為目標，總運輸成本主要由由兩部分組成:(1)運輸固定成本：如服務所有客戶所需要的車輛數、總行駛距離(或總行駛時間)和與所使用的車輛有關的固定費用；(2)運輸營業成本：如司機的管理費,各種工作人員的工資等.家樂福超市的業務運輸成本是物流總成本的主要組成部分，占有56%。因此降低公司運輸成本成為提高公司效益的直接有效途徑。公司自有

25、貨運成本各項比例如下表：表3-1公司貨運成本比例表固定費用（22%）營業費用（78%）折舊費（租賃費）：裝卸工具，車庫，辦公室，水電，通迅，差旅費，公務車費用業務印刷費人力（司機）：工資,額外福利，裝卸費投資利息：車輛，車庫,辦公室管理成本：職工月工資,額外福利,旅游和娛樂費用,房屋維修費，牌照費，職工培訓費，宣傳費及業務手續費。車輛運營成本：燃料（燃油，潤滑油，過濾器）維修費（人工費+零部件）輪胎費，交通規費，養路費大修理基金提存道路服務：通行費,保險,許可證和登記費高速公路使用費,燃油司機費用占總營業成本的29.4%；維修費和折舊費占總營業成本的19.5%；其它的運營費用占總營業成本的32

26、.6%；燃料費占總營業成本的18.5%；表上所述：公司車輛運營成本占據了總運輸成本的78%。隨著道路服務政策的變化，車輛營業成本在公司總成本中所占比例日益增大。距離是影響運輸成本的主要因素，因為它直接對勞動、燃料和維修保養等變動成本發生作用。針對公司當前成本構成狀況，可以知道：通過優化公司配送路線，減少運輸車輛行駛總里程，可以減少車輛燃油費和道路服務費支出，進而減少物流總成本。因此，本文針對家樂福配送中心車輛路線優化問題，提出的目標是：總運輸成本最小化。594配送中心632781594配送中心632781配送中心分店車輛路線此問題可以描述為：這是一種分送式配送模型,是由一個供應點對多個客戶的共

27、同配送。對配送中心負責的需求網點（家樂福分店），確定適當的配送車輛行駛路線，使其從配送中心出發，有序地通過各個分店各一次，最后返回配送中心，并在滿足一定的約束條件下(如車輛容量限制、行駛里程限制、時間限制、顧客需求量、交發貨時間等)，達到費用最少的目標。本文研究的是不考慮時間窗的非滿載車輛優化調度問題。表述如下：將貨物從配送中心配送到各分配送中心,由分配送中心派出容量為的貨車承運，現有m輛車，各分店對所需求的貨物有一定的要求，第i個分店的貨運量為gi，（i=1，2l）已知，在途中只有卸貨任務,完成任務后返回配送中心,求滿足配送需求的費用最少行車線路。分配送中心1分配送中心1分配送中心2分配送中

28、心3分店1分店2分店3分店4配送中心圖3-2家樂福配送體系結構3.2 模型的構建為建模方便，需考慮以下幾個前提假設條件：（1）配送中心不會出現缺貨的可能并且對顧客的基本配送資料（需求量、地理位置）為已知，配送中心的位置也已知；（2）不考慮配送時間限制，即客戶對貨物的需求沒有時間窗的規定；（3）不考慮每輛車為每個客戶的服務時間，即不考慮每個客戶的卸貨時間；（4）一個配送中心根據配送條件可以負責多個客戶，即一個配送中心服務多個客戶；（5）車輛由配送中心出發，服務被指定的需求點后，再返回配送中心，區域內的需求點假設為固定數量且位置已知，不發生變動。（6）配送中心擁有一定數量的單一車型的配送車輛，且每

29、輛車的容量已知。（7）每條配送路徑上各客戶需求量之和不超過配送車輛的容量；（8）每個客戶只能由一輛配送車輛送貨；（9）每輛車配送總里程不超過其最大行駛距離；（10）各道路均順暢，不考慮交通堵塞擁擠等特殊情況。將配送中心編號為0，車輛編號為k，任務編號為i=1,2, 所有車型載重量單一，每輛汽車的最大載重量為g，需要向L個需求點送貨，每個需求點的需求量為，并且滿足，需求點i到j的運距為，配送中心到各個需求點的距離為，再設為第輛汽車配送的需求點數（=0表示未使用第輛汽車），用集合表示第k條路徑，其中的元素表示需求點在路徑中的順序為（不包括配送中心），令=0表示配送中心，為每輛車單位里程的行駛費用，

30、為每輛車的派遣費用，考慮運輸量約束,停車點車輛數目等約束,可以定義如下的基本模型: (3-1) (3-2) (3-3) (3-4) (3-5) (3-6)在上述模型中各個公式所代表的涵義如下：（3-1）式為目標函數，求總的配送費用最低；（3-2）式用于保證每條路徑上各個需求點的需求量和不超過汽車的載重量；（3-3）式表明每條路徑上的需求點數不超過總需求點數；（3-4）式表明每個需求點都得到配送服務；（3-5）式表示每條路徑的需求點的組成；（3-6）式表示當第輛汽車服務的客戶數大于或等于1時，說明該輛汽車參加了配送，則取，當第k輛汽車服務的客戶數小于1時，表示未使用該輛汽車，因此取；3.3 節約

31、算法3.3.1節約算法的基本原理節約算法的核心思想是將運輸問題中存在的兩個回路（0， ，i，0）和（0，j， ，0）合并成一個回路（0， ，i，j，0）。在上面的合并操作中，整個運輸問題的總運輸距離會發生變化，如果變化后總運輸距離下降，則稱節約了運輸距離6。相應的變化值，叫做節約距離，如式（1）所示。（1）調整過程如圖3所示。jjjji 0i 00ii 調整前 調整后圖3-3節約算法的圖像描述3.3.2節約里程算法主要步驟已知條件:需求點集=1,2, n,各點需求量,各點間最短距離。第一步,形成一個初始解。確定各車輛配送點集令, =1,2,n (先采取單點配送)。第二步,進行節約度的計算。計算

32、所有點對的節約度Cij，然后對計算結果進行升第三步，進行回路的合并。從升序排列的節約度序列中的最上面的值開始，直到節約里程Cij的隊列空為止,重復下列步驟:按照節約里程Cij隊列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內以及合并次數不超過2),將i, j連接起來,即可令。如果不是這樣,則從節約里程隊列中去除當前的節約里程，分析下一個客3.3.3基于節約算法的配送路線優化表3-2 每個分店（一年365天）平均每天的需求量分店12345678910需求量（噸）2324123513分店11121314151617181920需求量（噸）2342121322現

33、有路線是固定不變且為已知,每條線路行駛距離可由表3-2求得, 配送中心與商店之間，商店與商店之間的距離分析如下表：表3-3 配送中心與分店之間,分店與分店之間的距離(0點表示配送中心)0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.113625626.41306.12136101611191614181310137.15.17.2211234.57.86.1018345131314119.2209.24.51

34、519.25196.1422112118050145.4311281038261533171814361753039363450037452641434020253624344139153369.22.8105143708.3189.26.44.224121204.2114.5234.5717616135.4458.30269.23.65.132209.22712148.5311289.22111133126182602725237.11118214161712179177191412419.29.22705.86.132189.528132013289.210163.616118436.43

35、.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.5147.1267.11215271820382024327.1323129014245.12023249.223136.415139.2262512201118181614011119.11714108.9148.53.6104.5153619.2189.57.2524110193.6125223.615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.1

36、3.6160105.1195.11711135.19.21841111416201514231712181007.12615189.267.2514394.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93.6195.1158.5190設每個車輛的運輸能力是8噸，根據案例可知，家樂福平均每天所用車輛數為12輛。現在用節約算法對該配送線路問題進行求解。根據配送中心與分店之間,分店與分店之間的距離距離表，計算出用戶間的節約

37、里程，表3-4 節約值矩陣表12345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.533.6217.9080.24.60.70.213.20.40.209224.47.52761724.8-0.801024.46.49.530318.829.40.227.201123.65.48.32531824.9-0.823.926.801203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.44.43.47.4014

38、16.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201020.96.40.5016-0.14.38.510110100.29109.502.39.90017014.36.31509.2144.28121030.47.54601815.28.48.717.20.213.917.71.413.216.715.10.21.212.71.29.113.201920.40.51301.2112.243220.811.41.515100.202014.52.96.913.55.513.213.50.716.315.314.4

39、0.5613.40.58.44.59.24.50從表3-4中選出節約值最大值為33.6，其對應的兩點為4、7。4、7兩處的需求量之和為7，未超過一輛車的運輸能力8，因此，連接4、7成回路，即0-4-7-0.再將頂點4和7的節約值賦為0.結果如表3-5所示。表3-512345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.50217.9080.24.60.70.213.20.40.209224.47.52761724.8-0.801024.46.49.530318.82

40、9.40.227.201123.65.48.32531824.9-0.823.926.801203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.44.43.47.401416.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201020.96.40.5016-0.14.38.510110100.29109.502.39.90017014.36.31509.2144.28121030.47.54601815.28.48.717.20.213.917.71.413

41、.216.715.10.21.212.71.29.113.201920.40.51301.2112.243220.811.41.515100.202014.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50從表3-5中選出節約值最大為30，其對應的兩個頂點為4、10。如果連接4和10 ，則與上述線路合并，其總需求量為10，超過一輛車的運輸能力8，因此，4和10不能連接 ，7和10也不能連接，則將4、10與7、10的節約值賦為0。繼續選出節約值最大為30，其對應兩個頂點為5、19。5和19兩處的需求量之和為3，未超過一輛車的

42、運輸能力8，因此，連接,5、19成回路，即0-5-19-0.再將頂點5和19的節約值賦為0。繼續選出節約值最大為27.2，其對應兩個頂點為9、10。9和10兩處的需求量之和為4，未超過一輛車的運輸能力8，因此，連接9、10成回路，即0-9-10-0.再將頂點9和10的節約值賦為0。選出節約值最大為27，其對應的兩個頂點為4、9。如果連接4和9，則與上述兩條線路合并，其總需求量為11，超過一輛車的運輸能力8，因此，4和9不能連接 ，7和9也不能連接，則將4、9與7、9的節約值賦為0。選出節約值最大為26.8，其對應的兩個頂點為10、11。如果連接10和11 ，則與上述線路合并，其總需求量為6，未

43、超過一輛車的運輸能力8，因此，連接0-9-10-11-0成回路 ，則將9、11與10、11的節約值賦為0。同時，由于頂點10成回路的中間點，則與頂點10相關的節約值都賦為0，表示頂點10不可能再與其他點相連，其結果如下表所示。表3-612345678910111213141516171819201025.4038.74.804237.48.50530.40.520618.45.68.717.22.207237.48.5 0217.9080.24.60.70.213.20.40.209224.47.506170-0.801000000000001123.65.48.32531824.9-0.80

44、001203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.403.47.401416.94.98.55.52.516.716.3-0.316016.5-0.53.901504.40.50200.2118.200020.96.40.5016-0.14.38.510110100.2909.502.39.90017014.36.31509.2144.2801030.47.54601815.28.48.717.20.213.917.71.413.2015.10.21.212.71.29.113.201920.40.5101.2112.2402

45、20.811.41.515100.202014.52.96.913.55.513.213.50.716.3014.40.5613.40.58.44.59.24.50選出節約值最大為25，其對應的兩個頂點為4、11。如果連接4和11，則與上述兩條線路合并，其總需求量為13，超過一輛車的運輸能力8，因此，4和11不能連接 ，7和11也不能連接，則將4、11與7、11的節約值賦為0。選出節約值最大為25，其對應的兩個頂點為5、12。如果連接5和12，則與上述線路合并，其總需求量為6，未超過一輛車的運輸能力8，因此，連接0-12-5-19-0成回路，則將5、12與12、19的節約值賦為0。同時，由于頂

46、點5成回路的中間點，則與頂點5相關的節約值都賦為0，表示頂點5不可能再與其他點相連，其結果如下表所示。表3-712345678910111213141516171819201025.4038.74.804237.48.50500000618.45.68.717.2007237.48.5 0017.9080.24.60.70.200.40.209224.47.500170-0.801000000000001123.65.48.300180-0.80001203.4-0.5-100.2017.100-10133.4-0.21.72.403.63.44.65.403.47.401416.94.98.

47、55.5016.716.3-0.316016.5-0.53.901504.40.5000.2118.200020.96.40.5016-0.14.38.510010100.2909.502.39.90017014.36.31509.2144.2801030.47.54601815.28.48.717.2013.917.71.413.2015.10.21.212.71.29.113.201920.40.5101.2112.2402011.41.515100.202014.52.96.913.5013.213.50.716.3014.40.5613.40.58.44.59.24.50從表3-7中選

48、出節約值最大為23.6，其對應的兩個頂點為1、11。如果連接1和11 ，則與上述線路合并，其總需求量為8，未超過一輛車的運輸能力8，因此，連接0-9-10-11-1-0成回路，則將與頂點1、9、10、11相關的節約值都賦為0，表示頂點1、9、10、11不可能再與其他點相連，其結果如下表所示。表3-8123456789101112131415161718192010200304.80407.48.50500000605.68.717.200707.48.5 0017.90804.60.70.200.40.20900000000010000000000011000000000001203.4-0.

49、5-100.2017.10000130-0.21.72.403.63.44.60007.401404.98.55.5016.716.3-0.3000-0.53.901504.40.5000.2118.200020.96.40.501604.38.510010100.200002.39.90017014.36.31509.2144.200030.47.54601808.48.717.2013.917.71.40000.21.212.71.29.113.201900.40.5101.2112.2000011.41.515100.202002.96.913.5013.213.50.70000.561

50、3.40.58.44.59.24.50從表3-8中選出節約值最大為20.9，其對應的兩個頂點為12、15。如果連接12和15，則與上述線路合并，其總需求量為7，未超過一輛車的運輸能力8，因此，連接0-15-12-5-19-0成回路，則將5、15；12、15與15、19的節約值賦為0。同時，由于頂點12成回路的中間點，則與頂點12相關的節約值都賦為0，表示頂點12不可能再與其他點相連，其結果如下表所示。表3-9123456789101112131415161718192010200304.80407.48.50500000605.68.717.200707.48.5 0017.90804.60.

51、70.200.40.209000000000100000000000110000000000012000000000000130-0.21.72.403.63.44.6000001404.98.55.5016.716.3-0.300003.901504.40.5000.2118.200006.40.501604.38.510010100.200002.39.90017014.36.31509.2144.200000.47.54601808.48.717.2013.917.71.400001.212.71.29.113.201900.40.5101.2112.2000011.41.50100.2

52、02002.96.913.5013.213.50.70000613.40.58.44.59.24.50從表3-9中選出節約值最大為18.2，其對應的兩個頂點為8、15。如果連接8和15，則與上述線路合并，其總需求量為12，超過一輛車的運輸能力8，因此， 8、19；8、5；8、12和8、15也不能連接，則將8、19；8、5；8、12和8、15的節約值賦為0.繼續選出節約值最大為17.9，其對應的兩個頂點為6、7。如果連接6和7，則與上述線路合并，其總需求量為9，超過一輛車的運輸能力8，因此，6和7不能連接 ，4和6也不能連接，則將6、7和4、6的節約值賦為0。選出節約值最大為17.7，其對應的兩

53、個頂點為7、18。如果連接7和18，則與上述線路合并，其總需求量為10，超過一輛車的運輸能力8，因此，7和18不能連接 ，4和18也不能連接，則將7、18和4、18的節約值賦為0。選出節約值最大值為16.7，其對應的兩點為6、14。6、14兩處的需求量之和為4，未超過一輛車的運輸能力8，因此，連接6、14成回路，即0-6-14-0.再將頂點6、14的節約值賦為0.選出節約值最大為16.3，其對應的兩個頂點為7、14。如果連接7和14，則與上述兩條線路合并，其總需求量為11，超過一輛車的運輸能力8，因此，7和14不能連接 ，4和14也不能連接，則將7、14和4、14的節約值賦為0.選出節約值最大

54、為15，其對應的兩個頂點為4、17。如果連接4和17，則與上述線路合并，其總需求量為8，未超過一輛車的運輸能力8，因此，連接0-17-4-7-0成回路，則將與頂點4、7、17相關的節約值都賦為0，表示頂點4、7、17不可能再與其他點相連，其結果如下表所示。表3-10123456789101112131415161718192010200304.8040000500000605.68.70007000 0000804.60.7000.4009000000000100000000000110000000000012000000000000130-0.21.7003.604.6000001404.9

55、8.50000-0.300003.901504.40.5000.20000006.40.501604.38.5001000.200002.39.90017000000000000000001808.48.70013.901.400001.212.71.29.1001900.40.5001.2012.2000011.41.50100.202002.96.90013.200.70000613.40.58.409.24.50選出節約值最大為13.9，其對應的兩個頂點為6、18。如果連接6和18，則與上述線路合并，其總需求量為7，未超過一輛車的運輸能力8，因此，連接0-18-6-14-0成回路，則將6

56、、18與14、18的節約值賦為0。同時，由于頂點6成回路的中間點，則與頂點6相關的節約值都賦為0，表示頂點6不可能再與其他點相連，其結果如下表所示。表3-11123456789101112131415161718192010200304.804000050000060000007000 0000804.60.7000009000000000100000000000110000000000012000000000000130-0.21.700004.6000001404.98.50000-0.300003.901504.40.50000000006.40.501604.38.500000.200

57、002.39.90017000000000000000001808.48.700001.400001.201.29.1001900.40.5000012.2000011.41.50100.202002.96.900000.70000613.40.58.409.24.50選出節約值最大為13.4，其對應的兩個頂點為14、20。如果連接14和20，則與上述線路合并，其總需求量為9，超過一輛車的運輸能力8，因此，14和20不能連接 ，6和20；18和20也不能連接，則將6、20；14、20和18、20的節約值賦為0.選出節約值最大值為11.4，其對應的兩點為13、19。如果連接13和19，則與上述線

58、路合并，其總需求量為11，超過一輛車的運輸能力8，因此，13和19不能連接，13、19；13、5；13、12和13、15也不能連接，則將13、19；13、5；13、12和13、15的節約值賦為0.選出節約值最大為9.9，其對應的兩個頂點為14、16。如果連接14和16，則與上述線路合并，其總需求量為9，超過一輛車的運輸能力8，因此，14和16不能連接 ，6和16；18和16也不能連接，則將6、16；14、16和18、16的節約值賦為0.選出節約值最大為8.7，其對應的兩個頂點為3、18。如果連接3和18，則與上述線路合并，其總需求量為9，超過一輛車的運輸能力8，因此，3和18不能連接 ，3和1

59、8；3和6；3和14也不能連接，則將3、18；3、6和3、14的節約值賦為0.選出節約值最大為8.5，其對應的兩個頂點為3、16。如果連接3和16，其總需求量為4，未超過一輛車的運輸能力8，因此，連接3、16成回路，即0-3-16-0.再將頂點3和16的節約值賦為0.選出節約值最大為8.4，其對應的兩個頂點為2、18。如果連接2和18，則與上述線路合并，其總需求量為10，超過一輛車的運輸能力8，因此，2和18；2和6；2和14也不能連接，則將2、18；2、6和2、14的節約值賦為0.選出節約值最大為8.4，其對應的兩個頂點為16、20。如果連接16和20，其總需求量為6，未超過一輛車的運輸能力

60、8，因此，連接16、20成回路，即0-3-16-20-0.再將頂點16、20和3、20的節約值都賦為0. 同時，由于頂點16成回路的中間點，則與頂點16相關的節約值都賦為0，表示頂點16不可能再與其他點相連，其結果如下表所示。表3-12123456789101112131415161718192010200304.804000050000060000007000 0000804.60.7000009000000000100000000000110000000000012000000000000130-0.21.700004.600000140000000-0.300003.901504.40.