學年論文之學年論文之 家樂福超市物流配送路線優(yōu)化家樂福超市物流配送路線優(yōu)化 專業(yè)專業(yè) 物流工程物流工程 班級班級 姓名姓名 學號學號 日期日期 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 摘要摘要 在物流配送業(yè)務中，合理確定配送路徑是提商服務質(zhì)量，降低配送成本，增 加經(jīng)濟效益的重要手段。物流配送系統(tǒng)中最優(yōu)路線的選擇問題一直都是配送中心 關注的焦點，針對當前家樂福物流配送體系不完善等方面的現(xiàn)狀，本文從可持續(xù) 發(fā)展的角度，用系統(tǒng)的觀念，來研究家樂福物流配送體系，優(yōu)化配送路線，使配 送體系合理化。 通過對家樂福超市現(xiàn)有物流配送路徑的分析研究，發(fā)現(xiàn)其中存在的一些問題， 并由此提出解決辦法，結(jié)合背景材料，建立了數(shù)學模型，運用遺傳算法對家樂福 物流配送路線進行優(yōu)化選擇，并得出結(jié)果。由此可見，家樂福超市原有的物流配 送路線還可以進行再優(yōu)化，從而達到運輸成本最小化的目標。 關鍵詞關鍵詞：物流配送；路徑優(yōu)化；節(jié)約里程算法 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 目 錄 1.緒論 .1 1.1 選題目的和意義1 1.2 國內(nèi)外物流配送路線優(yōu)化研究現(xiàn)狀2 2. 家樂福超市配送路線現(xiàn)狀 3 2.1 家樂福超市概況3 2.2 家樂福超市配送路線作業(yè)現(xiàn)狀4 2.2.1 配送距離分析4 2.2.2 車輛數(shù)分析5 2.2.3 需求量分析6 2.2.4 商品品種分析6 2.3 家樂福超市配送現(xiàn)有路線問題分析7 3.配送路線優(yōu)化建模與求解 .9 3.1 研究對象目標設定9 3.2 模型的構(gòu)建.11 3.3 節(jié)約算法.12 3.3.1 節(jié)約算法的基本原理 .12 3.3.2 節(jié)約里程算法主要步驟 .13 3.3.3 基于節(jié)約算法的配送路線優(yōu)化 .13 3.3.4 優(yōu)化后的配送線 .24 4.優(yōu)化結(jié)果分析 25 4.1 優(yōu)化前結(jié)果.25 4.2 優(yōu)化后結(jié)果.25 4.3 結(jié)論.26 5.總結(jié)與建議 27 參考文獻: .28 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 1 1.1.緒論緒論 1.11.1 選題目的和意義選題目的和意義 配送是一項特殊的、綜合性的物流運動，其運行和發(fā)展有著深刻的社會根源 和歷史背景。在市場經(jīng)濟體系中，物流配送如同人體的血管，把國民經(jīng)濟各個部 分緊密地聯(lián)系在一起。配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)，是將 貨物從物流結(jié)點送達收貨人的過程，是在集貨、配貨基礎上，完全按用戶要求， 包括種類、品種搭配、數(shù)量、時間等方面的要求所進行的運送，是“配”和“送” 的有機結(jié)合形式。其主要包括集貨作業(yè)、配貨作業(yè)、車載貨物的配裝、配送線路 的確定。 在生活中，基于電子商務的物流配送業(yè)務量逐漸增加，如果還沿用以前的物 流方法來組織配送，會產(chǎn)生很多問題。這些問題歸納起來，包括以下幾點: 1)服務質(zhì)量的下降。電子商務的特征是交易量巨大和交易速度極快，而傳統(tǒng) 物流配送的特點是人工調(diào)度、反應時間長。信息流與物流的矛盾會導致整個電子 商務客戶服務的低效。也許客戶可以在幾十秒內(nèi)完成一次交易，卻要等上一個星 期才能收到貨物，這樣的服務只能逐漸失掉客戶。 2)物流成本控制困難。傳統(tǒng)的物流配送大多是由人工調(diào)度的，在交易量較小 的情況下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快， 配送調(diào)度就會超出人工的能力范圍，會導致大量的不合理調(diào)度的出現(xiàn)，物流成本 無法控制。 3)增加城市交通的負擔。物流配送調(diào)度的不合理，會使物流配送的行車路線 變長，導致在運車輛增加，從而給本已擁擠的城市交通加重負擔。要解決以上的 問題，使物流配送調(diào)度滿足以下目標準時送貨。就是要客戶選擇貨物送達他們 指定地點的時間，要按照每個客戶的時間要求安排物流配送?？偝杀咀畹?。 總行車路徑最短。 當前，物流的現(xiàn)代化水平不僅成為反映一個國家現(xiàn)代化程度和綜合國力的重 要標志，也成為城市經(jīng)濟發(fā)展水平的體現(xiàn)，被喻為促進經(jīng)濟發(fā)展的“加速器” 。 物流配送是一種先進的現(xiàn)代物流形式，它不但給供應者和需求者帶來降低物流成 本、享受優(yōu)質(zhì)服務的直接效益，而且還能為社會節(jié)省運輸車次、緩解交通壓力、 減少運輸污染、保護生態(tài)環(huán)。 而今，由于小批量、多批次的及時配送方式的發(fā)展，運輸費用正在逐年提升， 許多企業(yè)的運費已經(jīng)超越了庫存費用，城市交通與改善物流的矛盾也愈演愈烈， 城市交通混雜、阻塞、車輛噪音、尾氣污染、車禍事故和能源浪費等現(xiàn)象更加嚴 重，若物流路線選擇的不合理，還會使物流配送的行車路線變長，導致在運車輛 增加，從而給本己擁擠的城市交通加重負擔，這就勢必要選擇合理有效的運輸路 線來減少重復運輸、倒流運輸、遷回運輸、單程運輸和空駛等，這樣不僅提高配 送效率，控制了物流成本，而且可限制車輛在城市中的運行時間，有效緩解城市 交通負擔。 物流配送系統(tǒng)中最優(yōu)路線的選擇問題一直都是配送中心關注的焦點，對于城 市配送而言，由于受交通堵塞和各種交通管制的影響，導致配送路徑尋優(yōu)更具復 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 2 雜性。所以本文通過對具有動態(tài)的交通堵塞和交通擁擠限制信息及靜態(tài)禁止通行 等限制信息的實際配送網(wǎng)絡的描述，提出解決兩種限制情況下配送網(wǎng)絡尋優(yōu)的方 法，建立了配送網(wǎng)絡圖中權(quán)重確定模型，并基于此進一步建立了城市物流配送決 策系統(tǒng)數(shù)學模型，運用二分領域搜索算法對其尋優(yōu)。 針對當前家樂福物流配送體系不完善等方面的現(xiàn)狀，本文從可持續(xù)發(fā)展的角 度，用系統(tǒng)的觀念，來研究家樂福物流配送體系，優(yōu)化配送路線，使配送體系合 理化:一方面通過建立一種快速、高效、網(wǎng)絡化的物流組織系統(tǒng)降低物流成本， 增加利潤;另一方面，增強家樂福的競爭力，使其配送系統(tǒ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)化中關鍵的一環(huán)，也是電子商務活動不可 缺少的內(nèi)容。對物流配送路線優(yōu)化，可以提高物流經(jīng)濟效益，實現(xiàn)物流科學化。 可以說對物流配送路線優(yōu)化理論與方法進行系統(tǒng)研究是物流集約化發(fā)展，構(gòu)建綜 合物流系統(tǒng)，建立現(xiàn)代調(diào)度指揮系統(tǒng)，發(fā)展智能交通運輸系統(tǒng)和開展電子商務的 基礎。 配送路線合理與否對配送速度，成本，效益影響很大，特別是多用戶配送線 路的確定更為復雜。采用科學的，合理的方法來確定配送路線，是配送活動中非 常重要的一項工作。 路線優(yōu)化問題最早是由 DANTZIG 和 RAMSER 于 1959 年提出的，由于這一問題 的理論涉及很多學科，很多實際問題的理論抽象都可歸結(jié)為這一類問題，應用前 景廣闊，所以很快便引起運籌學，應用數(shù)學，圖論與網(wǎng)絡分析，物流學科，交通 運輸工程，管理科學與工程，計算機應用等學科的專家，工程技術人員和管理者 的極大重視，自此，一直成為運籌學與組合優(yōu)化領域的前沿與研究熱點問題。 在國外，物流配送路線優(yōu)化問題已廣泛應用于生產(chǎn)，生活的各個方面。如 報紙投遞及線路的優(yōu)化，牛奶配送及送達線路的優(yōu)化，電話預訂貨物的車輛線 路設計，垃圾車的線路優(yōu)化，連鎖商店的送貨的線路優(yōu)化等等。目前，研究水 平已有很大發(fā)展，其理論成果除在汽車運輸領域外，在水運，航空，通訊，電 力，工業(yè)管理，計算機應用等領域也有一定的應用，還用于航空乘務員輪班安 排，輪船公司運送貨物經(jīng)過港口與貨物安排的優(yōu)化設計，交通車線路安排，生 產(chǎn)系統(tǒng)中的計劃與控制等多種組合優(yōu)化問題。 在國內(nèi)，該問題的系統(tǒng)研究還不多見。近年來有李軍等人課題組承擔的國家 自然科學基金 不確定信息條件下動態(tài)車輛路徑 等研究工作。 紀壽文等人 根據(jù)深圳市科技園的實際路網(wǎng)圖，采用神經(jīng)網(wǎng)絡的方法對運輸車輛優(yōu)化調(diào)度進行 了試驗研究。王正彬等人在分析 VRP 現(xiàn)有啟發(fā)式算法的基礎上，建立了考慮線 路安排的物流配送方案模型，并提出了求解該問題的搜索算法。 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 3 2.2. 家樂福超市配送路線現(xiàn)狀家樂福超市配送路線現(xiàn)狀 2.12.1 家樂福超市概況家樂福超市概況 成立于 1959 年的家樂福集團是大賣場業(yè)態(tài)的首創(chuàng)者，是歐洲第一大零售商， 世界第二大國際化零售連鎖集團?，F(xiàn)擁有 11,000 多家營運零售單位，業(yè)務范圍 遍及世界 30 個國家和地區(qū)。 集團以三種主要經(jīng)營業(yè)態(tài)引領市場：大型超市，超市以及折扣店。此外，家 樂福還在一些國家發(fā)展了便利店和會員制量販店。2004 年集團稅后銷售額增至 726.68 億歐元，員工總數(shù)超過 43 萬人。 2005 年，家樂福在財富雜志編排的全球 500 強企業(yè)中排名第 22 位。 法國家樂福集團是大型超級市場（Hypermarket）概念的創(chuàng)始者，于 1963 年 在法國開設了世界上第一家大型超市。1999 年 8 月 30 日家樂福兼并普羅莫代斯 組成世界第二大零售集團。如今家樂福已發(fā)展成為歐洲最大、全球第二大的零售 商。2004 年，家樂福集團被財富雜志評為全球 500 強企業(yè)的第 22 位。 家樂福于 1969 年開始進入國際市場，目前在世界上 31 個國家和地區(qū)擁有一 萬多家銷售網(wǎng)點，涉及的零售業(yè)態(tài)包括大賣場、超級市場、折扣店、便利店、倉 儲式商店與電子商務，集團的 50 萬名員工正致力于為 20 億消費者服務。家樂福 集團建立了全球性的采購網(wǎng)絡，向不同國家和地區(qū)的供應商采購具有市場競爭力 的商品。 家樂福的經(jīng)營理念是以低廉的價格、卓越的顧客服務和舒適的購物環(huán)境為廣 大消費者提供日常生活所需的各類消費品。家樂福對顧客的承諾是在價格、商品 種類、質(zhì)量、服務及便利性等各方面滿足消費者的需求。家樂福力爭通過自己的 努力成為當?shù)厣鐓^(qū)最好的購物場所，為消費者帶來更多的實惠和便利，并攜手和 各商業(yè)伙伴為當?shù)亟?jīng)濟的繁榮做出貢獻。 家樂福于 1995 年進入中國后，采用國際先進的超市管理模式，致力于為社 會各界提供價廉物美的商品和優(yōu)質(zhì)的服務，受到廣大消費者的青睞和肯定，其 “開心購物家樂?！?、“一站式購物”等理念已經(jīng)深入人心。如今，家樂福已成 功地進入了中國的 25 個城市，在北至哈爾濱、南至深圳、西至烏魯木齊、東至 上海的中國廣袤土地上開設了 109 家大型超市，聘請 3 萬多名員工。在在華外資 零售企業(yè)中處于領先地位。家樂福還向中國引進迪亞折扣店和冠軍食品超市兩種 業(yè)態(tài)。2004 年，家樂福(中國)被國內(nèi)媒體評為“在華最有影響力的企業(yè)”之一。 2004 年約有 2 億多人光顧了家樂福在中國的各門店，其中 68%為女性，32% 乘公共汽車，37%步行，15%騎自行車，9%乘坐出租車或小轎車前往家樂福購物。 家樂福成為了各地居民的好鄰居。 通過多年的經(jīng)營，家樂福向中國的商業(yè)界輸入了大型超市經(jīng)營管理方面的技 能和先進經(jīng)驗，并對商品采購、營銷管理、資產(chǎn)管理以及人力資源開發(fā)等各方面 實現(xiàn)現(xiàn)代化和本地化，為當?shù)亟?jīng)濟發(fā)展做了積極的貢獻。 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 4 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； 2 0i 2 0i Y-Y)x(xD）（ (2) 現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表 2-3 求得, 配送 中心與商店之間，商店與商店之間的距離分析如下表： 表表 2-22-2 配送中心與分店之間配送中心與分店之間, ,分店與分店之間的距離分店與分店之間的距離(0(0 點表示配送中心點表示配送中心) ) 01234567891011121314151617181920 00126.44.522309.2179.2171613156.48.5115119.2158.5 1120137.811392.862173.61.427153.6237.1136256 XY 189 2-45 324 41020 53-30 667 7815 8-7-6 9159 101012 11910 12-8-13 134-5 1466 15-7-8 1634 17-510 1829 191-15 2083 坐標 分店與配送中心間距離 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 5 26.41306.12136101611191614181310137.15.17.22112 34.57.86.1018345131314119.2209.24.51519.25196.1 422112118050145.43112810382615331718143617 530393634500374526414340202536243441391533 69.22.8105143708.3189.26.44.224121204.2114.5234.5 717616135.4458.30269.23.65.132209.22712148.53112 89.22111133126182602725237.1111821416171217 9177191412419.29.22705.86.132189.528132013289.2 10163.616118436.43.6255.802.231187.22611158.5289.2 11131.4149.210404.25.1236.12.2029165248.5147.1267.1 1215271820382024327.1323129014245.12023249.223 136.415139.2262512201118181614011119.11714108.9 148.53.6104.5153619.2189.57.2524110193.6125223.6 15112313153324202722826245.1111901618191119 1657.17.1117344.2121413118.5209.13.6160105.1195.1 1711135.19.21841111416201514231712181007.12615 189.267.2514394.58.517138.57.124145195.17.10248.5 191525211936152331122828269.2102211192624019 208.56126.117334.512179.29.27.1238.93.6195.1158.5190 2.2.22.2.2 車輛數(shù)分析車輛數(shù)分析 所需車輛數(shù)分析(家樂福配送中心一年(365 天)的車輛調(diào)度): 表表 2-32-3 車輛調(diào)度情況車輛調(diào)度情況 車輛運用數(shù) 101291110111010891011 運用天數(shù) 2530364246494838241386 表表 2-42-4 車輛運用數(shù)所占比率車輛運用數(shù)所占比率 車輛運用數(shù)相對比率累計比率 120.070.07 120.080.15 110.100.25 100.120.37 120.130.50 110.130.63 130.130.76 100.100.86 140.070.93 150.040.97 130.020.99 110.011.00 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 6 則家樂福平均每天所用車輛數(shù)為 12 輛。 2.2.32.2.3 需求量分析需求量分析 表表 2-52-5 每個分店（一年每個分店（一年 365365 天）平均每天的需求量天）平均每天的需求量 分店 12345678910 需求 量 2324123513 分店 11121314151617181920 需求 量 2342121322 2.2.42.2.4 商品品種分析商品品種分析 超市以滿足消費者對基本生活用品一次性購買需要為經(jīng)營宗旨，是一種經(jīng)營 品項較多的零售業(yè)態(tài)。下面對商品進行分類分析。 一、大分類 大分類是超市最粗線條的分類。大分類的主要標準是商品特征，如畜產(chǎn)、水 產(chǎn)、果菜、日配加工食品、一般食品、日用雜貨、日用百貨、家用電器等。為了 便于管理，超級市場的大分類一般以不超過 10 個為宜。 二、中分類 中分類是大分類中細分出來的類別。其分類標準主要有： (1)按商品功能與用途劃分。如日配品這個大分類下，可分出牛奶、豆制品、冰 品、冷凍食品等中分類。 (2)按商品制造方法劃分。如畜產(chǎn)品這個大分類下，可細分出熟肉制品的中分類， 包括咸肉、熏肉、火腿、香腸等。 (3)按商品產(chǎn)地劃分。如水果蔬菜這個大分類下，可細分出國產(chǎn)水果與進口水果 的中分類。 三、小分類 小分類是中分類中進一步細分出來的類別。主要分類標準有： (1)按功能用途劃分。如“畜產(chǎn)”大分類中、 “豬肉”中分類下，可進一步細分 出“排骨” 、 “肉米” 、 “里肌肉”等小分類。 (2)按規(guī)格包裝劃分。如“一般食品”大分類中、 “飲料”中分類下，可進一步 細分出“聽裝飲料” 、 “瓶裝飲料” 、 “盒裝飲料”等小分類。 (3)按商品成份分類。如“日用百貨”大分類中、 “鞋”中分類下，可進一步細 分出“皮鞋” 、 “人造革鞋” 、 “布鞋” 、 “塑料鞋”等小分類。 (4)按商品口味劃分。如“糖果餅干”大分類中、 “餅干”中分類下，可進一步 細分出“甜味餅干” 、 “咸味餅干” 、 “奶油餅干” 、 “果味餅干”等小分類。 四、單品 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 7 單品是商品分類中不能進一步細分的、完整獨立的商品品項。如上海申美飲 料有限公司生產(chǎn)的“355 毫升聽裝可口可樂” 、 “125 升瓶裝可口可樂” 、 “2 升瓶 裝可口可樂” 、 “2 升瓶裝雪碧” ，就屬于四個不同單品。 需要說明的是，商品分類并沒有統(tǒng)一固定的標準，各超市公司可根據(jù)市場和 自身的實際情況對商品進行分類。但商品分類應該以方便顧客購物、方便商品組 合、體現(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è)基礎非常薄弱,只有通過大的配送 食品日用品 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.首飾 糖類 酒類 茶葉 軟飲料 沖飲品 冷飲 咖啡豆|可可 其他糖酒飲料 10.衣物 5.加工食品11.箱包,袋,皮具 保健食品 休閑食品 方便食品 罐頭 食品 特色食品 調(diào)味品 其他加工食 品 12. 文體用品 6.煙草13.日用小五金 煙葉 香煙 其他煙草14.休閑家具 7.添加劑15.個人護理用品 食品添加劑 添加劑 發(fā)酵制品16.衛(wèi)浴用品 8.包裝機17.炊具 加工設備 食品包裝 其他機械包裝 制冷設備 18.灶具 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 8 系統(tǒng)的完善和整合才能形成規(guī)模的,高效的,社會化的物流配送系統(tǒng). 家樂福配送路線的分配存在以下幾方面的問題： （1）物流公司與門店之間的分布太分散，難以形成固定的配送線路 （2）送貨難以達到及時 （3）難以保證適量的庫存而不壓貨 （4）路線里程未達最短 （5）費用消耗大 （6）勞力消耗大，運力難以適當分配，難以調(diào)度車輛 （7）配送車輛噸位公里數(shù)大 （8）配送未實現(xiàn)自動化 （9）配送未實現(xiàn)網(wǎng)絡化 （10）配送服務未實現(xiàn)系列化 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 9 3.3.配送路線優(yōu)化建模與求解配送路線優(yōu)化建模與求解 3.13.1 研究對象目標設定研究對象目標設定 物流配送?？紤]以最小化總運輸成本或距離最短為目標，總運輸成本主要由 由兩部分組成:(1)運輸固定成本：如服務所有客戶所需要的車輛數(shù)、總行駛距離 (或總行駛時間)和與所使用的車輛有關的固定費用；(2)運輸營業(yè)成本：如司機的 管理費,各種工作人員的工資等. 家樂福超市的業(yè)務運輸成本是物流總成本的主要組成部分，占有 56%。因此 降低公司運輸成本成為提高公司效益的直接有效途徑。公司自有貨運成本各項比 例如下表： 表表 3-13-1 公司貨運成本比例表公司貨運成本比例表 固定費用（22%）營業(yè)費用（78%） 折舊費（租賃費）： 裝卸工具，車庫，辦公室， 水電，通迅，差旅費，公務車費用 業(yè)務印刷費 人力（司機）： 工資,額外福利，裝卸費 投資利息： 車輛，車庫,辦公室 管理成本： 職工月工資,額外福利,旅游和娛樂費用, 房屋維修費，牌照費，職工培訓費，宣傳 費及業(yè)務手續(xù)費。 車輛運營成本： 燃料（燃油，潤滑油，過濾器） 維修費（人工費+零部件） 輪胎費，交通規(guī)費，養(yǎng)路費 大修理基金提存 道路服務： 通行費,保險,許可證和登記費 高速公路使用費,燃油 司機費用占總營業(yè)成本的 29.4%；維修費和折舊費占總營業(yè)成本的 19.5%； 其它的運營費用占總營業(yè)成本的 32.6%；燃料費占總營業(yè)成本的 18.5%； 表上所述：公司車輛運營成本占據(jù)了總運輸成本的 78%。隨著道路服務政策 的變化，車輛營業(yè)成本在公司總成本中所占比例日益增大。距離是影響運輸成本 的主要因素，因為它直接對勞動、燃料和維修保養(yǎng)等變動成本發(fā)生作用。針對公 司當前成本構(gòu)成狀況，可以知道：通過優(yōu)化公司配送路線，減少運輸車輛行駛總 里程，可以減少車輛燃油費和道路服務費支出，進而減少物流總成本。 因此，本文針對家樂福配送中心車輛路線優(yōu)化問題，提出的目標是：總運輸 成本最小化。 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 10 5 9 4 配送中心 6 3 27 8 1 配送中心 分店 車輛路線 圖圖 3-13-1 家樂福的配送模式家樂福的配送模式 此問題可以描述為：這是一種分送式配送模型,是由一個供應點對多個客戶的 共同配送。對配送中心負責的需求網(wǎng)點（家樂福分店） ，確定適當?shù)呐渌蛙囕v行 駛路線，使其從配送中心出發(fā)，有序地通過各個分店各一次，最后返回配送中心， 并在滿足一定的約束條件下(如車輛容量限制、行駛里程限制、時間限制、顧客需 求量、交發(fā)貨時間等)，達到費用最少的目標。 本文研究的是不考慮時間窗的非滿載車輛優(yōu)化調(diào)度問題。表述如下：將貨物 從配送中心配送到各分配送中心,由分配送中心派出容量為的貨車承運，現(xiàn)有 mq 輛車，各分店對所需求的貨物有一定的要求，第 i 個分店的貨運量為 gi， （i=1，2l）已知，在途中只有卸貨任務,完成任務后返回配送中心,qgi 求滿足配送需求的費用最少行車線路。 圖圖 3-23-2 家樂福配送體系結(jié)構(gòu)家樂福配送體系結(jié)構(gòu) 分配送中心 1 分配送中心 2 分配送中心 3 分店 1 分店 2 分店 3分店 4 . 配送中心 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 11 3.23.2 模型的構(gòu)建模型的構(gòu)建 為建模方便，需考慮以下幾個前提假設條件： （1）配送中心不會出現(xiàn)缺貨的可能并且對顧客的基本配送資料（需求量、地理 位置）為已知，配送中心的位置也已知； （2）不考慮配送時間限制，即客戶對貨物的需求沒有時間窗的規(guī)定； （3）不考慮每輛車為每個客戶的服務時間，即不考慮每個客戶的卸貨時間； （4）一個配送中心根據(jù)配送條件可以負責多個客戶，即一個配送中心服務多個 客戶； （5）車輛由配送中心出發(fā)，服務被指定的需求點后，再返回配送中心，區(qū)域內(nèi) 的需求點假設為固定數(shù)量且位置已知，不發(fā)生變動。 （6）配送中心擁有一定數(shù)量的單一車型的配送車輛，且每輛車的容量已知。 （7）每條配送路徑上各客戶需求量之和不超過配送車輛的容量； （8）每個客戶只能由一輛配送車輛送貨； （9）每輛車配送總里程不超過其最大行駛距離； （10）各道路均順暢，不考慮交通堵塞擁擠等特殊情況。 將配送中心編號為 0，車輛編號為 k，任務編號為 i=1,2 , 所有車型載重l 量單一，每輛汽車的最大載重量為 g，需要向 L 個需求點送貨，每個需求點的需 求量為，并且滿足，需求點 i 到 j 的運距為，配送中心到), 2 , 1(Liqigqiijd 各個需求點的距離為，再設為第輛汽車配送的需求點數(shù)（,.,L),jidi210(jknk =0 表示未使用第輛汽車） ，用集合表示第 k 條路徑，其中的元素表示需knkkRkir 求點在路徑中的順序為 （不包括配送中心） ，令=0 表示配送中心，為kirki0krm 每輛車單位里程的行駛費用，為每輛車的派遣費用，考慮運輸量約束,停車點車C 輛數(shù)目等約束,可以定義如下的基本模型: (3-1)CK n nsignddmZ K ki krrrr k k k knkiik 11 )(min 0)1( (3-2) n gq k ki i r 1 (3-3) Lnk0 (3-4) Ln K k k 1 (3-5) ,.,2 , 1,.,2 , 1| kkikik niLrrR (3-6) 其他0 11 )( k k n nsign 在上述模型中各個公式所代表的涵義如下： 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 12 （3-1）式為目標函數(shù)，求總的配送費用最低； （3-2）式用于保證每條路徑上各個需求點的需求量和不超過汽車的載重量； （3-3）式表明每條路徑上的需求點數(shù)不超過總需求點數(shù)； （3-4）式表明每個需求點都得到配送服務； （3-5）式表示每條路徑的需求點的組成； （3-6）式表示當?shù)谳v汽車服務的客戶數(shù)大于或等于 1 時，說明該輛汽車參k 加了配送，則取，當?shù)?k 輛汽車服務的客戶數(shù)小于 1 時，表示未使用1)( k nsign 該輛汽車，因此?。?)( k nsign 3.33.3 節(jié)約算法節(jié)約算法 3.3.13.3.1 節(jié)約算法的基本原理節(jié)約算法的基本原理 節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0， ，i，0）和 （0，j， ，0）合并成一個回路（0， ，i，j，0） 。在上面的合并操作 中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱 節(jié)約了運輸距離6。相應的變化值，叫做節(jié)約距離，如式（1）所示。 ij C （1） ijioojji Cccc 調(diào)整過程如圖 3 所示。 調(diào)整前 調(diào)整后 圖圖 3-33-3 節(jié)約算法的圖像描述節(jié)約算法的圖像描述 3.3.23.3.2 節(jié)約里程算法主要步驟節(jié)約里程算法主要步驟 已知條件:需求點集=1,2, n,各點需求量,各點間最短距離。 R N i R ij c 0 j i 0 j i 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 13 第一步,形成一個初始解。確定各車輛配送點集令, 12 , m I II j Ij =1,2,n (先采取單點配送)。j 第二步,進行節(jié)約度的計算。計算所有點對的節(jié)約度，然后對計算結(jié) 果進行升序排列。 第三步，進行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始， 直到節(jié)約里程的隊列空為止,重復下列步驟:按照節(jié)約里程隊列從大 到小的順序,分析客戶 i 和 j 之間合并的可能性(是否滿足裝載限制條件、不在同 一路徑內(nèi)以及合并次數(shù)不超過 2),將 i, j 連接起來,即可令。; iijj IIII 如果不是這樣,則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對。 3.3.33.3.3 基于節(jié)約算法的配送路線優(yōu)化基于節(jié)約算法的配送路線優(yōu)化 表表3-23-2 每個分店（一年每個分店（一年365365天）平均每天的需求量天）平均每天的需求量 分店 12345678910 需求量 （噸） 2324123513 分店 11121314151617181920 需求量 （噸） 2342121322 現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表3-2求得, 配送中心 與商店之間，商店與商店之間的距離分析如下表： 表表3-33-3 配送中心與分店之間配送中心與分店之間, ,分店與分店之間的距離分店與分店之間的距離(0(0點表示配送中心點表示配送中心) ) 01234567891011121314151617181920 00126.44.522309.2179.2171613156.48.5115119.2158.5 1120137.811392.862173.61.427153.6237.1136256 26.41306.12136101611191614181310137.15.17.22112 34.57.86.1018345131314119.2209.24.51519.25196.1 422112118050145.43112810382615331718143617 530393634500374526414340202536243441391533 69.22.8105143708.3189.26.44.224121204.2114.5234.5 717616135.4458.30269.23.65.132209.22712148.53112 89.22111133126182602725237.1111821416171217 9177191412419.29.22705.86.132189.528132013289.2 10163.616118436.43.6255.802.231187.22611158.5289.2 11131.4149.210404.25.1236.12.2029165248.5147.1267.1 1215271820382024327.1323129014245.12023249.223 136.415139.2262512201118181614011119.11714108.9 148.53.6104.5153619.2189.57.2524110193.6125223.6 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 14 15112313153324202722826245.1111901618191119 1657.17.1117344.2121413118.5209.13.6160105.1195.1 1711135.19.21841111416201514231712181007.12615 189.267.2514394.58.517138.57.124145195.17.10248.5 191525211936152331122828269.2102211192624019 208.56126.117334.512179.29.27.1238.93.6195.1158.5190 設每個車輛的運輸能力是 8 噸，根據(jù)案例可知，家樂福平均每天所用車輛數(shù)為 12 輛?，F(xiàn)在用節(jié)約算法對該配送線路問題進行求解。 根據(jù)配送中心與分店之間,分店與分店之間的距離距離表，計算出用戶間的節(jié)約 里程， 表表 3-43-4 節(jié)約值矩陣表節(jié)約值矩陣表 1234567891011121314151617181920 10 2 5.4 0 3 8.74.8 0 4 237.48.5 0 5 30.40.52 0 6 18.45.68.717.22.2 0 7 237.48.533.6217.90 8 0.24.60.70.213.20.40.20 9 224.47.52761724.8-0.80 10 24.46.49.530318.829.40.227.20 11 23.65.48.32531824.9-0.823.926.80 12 03.4-0.5-1250.2017.100-10 13 3.4-0.21.72.411.43.63.44.65.44.43.47.40 14 16.94.98.55.52.516.716.3-0.31617.316.5-0.53.90 15 04.40.50200.2118.201020.96.40.50 16 -0.14.38.510110100.29109.502.39.900 17 014.36.31509.2144.28121030.47.5460 18 15.28.48.717.20.213.917.71.413.216.715.10.21.212.71.29.113.20 19 20.40.51301.2112.243220.811.41.515100.20 20 14.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 15 從表 3-4 中選出節(jié)約值最大值為 33.6，其對應的兩點為 4、7。4、7 兩處的 需求量之和為 7，未超過一輛車的運輸能力 8，因此，連接 4、7 成回路，即 0-4- 7-0.再將頂點 4 和 7 的節(jié)約值賦為 0.結(jié)果如表 3-5 所示。 表表 3-53-5 1234567891011121314151617181920 10 2 5.40 3 8.74.80 4 237.48.50 5 30.40.520 6 18.45.68.717.22.20 7 237.48.50217.90 8 0.24.60.70.213.20.40.20 9 224.47.52761724.8-0.80 10 24.46.49.530318.829.40.227.20 11 23.65.48.32531824.9-0.823.926.80 12 03.4-0.5-1250.2017.100-10 13 3.4-0.21.72.411.43.63.44.65.44.43.47.40 14 16.94.98.55.52.516.716.3-0.31617.316.5-0.53.90 15 04.40.50200.2118.201020.96.40.50 16 -0.14.38.510110100.29109.502.39.900 17 014.36.31509.2144.28121030.47.5460 18 15.28.48.717.20.213.917.71.413.216.715.10.21.212.71.29.113.20 19 20.40.51301.2112.243220.811.41.515100.20 20 14.52.96.913.55.513.213.50.716.315.314.40.5613.40.58.44.59.24.50 從表 3-5 中選出節(jié)約值最大為 30，其對應的兩個頂點為 4、10。如果連接 4 和 10 ，則與上述線路合并，其總需求量為 10，超過一輛車的運輸能力 8，因 此，4 和 10 不能連接 ，7 和 10 也不能連接，則將 4、10 與 7、10 的節(jié)約值賦為 0。 繼續(xù)選出節(jié)約值最大為 30，其對應兩個頂點為 5、19。5 和 19 兩處的需求量 之和為 3，未超過一輛車的運輸能力 8，因此，連接,5、19 成回路，即 0-5-19-0.再 將頂點 5 和 19 的節(jié)約值賦為 0。 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 16 繼續(xù)選出節(jié)約值最大為 27.2，其對應兩個頂點為 9、10。9 和 10 兩處的需求 量之和為 4，未超過一輛車的運輸能力 8，因此，連接 9、10 成回路，即 0-9-10- 0.再將頂點 9 和 10 的節(jié)約值賦為 0。 選出節(jié)約值最大為 27，其對應的兩個頂點為 4、9。如果連接 4 和 9，則與上 述兩條線路合并，其總需求量為 11，超過一輛車的運輸能力 8，因此，4 和 9 不 能連接 ，7 和 9 也不能連接，則將 4、9 與 7、9 的節(jié)約值賦為 0。 選出節(jié)約值最大為 26.8，其對應的兩個頂點為 10、11。如果連接 10 和 11 ，則與上述線路合并，其總需求量為 6，未超過一輛車的運輸能力 8，因此，連 接 0-9-10-11-0 成回路 ，則將 9、11 與 10、11 的節(jié)約值賦為 0。同時，由于頂 點 10 成回路的中間點，則與頂點 10 相關的節(jié)約值都賦為 0，表示頂點 10 不可能 再與其他點相連，其結(jié)果如下表所示。 表表 3-63-6 1234567891011121314151617181920 10 2 5.40 3 8.74.80 4 237.48.50 5 30.40.520 6 18.45.68.717.22.20 7 237.48.5 0217.90 8 0.24.60.70.213.20.40.20 9 224.47.506170-0.80 10 0000000000 11 23.65.48.32531824.9-0.8000 12 03.4-0.5-1250.2017.100-10 13 3.4-0.21.72.411.43.63.44.65.403.47.40 14 16.94.98.55.52.516.716.3-0.316016.5-0.53.90 15 04.40.50200.2118.200020.96.40.50 16 -0.14.38.510110100.2909.502.39.900 17 014.36.31509.2144.2801030.47.5460 18 15.28.48.717.20.213.917.71.413.2015.10.21.212.71.29.113.20 19 20.40.5101.2112.240220.811.41.515100.20 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 17 20 14.52.96.913.55.513.213.50.716.3014.40.5613.40.58.44.59.24.50 選出節(jié)約值最大為 25，其對應的兩個頂點為 4、11。如果連接 4 和 11，則 與上述兩條線路合并，其總需求量為 13，超過一輛車的運輸能力 8，因此，4 和 11 不能連接 ，7 和 11 也不能連接，則將 4、11 與 7、11 的節(jié)約值賦為 0。 選出節(jié)約值最大為 25，其對應的兩個頂點為 5、12。如果連接 5 和 12，則與 上述線路合并，其總需求量為 6，未超過一輛車的運輸能力 8，因此，連接 0-12- 5-19-0 成回路，則將 5、12 與 12、19 的節(jié)約值賦為 0。同時，由于頂點 5 成回 路的中間點，則與頂點 5 相關的節(jié)約值都賦為 0，表示頂點 5 不可能再與其他點 相連，其結(jié)果如下表所示。 表表 3-73-7 1234567891011121314151617181920 10 2 5.40 3 8.74.80 4 237.48.50 5 00000 6 18.45.68.717.200 7 237.48.5 0017.90 8 0.24.60.70.200.40.20 9 224.47.500170-0.80 10 0000000000 11 23.65.48.300180-0.8000 12 03.4-0.5-100.2017.100-10 13 3.4-0.21.72.403.63.44.65.403.47.40 14 16.94.98.55.5016.716.3-0.316016.5-0.53.90 15 04.40.5000.2118.200020.96.40.50 16 -0.14.38.510010100.2909.502.39.900 17 014.36.31509.2144.2801030.47.5460 18 15.28.48.717.2013.917.71.413.2015.10.21.212.71.29.113.20 19 20.40.5101.2112.2402011. 4 1.515100.20 家樂福超市物流配送路線優(yōu)化 安徽工業(yè)大學 18 20 14.52.96.913.5013.213.50.716.3014.40.5613.40.58.44.59.24.50 從表 3-7 中選出節(jié)約值最大為 23.6，其對應的兩個頂點為 1、11。如果連接 1 和 11 ，則與上述線路合并，其總需求量為 8，未超過一輛車的運輸能力 8，因 此，連接 0-9-10-11-1-0 成回路，則將與頂點 1、9、10、11 相關的節(jié)約值都賦 為 0，表示頂點 1、9、10、11 不可能再與其他點相連，其結(jié)果如下表所示。 表表 3-83-8 1234567891011121314151617181920 10 2 00 3 04.80 4 07.48.50 5 00000 6 05.68.717.200 7 07.48.5 0017.90 8 04.60.70.200.40.20 9 000000000 10 0000000000 11 00000000000 12 03.4-0.5-100.2017.10000 13 0-0.21.72.403.63.44.60007.40 14 04.98.55.5016.716.3-0.3000-0.53.90 15 04.40.5000.2118.200020.96.40.50 16 04.38.510010100.200002.39.900 17 014.36.31509.2144.200030.47.5460 18 08.48.717.2013.917.71.40000.21.212.71.29.113.20 19 00.40.5101.2112.2000011. 4 1.515100.2