家樂福超市物流配送路線優(yōu)化論文

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

2、化選擇，并得出結(jié)果。由此可見，家樂福超市原有的物流配送路線還可以進行再優(yōu)化，從而達到運輸成本最小化的目標。關(guān)鍵詞關(guān)鍵詞：物流配送；路徑優(yōu)化；節(jié)約里程算法.目 錄1.緒論 .11.1 選題目的和意義.11.2 國內(nèi)外物流配送路線優(yōu)化研究現(xiàn)狀.22. 家樂福超市配送路線現(xiàn)狀 .32.1 家樂福超市概況.32.2 家樂福超市配送路線作業(yè)現(xiàn)狀.42.2.1 配送距離分析.42.2.2 車輛數(shù)分析.52.2.3 需求量分析.62.2.4 商品品種分析.62.3 家樂福超市配送現(xiàn)有路線問題分析.73.配送路線優(yōu)化建模與求解 .93.1 研究對象目標設(shè)定.93.2 模型的構(gòu)建.113.3 節(jié)約算法.123.

3、3.1 節(jié)約算法的基本原理 .123.3.2 節(jié)約里程算法主要步驟 .133.3.3 基于節(jié)約算法的配送路線優(yōu)化 .133.3.4 優(yōu)化后的配送線 .244.優(yōu)化結(jié)果分析 .254.1 優(yōu)化前結(jié)果.254.2 優(yōu)化后結(jié)果.254.3 結(jié)論.265.總結(jié)與建議 .27參考文獻: .28.1.1.緒論緒論1.11.1 選題目的和意義選題目的和意義配送是一項特殊的、綜合性的物流運動，其運行和發(fā)展有著深刻的社會根源和歷史背景。在市場經(jīng)濟體系中，物流配送如同人體的血管，把國民經(jīng)濟各個部分緊密地聯(lián)系在一起。配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)，是將貨物從物流結(jié)點送達收貨人的過程，是在集貨、配貨基礎(chǔ)

4、上，完全按用戶要求，包括種類、品種搭配、數(shù)量、時間等方面的要求所進行的運送，是“配”和“送”的有機結(jié)合形式。其主要包括集貨作業(yè)、配貨作業(yè)、車載貨物的配裝、配送線路的確定。在生活中，基于電子商務(wù)的物流配送業(yè)務(wù)量逐漸增加，如果還沿用以前的物流方法來組織配送，會產(chǎn)生很多問題。這些問題歸納起來，包括以下幾點:1)服務(wù)質(zhì)量的下降。電子商務(wù)的特征是交易量巨大和交易速度極快，而傳統(tǒng)物流配送的特點是人工調(diào)度、反應(yīng)時間長。信息流與物流的矛盾會導(dǎo)致整個電子商務(wù)客戶服務(wù)的低效。也許客戶可以在幾十秒內(nèi)完成一次交易，卻要等上一個星期才能收到貨物，這樣的服務(wù)只能逐漸失掉客戶。2)物流成本控制困難。傳統(tǒng)的物流配送大多是由人

5、工調(diào)度的，在交易量較小的情況下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快，配送調(diào)度就會超出人工的能力范圍，會導(dǎo)致大量的不合理調(diào)度的出現(xiàn)，物流成本無法控制。3)增加城市交通的負擔(dān)。物流配送調(diào)度的不合理，會使物流配送的行車路線變長，導(dǎo)致在運車輛增加，從而給本已擁擠的城市交通加重負擔(dān)。要解決以上的問題，使物流配送調(diào)度滿足以下目標準時送貨。就是要客戶選擇貨物送達他們指定地點的時間，要按照每個客戶的時間要求安排物流配送?？偝杀咀畹??？傂熊嚶窂阶疃?。當(dāng)前，物流的現(xiàn)代化水平不僅成為反映一個國家現(xiàn)代化程度和綜合國力的重要標志，也成為城市經(jīng)濟發(fā)展水平的體現(xiàn)，被喻為促進經(jīng)濟發(fā)展的“加速器” 。物

6、流配送是一種先進的現(xiàn)代物流形式，它不但給供應(yīng)者和需求者帶來降低物流成本、享受優(yōu)質(zhì)服務(wù)的直接效益，而且還能為社會節(jié)省運輸車次、緩解交通壓力、減少運輸污染、保護生態(tài)環(huán)。而今，由于小批量、多批次的及時配送方式的發(fā)展，運輸費用正在逐年提升，許多企業(yè)的運費已經(jīng)超越了庫存費用，城市交通與改善物流的矛盾也愈演愈烈，城市交通混雜、阻塞、車輛噪音、尾氣污染、車禍事故和能源浪費等現(xiàn)象更加嚴重，若物流路線選擇的不合理，還會使物流配送的行車路線變長，導(dǎo)致在運車輛增加，從而給本己擁擠的城市交通加重負擔(dān)，這就勢必要選擇合理有效的運輸路線來減少重復(fù)運輸、倒流運輸、遷回運輸、單程運輸和空駛等，這樣不僅提高配送效率，控制了物流

7、成本，而且可限制車輛在城市中的運行時間，有效緩解城市交通負擔(dān)。物流配送系統(tǒng)中最優(yōu)路線的選擇問題一直都是配送中心關(guān)注的焦點，對于城市配送而言，由于受交通堵塞和各種交通管制的影響，導(dǎo)致配送路徑尋優(yōu)更具復(fù).雜性。所以本文通過對具有動態(tài)的交通堵塞和交通擁擠限制信息及靜態(tài)禁止通行等限制信息的實際配送網(wǎng)絡(luò)的描述，提出解決兩種限制情況下配送網(wǎng)絡(luò)尋優(yōu)的方法，建立了配送網(wǎng)絡(luò)圖中權(quán)重確定模型，并基于此進一步建立了城市物流配送決策系統(tǒng)數(shù)學(xué)模型，運用二分領(lǐng)域搜索算法對其尋優(yōu)。針對當(dāng)前家樂福物流配送體系不完善等方面的現(xiàn)狀，本文從可持續(xù)發(fā)展的角度，用系統(tǒng)的觀念，來研究家樂福物流配送體系，優(yōu)化配送路線，使配送體系合理化:一

8、方面通過建立一種快速、高效、網(wǎng)絡(luò)化的物流組織系統(tǒng)降低物流成本，增加利潤;另一方面，增強家樂福的競爭力，使其配送系統(tǒng)相應(yīng)得到優(yōu)化，從而使家樂福物流取得階段性成果，因此，對家樂福物流配送體系及其路線的優(yōu)化問題進行研究將具有很大的現(xiàn)實意義。1.21.2 國內(nèi)外物流配送國內(nèi)外物流配送路線優(yōu)化研究現(xiàn)狀路線優(yōu)化研究現(xiàn)狀物流配送路線優(yōu)化，是物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)，也是電子商務(wù)活動不可缺少的內(nèi)容。對物流配送路線優(yōu)化，可以提高物流經(jīng)濟效益，實現(xiàn)物流科學(xué)化?？梢哉f對物流配送路線優(yōu)化理論與方法進行系統(tǒng)研究是物流集約化發(fā)展，構(gòu)建綜合物流系統(tǒng)，建立現(xiàn)代調(diào)度指揮系統(tǒng)，發(fā)展智能交通運輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)。配送路線合

9、理與否對配送速度，成本，效益影響很大，特別是多用戶配送線路的確定更為復(fù)雜。采用科學(xué)的，合理的方法來確定配送路線，是配送活動中非常重要的一項工作。路線優(yōu)化問題最早是由 dantzig 和 ramser 于 1959 年提出的，由于這一問題的理論涉及很多學(xué)科，很多實際問題的理論抽象都可歸結(jié)為這一類問題，應(yīng)用前景廣闊，所以很快便引起運籌學(xué)，應(yīng)用數(shù)學(xué)，圖論與網(wǎng)絡(luò)分析，物流學(xué)科，交通運輸工程，管理科學(xué)與工程，計算機應(yīng)用等學(xué)科的專家，工程技術(shù)人員和管理者的極大重視，自此，一直成為運籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與研究熱點問題。 在國外，物流配送路線優(yōu)化問題已廣泛應(yīng)用于生產(chǎn)，生活的各個方面。如報紙投遞及線路的優(yōu)化

10、，牛奶配送及送達線路的優(yōu)化，電話預(yù)訂貨物的車輛線路設(shè)計，垃圾車的線路優(yōu)化，連鎖商店的送貨的線路優(yōu)化等等。目前，研究水平已有很大發(fā)展，其理論成果除在汽車運輸領(lǐng)域外，在水運，航空，通訊，電力，工業(yè)管理，計算機應(yīng)用等領(lǐng)域也有一定的應(yīng)用，還用于航空乘務(wù)員輪班安排，輪船公司運送貨物經(jīng)過港口與貨物安排的優(yōu)化設(shè)計，交通車線路安排，生產(chǎn)系統(tǒng)中的計劃與控制等多種組合優(yōu)化問題。在國內(nèi)，該問題的系統(tǒng)研究還不多見。近年來有李軍等人課題組承擔(dān)的國家自然科學(xué)基金 不確定信息條件下動態(tài)車輛路徑 等研究工作。 紀壽文等人根據(jù)深圳市科技園的實際路網(wǎng)圖，采用神經(jīng)網(wǎng)絡(luò)的方法對運輸車輛優(yōu)化調(diào)度進行了試驗研究。王正彬等人在分析 vrp

11、 現(xiàn)有啟發(fā)式算法的基礎(chǔ)上，建立了考慮線路安排的物流配送方案模型，并提出了求解該問題的搜索算法。 .2.2. 家樂福超市配送路線現(xiàn)狀家樂福超市配送路線現(xiàn)狀2.12.1 家樂福超市概況家樂福超市概況成立于 1959 年的家樂福集團是大賣場業(yè)態(tài)的首創(chuàng)者，是歐洲第一大零售商，世界第二大國際化零售連鎖集團?，F(xiàn)擁有 11,000 多家營運零售單位，業(yè)務(wù)范圍遍及世界 30 個國家和地區(qū)。集團以三種主要經(jīng)營業(yè)態(tài)引領(lǐng)市場：大型超市，超市以及折扣店。此外，家樂福還在一些國家發(fā)展了便利店和會員制量販店。2004 年集團稅后銷售額增至726.68 億歐元，員工總數(shù)超過 43 萬人。2005 年，家樂福在財富雜志編排的

12、全球 500 強企業(yè)中排名第 22 位。法國家樂福集團是大型超級市場（hypermarket）概念的創(chuàng)始者，于 1963 年在法國開設(shè)了世界上第一家大型超市。1999 年 8 月 30 日家樂福兼并普羅莫代斯組成世界第二大零售集團。如今家樂福已發(fā)展成為歐洲最大、全球第二大的零售商。2004 年，家樂福集團被財富雜志評為全球 500 強企業(yè)的第 22 位。家樂福于 1969 年開始進入國際市場，目前在世界上 31 個國家和地區(qū)擁有一萬多家銷售網(wǎng)點，涉及的零售業(yè)態(tài)包括大賣場、超級市場、折扣店、便利店、倉儲式商店與電子商務(wù)，集團的 50 萬名員工正致力于為 20 億消費者服務(wù)。家樂福集團建立了全球性

13、的采購網(wǎng)絡(luò)，向不同國家和地區(qū)的供應(yīng)商采購具有市場競爭力的商品。家樂福的經(jīng)營理念是以低廉的價格、卓越的顧客服務(wù)和舒適的購物環(huán)境為廣大消費者提供日常生活所需的各類消費品。家樂福對顧客的承諾是在價格、商品種類、質(zhì)量、服務(wù)及便利性等各方面滿足消費者的需求。家樂福力爭通過自己的努力成為當(dāng)?shù)厣鐓^(qū)最好的購物場所，為消費者帶來更多的實惠和便利，并攜手和各商業(yè)伙伴為當(dāng)?shù)亟?jīng)濟的繁榮做出貢獻。家樂福于 1995 年進入中國后，采用國際先進的超市管理模式，致力于為社會各界提供價廉物美的商品和優(yōu)質(zhì)的服務(wù)，受到廣大消費者的青睞和肯定，其“開心購物家樂?！?、“一站式購物”等理念已經(jīng)深入人心。如今，家樂福已成功地進入了中國的

14、 25 個城市，在北至哈爾濱、南至深圳、西至烏魯木齊、東至上海的中國廣袤土地上開設(shè)了 109 家大型超市，聘請 3 萬多名員工。在在華外資零售企業(yè)中處于領(lǐng)先地位。家樂福還向中國引進迪亞折扣店和冠軍食品超市兩種業(yè)態(tài)。2004 年，家樂福(中國)被國內(nèi)媒體評為“在華最有影響力的企業(yè)”之一。2004 年約有 2 億多人光顧了家樂福在中國的各門店，其中 68%為女性，32%乘公共汽車，37%步行，15%騎自行車，9%乘坐出租車或小轎車前往家樂福購物。家樂福成為了各地居民的好鄰居。通過多年的經(jīng)營，家樂福向中國的商業(yè)界輸入了大型超市經(jīng)營管理方面的技能和先進經(jīng)驗，并對商品采購、營銷管理、資產(chǎn)管理以及人力資源

15、開發(fā)等各方面實現(xiàn)現(xiàn)代化和本地化，為當(dāng)?shù)亟?jīng)濟發(fā)展做了積極的貢獻。.2.22.2 家樂福超市配送路線作業(yè)現(xiàn)狀家樂福超市配送路線作業(yè)現(xiàn)狀2.2.12.2.1 配送距離分析配送距離分析(1)配送需求點坐標：現(xiàn)在以家樂福物流配送中心為原點(0,0),建立直角坐標系,各商店的坐標如下表所示:x(km);y(km) 表表 2-12-1 分店所在地坐標分店所在地坐標 i=1，2.20；20i20iy-y)x(xd）（(2) 現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表 2-3 求得, 配送中心與商店之間，商店與商店之間的距離分析如下表： 表表 2-22-2 配送中心與分店之間配送中心與分店之間, ,分店

16、與分店之間的距離分店與分店之間的距離(0(0 點表示配送中心點表示配送中心) )0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.1136256xy1892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083坐標分店與配送中心間距離.26.41306.121361016111916141

17、81310137.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.5311289.22111133126182602725237.1111821416171217917719141

18、2419.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.5153619.2189.57.2524110193.6125223.615112313153324202722

19、826245.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.6195.1158.51902.2.22.2.2 車輛數(shù)分析車輛數(shù)分析所需車輛數(shù)分析(家樂福配送中心一

20、年(365 天)的車輛調(diào)度):表表 2-32-3 車輛調(diào)度情況車輛調(diào)度情況車輛運用數(shù)101291110111010891011運用天數(shù)2530364246494838241386表表 2-42-4 車輛運用數(shù)所占比率車輛運用數(shù)所占比率車輛運用數(shù)相對比率累計比率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則家樂福平均每天所用車輛數(shù)為 12 輛。.2.2.32.2.3 需求量分析需求量分析表表 2-52-

21、5 每個分店（一年每個分店（一年 365365 天）平均每天的需求量天）平均每天的需求量分店12345678910需求量2324123513分店11121314151617181920需求量23421213222.2.42.2.4 商品品種分析商品品種分析超市以滿足消費者對基本生活用品一次性購買需要為經(jīng)營宗旨，是一種經(jīng)營品項較多的零售業(yè)態(tài)。下面對商品進行分類分析。一、大分類 大分類是超市最粗線條的分類。大分類的主要標準是商品特征，如畜產(chǎn)、水產(chǎn)、果菜、日配加工食品、一般食品、日用雜貨、日用百貨、家用電器等。為了便于管理，超級市場的大分類一般以不超過 10 個為宜。 二、中分類 中分類是大分類中細

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

23、飲料” 、 “瓶裝飲料” 、 “盒裝飲料”等小分類。 (3)按商品成份分類。如“日用百貨”大分類中、 “鞋”中分類下，可進一步細分出“皮鞋” 、 “人造革鞋” 、 “布鞋” 、 “塑料鞋”等小分類。 (4)按商品口味劃分。如“糖果餅干”大分類中、 “餅干”中分類下，可進一步細分出“甜味餅干” 、 “咸味餅干” 、 “奶油餅干” 、 “果味餅干”等小分類。 四、單品 單品是商品分類中不能進一步細分的、完整獨立的商品品項。如上海申美飲料有限公司生產(chǎn)的“355 毫升聽裝可口可樂” 、 “125 升瓶裝可口可樂” 、 “2 升瓶裝可口可樂” 、 “2 升瓶裝雪碧” ，就屬于四個不同單品。 .需要說明的

24、是，商品分類并沒有統(tǒng)一固定的標準，各超市公司可根據(jù)市場和自身的實際情況對商品進行分類。但商品分類應(yīng)該以方便顧客購物、方便商品組合、體現(xiàn)企業(yè)特點為目的。具體分類如下表所示：表表 2-62-6 商品品種商品品種2.32.3 家樂福超市配送現(xiàn)有路線問題分析家樂福超市配送現(xiàn)有路線問題分析家樂福的配送系統(tǒng)和信息系統(tǒng)是較落后的.家樂福至今沒有在中國建立起統(tǒng)一的配送體系,且計算機系統(tǒng)的開發(fā)和建立,要落后于競爭對手沃爾瑪好幾年.家樂福這種”滯后”的配送系統(tǒng)與信息系統(tǒng)是其戰(zhàn)略規(guī)劃的成果,因為商品的集中配送是連鎖商業(yè)帶來的,但是目前中國連鎖商業(yè)基礎(chǔ)非常薄弱,只有通過大的配送系統(tǒng)的完善和整合才能形成規(guī)模的,高效的,

25、社會化的物流配送系統(tǒng).家樂福配送路線的分配存在以下幾方面的問題：（1）物流公司與門店之間的分布太分散，難以形成固定的配送線路（2）送貨難以達到及時食品日用品1.糧油1.日化產(chǎn)品糧食 米面 淀粉 食用油 主食熟食 豆制品 其他糧油2.日雜用品2.果蔬3. 家居用品新鮮蔬菜 新鮮水果 食用菌 蔬菜制品 干果|堅果 果蔬深加工 其他果蔬4. 清潔用品及用具3.水產(chǎn)5.餐具鮮活水產(chǎn)品 粗加工水產(chǎn)品 精加工水產(chǎn)品 其他水產(chǎn)6.廚具畜產(chǎn)7.日用小家電鮮活畜禽 鮮肉類 鮮蛋類 鮮奶類 肉制品 蛋制品 乳制品 蜜制品 8.家用塑料制品 4.糖酒飲料9.首飾糖類 酒類 茶葉 軟飲料 沖飲品 冷飲 咖啡豆|可可

26、其他糖酒飲料10.衣物5.加工食品11.箱包,袋,皮具保健食品 休閑食品 方便食品 罐頭食品 特色食品 調(diào)味品 其他加工食品12. 文體用品6.煙草13.日用小五金煙葉 香煙 其他煙草14.休閑家具7.添加劑15.個人護理用品食品添加劑 添加劑 發(fā)酵制品16.衛(wèi)浴用品8.包裝機17.炊具加工設(shè)備 食品包裝 其他機械包裝 制冷設(shè)備18.灶具.（3）難以保證適量的庫存而不壓貨（4）路線里程未達最短（5）費用消耗大（6）勞力消耗大，運力難以適當(dāng)分配，難以調(diào)度車輛（7）配送車輛噸位公里數(shù)大（8）配送未實現(xiàn)自動化（9）配送未實現(xiàn)網(wǎng)絡(luò)化（10）配送服務(wù)未實現(xiàn)系列化3.3.配送路線優(yōu)化建模與求解配送路線優(yōu)化

27、建模與求解3.13.1 研究對象目標設(shè)定研究對象目標設(shè)定物流配送?？紤]以最小化總運輸成本或距離最短為目標，總運輸成本主要由.由兩部分組成:(1)運輸固定成本：如服務(wù)所有客戶所需要的車輛數(shù)、總行駛距離(或總行駛時間)和與所使用的車輛有關(guān)的固定費用；(2)運輸營業(yè)成本：如司機的管理費,各種工作人員的工資等.家樂福超市的業(yè)務(wù)運輸成本是物流總成本的主要組成部分，占有 56%。因此降低公司運輸成本成為提高公司效益的直接有效途徑。公司自有貨運成本各項比例如下表：表表 3-13-1 公司貨運成本比例表公司貨運成本比例表固定費用（22%）營業(yè)費用（78%）折舊費（租賃費）：裝卸工具，車庫，辦公室，水電，通迅，

28、差旅費，公務(wù)車費用業(yè)務(wù)印刷費人力（司機）：工資,額外福利，裝卸費投資利息：車輛，車庫,辦公室管理成本：職工月工資,額外福利,旅游和娛樂費用,房屋維修費，牌照費，職工培訓(xùn)費，宣傳費及業(yè)務(wù)手續(xù)費。車輛運營成本：燃料（燃油，潤滑油，過濾器）維修費（人工費+零部件）輪胎費，交通規(guī)費，養(yǎng)路費大修理基金提存道路服務(wù)：通行費,保險,許可證和登記費高速公路使用費,燃油司機費用占總營業(yè)成本的 29.4%；維修費和折舊費占總營業(yè)成本的 19.5%；其它的運營費用占總營業(yè)成本的 32.6%；燃料費占總營業(yè)成本的 18.5%；表上所述：公司車輛運營成本占據(jù)了總運輸成本的 78%。隨著道路服務(wù)政策的變化，車輛營業(yè)成本在

29、公司總成本中所占比例日益增大。距離是影響運輸成本的主要因素，因為它直接對勞動、燃料和維修保養(yǎng)等變動成本發(fā)生作用。針對公司當(dāng)前成本構(gòu)成狀況，可以知道：通過優(yōu)化公司配送路線，減少運輸車輛行駛總里程，可以減少車輛燃油費和道路服務(wù)費支出，進而減少物流總成本。因此，本文針對家樂福配送中心車輛路線優(yōu)化問題，提出的目標是：總運輸成本最小化。.594配送中心632781配送中心分店車輛路線圖圖 3-13-1 家樂福的配送模式家樂福的配送模式此問題可以描述為：這是一種分送式配送模型,是由一個供應(yīng)點對多個客戶的共同配送。對配送中心負責(zé)的需求網(wǎng)點（家樂福分店） ，確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序

30、地通過各個分店各一次，最后返回配送中心，并在滿足一定的約束條件下(如車輛容量限制、行駛里程限制、時間限制、顧客需求量、交發(fā)貨時間等)，達到費用最少的目標。本文研究的是不考慮時間窗的非滿載車輛優(yōu)化調(diào)度問題。表述如下：將貨物從配送中心配送到各分配送中心,由分配送中心派出容量為的貨車承運，現(xiàn)有 mq輛車，各分店對所需求的貨物有一定的要求，第 i 個分店的貨運量為gi， （i=1，2l）已知，在途中只有卸貨任務(wù),完成任務(wù)后返回配送中心,qgi求滿足配送需求的費用最少行車線路。圖圖 3-23-2 家樂福配送體系結(jié)構(gòu)家樂福配送體系結(jié)構(gòu)分配送中心 1分配送中心 2分配送中心 3.分店 1分店 2分店 3分店

31、 4.配送中心.3.23.2 模型的構(gòu)建模型的構(gòu)建為建模方便，需考慮以下幾個前提假設(shè)條件：（1）配送中心不會出現(xiàn)缺貨的可能并且對顧客的基本配送資料（需求量、地理位置）為已知，配送中心的位置也已知；（2）不考慮配送時間限制，即客戶對貨物的需求沒有時間窗的規(guī)定；（3）不考慮每輛車為每個客戶的服務(wù)時間，即不考慮每個客戶的卸貨時間；（4）一個配送中心根據(jù)配送條件可以負責(zé)多個客戶，即一個配送中心服務(wù)多個客戶；（5）車輛由配送中心出發(fā)，服務(wù)被指定的需求點后，再返回配送中心，區(qū)域內(nèi)的需求點假設(shè)為固定數(shù)量且位置已知，不發(fā)生變動。（6）配送中心擁有一定數(shù)量的單一車型的配送車輛，且每輛車的容量已知。（7）每條配送

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

33、kir求點在路徑中的順序為 （不包括配送中心） ，令=0 表示配送中心，為kirki0krm每輛車單位里程的行駛費用，為每輛車的派遣費用，考慮運輸量約束,停車點車c輛數(shù)目等約束,可以定義如下的基本模型: (3-1)cknnsignddmzkkikrrrrkkkknkiik 11)(min0)1( (3-2) ngqkkiir1 (3-3) lnk0 (3-4) lnkkk1 (3-5) ,.,2 , 1,.,2 , 1|kkikiknilrrr (3-6) 其他011)(kknnsign在上述模型中各個公式所代表的涵義如下：（3-1）式為目標函數(shù)，求總的配送費用最低；.（3-2）式用于保證每條

34、路徑上各個需求點的需求量和不超過汽車的載重量；（3-3）式表明每條路徑上的需求點數(shù)不超過總需求點數(shù)；（3-4）式表明每個需求點都得到配送服務(wù)；（3-5）式表示每條路徑的需求點的組成；（3-6）式表示當(dāng)?shù)谳v汽車服務(wù)的客戶數(shù)大于或等于 1 時，說明該輛汽車參k加了配送，則取，當(dāng)?shù)?k 輛汽車服務(wù)的客戶數(shù)小于 1 時，表示未使用1)(knsign該輛汽車，因此?。?)(knsign3.33.3 節(jié)約算法節(jié)約算法3.3.13.3.1 節(jié)約算法的基本原理節(jié)約算法的基本原理節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0， ，i，0）和（0，j， ，0）合并成一個回路（0， ，i，j，0） 。在上面的合

35、并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱節(jié)約了運輸距離6。相應(yīng)的變化值，叫做節(jié)約距離，如式（1）所示。ijc （1）ijioojjicccc調(diào)整過程如圖 3 所示。 調(diào)整前 調(diào)整后 圖圖 3-33-3 節(jié)約算法的圖像描述節(jié)約算法的圖像描述3.3.23.3.2 節(jié)約里程算法主要步驟節(jié)約里程算法主要步驟已知條件:需求點集=1,2, n,各點需求量,各點間最短距離。rnirijc第一步,形成一個初始解。確定各車輛配送點集令, 12,mi ii jij0ji 0ji.=1,2,n (先采取單點配送)。j第二步,進行節(jié)約度的計算。計算所有點對的節(jié)約度，然后對計算結(jié)果進

36、行升序排列。第三步，進行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始，直到節(jié)約里程的隊列空為止,重復(fù)下列步驟:按照節(jié)約里程隊列從大到小的順序,分析客戶 i 和 j 之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過 2),將 i, j 連接起來,即可令。;iijjiiii 如果不是這樣,則從節(jié)約里程隊列中去除當(dāng)前的節(jié)約里程，分析下一個客戶對。3.3.33.3.3 基于節(jié)約算法的配送路線優(yōu)化基于節(jié)約算法的配送路線優(yōu)化表表3-23-2 每個分店（一年每個分店（一年365365天）平均每天的需求量天）平均每天的需求量分店12345678910需求量（噸）23241235

37、13分店11121314151617181920需求量（噸）2342121322現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表3-2求得, 配送中心與商店之間，商店與商店之間的距離分析如下表：表表3-33-3 配送中心與分店之間配送中心與分店之間, ,分店與分店之間的距離分店與分店之間的距離(0(0點表示配送中心點表示配送中心) )0123456789101112131415161718192000126.44.522309.2179.2171613156.48.5115119.2158.51120137.811392.862173.61.427153.6237.113625626.413

38、06.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.5311289.22111133126182602725237.1111

39、8214161712179177191412419.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.5153619.2189.57.2524110193.6125223.

40、615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.13.6160105.1195.1.1711135.19.21841111416201514231712181007.12615189.267.2514394.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93.6195.1158.5190設(shè)每個車輛的運輸能力是 8 噸

41、，根據(jù)案例可知，家樂福平均每天所用車輛數(shù)為 12輛?，F(xiàn)在用節(jié)約算法對該配送線路問題進行求解。根據(jù)配送中心與分店之間,分店與分店之間的距離距離表，計算出用戶間的節(jié)約里程， 表表 3-43-4 節(jié)約值矩陣表節(jié)約值矩陣表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.

42、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.216.715.10.21.212.71.

43、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-4 中選出節(jié)約值最大值為 33.6，其對應(yīng)的兩點為 4、7。4、7 兩處的需求量之和為 7，未超過一輛車的運輸能力 8，因此，連接 4、7 成回路，即 0-4-7-0.再將頂點 4 和 7 的節(jié)約值賦為 0.結(jié)果如表 3-5 所示。.表表 3-53-512345678910111213141516171819201025.4038.74.804237.

44、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.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.401416.94.98.55.52.516.716.3-0.31617.316.5-0.53.901504.40.50200.2118.201

45、020.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.40.5613.40.58.44.59.24.50 從表 3-5 中選出節(jié)約值最大為 30，其對應(yīng)的兩個頂點為 4、10。如果連接4 和

46、10 ，則與上述線路合并，其總需求量為 10，超過一輛車的運輸能力 8，因此，4 和 10 不能連接 ，7 和 10 也不能連接，則將 4、10 與 7、10 的節(jié)約值賦為0。繼續(xù)選出節(jié)約值最大為 30，其對應(yīng)兩個頂點為 5、19。5 和 19 兩處的需求量之和為 3，未超過一輛車的運輸能力 8，因此，連接,5、19 成回路，即 0-5-19-0.再將頂點 5 和 19 的節(jié)約值賦為 0。繼續(xù)選出節(jié)約值最大為 27.2，其對應(yīng)兩個頂點為 9、10。9 和 10 兩處的需求量之和為 4，未超過一輛車的運輸能力 8，因此，連接 9、10 成回路，即 0-9-10-0.再將頂點 9 和 10 的節(jié)約

47、值賦為 0。選出節(jié)約值最大為 27，其對應(yīng)的兩個頂點為 4、9。如果連接 4 和 9，則與上.述兩條線路合并，其總需求量為 11，超過一輛車的運輸能力 8，因此，4 和 9 不能連接 ，7 和 9 也不能連接，則將 4、9 與 7、9 的節(jié)約值賦為 0。選出節(jié)約值最大為 26.8，其對應(yīng)的兩個頂點為 10、11。如果連接 10 和 11 ，則與上述線路合并，其總需求量為 6，未超過一輛車的運輸能力 8，因此，連接 0-9-10-11-0 成回路 ，則將 9、11 與 10、11 的節(jié)約值賦為 0。同時，由于頂點 10 成回路的中間點，則與頂點 10 相關(guān)的節(jié)約值都賦為 0，表示頂點 10 不可

48、能再與其他點相連，其結(jié)果如下表所示。表表 3-63-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.80001203.4-0.5-1250.2017.100-10133.4-0.21.72.411.43.63.44.65.403.47.401416.94.98.55.52.516.7

49、16.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.240220.811.41.515100.202014.52.96.913.55.513.213.50.716.3014.40.5613.40.58.44.59.24.50 選出節(jié)約值最大

50、為 25，其對應(yīng)的兩個頂點為 4、11。如果連接 4 和 11，則與上述兩條線路合并，其總需求量為 13，超過一輛車的運輸能力 8，因此，4 和.11 不能連接 ，7 和 11 也不能連接，則將 4、11 與 7、11 的節(jié)約值賦為 0。選出節(jié)約值最大為 25，其對應(yīng)的兩個頂點為 5、12。如果連接 5 和 12，則與上述線路合并，其總需求量為 6，未超過一輛車的運輸能力 8，因此，連接 0-12-5-19-0 成回路，則將 5、12 與 12、19 的節(jié)約值賦為 0。同時，由于頂點 5 成回路的中間點，則與頂點 5 相關(guān)的節(jié)約值都賦為 0，表示頂點 5 不可能再與其他點相連，其結(jié)果如下表所示

51、。表表 3-73-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.55.5016.716.3-0.316016.5-0.53.901504.40.5000.

52、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 中選出節(jié)約值最大為 23.6，其對應(yīng)的兩個頂點為 1、11。如果連接1 和 11 ，則與

53、上述線路合并，其總需求量為 8，未超過一輛車的運輸能力 8，因此，連接 0-9-10-11-1-0 成回路，則將與頂點 1、9、10、11 相關(guān)的節(jié)約值都賦為 0，表示頂點 1、9、10、11 不可能再與其他點相連，其結(jié)果如下表所示。表表 3-83-8.123456789101112131415161718192010200304.80407.48.50500000605.68.717.200707.48.5 0017.90804.60.70.200.40.20900000000010000000000011000000000001203.4-0.5-100.2017.10000130-0.2

54、1.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.5613.40.58.44.59.24.50從表 3

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

56、4.60.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.50

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

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

59、并，其總需求量為 11，超過一輛車的運輸能力 8，因此，7 和14 不能連接 ，4 和 14 也不能連接，則將 7、14 和 4、14 的節(jié)約值賦為 0.選出節(jié)約值最大為 15，其對應(yīng)的兩個頂點為 4、17。如果連接 4 和 17，則與上述線路合并，其總需求量為 8，未超過一輛車的運輸能力 8，因此，連接 0-17-.4-7-0 成回路，則將與頂點 4、7、17 相關(guān)的節(jié)約值都賦為 0，表示頂點 4、7、17不可能再與其他點相連，其結(jié)果如下表所示。表表 3-103-10123456789101112131415161718192010200304.8040000500000605.68.700

60、07000 0000804.60.7000.4009000000000100000000000110000000000012000000000000130-0.21.7003.604.6000001404.98.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.