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

2、標(biāo)。 關(guān)鍵詞：物流配送；路徑優(yōu)化；遺傳算法 the logistics of supermarket of carrefour provides and delivers the route to optimize abstract in logistics and distribution business, a reasonable path is to determine the distribution to service quality, reduce distribution costs, an important means to enhance economic effici

3、ency. logistics 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 developmen

4、t, the concept 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 wh

5、ich, combined with 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

6、order to minimize transportation costs to reach the goal. key words： logistics and distribution; path optimization; genetic algorithm 畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文） ，是我個(gè)人在指導(dǎo)教 師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別 加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過 的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)

7、位 或?qū)W歷而使用過的材料。對(duì)本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人 或集體，均已在文中作了明確的說明并表示了謝意。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日期： 使用授權(quán)說明使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論 文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和 電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并 提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其 它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊?文的部分或全部內(nèi)容。 作者簽名： 日 期： 學(xué)位論文原創(chuàng)性聲明學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)

8、師的指導(dǎo)下獨(dú)立進(jìn)行 研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本 論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。對(duì)本 文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。 本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定， 同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版， 允許論文被查閱和借閱。本人授權(quán) 大學(xué)可以將本學(xué)位 論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、 縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 涉

9、密論文按學(xué)校規(guī)定處理。 作者簽名：日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 指導(dǎo)教師評(píng)閱書指導(dǎo)教師評(píng)閱書 指導(dǎo)教師評(píng)價(jià)：指導(dǎo)教師評(píng)價(jià)： 一、撰寫（設(shè)計(jì)）過程 1、學(xué)生在論文（設(shè)計(jì)）過程中的治學(xué)態(tài)度、工作精神 優(yōu) 良 中 及格 不及格 2、學(xué)生掌握專業(yè)知識(shí)、技能的扎實(shí)程度 優(yōu) 良 中 及格 不及格 3、學(xué)生綜合運(yùn)用所學(xué)知識(shí)和專業(yè)技能分析和解決問題的能力 優(yōu) 良 中 及格 不及格 4、研究方法的科學(xué)性；技術(shù)線路的可行性；設(shè)計(jì)方案的合理性 優(yōu) 良 中 及格 不及格 5、完成畢業(yè)論文（設(shè)計(jì)）期間的出勤情況 優(yōu) 良 中 及格 不及格 二、論文（設(shè)計(jì)）質(zhì)量 1、論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫

10、規(guī)范？ 優(yōu) 良 中 及格 不及格 2、是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？ 優(yōu) 良 中 及格 不及格 三、論文（設(shè)計(jì)）水平 1、論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問題的指導(dǎo)意義 優(yōu) 良 中 及格 不及格 2、論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？ 優(yōu) 良 中 及格 不及格 3、論文（設(shè)計(jì)說明書）所體現(xiàn)的整體水平 優(yōu) 良 中 及格 不及格 建議成績：建議成績： 優(yōu)優(yōu) 良良 中中 及格及格 不及格不及格 （在所選等級(jí)前的內(nèi)畫“”） 指導(dǎo)教師：指導(dǎo)教師： （簽名） 單位：單位： （蓋章） 年年 月月 日日 評(píng)閱教師評(píng)閱書評(píng)閱教師評(píng)閱書 評(píng)閱教師評(píng)價(jià)：評(píng)閱教師評(píng)價(jià)： 一、論文（設(shè)計(jì)）質(zhì)量

11、一、論文（設(shè)計(jì)）質(zhì)量 1、論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？ 優(yōu) 良 中 及格 不及格 2、是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？ 優(yōu) 良 中 及格 不及格 二、論文（設(shè)計(jì)）水平二、論文（設(shè)計(jì)）水平 1、論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問題的指導(dǎo)意義 優(yōu) 良 中 及格 不及格 2、論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？ 優(yōu) 良 中 及格 不及格 3、論文（設(shè)計(jì)說明書）所體現(xiàn)的整體水平 優(yōu) 良 中 及格 不及格 建議成績：建議成績： 優(yōu)優(yōu) 良良 中中 及格及格 不及格不及格 （在所選等級(jí)前的內(nèi)畫“”） 評(píng)閱教師：評(píng)閱教師： （簽名） 單位：單位： （蓋章） 年年 月月 日日

12、教研室（或答辯小組）及教學(xué)系意見教研室（或答辯小組）及教學(xué)系意見 教研室（或答辯小組）評(píng)價(jià)：教研室（或答辯小組）評(píng)價(jià)： 一、答辯過程一、答辯過程 1、畢業(yè)論文（設(shè)計(jì)）的基本要點(diǎn)和見解的敘述情況 優(yōu) 良 中 及格 不及格 2、對(duì)答辯問題的反應(yīng)、理解、表達(dá)情況 優(yōu) 良 中 及格 不及格 3、學(xué)生答辯過程中的精神狀態(tài) 優(yōu) 良 中 及格 不及格 二、論文（設(shè)計(jì)）質(zhì)量二、論文（設(shè)計(jì)）質(zhì)量 1、論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？ 優(yōu) 良 中 及格 不及格 2、是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？ 優(yōu) 良 中 及格 不及格 三、論文（設(shè)計(jì)）水平三、論文（設(shè)計(jì)）水平 1、論文（設(shè)計(jì)）的理論

13、意義或?qū)鉀Q實(shí)際問題的指導(dǎo)意義 優(yōu) 良 中 及格 不及格 2、論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？ 優(yōu) 良 中 及格 不及格 3、論文（設(shè)計(jì)說明書）所體現(xiàn)的整體水平 優(yōu) 良 中 及格 不及格 評(píng)定成績：評(píng)定成績： 優(yōu)優(yōu) 良良 中中 及格及格 不及格不及格 （在所選等級(jí)前的內(nèi)畫“”） 教研室主任（或答辯小組組長）：教研室主任（或答辯小組組長）： （簽名） 年年 月月 日日 教學(xué)系意見：教學(xué)系意見： 系主任：系主任： （簽名） 年年 月月 日日 目目 錄錄 1.緒論.1 1.1 選題目的和意義.1 1.2 國內(nèi)外物流配送路線優(yōu)化研究現(xiàn)狀.2 1.3 研究內(nèi)容與技術(shù)路線.3 2. 家樂福超市配送路

14、線現(xiàn)狀.5 2.1 家樂福超市概況.5 2.2 家樂福超市配送路線作業(yè)現(xiàn)狀.6 2.2.1 配送距離分析.6 2.2.2 車輛數(shù)分析.7 2.2.3 需求量分析.8 2.2.4 商品品種分析.8 2.3 家樂福超市配送現(xiàn)有路線問題分析.11 3.配送路線優(yōu)化建模與求解.12 3.1 研究對(duì)象目標(biāo)設(shè)定.12 3.2 模型的構(gòu)建.14 3.2 遺傳算法.16 3.2.1 遺傳算法介紹.16 3.2.2 算法思想與算法流程.18 4.優(yōu)化結(jié)果分析.21 4.2 優(yōu)化后結(jié)果.21 4.3 結(jié)論.22 5.總結(jié)與建議.23 參考文獻(xiàn).24 致謝.25 附錄一：matlab 編程.26 1.緒論 1.1

15、選題目的和意義 配送是一項(xiàng)特殊的、綜合性的物流運(yùn)動(dòng)，其運(yùn)行和發(fā)展有著深刻的社會(huì)根源 和歷史背景。在市場經(jīng)濟(jì)體系中，物流配送如同人體的血管，把國民經(jīng)濟(jì)各個(gè)部 分緊密地聯(lián)系在一起。配送是物流中一個(gè)重要的直接與消費(fèi)者相連的環(huán)節(jié)，是將 貨物從物流結(jié)點(diǎn)送達(dá)收貨人的過程，是在集貨、配貨基礎(chǔ)上，完全按用戶要求， 包括種類、品種搭配、數(shù)量、時(shí)間等方面的要求所進(jìn)行的運(yùn)送，是“配”和“送” 的有機(jī)結(jié)合形式。其主要包括集貨作業(yè)、配貨作業(yè)、車載貨物的配裝、配送線路 的確定。 在生活中，基于電子商務(wù)的物流配送業(yè)務(wù)量逐漸增加，如果還沿用以前的物 流方法來組織配送，會(huì)產(chǎn)生很多問題。這些問題歸納起來，包括以下幾點(diǎn): 1)服務(wù)

16、質(zhì)量的下降。電子商務(wù)的特征是交易量巨大和交易速度極快，而傳統(tǒng) 物流配送的特點(diǎn)是人工調(diào)度、反應(yīng)時(shí)間長。信息流與物流的矛盾會(huì)導(dǎo)致整個(gè)電子 商務(wù)客戶服務(wù)的低效。也許客戶可以在幾十秒內(nèi)完成一次交易，卻要等上一個(gè)星 期才能收到貨物，這樣的服務(wù)只能逐漸失掉客戶。 2)物流成本控制困難。傳統(tǒng)的物流配送大多是由人工調(diào)度的，在交易量較小 的情況下，可以合理地安排配送，降低成本。一旦交易量增加、交易速度加快， 配送調(diào)度就會(huì)超出人工的能力范圍，會(huì)導(dǎo)致大量的不合理調(diào)度的出現(xiàn)，物流成本 無法控制。 3)增加城市交通的負(fù)擔(dān)。物流配送調(diào)度的不合理，會(huì)使物流配送的行車路線 變長，導(dǎo)致在運(yùn)車輛增加，從而給本已擁擠的城市交通加重

17、負(fù)擔(dān)。要解決以上的 問題，使物流配送調(diào)度滿足以下目標(biāo)準(zhǔn)時(shí)送貨。就是要客戶選擇貨物送達(dá)他們 指定地點(diǎn)的時(shí)間，要按照每個(gè)客戶的時(shí)間要求安排物流配送?？偝杀咀畹汀?總行車路徑最短。 當(dāng)前，物流的現(xiàn)代化水平不僅成為反映一個(gè)國家現(xiàn)代化程度和綜合國力的重 要標(biāo)志，也成為城市經(jīng)濟(jì)發(fā)展水平的體現(xiàn)，被喻為促進(jìn)經(jīng)濟(jì)發(fā)展的“加速器” 。 物流配送是一種先進(jìn)的現(xiàn)代物流形式，它不但給供應(yīng)者和需求者帶來降低物流成 本、享受優(yōu)質(zhì)服務(wù)的直接效益，而且還能為社會(huì)節(jié)省運(yùn)輸車次、緩解交通壓力、 減少運(yùn)輸污染、保護(hù)生態(tài)環(huán)。 而今，由于小批量、多批次的及時(shí)配送方式的發(fā)展，運(yùn)輸費(fèi)用正在逐年提升， 許多企業(yè)的運(yùn)費(fèi)已經(jīng)超越了庫存費(fèi)用，城市交

18、通與改善物流的矛盾也愈演愈烈， 城市交通混雜、阻塞、車輛噪音、尾氣污染、車禍?zhǔn)鹿屎湍茉蠢速M(fèi)等現(xiàn)象更加嚴(yán) 重，若物流路線選擇的不合理，還會(huì)使物流配送的行車路線變長，導(dǎo)致在運(yùn)車輛 增加，從而給本己擁擠的城市交通加重負(fù)擔(dān)，這就勢必要選擇合理有效的運(yùn)輸路 線來減少重復(fù)運(yùn)輸、倒流運(yùn)輸、遷回運(yùn)輸、單程運(yùn)輸和空駛等，這樣不僅提高配 送效率，控制了物流成本，而且可限制車輛在城市中的運(yùn)行時(shí)間，有效緩解城市 交通負(fù)擔(dān)。 物流配送系統(tǒng)中最優(yōu)路線的選擇問題一直都是配送中心關(guān)注的焦點(diǎn)，對(duì)于城 市配送而言，由于受交通堵塞和各種交通管制的影響，導(dǎo)致配送路徑尋優(yōu)更具復(fù) 雜性。所以本文通過對(duì)具有動(dòng)態(tài)的交通堵塞和交通擁擠限制信息

19、及靜態(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)域搜索算法對(duì)其尋優(yōu)。 針對(duì)當(dāng)前家樂福物流配送體系不完善等方面的現(xiàn)狀，本文從可持續(xù)發(fā)展的角 度，用系統(tǒng)的觀念，來研究家樂福物流配送體系，優(yōu)化配送路線，使配送體系合 理化:一方面通過建立一種快速、高效、網(wǎng)絡(luò)化的物流組織系統(tǒng)降低物流成本， 增加利潤;另一方面，增強(qiáng)家樂福的競爭力，使其配送系統(tǒng)相應(yīng)得到優(yōu)化，從而 使家樂福物流取得階段性成果，因此，對(duì)家樂福物流配送體系及其路線的優(yōu)化問 題進(jìn)行研究將具有很大的現(xiàn)實(shí)意義。 1

20、.2 國內(nèi)外物流配送路線優(yōu)化研究現(xiàn)狀 物流配送路線優(yōu)化，是物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)，也是電子商務(wù)活動(dòng)不可 缺少的內(nèi)容。對(duì)物流配送路線優(yōu)化，可以提高物流經(jīng)濟(jì)效益，實(shí)現(xiàn)物流科學(xué)化。 可以說對(duì)物流配送路線優(yōu)化理論與方法進(jìn)行系統(tǒng)研究是物流集約化發(fā)展，構(gòu)建綜 合物流系統(tǒng)，建立現(xiàn)代調(diào)度指揮系統(tǒng)，發(fā)展智能交通運(yùn)輸系統(tǒng)和開展電子商務(wù)的 基礎(chǔ)。 配送路線合理與否對(duì)配送速度，成本，效益影響很大，特別是多用戶配送線 路的確定更為復(fù)雜。采用科學(xué)的，合理的方法來確定配送路線，是配送活動(dòng)中非 常重要的一項(xiàng)工作。 路線優(yōu)化問題最早是由 dantzig 和 ramser 于 1959 年提出的，由于這一問題 的理論涉及很多學(xué)

21、科，很多實(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)，生活的各個(gè)方面。如 報(bào)紙投遞及線路的優(yōu)化，牛奶配送及送達(dá)線路的優(yōu)化，電話預(yù)訂貨物的車輛線 路設(shè)計(jì)，垃圾車的線路優(yōu)化，連鎖商店的送貨的線路優(yōu)化等等。目前，研究水 平已有很大發(fā)展，其理論成果除在汽車運(yùn)輸領(lǐng)域外，在水運(yùn)，航空，通訊，電 力，工業(yè)管理，計(jì)算機(jī)應(yīng)用等領(lǐng)域也有一定的應(yīng)用，還用于航

22、空乘務(wù)員輪班安 排，輪船公司運(yùn)送貨物經(jīng)過港口與貨物安排的優(yōu)化設(shè)計(jì)，交通車線路安排，生 產(chǎn)系統(tǒng)中的計(jì)劃與控制等多種組合優(yōu)化問題。 在國內(nèi)，該問題的系統(tǒng)研究還不多見。近年來有李軍等人課題組承擔(dān)的國家 自然科學(xué)基金 不確定信息條件下動(dòng)態(tài)車輛路徑 等研究工作。 紀(jì)壽文等人 根據(jù)深圳市科技園的實(shí)際路網(wǎng)圖，采用神經(jīng)網(wǎng)絡(luò)的方法對(duì)運(yùn)輸車輛優(yōu)化調(diào)度進(jìn)行 了試驗(yàn)研究。王正彬等人在分析 vrp 現(xiàn)有啟發(fā)式算法的基礎(chǔ)上，建立了考慮線 路安排的物流配送方案模型，并提出了求解該問題的搜索算法。 1.3 研究內(nèi)容與技術(shù)路線 本文結(jié)構(gòu)： 緒論（研究背景，目的，意義及現(xiàn)狀） 路線優(yōu)化現(xiàn)狀（公司概況，需求貨物品種，貨物 需求量，

23、分店分布，車輛數(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)狀分析，及存在的問題分析； 第三章：針對(duì)問題設(shè)定目標(biāo)，構(gòu)建數(shù)學(xué)模型，引入遺傳算法，編程實(shí)現(xiàn)； 第四章：優(yōu)化結(jié)果分析； 第五章：結(jié)論，總結(jié)與建議； 本文技術(shù)路線： （1）分析家樂福超市物流配送路線狀況，并針對(duì)路線優(yōu)化提出問題； （2）在考慮成本最小化的目標(biāo)及其各種約束條件的基礎(chǔ)上建立數(shù)學(xué)模型； （3）根據(jù)具體物流

24、配送的特點(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)。現(xiàn)擁有 11,000 多家營運(yùn)零售單位，業(yè)務(wù)范圍 遍及世界 30 個(gè)國家和地區(qū)。 集團(tuán)以三種主要經(jīng)營業(yè)態(tài)引領(lǐng)市場：大型超市，超市以及折扣店。此外，家 樂福還在一些國家發(fā)展了便利店和會(huì)員制量販店。2004 年集團(tuán)稅后銷售額增至 726.68 億歐元，員工總數(shù)超過 43 萬人。 2005 年，家樂福在財(cái)富雜志編排的全球 500

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

26、球性的采購網(wǎng)絡(luò)，向不同國家和地區(qū)的供應(yīng)商采購具有市場競爭力 的商品。 家樂福的經(jīng)營理念是以低廉的價(jià)格、卓越的顧客服務(wù)和舒適的購物環(huán)境為廣 大消費(fèi)者提供日常生活所需的各類消費(fèi)品。家樂福對(duì)顧客的承諾是在價(jià)格、商品 種類、質(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)的超市管理模式，致力于為社 會(huì)各界提供價(jià)廉物美的商品和優(yōu)質(zhì)的服務(wù)，受到廣大消費(fèi)者的青睞和肯定，其 “開心購物家樂福”、“一站式購物”等理念已經(jīng)深入人心。如今，家樂

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

28、商品采購、營銷管理、資產(chǎn)管理以及人力資源開發(fā)等各方面 實(shí)現(xiàn)現(xiàn)代化和本地化，為當(dāng)?shù)亟?jīng)濟(jì)發(fā)展做了積極的貢獻(xiàn)。 2.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-12-1 分店所在地坐標(biāo)分店所在地坐標(biāo) 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 坐標(biāo) 分店與配送中心間距離 1634 17-510 1829 191-15

29、2083 i=1，2.20； 2 0i 2 0i y-y)x(xd）（ (2) 現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表 2-3 求得, 配送 中心與商店之間，商店與商店之間的距離分析如下表： 表表 2-22-2 配送中心與分店之間配送中心與分店之間, ,分店與分店之間的距離分店與分店之間的距離 (0(0 點(diǎn)表示配送中心點(diǎn)表示配送中心) ) 01234567891011121314151617181920 00126.44.522309.2179.2171613156.48.5115119.2158.5 1120137.811392.862173.61.427153.6237.113

30、6256 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.22111133126

31、182602725237.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

32、.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.6

33、195.1158.5190 2.2.2 車輛數(shù)分析 所需車輛數(shù)分析(家樂福配送中心一年(365 天)的車輛調(diào)度): 表表 2-32-3 車輛調(diào)度情況車輛調(diào)度情況 車輛運(yùn)用數(shù) 101291110111010891011 運(yùn)用天數(shù) 2530364246494838241386 表表 2-42-4 車輛運(yùn)用數(shù)所占比率車輛運(yùn)用數(shù)所占比率 車輛運(yùn)用數(shù)相對(duì)比率累計(jì)比率 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

34、 110.011.00 則家樂福平均每天所用車輛數(shù)為 12 輛。 2.2.3 需求量分析 表表 2-52-5 每個(gè)分店（一年每個(gè)分店（一年 365365 天）平均每天的需求量天）平均每天的需求量 分店 12345678910 需求 量 2324123513 分店 11121314151617181920 需求 量 2342121322 2.2.4 商品品種分析 超市以滿足消費(fèi)者對(duì)基本生活用品一次性購買需要為經(jīng)營宗旨，是一種經(jīng)營 品項(xiàng)較多的零售業(yè)態(tài)。下面對(duì)商品進(jìn)行分類分析。 一、大分類 大分類是超市最粗線條的分類。大分類的主要標(biāo)準(zhǔn)是商品特征，如畜產(chǎn)、水 產(chǎn)、果菜、日配加工食品、一般食品、日用雜貨

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

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

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

38、粗加工水產(chǎn)品 精加工水 產(chǎn)品 其他水產(chǎn) 6.廚具 畜產(chǎn)7.日用小家電 鮮活畜禽 鮮肉類 鮮蛋類 鮮奶類 肉制品 蛋制品 乳制品 蜜制品 8.家用塑料制品 4.糖酒飲料9.首飾 糖類 酒類 茶葉 軟飲料 沖飲品 冷飲 咖啡豆|可可 其他糖酒飲料 10.衣物 5.加工食品11.箱包,袋,皮具 保健食品 休閑食品 方便食品 罐頭 食品 特色食品 調(diào)味品 其他加工食 品 12. 文體用品 6.煙草13.日用小五金 煙葉 香煙 其他煙草14.休閑家具 7.添加劑15.個(gè)人護(hù)理用品 食品添加劑 其他添加劑 發(fā)酵制品16.衛(wèi)浴用品 8.包裝機(jī)17.炊具 加工設(shè)備 食品包裝 其他機(jī)械包裝 制冷設(shè)備 18.灶具

39、 2.3 家樂福超市配送現(xiàn)有路線問題分析 家樂福的配送系統(tǒng)和信息系統(tǒng)是較落后的.家樂福至今沒有在中國建立起統(tǒng) 一的配送體系,且計(jì)算機(jī)系統(tǒng)的開發(fā)和建立,要落后于競爭對(duì)手沃爾瑪好幾年.家 樂福這種”滯后”的配送系統(tǒng)與信息系統(tǒng)是其戰(zhàn)略規(guī)劃的成果,因?yàn)樯唐返募?配送是連鎖商業(yè)帶來的,但是目前中國連鎖商業(yè)基礎(chǔ)非常薄弱,只有通過大的配送 系統(tǒng)的完善和整合才能形成規(guī)模的,高效的,社會(huì)化的物流配送系統(tǒng). 家樂福配送路線的分配存在以下幾方面的問題： （1）物流公司與門店之間的分布太分散，難以形成固定的配送線路 （2）送貨難以達(dá)到及時(shí) （3）難以保證適量的庫存而不壓貨 （4）路線里程未達(dá)最短 （5）費(fèi)用消耗大

40、（6）勞力消耗大，運(yùn)力難以適當(dāng)分配，難以調(diào)度車輛 （7）配送車輛噸位公里數(shù)大 （8）配送未實(shí)現(xiàn)自動(dòng)化 （9）配送未實(shí)現(xiàn)網(wǎng)絡(luò)化 （10）配送服務(wù)未實(shí)現(xiàn)系列化 3.配送路線優(yōu)化建模與求解 3.1 研究對(duì)象目標(biāo)設(shè)定 物流配送?？紤]以最小化總運(yùn)輸成本或距離最短為目標(biāo)，總運(yùn)輸成本主要由 由兩部分組成:(1)運(yùn)輸固定成本：如服務(wù)所有客戶所需要的車輛數(shù)、總行駛距離 (或總行駛時(shí)間)和與所使用的車輛有關(guān)的固定費(fèi)用；(2)運(yùn)輸營業(yè)成本：如司機(jī)的 管理費(fèi),各種工作人員的工資等. 家樂福超市的業(yè)務(wù)運(yùn)輸成本是物流總成本的主要組成部分，占有 56%。因此 降低公司運(yùn)輸成本成為提高公司效益的直接有效途徑。公司自有貨運(yùn)成本

41、各項(xiàng)比 例如下表： 表表 3-13-1 公司貨運(yùn)成本比例表公司貨運(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) 投資利息： 車輛，車庫,辦公室 管理成本： 職工月工資,額外福利,旅游和娛樂費(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),保險(xiǎn),許可證和登記費(fèi) 高速公路使用費(fèi),燃油 司機(jī)費(fèi)用占總營業(yè)成本的 29.4%；

42、維修費(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)樗苯訉?duì)勞動(dòng)、燃料和維修保養(yǎng)等變動(dòng)成本發(fā)生作用。針對(duì)公 司當(dāng)前成本構(gòu)成狀況，可以知道：通過優(yōu)化公司配送路線，減少運(yùn)輸車輛行駛總 里程，可以減少車輛燃油費(fèi)和道路服務(wù)費(fèi)支出，進(jìn)而減少物流總成本。 因此，本文針對(duì)家樂福配送中心車輛路線優(yōu)化問題，提出的目標(biāo)是：總運(yùn)輸 成本最小化。 5 9 4 配送中心 6 3 27 8 1

43、配送中心 分店 車輛路線 圖圖 3-13-1 家樂福的配送模式家樂福的配送模式 此問題可以描述為：這是一種分送式配送模型,是由一個(gè)供應(yīng)點(diǎn)對(duì)多個(gè)客戶的 共同配送。對(duì)配送中心負(fù)責(zé)的需求網(wǎng)點(diǎn)（家樂福分店） ，確定適當(dāng)?shù)呐渌蛙囕v行 駛路線，使其從配送中心出發(fā)，有序地通過各個(gè)分店各一次，最后返回配送中心， 并在滿足一定的約束條件下(如車輛容量限制、行駛里程限制、時(shí)間限制、顧客需 求量、交發(fā)貨時(shí)間等)，達(dá)到費(fèi)用最少的目標(biāo)。 本文研究的是不考慮時(shí)間窗的非滿載車輛優(yōu)化調(diào)度問題。表述如下：將貨物 從配送中心配送到各分配送中心,由分配送中心派出容量為的貨車承運(yùn)，現(xiàn)有 mq 輛車，各分店對(duì)所需求的貨物有一定的要求，

44、第 i 個(gè)分店的貨運(yùn)量為 gi， （i=1，2l）已知，在途中只有卸貨任務(wù),完成任務(wù)后返回配送中心,qgi 求滿足配送需求的費(fèi)用最少行車線路。 圖圖 3-23-2 家樂福配送體系結(jié)構(gòu)家樂福配送體系結(jié)構(gòu) 3.2 模型的構(gòu)建 為建模方便，需考慮以下幾個(gè)前提假設(shè)條件： （1）配送中心不會(huì)出現(xiàn)缺貨的可能并且對(duì)顧客的基本配送資料（需求量、地理 位置）為已知，配送中心的位置也已知； （2）不考慮配送時(shí)間限制，即客戶對(duì)貨物的需求沒有時(shí)間窗的規(guī)定； （3）不考慮每輛車為每個(gè)客戶的服務(wù)時(shí)間，即不考慮每個(gè)客戶的卸貨時(shí)間； （4）一個(gè)配送中心根據(jù)配送條件可以負(fù)責(zé)多個(gè)客戶，即一個(gè)配送中心服務(wù)多個(gè) 客戶； （5）車輛由

45、配送中心出發(fā)，服務(wù)被指定的需求點(diǎn)后，再返回配送中心，區(qū)域內(nèi) 的需求點(diǎn)假設(shè)為固定數(shù)量且位置已知，不發(fā)生變動(dòng)。 （6）配送中心擁有一定數(shù)量的單一車型的配送車輛，且每輛車的容量已知。 （7）每條配送路徑上各客戶需求量之和不超過配送車輛的容量； （8）每個(gè)客戶只能由一輛配送車輛送貨； （9）每輛車配送總里程不超過其最大行駛距離； （10）各道路均順暢，不考慮交通堵塞擁擠等特殊情況。 將配送中心編號(hào)為 0，車輛編號(hào)為 k，任務(wù)編號(hào)為 i=1,2. , 所有車型載重l 量單一，每輛汽車的最大載重量為 g，需要向 l 個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的需 求量為，并且滿足，需求點(diǎn) i 到 j 的運(yùn)距為，配送中心到)

46、, 2 , 1(liqigqiijd 各個(gè)需求點(diǎn)的距離為，再設(shè)為第輛汽車配送的需求點(diǎn)數(shù)（,.,l),jidi210(jknk 分配送中心 1 分配送中心 2 分配送中心 3. . 分店 1 分店 2 分店 3分店 4. . 配送中心 =0 表示未使用第輛汽車） ，用集合表示第 k 條路徑，其中的元素表示需knkkrkir 求點(diǎn)在路徑中的順序?yàn)?（不包括配送中心） ，令=0 表示配送中心，為kirki0krm 每輛車單位里程的行駛費(fèi)用，為每輛車的派遣費(fèi)用，考慮運(yùn)輸量約束,停車點(diǎn)車c 輛數(shù)目等約束,可以定義如下的基本模型: (3-1)ck n nsignddmz k ki krrrr k k k

47、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 在上述模型中各個(gè)公式所代表的涵義如下： （3-1）式為目標(biāo)函數(shù)，求總的配送費(fèi)用最低； （3-2）式用于保證每條路徑上各個(gè)需求點(diǎn)的需求量和不超過汽車的載重量； （3-3）式表明每條路徑上的需求點(diǎn)數(shù)不超過總需求點(diǎn)數(shù)； （3-4）式表明每個(gè)需求點(diǎn)都得到配送服務(wù)； （3-5）式表示每條路徑的需求點(diǎn)的組成； （3-6）式表示當(dāng)?shù)谳v汽車

48、服務(wù)的客戶數(shù)大于或等于 1 時(shí)，說明該輛汽車參k 加了配送，則取，當(dāng)?shù)?k 輛汽車服務(wù)的客戶數(shù)小于 1 時(shí)，表示未使用1)( k nsign 該輛汽車，因此??；0)( k nsign 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)度，不受約束條件束縛。 基于以上幾點(diǎn),本文將采用遺傳算法對(duì)家樂福超市物流配送路線進(jìn)行尋優(yōu)。 遺傳算法是由美國michiga

49、n大學(xué)的holland教授于1969年提出,后經(jīng) dejong、goldberg等人歸納總結(jié)所形成的一類模擬進(jìn)化算法。它來源于達(dá)爾文的 進(jìn)化論、魏茨曼的物種選擇學(xué)說和孟德爾的群體遺傳學(xué)說。 本文所設(shè)計(jì)的遺傳算法的基本流程如下： step1：初始化，產(chǎn)生初始種群。 step2：個(gè)體評(píng)價(jià)，即計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度。 step3：按選擇概率 ps，執(zhí)行選擇算子，從當(dāng)前種群中選擇部分個(gè)體進(jìn)入下一代 種群。 step4：按交叉概率 pc，執(zhí)行交叉算子。 step5：按變異概率 pm，執(zhí)行變異算子。 step6：若滿足設(shè)定的終止條件，則執(zhí)行 step7，否則執(zhí)行 step2。 step7：輸出種群中適

50、應(yīng)度最優(yōu)的個(gè)體作為問題的最優(yōu)解或滿意解。 圖圖 3-33-3 應(yīng)用遺傳算法求解問題示意圖應(yīng)用遺傳算法求解問題示意圖 第一步和第二步可以歸結(jié)為建立優(yōu)化問題的模型，可以是解析性的數(shù)學(xué)模型， 也可以是非解析性模型。這是應(yīng)用任何優(yōu)化算法求解優(yōu)化問題都需要的步驟。 第三步“編碼”實(shí)際上包含了設(shè)計(jì)或選擇個(gè)體基因型的表示方法、設(shè)計(jì)解的 表現(xiàn)型到個(gè)體基因型的轉(zhuǎn)換算法。 第四步“解碼”是因?yàn)檫z傳算子只作用于編碼后的染色體，而染色體的優(yōu)劣 要到解空間計(jì)算其對(duì)應(yīng)的值由個(gè)體表現(xiàn)型計(jì)算目標(biāo)函數(shù)值后才能進(jìn)行判斷。 第五步“確定適應(yīng)度轉(zhuǎn)換規(guī)則”是因?yàn)槿旧w所對(duì)應(yīng)的解空間的值可能相差 很大，不適合直接用來定量評(píng)估個(gè)體的優(yōu)劣。

51、 第六步“設(shè)計(jì)遺傳算子”即為設(shè)計(jì)交叉、變異、選擇等遺傳操作，遺傳算子 與待優(yōu)化問題、染色體的編碼方案有很大的關(guān)系，也是遺傳算法應(yīng)用領(lǐng)域的一個(gè) 重要?jiǎng)?chuàng)新點(diǎn)。 第七步“確定運(yùn)行參數(shù)”即確定遺傳算法中的交叉概率、變異概率、最大進(jìn) 化代數(shù)等參數(shù)。 最優(yōu)化問題描述 確定決策變量,約束條件建立優(yōu)化模型 編碼,解碼 確定適應(yīng)度轉(zhuǎn)換規(guī)則 個(gè)體基因型 x 適應(yīng)度 f(x) 設(shè)計(jì)遺傳算子 確定運(yùn)行參數(shù) 遺傳算法 解空間 遺傳算法空間 第一步 第二步 第三四步第五步 第六步 第七步 3.2.2 算法思想與算法流程 首先根據(jù)每項(xiàng)任務(wù)的需求量 qi，總?cè)蝿?wù)量以及每輛車的最大載重量 q，每輛 車的任務(wù)不超過其最大載重量

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

53、次，經(jīng) 過以前未經(jīng)過的 i21，i22.i2t路線，又回到配送中心，形成子路徑 2；這樣重復(fù)， 直到每個(gè)分店都被訪問到且每個(gè)分店只訪問一次， 項(xiàng)任務(wù)全部完成為止；其中l(wèi) 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 交換位置，會(huì)使函 數(shù)目標(biāo)

54、值改變；而子路徑之間是無序的，若子路徑 1和子路徑 2交換位置， 卻不會(huì)改變目標(biāo)函數(shù)的值。 （2）初始種群 滿足編碼方案的前提下,隨機(jī)產(chǎn)生 l 個(gè)需求點(diǎn)的全排列,構(gòu)成初始種群,如： i1，i2，.i 。若qijg 且 qijg 將 s 至 的基因依次向后移動(dòng)一位,使 l 1s 1j s 1j l s 位空出,將 0 插入 s 位。接著若 qijg 且 qijg 如上面的操作,使 t 空出, 1t sj t sj 將配送中心插入第 t 位。如此繼續(xù)，直到將 m 個(gè)配送中心全部插入染色體為止。 這樣就構(gòu)成了一條初始染色體，如此反復(fù)，構(gòu)造滿足群體數(shù)的染色體個(gè)數(shù)。 （3）適應(yīng)度函數(shù) 對(duì)種群中的每個(gè)染色

55、體 vi(i=1,2,.l)根據(jù)目標(biāo)函數(shù)的式子計(jì)算其值為 ui,若染 色體對(duì)應(yīng)的是不可行解，則賦予其目標(biāo)函數(shù)值一個(gè)很大的整數(shù)，適應(yīng)度函數(shù)可以 設(shè)為：fi =1/zi+m*1000,則 fi 0，zi為染色體 vi對(duì)應(yīng)的運(yùn)輸成本；fi 為染色體 vi 的適應(yīng)度，fi越大，其性能越好，其對(duì)應(yīng)的解越接近最優(yōu)解。 （4）遺傳算子 1)選擇算子 個(gè)體選擇的分配方法:按比例的適應(yīng)度分配。 利用比例于各個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性，選擇概率公式為: p i= fi / fi 即適應(yīng)度越大，其選擇概率越大。 m i 1 根據(jù)計(jì)算父代和子代的適應(yīng)度，并將每代群體中的 n 個(gè)個(gè)體按適應(yīng)度由大到 小排列，

56、排在第一位的個(gè)體性能最優(yōu)，將它復(fù)制一個(gè)直接進(jìn)入下一代，并排在第 一位。下一代群體的另 n-1 個(gè)個(gè)體需要根據(jù)前代群體的 n 個(gè)個(gè)體的適應(yīng)度，采用 輪盤賭選擇法產(chǎn)生。 2)交叉算子 對(duì)通過選擇操作的新群體，除排在第一位的最優(yōu)個(gè)體外，另 n-1 個(gè)個(gè)體要按 交叉概率 pc進(jìn)行配對(duì)交叉重組。本文采用順序法實(shí)施交叉操作： a)隨機(jī)在你代個(gè)體中選取一個(gè)交配區(qū)域,如兩父代個(gè)體及交配區(qū)域定為：a = 47|8563|921，b=83|4691|257； b)將 b 的交配區(qū)域加到 a 的前面，a 的交配區(qū)域加到 b 的前面，得： a=4691|478563921，b=8563|834691257； c)在

57、a，b中自交配區(qū)域后依次刪除與交配區(qū)相同的自然數(shù)，得到最終的兩個(gè) 個(gè)體分別為：a=496178532，b=856349127。 3)變異算子 以一定的變概率 pm隨機(jī)選取發(fā)生變異的個(gè)體染色體，然后在該染色體上隨 機(jī)選取 2 個(gè)非零基因位，把這 2 個(gè)位置上的基因互換形成新的基因串。 （5）控制參數(shù)和算法的終止條件 1)參數(shù)設(shè)置 交叉概率 pc=0.6；變異概率 pm=0.01；終止代數(shù) t=100；初始種群 n=100； =0.65；車輛數(shù) m=qi/+1（gi為需求點(diǎn) i 的貨運(yùn)量） ；g=8 噸； m i 1 2)終止條件 由于計(jì)算時(shí)間的機(jī)器容量都是有限的，代數(shù)不能無限長，故當(dāng)?shù)螖?shù)達(dá)到

58、 規(guī)定值 t 時(shí)，停止計(jì)算。 4.優(yōu)化結(jié)果分析 4.14.1 優(yōu)化前結(jié)果優(yōu)化前結(jié)果 表表 4-1 優(yōu)化前路線分析優(yōu)化前路線分析 現(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-013.9848.75% 0-16-20-05.13.8847.5% 0-13

59、-06.43.7846.25% 0-7-12-0325.7870.125% 合計(jì)211.945.180(平均)50.3% 優(yōu)化前成本經(jīng)計(jì)算為 10757 元。 4.2 優(yōu)化后結(jié)果 表表 4-2 運(yùn)行結(jié)果分析運(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.3512291 最小值7291.5

60、710147 表表 4-34-3 優(yōu)化后路線優(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%; 總成