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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、2 家樂福超市配送路線作業(yè)現(xiàn)狀2.2.1 配送距離分析(1)配送需求點(diǎn)坐標(biāo)：現(xiàn)在以家樂福物流配送中心為原點(diǎn)(0,0),建立直角坐標(biāo)系,各商店的坐標(biāo)如下表所示:X(km);Y(km)表2-1分店所在地坐標(biāo)分店與配送中心間距離坐標(biāo)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點(diǎn)表示配送中心)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天)的車輛調(diào)度):表2-3車輛調(diào)度情況車輛運(yùn)用數(shù)101291110111010891011運(yùn)用天數(shù)2530364246494838241386表2-4車輛運(yùn)用數(shù)所占比率車輛運(yùn)用數(shù)相對比率累計(jì)比率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 商品品種分析超市以滿足消費(fèi)者對基本生活用品一次性購買需要為經(jīng)營宗旨，是一種經(jīng)營品項(xiàng)較多的零售業(yè)態(tài)。下面對商品進(jìn)行分類分析。 一、大分類 大分類是超市最粗線條的分類。大分類的主要標(biāo)準(zhǔn)是商品特征，如畜產(chǎn)、

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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隨機(jī)選取發(fā)生變異的個體染色體，然后在該染色體上隨機(jī)選取2個非零基因位，把這2個位置上的基因互換形成新的基因串。（5）控制參數(shù)和算法的終止條件1)參數(shù)設(shè)置交叉概率Pc=0.6；變異概率Pm=0.

46、01；終止代數(shù)T=100；初始種群N=100；=0.65；車輛數(shù)m=qi/+1（gi為需求點(diǎn)i的貨運(yùn)量）；g=8噸；2)終止條件由于計(jì)算時間的機(jī)器容量都是有限的，代數(shù)不能無限長，故當(dāng)?shù)螖?shù)達(dá)到規(guī)定值T時，停止計(jì)算。4.優(yōu)化結(jié)果分析現(xiàn)有路線行駛距離（KM）實(shí)載量（噸）準(zhǔn)載量（噸）實(shí)載率（%）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%合計(jì)211.945.180(平均)50.3%4.1 優(yōu)化前結(jié)果表4-1優(yōu)化前路線分析優(yōu)化前成本經(jīng)計(jì)算為10757元。4.2 優(yōu)化后結(jié)果表4-2運(yùn)行結(jié)果分析所需車輛數(shù)行駛距離（KM）運(yùn)輸成本（元）第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）實(shí)載量（噸）準(zhǔn)載量（噸）實(shí)載率%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%合計(jì)231.345.656（平均）81.43%優(yōu)化后只需要7輛車，減少了5輛車；實(shí)載率增加到81.43%，提高了31.13%;總成本減少了610元。D=291.57

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

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