工程科技家樂福配送路徑優(yōu)化

1、家樂福超市物流配送路的線優(yōu)化摘要在物流配送業(yè)務中，合理確定配送路徑是提商服務質量，降低配送成本，增加經濟效益的重要手段。物流配送系統(tǒng)中最優(yōu)路線的選擇問題一直都是配送中心關注的焦點，針對當前家樂福物流配送體系不完善等方面的現(xiàn)狀，本文從可持續(xù)發(fā)展的角度，用系統(tǒng)的觀念，來研究家樂福物流配送體系，優(yōu)化配送路線，使配送體系合理化。通過對家樂福超市現(xiàn)有物流配送路徑的分析研究，發(fā)現(xiàn)其中存在的一些問題，并由此提出解決辦法，結合背景材料，建立了數(shù)學模型，運用遺傳算法對家樂福物流配送路線進行優(yōu)化選擇，并得出結果。由此可見，家樂福超市原有的物流配送路線還可以進行再優(yōu)化，從而達到運輸成本最小化的目標。關鍵詞：物流配送

2、；路徑優(yōu)化；遺傳算法THELOGISTICS OF SUPERMARKET OF CARREFOUR PROVIDES AND DELIVERS THE ROUTE TO OPTIMIZEAbstractIn logistics and distribution business, a reasonable path is to determine the distribution to service quality, reduce distribution costs, an important means to enhance economic efficiency. Logistics

3、 and distribution system in the selection of the optimal route distribution center has been the focus of attention, in view of the current system Carrefour logistics aspects of the current situation leaves much to be desired, this article from the perspective of sustainable development, the concept

4、of using the system, to study at home Lok Fu logistics system and optimize the distribution line, so that the rationalization of distribution systems. Carrefour supermarket on the existing logistics and distribution analysis of the path and found some problems and propose solutions which, combined w

5、ith background materials, the establishment of a mathematical model, Carrefour use of genetic algorithms to optimize logistics and distribution routes choices and the outcome. This shows that Carrefour supermarket logistics original route can also be used for further optimization, in order to minimi

6、ze transportation costs to reach the goal.Key words： logistics and distribution; path optimization; genetic algorithm目 錄1.緒論11.1 選題目的和意義11.2 國內外物流配送路線優(yōu)化研究現(xiàn)狀21.3 研究內容與技術路線32. 家樂福超市配送路線現(xiàn)狀52.1 家樂福超市概況52.2 家樂福超市配送路線作業(yè)現(xiàn)狀62.2.1 配送距離分析62.2.2 車輛數(shù)分析72.2.3 需求量分析82.2.4 商品品種分析82.3 家樂福超市配送現(xiàn)有路線問題分析113.配送路線優(yōu)化建模與求解

7、123.1 研究對象目標設定123.2 模型的構建143.2 遺傳算法163.2.1 遺傳算法介紹163.2.2 算法思想與算法流程184.優(yōu)化結果分析214.2 優(yōu)化后結果214.3 結論225.總結與建議23參考文獻24致謝25附錄一：MATLAB編程261.緒論1.1 選題目的和意義配送是一項特殊的、綜合性的物流運動，其運行和發(fā)展有著深刻的社會根源和歷史背景。在市場經濟體系中，物流配送如同人體的血管，把國民經濟各個部分緊密地聯(lián)系在一起。配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)，是將貨物從物流結點送達收貨人的過程，是在集貨、配貨基礎上，完全按用戶要求，包括種類、品種搭配、數(shù)量、時間等方

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

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

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

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

12、本，增加利潤;另一方面，增強家樂福的競爭力，使其配送系統(tǒng)相應得到優(yōu)化，從而使家樂福物流取得階段性成果，因此，對家樂福物流配送體系及其路線的優(yōu)化問題進行研究將具有很大的現(xiàn)實意義。1.2 國內外物流配送路線優(yōu)化研究現(xiàn)狀物流配送路線優(yōu)化，是物流系統(tǒng)優(yōu)化中關鍵的一環(huán)，也是電子商務活動不可缺少的內容。對物流配送路線優(yōu)化，可以提高物流經濟效益，實現(xiàn)物流科學化。可以說對物流配送路線優(yōu)化理論與方法進行系統(tǒng)研究是物流集約化發(fā)展，構建綜合物流系統(tǒng)，建立現(xiàn)代調度指揮系統(tǒng)，發(fā)展智能交通運輸系統(tǒng)和開展電子商務的基礎。配送路線合理與否對配送速度，成本，效益影響很大，特別是多用戶配送線路的確定更為復雜。采用科學的，合理的方

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

14、前，研究水平已有很大發(fā)展，其理論成果除在汽車運輸領域外，在水運，航空，通訊，電力，工業(yè)管理，計算機應用等領域也有一定的應用，還用于航空乘務員輪班安排，輪船公司運送貨物經過港口與貨物安排的優(yōu)化設計，交通車線路安排，生產系統(tǒng)中的計劃與控制等多種組合優(yōu)化問題。在國內，該問題的系統(tǒng)研究還不多見。近年來有李軍等人課題組承擔的國家自然科學基金不確定信息條件下動態(tài)車輛路徑等研究工作。紀壽文等人根據(jù)深圳市科技園的實際路網圖，采用神經網絡的方法對運輸車輛優(yōu)化調度進行了試驗研究。王正彬等人在分析VRP現(xiàn)有啟發(fā)式算法的基礎上，建立了考慮線路安排的物流配送方案模型，并提出了求解該問題的搜索算法。1.3 研究內容與技術

15、路線本文結構：緒論（研究背景，目的，意義及現(xiàn)狀）路線優(yōu)化現(xiàn)狀（公司概況，需求貨物品種，貨物需求量，分店分布，車輛數(shù)，現(xiàn)有路線分配方法）構建模型（目標設定，函數(shù)構建）模型求解（遺傳算法介紹，算法流程， 編程實現(xiàn)）優(yōu)化結果分析結論，總結與建議圖1-1：論文結構圖本文章節(jié)安排：第一章：研究背景，目的及意議，研究發(fā)展現(xiàn)狀，論文結構與技術路線；第二章：家樂福超市物流配送路線現(xiàn)狀分析，及存在的問題分析；第三章：針對問題設定目標，構建數(shù)學模型，引入遺傳算法，編程實現(xiàn)；第四章：優(yōu)化結果分析；第五章：結論，總結與建議；本文技術路線：（1）分析家樂福超市物流配送路線狀況，并針對路線優(yōu)化提出問題；（2）在考慮成本最

16、小化的目標及其各種約束條件的基礎上建立數(shù)學模型；（3）根據(jù)具體物流配送的特點和要求，提出車輛路線優(yōu)化方案；（4）引入遺傳算法進行求解，采用MATLAB計算機編程進行算法實現(xiàn)；2. 家樂福超市配送路線現(xiàn)狀2.1 家樂福超市概況成立于1959年的家樂福集團是大賣場業(yè)態(tài)的首創(chuàng)者，是歐洲第一大零售商，世界第二大國際化零售連鎖集團。現(xiàn)擁有11,000多家營運零售單位，業(yè)務范圍遍及世界30個國家和地區(qū)。集團以三種主要經營業(yè)態(tài)引領市場：大型超市，超市以及折扣店。此外，家樂福還在一些國家發(fā)展了便利店和會員制量販店。2004年集團稅后銷售額增至726.68億歐元，員工總數(shù)超過43萬人。2005年，家樂福在財富雜

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

18、具有市場競爭力的商品。家樂福的經營理念是以低廉的價格、卓越的顧客服務和舒適的購物環(huán)境為廣大消費者提供日常生活所需的各類消費品。家樂福對顧客的承諾是在價格、商品種類、質量、服務及便利性等各方面滿足消費者的需求。家樂福力爭通過自己的努力成為當?shù)厣鐓^(qū)最好的購物場所，為消費者帶來更多的實惠和便利，并攜手和各商業(yè)伙伴為當?shù)亟洕姆睒s做出貢獻。家樂福于1995年進入中國后，采用國際先進的超市管理模式，致力于為社會各界提供價廉物美的商品和優(yōu)質的服務，受到廣大消費者的青睞和肯定，其“開心購物家樂?！?、“一站式購物”等理念已經深入人心。如今，家樂福已成功地進入了中國的25個城市，在北至哈爾濱、南至深圳、西至烏魯

19、木齊、東至上海的中國廣袤土地上開設了109家大型超市，聘請3萬多名員工。在在華外資零售企業(yè)中處于領先地位。家樂福還向中國引進迪亞折扣店和冠軍食品超市兩種業(yè)態(tài)。2004年，家樂福(中國)被國內媒體評為“在華最有影響力的企業(yè)”之一。2004年約有2億多人光顧了家樂福在中國的各門店，其中68%為女性，32%乘公共汽車，37%步行，15%騎自行車，9%乘坐出租車或小轎車前往家樂福購物。家樂福成為了各地居民的好鄰居。通過多年的經營，家樂福向中國的商業(yè)界輸入了大型超市經營管理方面的技能和先進經驗，并對商品采購、營銷管理、資產管理以及人力資源開發(fā)等各方面實現(xiàn)現(xiàn)代化和本地化，為當?shù)亟洕l(fā)展做了積極的貢獻。2.

20、2 家樂福超市配送路線作業(yè)現(xiàn)狀2.2.1 配送距離分析(1)配送需求點坐標：現(xiàn)在以家樂福物流配送中心為原點(0,0),建立直角坐標系,各商店的坐標如下表所示:X(km);Y(km)表2-1分店所在地坐標分店與配送中心間距離坐標XY1892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083 i=1，2.20；(2) 現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表2-3求得, 配送中心與商店之間，商店與商店之間的距離分析如下表：表2-2 配送中心與分店之間,分店與分店

21、之間的距離(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.51519.25196.1422112118050145.43112810382615331718143617530393634500374526414340

22、20253624344139153369.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.6255.802.231187.22611158.5289.211131.4149.210404.25.1236.12.2029165248.5147.

23、1267.11215271820382024327.1323129014245.12023249.223136.415139.2262512201118181614011119.11714108.9148.53.6104.5153619.2189.57.2524110193.6125223.615112313153324202722826245.11119016181911191657.17.1117344.2121413118.5209.13.6160105.1195.11711135.19.21841111416201514231712181007.12615189.267.2514394

24、.58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93.6195.1158.51902.2.2 車輛數(shù)分析所需車輛數(shù)分析(家樂福配送中心一年(365天)的車輛調度):表2-3車輛調度情況車輛運用數(shù)101291110111010891011運用天數(shù)2530364246494838241386表2-4車輛運用數(shù)所占比率車輛運用數(shù)相對比率累計比率120.070.07120.080.15110.100.25100.120.371

25、20.130.50110.130.63130.130.76100.100.86140.070.93150.040.97130.020.99110.011.00則家樂福平均每天所用車輛數(shù)為12輛。2.2.3 需求量分析表2-5 每個分店（一年365天）平均每天的需求量分店12345678910需求量2324123513分店11121314151617181920需求量23421213222.2.4 商品品種分析超市以滿足消費者對基本生活用品一次性購買需要為經營宗旨，是一種經營品項較多的零售業(yè)態(tài)。下面對商品進行分類分析。 一、大分類 大分類是超市最粗線條的分類。大分類的主要標準是商品特征，如畜產、

26、水產、果菜、日配加工食品、一般食品、日用雜貨、日用百貨、家用電器等。為了便于管理，超級市場的大分類一般以不超過10個為宜。 二、中分類 中分類是大分類中細分出來的類別。其分類標準主要有： (1)按商品功能與用途劃分。如日配品這個大分類下，可分出牛奶、豆制品、冰品、冷凍食品等中分類。 (2)按商品制造方法劃分。如畜產品這個大分類下，可細分出熟肉制品的中分類，包括咸肉、熏肉、火腿、香腸等。 (3)按商品產地劃分。如水果蔬菜這個大分類下，可細分出國產水果與進口水果的中分類。 三、小分類 小分類是中分類中進一步細分出來的類別。主要分類標準有： (1)按功能用途劃分。如“畜產”大分類中、“豬肉”中分類下

27、，可進一步細分出“排骨”、“肉米”、“里肌肉”等小分類。 (2)按規(guī)格包裝劃分。如“一般食品”大分類中、“飲料”中分類下，可進一步細分出“聽裝飲料”、“瓶裝飲料”、“盒裝飲料”等小分類。 (3)按商品成份分類。如“日用百貨”大分類中、“鞋”中分類下，可進一步細分出“皮鞋”、“人造革鞋”、“布鞋”、“塑料鞋”等小分類。 (4)按商品口味劃分。如“糖果餅干”大分類中、“餅干”中分類下，可進一步細分出“甜味餅干”、“咸味餅干”、“奶油餅干”、“果味餅干”等小分類。 四、單品 單品是商品分類中不能進一步細分的、完整獨立的商品品項。如上海申美飲料有限公司生產的“355毫升聽裝可口可樂”、“125升瓶裝可

28、口可樂”、“2升瓶裝可口可樂”、“2升瓶裝雪碧”，就屬于四個不同單品。 需要說明的是，商品分類并沒有統(tǒng)一固定的標準，各超市公司可根據(jù)市場和自身的實際情況對商品進行分類。但商品分類應該以方便顧客購物、方便商品組合、體現(xiàn)企業(yè)特點為目的。具體分類如下表所示：表2-6 商品品種食品日用品1.糧油1.日化產品糧食米面淀粉食用油主食熟食豆制品其他糧油2.日雜用品2.果蔬3. 家居用品新鮮蔬菜新鮮水果食用菌蔬菜制品干果|堅果果蔬深加工其他果蔬4. 清潔用品及用具3.水產5.餐具鮮活水產品粗加工水產品精加工水產品其他水產6.廚具畜產7.日用小家電鮮活畜禽鮮肉類鮮蛋類鮮奶類肉制品蛋制品乳制品蜜制品8.家用塑料制

29、品 4.糖酒飲料9.首飾糖類酒類茶葉軟飲料沖飲品冷飲咖啡豆|可可其他糖酒飲料10.衣物5.加工食品11.箱包,袋,皮具保健食品休閑食品方便食品罐頭食品特色食品調味品其他加工食品12. 文體用品6.煙草13.日用小五金煙葉香煙其他煙草14.休閑家具7.添加劑15.個人護理用品食品添加劑其他添加劑發(fā)酵制品16.衛(wèi)浴用品8.包裝機17.炊具加工設備食品包裝其他機械包裝制冷設備18.灶具2.3 家樂福超市配送現(xiàn)有路線問題分析家樂福的配送系統(tǒng)和信息系統(tǒng)是較落后的.家樂福至今沒有在中國建立起統(tǒng)一的配送體系,且計算機系統(tǒng)的開發(fā)和建立,要落后于競爭對手沃爾瑪好幾年.家樂福這種”滯后”的配送系統(tǒng)與信息系統(tǒng)是其戰(zhàn)

30、略規(guī)劃的成果,因為商品的集中配送是連鎖商業(yè)帶來的,但是目前中國連鎖商業(yè)基礎非常薄弱,只有通過大的配送系統(tǒng)的完善和整合才能形成規(guī)模的,高效的,社會化的物流配送系統(tǒng).家樂福配送路線的分配存在以下幾方面的問題：（1） 物流公司與門店之間的分布太分散，難以形成固定的配送線路（2） 送貨難以達到及時（3） 難以保證適量的庫存而不壓貨（4） 路線里程未達最短（5） 費用消耗大（6） 勞力消耗大，運力難以適當分配，難以調度車輛（7） 配送車輛噸位公里數(shù)大（8） 配送未實現(xiàn)自動化（9） 配送未實現(xiàn)網絡化（10） 配送服務未實現(xiàn)系列化3.配送路線優(yōu)化建模與求解3.1 研究對象目標設定物流配送?？紤]以最小化總運輸

31、成本或距離最短為目標，總運輸成本主要由由兩部分組成:(1)運輸固定成本：如服務所有客戶所需要的車輛數(shù)、總行駛距離(或總行駛時間)和與所使用的車輛有關的固定費用；(2)運輸營業(yè)成本：如司機的管理費,各種工作人員的工資等.家樂福超市的業(yè)務運輸成本是物流總成本的主要組成部分，占有56%。因此降低公司運輸成本成為提高公司效益的直接有效途徑。公司自有貨運成本各項比例如下表：表3-1公司貨運成本比例表固定費用（22%）營業(yè)費用（78%）折舊費（租賃費）：裝卸工具，車庫，辦公室，水電，通迅，差旅費，公務車費用業(yè)務印刷費人力（司機）：工資,額外福利，裝卸費投資利息：車輛，車庫,辦公室管理成本：職工月工資,額外

32、福利,旅游和娛樂費用,房屋維修費，牌照費，職工培訓費，宣傳費及業(yè)務手續(xù)費。車輛運營成本：燃料（燃油，潤滑油，過濾器）維修費（人工費+零部件）輪胎費，交通規(guī)費，養(yǎng)路費大修理基金提存道路服務：通行費,保險,許可證和登記費高速公路使用費,燃油司機費用占總營業(yè)成本的29.4%；維修費和折舊費占總營業(yè)成本的19.5%；其它的運營費用占總營業(yè)成本的32.6%；燃料費占總營業(yè)成本的18.5%；表上所述：公司車輛運營成本占據(jù)了總運輸成本的78%。隨著道路服務政策的變化，車輛營業(yè)成本在公司總成本中所占比例日益增大。距離是影響運輸成本的主要因素，因為它直接對勞動、燃料和維修保養(yǎng)等變動成本發(fā)生作用。針對公司當前成本

33、構成狀況，可以知道：通過優(yōu)化公司配送路線，減少運輸車輛行駛總里程，可以減少車輛燃油費和道路服務費支出，進而減少物流總成本。因此，本文針對家樂福配送中心車輛路線優(yōu)化問題，提出的目標是：總運輸成本最小化。594配送中心632781配送中心分店車輛路線圖3-1 家樂福的配送模式此問題可以描述為：這是一種分送式配送模型,是由一個供應點對多個客戶的共同配送。對配送中心負責的需求網點（家樂福分店），確定適當?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序地通過各個分店各一次，最后返回配送中心，并在滿足一定的約束條件下(如車輛容量限制、行駛里程限制、時間限制、顧客需求量、交發(fā)貨時間等)，達到費用最少的目標。本文

34、研究的是不考慮時間窗的非滿載車輛優(yōu)化調度問題。表述如下：將貨物從配送中心配送到各分配送中心,由分配送中心派出容量為的貨車承運，現(xiàn)有m輛車，各分店對所需求的貨物有一定的要求，第i個分店的貨運量為gi，（i=1，2l）已知，在途中只有卸貨任務,完成任務后返回配送中心,求滿足配送需求的費用最少行車線路。分配送中心1分配送中心2分配送中心3.分店1分店2分店3分店4.配送中心圖3-2家樂福配送體系結構3.2 模型的構建為建模方便，需考慮以下幾個前提假設條件：（1）配送中心不會出現(xiàn)缺貨的可能并且對顧客的基本配送資料（需求量、地理位置）為已知，配送中心的位置也已知；（2）不考慮配送時間限制，即客戶對貨物的

35、需求沒有時間窗的規(guī)定；（3）不考慮每輛車為每個客戶的服務時間，即不考慮每個客戶的卸貨時間；（4）一個配送中心根據(jù)配送條件可以負責多個客戶，即一個配送中心服務多個客戶；（5）車輛由配送中心出發(fā)，服務被指定的需求點后，再返回配送中心，區(qū)域內的需求點假設為固定數(shù)量且位置已知，不發(fā)生變動。（6）配送中心擁有一定數(shù)量的單一車型的配送車輛，且每輛車的容量已知。（7）每條配送路徑上各客戶需求量之和不超過配送車輛的容量；（8）每個客戶只能由一輛配送車輛送貨；（9）每輛車配送總里程不超過其最大行駛距離；（10）各道路均順暢，不考慮交通堵塞擁擠等特殊情況。將配送中心編號為0，車輛編號為k，任務編號為i=1,2.,

36、 所有車型載重量單一，每輛汽車的最大載重量為g，需要向L個需求點送貨，每個需求點的需求量為，并且滿足，需求點i到j的運距為，配送中心到各個需求點的距離為，再設為第輛汽車配送的需求點數(shù)（=0表示未使用第輛汽車），用集合表示第k條路徑，其中的元素表示需求點在路徑中的順序為（不包括配送中心），令=0表示配送中心，為每輛車單位里程的行駛費用，為每輛車的派遣費用，考慮運輸量約束,停車點車輛數(shù)目等約束,可以定義如下的基本模型: (3-1) (3-2) (3-3) (3-4) (3-5) (3-6)在上述模型中各個公式所代表的涵義如下：（3-1）式為目標函數(shù)，求總的配送費用最低；（3-2）式用于保證每條路徑

37、上各個需求點的需求量和不超過汽車的載重量；（3-3）式表明每條路徑上的需求點數(shù)不超過總需求點數(shù)；（3-4）式表明每個需求點都得到配送服務；（3-5）式表示每條路徑的需求點的組成；（3-6）式表示當?shù)谳v汽車服務的客戶數(shù)大于或等于1時，說明該輛汽車參加了配送，則取，當?shù)趉輛汽車服務的客戶數(shù)小于1時，表示未使用該輛汽車，因此??；3.2 遺傳算法3.2.1 遺傳算法介紹遺傳算法與其它傳統(tǒng)方法相比,具有如下優(yōu)點:（1）適用范圍廣，具有很強的搜索能力；（2）能以很大的概率找到問題的全局最優(yōu)解；（3）能有效處理較大規(guī)模優(yōu)化問題；（4）搜尋空間并行性；（5）魯棒性強；（6）智能性；（7）只通過目標函數(shù)計算適應

38、度，不受約束條件束縛。基于以上幾點,本文將采用遺傳算法對家樂福超市物流配送路線進行尋優(yōu)。遺傳算法是由美國Michigan大學的Holland教授于1969年提出,后經DeJong、Goldberg等人歸納總結所形成的一類模擬進化算法。它來源于達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說。本文所設計的遺傳算法的基本流程如下：STEP1：初始化，產生初始種群。STEP2：個體評價，即計算種群中每個個體的適應度。STEP3：按選擇概率PS，執(zhí)行選擇算子，從當前種群中選擇部分個體進入下一代種群。STEP4：按交叉概率PC，執(zhí)行交叉算子。STEP5：按變異概率Pm，執(zhí)行變異算子。STEP6

39、：若滿足設定的終止條件，則執(zhí)行STEP7，否則執(zhí)行STEP2。STEP7：輸出種群中適應度最優(yōu)的個體作為問題的最優(yōu)解或滿意解。解空間最優(yōu)化問題描述第二步第一步建立優(yōu)化模型確定決策變量,約束條件第五步確定適應度轉換規(guī)則第三四步編碼,解碼個體基因型x適應度F(X)第六步設計遺傳算子第七步確定運行參數(shù)遺傳算法空間遺傳算法圖3-3應用遺傳算法求解問題示意圖第一步和第二步可以歸結為建立優(yōu)化問題的模型，可以是解析性的數(shù)學模型，也可以是非解析性模型。這是應用任何優(yōu)化算法求解優(yōu)化問題都需要的步驟。第三步“編碼”實際上包含了設計或選擇個體基因型的表示方法、設計解的表現(xiàn)型到個體基因型的轉換算法。第四步“解碼”是因

40、為遺傳算子只作用于編碼后的染色體，而染色體的優(yōu)劣要到解空間計算其對應的值由個體表現(xiàn)型計算目標函數(shù)值后才能進行判斷。第五步“確定適應度轉換規(guī)則”是因為染色體所對應的解空間的值可能相差很大，不適合直接用來定量評估個體的優(yōu)劣。第六步“設計遺傳算子”即為設計交叉、變異、選擇等遺傳操作，遺傳算子與待優(yōu)化問題、染色體的編碼方案有很大的關系，也是遺傳算法應用領域的一個重要創(chuàng)新點。第七步“確定運行參數(shù)”即確定遺傳算法中的交叉概率、變異概率、最大進化代數(shù)等參數(shù)。3.2.2 算法思想與算法流程首先根據(jù)每項任務的需求量qi，總任務量以及每輛車的最大載重量q，每輛車的任務不超過其最大載重量g，確定至少需要m輛車來完成

41、任務,最后計算每輛車的總里程，其中總里程最小的即為所求任務安排。（1）構造染色體設車輛的可行線路可以編成自然數(shù)編碼的長度為m+ 的染色體（i11，i12，i13，.i1s；i21，i22.i2t；.；im1，im2.im.），ikj為有需求的分店,即第ikj項任務,為分店的總數(shù)目，m為車輛從配送中心出發(fā),經過各分店后,又回到配送中心的各條回路，即m輛車；車輛行駛線路為：第一輛車從配送中心出發(fā)，每個分店訪問一次，經過i11，i12，i13，.i1s的路線，又回到配送中心，形成子路徑1；第二輛車從配送中心出發(fā)，每個分店訪問一次，經過以前未經過的i21，i22.i2t路線，又回到配送中心，形成子路徑

42、2；這樣重復，直到每個分店都被訪問到且每個分店只訪問一次，項任務全部完成為止；其中i1s 與i2t交換位置,表示行駛路徑的改變,也使函數(shù)目標改變；算出每條路徑的總行程，其中總行程最小的即為所求的最優(yōu)化路徑，其總運輸費用最小。如染色體12345678表示行車路線：子路徑1：配送中心任務1任務2配送中心子路徑2：配送中心任務3任務4任務5配送中心子路徑3：配送中心任務6任務7任務8配送中心這種染色體結構子路徑內部是有序的，若子路徑1中點1，2交換位置，會使函數(shù)目標值改變；而子路徑之間是無序的，若子路徑1和子路徑2交換位置，卻不會改變目標函數(shù)的值。（2）初始種群滿足編碼方案的前提下,隨機產生L個需求

43、點的全排列,構成初始種群,如：i1，i2，.i。若qijg且 qijg將S至的基因依次向后移動一位,使S位空出,將0插入S位。接著若 qijg且 qijg如上面的操作,使t空出,將配送中心插入第t位。如此繼續(xù)，直到將m個配送中心全部插入染色體為止。這樣就構成了一條初始染色體，如此反復，構造滿足群體數(shù)的染色體個數(shù)。（3）適應度函數(shù)對種群中的每個染色體Vi(i=1,2,.l)根據(jù)目標函數(shù)的式子計算其值為Ui,若染色體對應的是不可行解，則賦予其目標函數(shù)值一個很大的整數(shù)，適應度函數(shù)可以設為：fi =1/Zi+M*1000,則fi 0，Zi為染色體Vi對應的運輸成本；fi 為染色體Vi的適應度，fi越大

44、，其性能越好，其對應的解越接近最優(yōu)解。（4）遺傳算子1)選擇算子個體選擇的分配方法:按比例的適應度分配。利用比例于各個體適應度的概率決定其子孫的遺留可能性，選擇概率公式為:p i= fi / fi 即適應度越大，其選擇概率越大。根據(jù)計算父代和子代的適應度，并將每代群體中的N個個體按適應度由大到小排列，排在第一位的個體性能最優(yōu)，將它復制一個直接進入下一代，并排在第一位。下一代群體的另N-1個個體需要根據(jù)前代群體的N個個體的適應度，采用輪盤賭選擇法產生。2)交叉算子對通過選擇操作的新群體，除排在第一位的最優(yōu)個體外，另N-1個個體要按交叉概率pc進行配對交叉重組。本文采用順序法實施交叉操作：a)隨機

45、在你代個體中選取一個交配區(qū)域,如兩父代個體及交配區(qū)域定為：A = 47|8563|921，B=83|4691|257；b)將B的交配區(qū)域加到A的前面，A的交配區(qū)域加到B的前面，得：A=4691|478563921，B=8563|834691257；c)在A，B中自交配區(qū)域后依次刪除與交配區(qū)相同的自然數(shù)，得到最終的兩個個體分別為：A=496178532，B=856349127。3)變異算子以一定的變概率Pm隨機選取發(fā)生變異的個體染色體，然后在該染色體上隨機選取2個非零基因位，把這2個位置上的基因互換形成新的基因串。（5）控制參數(shù)和算法的終止條件1)參數(shù)設置交叉概率Pc=0.6；變異概率Pm=0.

46、01；終止代數(shù)T=100；初始種群N=100；=0.65；車輛數(shù)m=qi/+1（gi為需求點i的貨運量）；g=8噸；2)終止條件由于計算時間的機器容量都是有限的，代數(shù)不能無限長，故當?shù)螖?shù)達到規(guī)定值T時，停止計算。4.優(yōu)化結果分析現(xiàn)有路線行駛距離（KM）實載量（噸）準載量（噸）實載率（%）0-2-5-0363.8847.5%0-9-12-0323.9848.75%0-15-18-0193.8847.5%0-4-0223.6845%0-10-17-0153.7846.25%0-1-19-0253.9848.75%0-3-11-09.23.8847.5%0-8-09.24.8860%0-6-14

47、-013.9848.75%0-16-20-05.13.8847.5%0-13-06.43.7846.25%0-7-12-0325.7870.125%合計211.945.180(平均)50.3%4.1 優(yōu)化前結果表4-1優(yōu)化前路線分析優(yōu)化前成本經計算為10757元。4.2 優(yōu)化后結果表4-2運行結果分析所需車輛數(shù)行駛距離（KM）運輸成本（元）第1次7376.8712706第2次7372.6312579第3次7333.5211406第4次7381.5912848第5次7416.6913901第6次7374.5812637第7次7383.3612901第8次7291.5710147平均值7366.3

48、512291最小值7291.5710147表4-3優(yōu)化后路線優(yōu)化后路線行駛距離（KM）實載量（噸）準載量（噸）實載率%0-11-13-19-0267.6895%0-10-5-7-0886.5881.25%0-20-3-1-013.95.5871.25%0-12-16-18-025.17.8897.5%0-8-9-6-036.27.4892.5%0-4-17-2-023.17.9898.75%0-15-14-0192.9836.25%合計231.345.656（平均）81.43%優(yōu)化后只需要7輛車，減少了5輛車；實載率增加到81.43%，提高了31.13%;總成本減少了610元。D=291.57

49、KM;K=7輛;minZ=10147元.4.3 結論在物流配送業(yè)務中，合理確定配送路徑是提商服務質量，降低配送成本，增加經濟效益的重要手段。本文以家樂福物流配送路徑為研究背景，探討物流配送路徑優(yōu)化問題，針對家樂福物流配送路徑的現(xiàn)狀，分析其不足之處，找出了車輛路徑優(yōu)化存在的問題；分析了相關的配送數(shù)據(jù)，并對優(yōu)化計算方法進行了分析，結合實際情況，選擇遺傳算法作為論文的主要方法；結合背景材料，建立了數(shù)學模型，并設計了遺傳算法；通過本文的分析可知，家樂福的現(xiàn)有配送路線還可以再優(yōu)化，而達到節(jié)約運輸成本的目的；還證明了遺傳算法在路徑優(yōu)化問題中是一種很實用的計算方法，具備很多優(yōu)點。5.總結與建議總配送中心統(tǒng)籌

50、規(guī)劃車輛數(shù)量，調整各個分配送中心的車輛數(shù)，預留一定的備用車輛，分配送中心編排好車輛的出車順序，兼顧車輛保養(yǎng)保修等；此外，公司的發(fā)展必然使其業(yè)務范圍擴大，出現(xiàn)新的貨物類別，所以需要適時地增加其他的車型。針對配送車輛，特提出以下幾點意見：（1）對重要客戶指定某幾輛車專門負責，以保證服務質量；（2）劃分配送區(qū)域時區(qū)，針對較遠的客戶群，使用較大配送量的車輛負責配送，而較近的客戶群則使用一般性的車輛負責配送；（3）指定某幾輛車專門負責臨時需求，即隨要隨送；（4）在路線安排上，一般方法是將客戶按地理位置分成幾個區(qū)域，再按照客戶要求的送達時間從小到大進行排序，優(yōu)先滿足要求送達時間早的客戶，如遇到問題則再進行調整。參考文獻1李軍，郭耀煌，物流車輛優(yōu)化調度理論與方法M.中國物資出版社.2謝勝利,唐敏,董金祥.求解TSP問題的一種改進的遺傳算法J.計算楨工程與應用,2002,38(8):58-60.3李向陽.遺傳算法求解VRP問題J.計算機工程與設計,2004,25(2):271-276.4胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究J.中國管理科學,200