1、第一章緒論1.1研究背景目前國際零售資本大量進入中國，有來自美國的沃爾瑪、 德國的麥德龍、法國的家樂福等幾家國際連鎖超市， 加上本市本土超市大大小小近幾十家超市，連鎖超市行業(yè)競爭日趨激烈。連鎖超市要想在市場競爭中獲得優(yōu)勢，很大程度上取決物流成本的控制，而這卻是供應(yīng)鏈管理可以提供的。本課題正是研究連鎖超市供應(yīng)鏈中的重要環(huán)節(jié)一物流配送方案設(shè)計。目前物流己經(jīng)成為公認的“第三利潤源泉”，而物流配送則被人們認為是這一利潤源泉的突破口，受到了國內(nèi)各行業(yè)的極大重視并得到迅速的發(fā)展。近兩年來我市的連鎖超市迅速發(fā)展，在促進物流配送業(yè)發(fā)展的同時，也對配送提出了更高的要求，物流配送成為廣泛關(guān)注的焦點。由于我國消費者

2、購物習(xí)慣的改變，這也直接導(dǎo)致了零售業(yè)態(tài)的多樣化，并衍生出多樣、快捷的商品配送需求。而自從中國加入世貿(mào)組織后，面對日趨激烈的市場競爭，各行各業(yè)都將面臨著現(xiàn)代化的物流配送模式的挑戰(zhàn)。在對連鎖超市物流配送的研究分析過程中，連鎖超市物流配送方案的合理化將直接影響到整個超市的物流成本。超市的配送方案是否合理化，是要根據(jù)企業(yè)的具體情況進行分析的，例如超市的配送的主體、配送的對象、配送的模式、以及顧客的需求等各種因素來決定的。在物流業(yè)發(fā)展迅猛的今天，設(shè)計一個合理的物流配送方案，具有很大意義。本課題以家樂福超市作為研究對象，首先分析配送模式現(xiàn)狀及存在的問題，之后通過分析超市銷售數(shù)據(jù)、目標客戶、客戶購買行為、商

3、品結(jié)構(gòu)等，并結(jié)合家樂福超市個門店的具體情況，通過遺傳算法優(yōu)化家樂福連鎖超市的配送路線，確定配送方案，并提出相關(guān)建議。1.2超市配送的現(xiàn)狀及發(fā)展趨勢超市配送的現(xiàn)狀在我國零售連鎖業(yè)不斷發(fā)生著日新月異變化的同時，連鎖企業(yè)信息系統(tǒng)的建卻相對滯 后，特別是配送系統(tǒng)落后制約了我國零售連鎖業(yè)發(fā)展，成為了向國際零售巨頭挑戰(zhàn)的瓶頸。 其主要的原因是因為合理的配送活動可以提高企業(yè)的供應(yīng)保證程度，降低缺貨風(fēng)險，實現(xiàn)低庫存或者零庫存，從而降低物流成本。國外一些連鎖超市企業(yè)非常重視配送系統(tǒng)的建設(shè)。其獨特的配送體系，大大降低了物流成本，加速了貨物周轉(zhuǎn)率。而相比之下，我國的零售企業(yè)統(tǒng)的落后。國內(nèi)的配送中心雖然擁有充足的場地

4、，足夠的人員配備和齊全的機械設(shè)備，但是仍然與國際先進水平仍然存在差距，主要是國內(nèi)的配送中心其配送系統(tǒng)大多只停留在庫存管理的水平，自動化、信息化程度低，對市場需求反應(yīng)速度慢。對于國內(nèi)的企業(yè)經(jīng)驗型的手工調(diào)節(jié)仍然在配送中起著舉足輕重的作用，配送方式大部分還是采用由門店提出補貨請求這種被動式的配送方式進行配送。這種經(jīng)驗型被動式配送方式與現(xiàn)代化的物流配送相差甚遠。但是值得慶幸的是，在中國零售連鎖業(yè)界已經(jīng)達成了共識，那就是“物流配送”和“信息技術(shù)”是連鎖企業(yè)競爭的主要砝碼和勝出的關(guān)鍵，配送系統(tǒng)這一環(huán)節(jié)已經(jīng)受到國內(nèi)各大業(yè)界的廣泛關(guān)注。超市配送的發(fā)展趨勢（1） 網(wǎng)絡(luò)化發(fā)展趨勢 現(xiàn)代社會產(chǎn)品的多元化以及門店數(shù)量

5、日益增多，超市的連鎖經(jīng)營成為主要趨勢。所以如何能夠及時采集企業(yè)內(nèi)部各門店商品銷售、存貨、訂貨信息，從而有效加快商品流轉(zhuǎn)速度這將勢必成為連鎖企業(yè)面臨的問題，并且我國現(xiàn)在互聯(lián)網(wǎng)技術(shù)已經(jīng)比較成熟，互聯(lián)網(wǎng)在商業(yè)領(lǐng)域的應(yīng)用也日趨普及，已近完全具備做好連鎖企業(yè)配送系統(tǒng)網(wǎng)絡(luò)化的技術(shù)支持。所以超市配送必然有著網(wǎng)絡(luò)化的發(fā)展趨勢。（2） 智能化發(fā)展趨勢 商業(yè)智能（BI）是一種以數(shù)據(jù)倉庫技術(shù)為基礎(chǔ)，借助聯(lián)機分析處理、數(shù)據(jù)挖掘工具來增強對數(shù)據(jù)的分析和處理能力，從而實現(xiàn)對企業(yè)業(yè)務(wù)信息的智能化管理的嶄新技術(shù)。目前國內(nèi)的應(yīng)用只是起步階段，一些開始涉足的企業(yè)還處在數(shù)據(jù)倉庫以及數(shù)據(jù) 集市的建設(shè)階段。在連鎖超市，商業(yè)智能可以對門

6、店的銷售數(shù)據(jù)、顧客購買行為、供應(yīng)商信息、門店員工管理等方面進行綜合分析。特別是在配送系統(tǒng)中引入商業(yè)智能技術(shù)以后，可以有效改善目前系統(tǒng)的不足，提高市場反應(yīng)率、準確率，從而達到提高企業(yè)的競爭力的目的。所以超市配送必然有著智能化的發(fā)展趨勢。1.3配送路線優(yōu)化的意義配送合理化與否是配送決策系統(tǒng)的重要內(nèi)容，配送線路的合理與否又是配送合理化的關(guān)鍵。選擇合的理配送路線，對企業(yè)和社會都具有很重要的意義。對企業(yè)來說，（1）優(yōu)化配送路線，可以減少配送時間和配送里程，提高配送效率，增加 車輛利用率，降低配送成本。（2）可以加快物流速度，能準時、快速地把貨物送到客戶的手中，提高客戶滿意度。（3）使配送作業(yè)安排合理化，

7、提高企業(yè)作業(yè)效率，有利于企業(yè)提高競 爭力與效益。對社會來說，它可以節(jié)省運輸車輛，減少車輛空載率，降低了社會物流成本，對其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。與此同時，還能緩解交通緊張狀況，減少噪聲、尾氣排放等運輸污染，對民生和環(huán)境也有不容忽視的作用。第二章家樂福超市配送現(xiàn)狀分析2.1家樂福超市公司簡介家樂福超市成立于1959年的家樂福集團是大賣場業(yè)態(tài)的首創(chuàng)者，是歐洲第一大零售商，世界第二大國際化零售連鎖集團?，F(xiàn)擁有11,000多家營運零售單位，業(yè)務(wù)范圍遍及世界30個國家和地區(qū)。集團以三種主要經(jīng)營業(yè)態(tài)引領(lǐng)市場： 大型超市，超市以及折扣店。 此外，家樂福還在一 些國家發(fā)展了便利店和會員制量販店。 2

8、004年集團稅后銷售額增至 726.68億歐元，員工總 數(shù)超過43萬人。家樂福于1969年開始進入國際市場，目前在世界上31個國家和地區(qū)擁有一萬多家銷售網(wǎng)點，涉及的零售業(yè)態(tài)包括大賣場、超級市場、折扣店、便利店、倉儲式商店與電子商務(wù)，集團的50萬名員工正致力于為 20億消費者服務(wù)。家樂福集團建立了全球性的采購網(wǎng)絡(luò)，向不同國家和地區(qū)的供應(yīng)商采購具有市場競爭力的商品。家樂福于1995年進入中國后，采用國際先進的超市管理模式，致力于為社會各界提供價廉物美的商品和優(yōu)質(zhì)的服務(wù)，受到廣大消費者的青睞和肯定，其“開心購物家樂福”、“一站式購物”等理念已經(jīng)深入人心。如今，家樂福已成功地進入了中國的25個城市，在

9、北至哈爾濱、南至深圳、 西至烏魯木齊、東至上海的中國廣袤土地上開設(shè)了109家大型超市，聘請3萬多名員工。在在華外資零售企業(yè)中處于領(lǐng)先地位。家樂福還向中國引進迪亞折扣店和冠軍食品超市兩種業(yè)態(tài)。本文以上海的家樂福超市為研究對象，分析20個分店的物流配送路線優(yōu)化問題。家樂福分店數(shù)目有 20個，且都具有一定的規(guī)模，網(wǎng)點的貨物需求情況類似。需求網(wǎng)點 處在配送中心輻射范圍內(nèi)。2.2家樂福超市配送路線作業(yè)現(xiàn)狀中轉(zhuǎn)站分析中轉(zhuǎn)站對于配送線路的影響力是不言而喻的，由于中轉(zhuǎn)站的存在決定了配送線路的網(wǎng)點布局，進而影響到配送線路的網(wǎng)絡(luò)規(guī)劃。因此看，可以說要研究配送線路的優(yōu)化，必須首先研究中轉(zhuǎn)站的分布情況。2.2. 1.

10、1中轉(zhuǎn)站的地理位置分析(1) 配送需求點現(xiàn)在以家樂福物流配送中心為原點(0,0),根據(jù)各個分店具體地理位置換算成二維坐標，各商店的坐標如下表 1所示：X(km)； Y(km)表2-1分店所在地坐標XY坐分店與配送中心間距1892-453244102053-3066778158-7-691591010121191012-8-13134-5146615-7-8163417-5101829191-152083車輛路線圖2-1 家樂福的配送模式2求得，配送中心與商店(2) 現(xiàn)有路線是固定不變且為已知，每條線路行駛距離可由表之間，商店與商店之間的距離分析如下表：表2-2 配送中心與分店之間，分店與分店之

11、間的距離(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.431128103826153317181436175303936345003745264143402

12、0253624344139153369.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.1

13、267.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.

14、58.517138.57.124145195.17.10248.5191525211936152331122828269.2102211192624019208.56126.117334.512179.29.27.1238.93.6195.1158.5190221.2 中轉(zhuǎn)站需求信息分析具體的每個分店（一年 365天）平均每天的需求量信息見表。表2-3 每個分店（一年365天）平均每天的需求量分店12345678910需求量2324123513分店11121314151617181920需求量2342121322車輛數(shù)分析所需車輛數(shù)分析（家樂福配送中心一年（365天）的車輛調(diào)度）:表2-4車輛

15、調(diào)度情況車輛運用數(shù)101291110111010891011運用天數(shù)2530364246494838241386表2-5車輛運用數(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.3家樂福超市配送存在的問題目前家樂福的物流體系是，所有貨物由供貨商直接送達店面，這種方式雖然靈活，但影響了供貨速度，也加重了供貨商的負擔。由于家樂福各門店自

16、行采購，供貨商不一，大大影響了供貨速度；并且，家樂福目前的供貨方式也加重了供貨商負擔。家樂福的商品配送分幾種情況，大部分情況是通過第三方物流實現(xiàn)的，費用由供應(yīng)商承擔。有些家樂福的門店還習(xí)慣于將降價損失、 損耗和營業(yè)額、毛利率指標的完不成數(shù)，轉(zhuǎn)嫁給供應(yīng)商來承擔，也就是說供應(yīng)商與總部談好的交易條件到了門店是要附加的，因為家樂福是最大的， 供應(yīng)商也無可奈何；另外據(jù)悉，家樂福近期采取的分區(qū)采購政策，也使得供貨商從過去習(xí)慣于以一對一的模式變成了以一對多，這樣無疑加大了供貨商的運營成本，從而導(dǎo)致他們抱怨多多。主要問題如下：（1）即時配送率低家樂福超市目前物流管理還是有很多不足的地方，即時配送率很低，配送的

17、殘損率和差錯率也較高，供應(yīng)鏈并不是很暢通。此外，由于現(xiàn)在產(chǎn)品的多元化，現(xiàn)在快速消費品對消費及時程度也要求很高，運輸過程中對配送時間（從生產(chǎn)日期到目前的市場 ）要求也是一個相當 高的地步，如果一些奶制品的配送時間超過3天，超市就不會要了，而有些商品超過一個的配送時間就會成為滯銷品。 雖然家樂福超市為了增強企業(yè)競爭力降低物流成本也建立了自己 的配送中心，為企業(yè)內(nèi)部的連鎖網(wǎng)點提供物流配送服務(wù)，但是從總體來看，配送中心的運作 效率不高，配送的差錯率和殘損率較高。（2）基礎(chǔ)設(shè)施較差家樂福超市目前一些基礎(chǔ)設(shè)施并不是很完善， 現(xiàn)代化、信息化、機械化程度較低， 配送 效率也越低，由于這些原因?qū)е屡渌瓦^程物耗大

18、， 所以也就使得物流成本提高， 這也是家樂 福超市物流配送成本居高不下的原因。（3）配送標準化水平低家樂福超市配送的現(xiàn)代化水平較低，配送的標準化、規(guī)范化是連鎖經(jīng)營的核心，設(shè)計一個規(guī)范的統(tǒng)一的有序的業(yè)務(wù)流程式系統(tǒng)是實行連鎖經(jīng)營和配送的關(guān)鍵。家樂福連鎖超市規(guī)范化水平偏低也是一個不容忽視的現(xiàn)實，配送中心關(guān)于集、配、送等功能還沒有形成一套規(guī)范的作業(yè)程序和嚴整的體系。一個企業(yè)要想做高效的物流配送業(yè)務(wù)，那么在運輸工具和信息系統(tǒng)方面必須做到標準化。（4）競爭手段單一家樂福超市整體經(jīng)營水平低下，營銷手段單一，超市主要還是停留在價格競爭的基礎(chǔ)層 面上。第三章家樂福超市物流配送路線的優(yōu)化3.1研究對象目標設(shè)定物流

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

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

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

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

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

24、需求點的需求量為qi（i =1,2,丄），并且滿足qi ： g，需求點i到j(luò)的運距為dj，配送中心到各個需求點的距離為dij（i = 0,j = 1,2,.,L），再設(shè)nk為第k輛汽車配送的需求點數(shù)（m=o表示未使用第k輛汽車），用集合Rk表示第k條路徑，其中的元素rki表示需求點rki在路徑k中的順序為i （不包括配送中心），令rko=o表示配送中心， m為每輛車單位里程的行駛費用，C為每輛車的派遣費用，考慮運輸量約束，停車點車輛數(shù)目等約束，可以定義如下的基本模型：k nkminZ 二m 'drk(Mdmsign(nk) K C (3-1)k生i生nk、qrki g(3-2)i 1(

25、3-3)(3-4)(3-5)Rk 二Ji hi 爼2,，L,i =1,2,., nJsig n(njnk >10 其他(3-6)在上述模型中各個公式所代表的涵義如下：（3-1 ）式為目標函數(shù)，求總的配送費用最低；（3-2）式用于保證每條路徑上各個需求點的需求量和不超過汽車的載重量;（3-3 ）式表明每條路徑上的需求點數(shù)不超過總需求點數(shù)；（3-4 ）式表明每個需求點都得到配送服務(wù)；（3-5）式表示每條路徑的需求點的組成；(3-6 )式表示當?shù)趉輛汽車服務(wù)的客戶數(shù)大于或等于1時，說明該輛汽車參加了配送,則取 sign(nk)=1，當?shù)趉輛汽車服務(wù)的客戶數(shù)小于1時，表示未使用該輛汽車，因此取s

26、ign(nQ =0 ；第四章家樂福超市物流配送路線模型求解4.1遺傳算法的原理遺傳算法GA(Genetic Algorithms)把問題的解表示成"染色體”，在算法中也即是以二 進制編碼或自然數(shù)編碼的串。并且在執(zhí)行遺傳算法之前，給出一群“染色體”，也即假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)實際 情況的“染色體”來復(fù)制，再通過交叉、變異的過程，能夠產(chǎn)生更加適應(yīng)環(huán)境的新一代“染 色體”組。如此，一代一代地進化，到最后就會獲得最適應(yīng)環(huán)境的一個“染色體”，它就是 我們所求問題的最優(yōu)解。長度為L的n個串bi(i=i , 2,，n)，就是遺傳算法的初

27、始解群，也可以稱之為初始群 體。在這每一個串中，每個位就是單個染色體的基因。依照生物進化的術(shù)語，對群體需要執(zhí) 行的操作有以下三種：(1) 選擇(Selection)這是從群體中選擇出較適應(yīng)環(huán)境的個體。這些選中的個體用于繁殖下一代。故有時也稱這一操作為再生。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應(yīng)度而決定其繁殖量的，故有時也稱為非均勻再生。(2) 交叉(Crossover)就是在選取用來繁殖下一代染色體的個體中，對其中兩個不同的單個染色體隨機選擇一個子串交叉，并以此來產(chǎn)生新的個體。(3) 變異(Mutation)這是在選取的個體中， 隨機得選擇兩點，將兩個點之間的子串按照一定的規(guī)

28、則和約定進 行變異。遺傳算法與其它傳統(tǒng)方法相比，具有如下優(yōu)點：(1) 適用范圍廣，具有很強的搜索能力；(2) 能以很大的概率找到問題的全局最優(yōu)解；(3) 能有效處理較大規(guī)模優(yōu)化問題；(4) 搜尋空間并行性；(5) 魯棒性強；(6 )智能性；(7)只通過目標函數(shù)計算適應(yīng)度，不受約束條件束縛?；谝陨蠋c，本文將采用遺傳算法對家樂福超市物流配送路線進行尋優(yōu)。4.2遺傳算法的步驟算法思想與算法流程首先根據(jù)每項任務(wù)的需求量q,總?cè)蝿?wù)量以及每輛車的最大載重量q，每輛車的任務(wù)不超過其最大載重量 g，確定至少需要 m輛車來完成任務(wù)，最后計算每輛車的總里程，其中總 里程最小的即為所求任務(wù)安排。(1)構(gòu)造染色體

29、設(shè)車輛的可行線路可以編成自然數(shù)編碼的長度為m+ I的染色體(iii，i 12，i 13， iis； i 21， i 22 i2t ； ； i mi，i m2im| .)，i kj為有需求的分店，即第i kj項任務(wù),|為分店的總數(shù)目，m為車輛從配送中心出發(fā)，經(jīng)過各分 店后,又回到配送中心的各條回路， 即m輛車；車輛行駛線路為：第一輛車從配送中心出發(fā)， 每個分店訪問一次，經(jīng)過 i 11， i 12， i 13， i1s的路線，又回到配送中心，形成子路徑1；第二輛車從配送中心出發(fā)，每個分店訪問一次，經(jīng)過以前未經(jīng)過的i 21， i 22i 2t路線，又回到配送中心，形成子路徑2;這樣重復(fù)，直到每個分店

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

31、下，隨機產(chǎn)生 L個需求點的全排列，構(gòu)成初始種群，女口： i1，s Jsi2,.i l。若qijW g且qij > g將S至I的基因依次向后移動一位,使S位空出,t將0插入S位。接著若7j =sJ4Vtq ij <g且v qij >g如上面的操作,使t空出，將配送中心插入j=s第t位。如此繼續(xù)，直到將m個配送中心全部插入染色體為止。這樣就構(gòu)成了一條初始染色 體，如此反復(fù)，構(gòu)造滿足群體數(shù)的染色體個數(shù)。(3) 適應(yīng)度函數(shù)對種群中的每個染色體 V(i=1,2,.)根據(jù)目標函數(shù)的式子計算其值為U,若染色體對應(yīng)的是不可行解，則賦予其目標函數(shù)值一個很大的整數(shù)，適應(yīng)度函數(shù)可以設(shè)為：f=1/Z

32、i+M*1000,則fi >0 , Z為染色體 V對應(yīng)的運輸成本；fi為染色體V的適應(yīng)度，fi越大, 其性能越好，其對應(yīng)的解越接近最優(yōu)解。(4) 遺傳算子1) 選擇算子個體選擇的分配方法：按比例的適應(yīng)度分配。利用比例于各個體適應(yīng)度的概率決定其子孫的遺留可能性，選擇概率公式為MP i = f i / 'i =1f i即適應(yīng)度越大，其選擇概率越大。根據(jù)計算父代和子代的適應(yīng)度，并將每代群體中的 N個個體按適應(yīng)度由大到小排列，排在第一位的個體性能最優(yōu)，將它復(fù)制一個直接進入下一代，并排在第一位。下一代群體的另N-1個個體需要根據(jù)前代群體的N個個體的適應(yīng)度，采用輪盤賭選擇法產(chǎn)生。2) 交叉算

33、子對通過選擇操作的新群體，除排在第一位的最優(yōu)個體外，另N-1個個體要按交叉概率Pc進行配對交叉重組。本文采用順序法實施交叉操作：a) 隨機在你代個體中選取一個交配區(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ā)生

34、變異的個體染色體，然后在該染色體上隨機選取非零基因位，把這 2個位置上的基因互換形成新的基因串。（5）控制參數(shù)和算法的終止條件1）參數(shù)設(shè)置交叉概率Pc=0.6 ;變異概率 Pm=0.01 ;終止代數(shù) T=100;初始種群 N=100;mS=0.65 ;車輛數(shù) m=v qi/ S +1 （gi為需求點i的貨運量）;g=8噸；i A2）終止條件由于計算時間的機器容量都是有限的，代數(shù)不能無限長，故當?shù)螖?shù)達到規(guī)定值T時，停止計算。遺傳算法的理論求解步驟本文所設(shè)計的遺傳算法的基本流程如下：STEP1 :初始化，產(chǎn)生初始種群。STEP2 :個體評價，即計算種群中每個個體的適應(yīng)度。STEP3 :按選擇概

35、率 Ps,執(zhí)行選擇算子，從當前種群中選擇部分個體進入下一代種群。STEP4 :按交叉概率 Pc,執(zhí)行交叉算子。STEP5 :按變異概率 Pm,執(zhí)行變異算子。STEP6 :若滿足設(shè)定的終止條件，則執(zhí)行 STEP7否則執(zhí)行STEP2STEP7 :輸出種群中適應(yīng)度最優(yōu)的個體作為問題的最優(yōu)解或滿意解。圖4-1應(yīng)用遺傳算法求解問題示意圖第一步和第二步可以歸結(jié)為建立優(yōu)化問題的模型，可以是解析性的數(shù)學(xué)模型，也可以是非解析性模型。這是應(yīng)用任何優(yōu)化算法求解優(yōu)化問題都需要的步驟。第三步“編碼”實際上包含了設(shè)計或選擇個體基因型的表示方法、設(shè)計解的表現(xiàn)型到個體基因型的轉(zhuǎn)換算法。第四步“解碼”是因為遺傳算子只作用于編碼

36、后的染色體，而染色體的優(yōu)劣要到解空間計算其對應(yīng)的值由個體表現(xiàn)型計算目標函數(shù)值后才能進行判斷。第五步“確定適應(yīng)度轉(zhuǎn)換規(guī)則” 是因為染色體所對應(yīng)的解空間的值可能相差很大，不適合直接用來定量評估個體的優(yōu)劣。第六步“設(shè)計遺傳算子”即為設(shè)計交叉、變異、選擇等遺傳操作，遺傳算子與待優(yōu)化問題、染色體的編碼方案有很大的關(guān)系，也是遺傳算法應(yīng)用領(lǐng)域的一個重要創(chuàng)新點。第七步“確定運行參數(shù)”即確定遺傳算法中的交叉概率、變異概率、最大進化代數(shù)等參數(shù)。4.3優(yōu)化結(jié)果分析優(yōu)化前結(jié)果表4-1優(yōu)化前路線分析現(xiàn)有路線行駛距離（KM）實載量（噸）準載量（噸）實載率（%）0-2-5-0363.8847.5%0-9-12-0323.9

37、848.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-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%優(yōu)化前成本經(jīng)計算為10757元。優(yōu)化后結(jié)果表4-2運行結(jié)果分析所需車輛數(shù)行駛距離（KM運輸成本（元）第1次7376.8712706第2次7372.6312579第

38、3次7333.5211406第4次7381.5912848第5次7416.6913901第6次7374.5812637第7次7383.3612901第8次7291.5710147平均值7366.3512291最小值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-1

39、4-0192.9836.25%合計231.345.656（平均）81.43%優(yōu)化后只需要7輛車，減少了 5輛車；實載率增加到81.43%，提高了 31.13%;總成本減少了 610元。D=291.57KM;K=7 輛;minZ=10147 元.通過本文的分析可知，家樂福的現(xiàn)有配送路線還可以再優(yōu)化，而達到節(jié)約運輸成本的目的；第五章總結(jié)與建議在物流配送業(yè)務(wù)中， 合理確定配送路徑是提商服務(wù)質(zhì)量，降低配送成本，增加經(jīng)濟效益的重要手段。本文以家樂福物流配送路徑為研究背景，探討物流配送路徑優(yōu)化問題，針對家樂福物流配送路徑的現(xiàn)狀， 分析其不足之處，找出了車輛路徑優(yōu)化存在的問題；分析了相關(guān)的配送數(shù)據(jù)，并對優(yōu)化

40、計算方法進行了分析，結(jié)合實際情況，選擇遺傳算法作為論文的主要方法；結(jié)合背景材料，建立了數(shù)學(xué)模型，并設(shè)計了遺傳算法；通過本文的分析可知，家樂福 的現(xiàn)有配送路線還可以再優(yōu)化，而達到節(jié)約運輸成本的目的；還證明了遺傳算法在路徑優(yōu)化問題中是一種很實用的計算方法，具備很多優(yōu)點。公司還在如下方面加強。（1）全面掌握每種業(yè)態(tài)模式各門店的需求情況。深入本配送區(qū)域的門店，進行細致周密的調(diào)查研究，了解和掌握各門店銷售情況和各種商品的品種、規(guī)格、型號、數(shù)量、接受價 格和供應(yīng)周期等情況，并進行科學(xué)的預(yù)測。在此基礎(chǔ)上，建立配送檔案，深入門店，隨時掌 握門店需求，迅速傳遞信息，加強各種業(yè)態(tài)模式下門店之間的聯(lián)系，可以采用大店

41、管理小店的管理方法，保證按需組織配送。（2）建立好公司與供應(yīng)商之間的關(guān)系。根據(jù)所要配送的商品的特性、門店的具體位置和供應(yīng)商的合作愿望以及合作能力， 將一部分配送任務(wù)交給供應(yīng)商去完成。因為大批量購買能夠使價格更低，同時單位配送成本也會隨之降低，所以公司可以通過加大蘇果超市的主要產(chǎn)品的配送比例獲得更多的利益。（3）調(diào)整好配送人員各層次結(jié)構(gòu)的比例和加強配送人員的培訓(xùn)。蘇果公司物流配送人員由戰(zhàn)略層人員、戰(zhàn)術(shù)層人員和操作層人員三種層次的員工構(gòu)成，公司應(yīng)當合理調(diào)整不同層次物流配送人員的比例， 調(diào)動員工的積極性， 加強對員工的培訓(xùn)， 充分挖掘各層次人員的潛 力，讓員工各司其職，各盡所能。參考文獻1 袁慶達，

42、閆昱，周再玲.Tabu Search算法在優(yōu)化配送線路問題中的應(yīng)用J.計算機工程，2001, 1127 ( 11): 86-89.2 高曉亮，伊俊敏，甘衛(wèi)華.倉儲與配送管理M.北京：清華大學(xué)出版社，2009: 288-3003 許星,物流配送路徑優(yōu)化問題的研究D.浙江：浙江大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機應(yīng)用技術(shù),2006.4 李金蘋.現(xiàn)代物流配送系統(tǒng)的運輸優(yōu)化調(diào)度方案 J.物流技術(shù)，2002, (5): 11-13. 賈爭現(xiàn).物流配送中心規(guī)劃與設(shè)計 M.北京：機械工業(yè)出版社， 2011, (8): 1-22.附錄程序代碼,商店與商店之間的距離fun ction distA ;%計算配送中心與商

43、店之間zb=0 0 01 8 92 -4 53 2 44 10 205 3 -306 6 77 8 158 -7 -69 15 910 10 1211 9 1012 -8 -1313 4 -514 6 615 -7 -816 3 417 -5 1018 2 919 1 -1520 8 3；n,nn=size(zb);distA=zeros (n,n);for i=1: nfor j=1: nx=sqrt(zb(i,2)-zb(j,2)F2+(zb(i,3)-zb(j,3)A2);format short gy=roundn( x,-2);distA(i,j)=y;endenddistAfun

44、ctio n vrpdistA=zbzl;h,hh=size(distA);lchrom=h-1;% 染色體長度popsize=100;% 種群規(guī)模pc=0.6;%交叉概率pm=0.01;%變異概率maxge n=100;%最大進化代數(shù)調(diào)用初始化種群函數(shù)pop=in itialize(popsize,lchrom); %口為按各網(wǎng)點序號排列的需求量q=232412352342121322；for ii=1:maxge np=pop;kmun=zeros(popsize,1);for i=1:popsizesumd2=0;for j=1:(lchrom-1)sumd1=distA(p(i, j)

45、+1, p(i, j+1)+1);%distA=dista nee sumd2=sumd2+sumd1;endsumd2=sumd2+distA(1, p(i, 1)+1)+distA(1, p(i, lchrom)+1);sumq2=q(p(i, 1);k=1;fcf=0;t=0;for j=2:lchromsumq1=q(p(i, j);%q= 需求量sumq2=sumq2+sumq1;if sumq2>8sumq2=q(p (i, j);sumd2=sumd2+distA (1, p(i, j-1)+1)+distA(1,p(i, j)+1)-distA(p(i,j-1)+1,p(

46、i,j)+1)；k=k+1;%用車數(shù)量t=0;endenddistB(i,1)=sumd2;ch=7;M=ch-k;if M>0M=0;elseM=-M;endkmun (i)=k;fit(i,1)=1/(distB(i, 1)*30+k*200+M*1000);enddistB;kmun;totalfit=sum(fit);prob=fit/totalfit;prob=cumsum(prob);rNums=sort(ra nd(popsize,1);%Ge nerate ran dom nu mbers%Select in dividuals from the oldPop to the newfitI n=1; newln=1;while newl