超市物流配送路線優(yōu)化范本

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

2、再優(yōu)化,從而達(dá)到運(yùn)輸成本最小化的目標(biāo)。關(guān)鍵詞：物流配送;路徑優(yōu)化;節(jié)約里程算法目 錄 TOC o 1-3 h z HYPERLINK N:整理后l1.緒論 PGEREF _oc360615011 1HYPERLIK l _Toc3606012.1 選題目的和意義PAGEREF Toc365012 h 1HERIN l _Tc36061503 12 國(guó)內(nèi)外物流配送路線優(yōu)化研究現(xiàn)狀PAGERF _oc30613 h2HYPERLINK N:整理后2. 家樂福超市配送路線現(xiàn)狀 PAEFTo36065014 3HYPERLINK N:整理后l2. 家樂福超市概況 PAGEREF _Toc3606515

3、 h 3HYPERLINK N:整理后 l _To3606506.2家樂福超市配送路線作業(yè)現(xiàn)狀 PGE _Tc36061516 h4HYPERLINK N:整理后22.1 配送距離分析 PAGREF_36015017 h 4HYPERLINK N:整理后l2.22 車輛數(shù)分析 AGEE_oc36518h 5HYPERLINK N:整理后.3 需求量分析 PAGER Tc3606501 6 YPERI l _Toc361520 2.2. 商品品種分析PAGER_Toc3606100 h 6HYPERINK l _o36521 2.3 家樂福超市配送現(xiàn)有路線問題分析PGEREF Toc606102

4、 h 7HYPERLINK N:整理后3.配送路線優(yōu)化建模與求解 GEEF Toc3606122 h 9HYPERLINK N:整理后3.研究對(duì)象目標(biāo)設(shè)定PGERE Toc6061523h 9HYPERLINK N:整理后3.2 模型的構(gòu)建PAGEREFToc36061502 11HYPERLINK N:整理后3.節(jié)約算法 PAGREF _oc360610 h 12HYPERLINK N:整理后 l _Toc3606150263.31節(jié)約算法的差不多原理 PAGEREF To36606h 12 HYELIK loc360615027 .2節(jié)約里程算法要緊步驟 GEREF _Toc3606152

5、 1HYPERLINK N:整理后.3基于節(jié)約算法的配送路線優(yōu)化PAEEF oc30102 h 3HYPERLINK N:整理后33.4優(yōu)化后的配送線 PAF _To3661502h HPERLI l Tc3601530 4.優(yōu)化結(jié)果分析 PAEREF _Toc65030 h 25YPERLIN l_c60615031 4.1 優(yōu)化前結(jié)果 AGEREF _oc3661503 h 25 HYPIN l_Toc3661502 42優(yōu)化后結(jié)果 PAGEE _oc6061532 2HYPERLINK N:整理后43結(jié)論 PAGREF _Toc3606503 h26 HYPELINK l _Toc306

6、5034 .總結(jié)與建議 PGEREF_To36015034 h 27HYPERLINK N:整理后l參考文獻(xiàn): PAGEREF _T66150 h 281.緒論1.1 選題目的和意義配送是一項(xiàng)專門的、綜合性的物流運(yùn)動(dòng)，其運(yùn)行和進(jìn)展有著深刻的社會(huì)根源和歷史背景。在市場(chǎng)經(jīng)濟(jì)體系中，物流配送如同人體的血管，把國(guó)民經(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è)、車載物資的配裝、配送線路

7、的確定。在生活中，基于電子商務(wù)的物流配送業(yè)務(wù)量逐漸增加,假如還沿用往常的物流方法來組織配送,會(huì)產(chǎn)生專門多問題。這些問題歸納起來，包括以下幾點(diǎn):1)服務(wù)質(zhì)量的下降。電子商務(wù)的特征是交易量巨大和交易速度極快,而傳統(tǒng)物流配送的特點(diǎn)是人工調(diào)度、反應(yīng)時(shí)刻長(zhǎng)。信息流與物流的矛盾會(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)，物流成

8、本無法操縱。3)增加都市交通的負(fù)擔(dān)。物流配送調(diào)度的不合理，會(huì)使物流配送的行車路線變長(zhǎng)，導(dǎo)致在運(yùn)車輛增加,從而給本已擁擠的都市交通加重負(fù)擔(dān)。要解決以上的問題，使物流配送調(diào)度滿足以下目標(biāo)準(zhǔn)時(shí)送貨。確實(shí)是要客戶選擇物資送達(dá)他們指定地點(diǎn)的時(shí)刻,要按照每個(gè)客戶的時(shí)刻要求安排物流配送?？偝杀咀畹??？傂熊嚶窂阶疃?。當(dāng)前，物流的現(xiàn)代化水平不僅成為反映一個(gè)國(guó)家現(xiàn)代化程度和綜合國(guó)力的重要標(biāo)志,也成為都市經(jīng)濟(jì)進(jìn)展水平的體現(xiàn),被喻為促進(jìn)經(jīng)濟(jì)進(jìn)展的“加速器”。物流配送是一種先進(jìn)的現(xiàn)代物流形式,它不但給供應(yīng)者和需求者帶來降低物流成本、享受優(yōu)質(zhì)服務(wù)的直接效益，而且還能為社會(huì)節(jié)約運(yùn)輸車次、緩解交通壓力、減少運(yùn)輸污染、愛護(hù)生態(tài)

9、環(huán)。而今，由于小批量、多批次的及時(shí)配送方式的進(jìn)展,運(yùn)輸費(fèi)用正在逐年提升，許多企業(yè)的運(yùn)費(fèi)差不多超越了庫(kù)存費(fèi)用,都市交通與改善物流的矛盾也愈演愈烈,都市交通混雜、堵塞、車輛噪音、尾氣污染、車禍?zhǔn)鹿屎湍茉窗踪M(fèi)等現(xiàn)象更加嚴(yán)峻,若物流路線選擇的不合理，還會(huì)使物流配送的行車路線變長(zhǎng)，導(dǎo)致在運(yùn)車輛增加,從而給本己擁擠的都市交通加重負(fù)擔(dān),這就勢(shì)必要選擇合理有效的運(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),關(guān)于都市配送而言，由于受交通堵塞

10、和各種交通管制的阻礙，導(dǎo)致配送路徑尋優(yōu)更具復(fù)雜性。因此本文通過對(duì)具有動(dòng)態(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)域搜索算法對(duì)其尋優(yōu)。針對(duì)當(dāng)前家樂福物流配送體系不完善等方面的現(xiàn)狀,本文從可持續(xù)進(jìn)展的角度，用系統(tǒng)的觀念，來研究家樂福物流配送體系,優(yōu)化配送路線，使配送體系合理化:一方面通過建立一種快速、高效、網(wǎng)絡(luò)化的物流組織系統(tǒng)降低物流成本,增加利潤(rùn);另一方面,增強(qiáng)家樂福的競(jìng)爭(zhēng)力,使其配送系統(tǒng)相應(yīng)得到優(yōu)化，從而使家樂福物流取得時(shí)期性成

11、果,因此，對(duì)家樂福物流配送體系及其路線的優(yōu)化問題進(jìn)行研究將具有專門大的現(xiàn)實(shí)意義。1.2國(guó)內(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)研究是物流集約化進(jìn)展，構(gòu)建綜合物流系統(tǒng),建立現(xiàn)代調(diào)度指揮系統(tǒng),進(jìn)展智能交通運(yùn)輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)。配送路線合理與否對(duì)配送速度,成本,效益阻礙專門大，特不是多用戶配送線路的確定更為復(fù)雜。采納科學(xué)的,合理的方法來確定配送路線，是配送活動(dòng)中特不重要的一項(xiàng)工作。路線優(yōu)化問題最早是由DANTZIG和RER于1

12、59年提出的,由于這一問題的理論涉及專門多學(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)問題。 在國(guó)外，物流配送路線優(yōu)化問題已廣泛應(yīng)用于生產(chǎn),生活的各個(gè)方面。如報(bào)紙投遞及線路的優(yōu)化,牛奶配送及送達(dá)線路的優(yōu)化，電話預(yù)訂物資的車輛線路設(shè)計(jì)，垃圾車的線路優(yōu)化,連鎖商店的送貨的線路優(yōu)化等等。目前,研究水平已有專門大進(jìn)展,其理論成果除在汽車運(yùn)輸領(lǐng)域外，在水運(yùn),航空,通訊,電力，工業(yè)治理,計(jì)算

13、機(jī)應(yīng)用等領(lǐng)域也有一定的應(yīng)用，還用于航空乘務(wù)員輪班安排,輪船公司運(yùn)送物資通過港口與物資安排的優(yōu)化設(shè)計(jì),交通車線路安排,生產(chǎn)系統(tǒng)中的打算與操縱等多種組合優(yōu)化問題。在國(guó)內(nèi)，該問題的系統(tǒng)研究還不多見。近年來有李軍等人課題組承擔(dān)的國(guó)家自然科學(xué)基金不確定信息條件下動(dòng)態(tài)車輛路徑等研究工作。紀(jì)壽文等人依照深圳市科技園的實(shí)際路網(wǎng)圖,采納神經(jīng)網(wǎng)絡(luò)的方法對(duì)運(yùn)輸車輛優(yōu)化調(diào)度進(jìn)行了試驗(yàn)研究。王正彬等人在分析V現(xiàn)有啟發(fā)式算法的基礎(chǔ)上,建立了考慮線路安排的物流配送方案模型，并提出了求解該問題的搜索算法。 2.家樂福超市配送路線現(xiàn)狀2家樂福超市概況成立于1959年的家樂福集團(tuán)是大賣場(chǎng)業(yè)態(tài)的首創(chuàng)者，是歐洲第一大零售商，世界第二

14、大國(guó)際化零售連鎖集團(tuán)?，F(xiàn)擁有11,000多家營(yíng)運(yùn)零售單位，業(yè)務(wù)范圍遍及世界30個(gè)國(guó)家和地區(qū)。集團(tuán)以三種要緊經(jīng)營(yíng)業(yè)態(tài)引領(lǐng)市場(chǎng)：大型超市,超市以及折扣店。此外，家樂福還在一些國(guó)家進(jìn)展了便利店和會(huì)員制量販店。2004年集團(tuán)稅后銷售額增至7268億歐元,職員總數(shù)超過43萬人。205年，家樂福在財(cái)寶雜志編排的全球500強(qiáng)企業(yè)中排名第22位。法國(guó)家樂福集團(tuán)是大型超級(jí)市場(chǎng)（yperarket）概念的創(chuàng)始者,于163年在法國(guó)開設(shè)了世界上第一家大型超市。199年8月30日家樂福兼并普羅莫代斯組成世界第二大零售集團(tuán)?，F(xiàn)在家樂福已進(jìn)展成為歐洲最大、全球第二大的零售商。20年，家樂福集團(tuán)被財(cái)寶雜志評(píng)為全球5強(qiáng)企業(yè)的第

15、22位。家樂福于969年開始進(jìn)入國(guó)際市場(chǎng),目前在世界上31個(gè)國(guó)家和地區(qū)擁有一萬多家銷售網(wǎng)點(diǎn),涉及的零售業(yè)態(tài)包括大賣場(chǎng)、超級(jí)市場(chǎng)、折扣店、便利店、倉(cāng)儲(chǔ)式商店與電子商務(wù),集團(tuán)的5萬名職員正致力于為20億消費(fèi)者服務(wù)。家樂福集團(tuán)建立了全球性的采購(gòu)網(wǎng)絡(luò),向不同國(guó)家和地區(qū)的供應(yīng)商采購(gòu)具有市場(chǎng)競(jìng)爭(zhēng)力的商品。家樂福的經(jīng)營(yíng)理念是以低廉的價(jià)格、卓越的顧客服務(wù)和舒適的購(gòu)物環(huán)境為寬敞消費(fèi)者提供日常生活所需的各類消費(fèi)品。家樂福對(duì)顧客的承諾是在價(jià)格、商品種類、質(zhì)量、服務(wù)及便利性等各方面滿足消費(fèi)者的需求。家樂福力爭(zhēng)通過自己的努力成為當(dāng)?shù)厣鐓^(qū)最好的購(gòu)物場(chǎng)所，為消費(fèi)者帶來更多的實(shí)惠和便利,并攜手和各商業(yè)伙伴為當(dāng)?shù)亟?jīng)濟(jì)的繁榮做出

16、貢獻(xiàn)。家樂福于95年進(jìn)入中國(guó)后,采納國(guó)際先進(jìn)的超市治理模式，致力于為社會(huì)各界提供價(jià)廉物美的商品和優(yōu)質(zhì)的服務(wù),受到寬敞消費(fèi)者的青睞和確信，其“快樂購(gòu)物家樂福”、“一站式購(gòu)物”等理念差不多深入人心。現(xiàn)在,家樂福已成功地進(jìn)入了中國(guó)的2個(gè)都市，在北至哈爾濱、南至深圳、西至烏魯木齊、東至上海的中國(guó)廣袤土地上開設(shè)了09家大型超市,聘請(qǐng)萬多名職員。在在華外資零售企業(yè)中處于領(lǐng)先地位。家樂福還向中國(guó)引進(jìn)迪亞折扣店和冠軍食品超市兩種業(yè)態(tài)。2004年，家樂福(中國(guó))被國(guó)內(nèi)媒體評(píng)為“在華最有阻礙力的企業(yè)”之一。2004年約有2億多人光顧了家樂福在中國(guó)的各門店，其中68為女性，32%乘公共汽車，%步行，1%騎自行車，9

17、%乘坐出租車或小轎車前往家樂福購(gòu)物。家樂福成為了各地居民的好鄰居。通過多年的經(jīng)營(yíng)，家樂福向中國(guó)的商業(yè)界輸入了大型超市經(jīng)營(yíng)治理方面的技能和先進(jìn)經(jīng)驗(yàn)，并對(duì)商品采購(gòu)、營(yíng)銷治理、資產(chǎn)治理以及人力資源開發(fā)等各方面實(shí)現(xiàn)現(xiàn)代化和本地化,為當(dāng)?shù)亟?jīng)濟(jì)進(jìn)展做了積極的貢獻(xiàn)。2.2 家樂福超市配送路線作業(yè)現(xiàn)狀2.2.配送距離分析(1)配送需求點(diǎn)坐標(biāo)：現(xiàn)在以家樂福物流配送中心為原點(diǎn)(0,）,建立直角坐標(biāo)系,各商店的坐標(biāo)如下表所示：X(k）;Y(k） 表2-分店所在地坐標(biāo)分店與配送中心間距離坐標(biāo)XY1892453240253-30778869151019102-8-1134-514657-813417-508219-15

18、2083 i，20;(2) 現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表2-3求得, 配送中心與商店之間,商店與商店之間的距離分析如下表: 表2-2 配送中心與分店之間,分店與分店之間的距離(0點(diǎn)表示配送中心)12467910112131451671812026.4.5239.2179.1131648.51511958.12017.8132.86173.61.42753.37.113626.130.1236106119161481103.151722123.7.86101834531311.222.151921961421118050145431813826153171814353039

19、36300374526414405324441391536922.8051470.319.26.4.224121204.2114.54.571766135.58.3069.613220.2212148.531289.211131268260272523.11821461712179171914.270586.13289.2813201329.2116.11843.6255.802.2187.26111585289.21113.4491040.2.12.12.2029165245147126115272038202437.1323290142420349.23136.41513.22625122

20、0111116141119.117418.98.53.10.553619.189.7.52110193.612522.1512315332402722826245.1190618916577.114.11413118.520.3.66010.119511711135.19.2184111410154217121107.168.267.2143.85718.57.4141917.1048.5191522119153228286.2102192401920.5626117517.2972393.6195.18.902.2.車輛數(shù)分析所需車輛數(shù)分析（家樂福配送中心一年(36天）的車輛調(diào)度):表23車

21、輛調(diào)度情況車輛運(yùn)用數(shù)10291111100811運(yùn)用天數(shù)25036424644884136表-4車輛運(yùn)用數(shù)所占比率車輛運(yùn)用數(shù)相對(duì)比率累計(jì)比率1070.720.080.15110100.2500.120.37120.130.5110.130.10130.7100.10.610.07.3150.0.97130.020.9110.0100則家樂福平均每天所用車輛數(shù)為1輛。2.3 需求量分析表25每個(gè)分店（一年365天)平均每天的需求量分店123456790需求量2412351分店11121341516181920需求量23132.2. 商品品種分析超市以滿足消費(fèi)者對(duì)差不多生活用品一次性購(gòu)買需要為經(jīng)營(yíng)

22、宗旨,是一種經(jīng)營(yíng)品項(xiàng)較多的零售業(yè)態(tài)。下面對(duì)商品進(jìn)行分類分析。一、大分類 大分類是超市最粗線條的分類。大分類的要緊標(biāo)準(zhǔn)是商品特征，如畜產(chǎn)、水產(chǎn)、果菜、日配加工食品、一般食品、日用雜貨、日用百貨、家用電器等。為了便于治理,超級(jí)市場(chǎng)的大分類一般以不超過1個(gè)為宜。二、中分類 中分類是大分類中細(xì)分出來的類不。其分類標(biāo)準(zhǔn)要緊有:（1)按商品功能與用途劃分。如日配品那個(gè)大分類下，可分出牛奶、豆制品、冰品、冷凍食品等中分類。 (2）按商品制造方法劃分。如畜產(chǎn)品那個(gè)大分類下，可細(xì)分出熟肉制品的中分類，包括咸肉、熏肉、火腿、香腸等。(3)按商品產(chǎn)地劃分。如水果蔬菜那個(gè)大分類下,可細(xì)分出國(guó)產(chǎn)水果與進(jìn)口水果的中分類。

23、 三、小分類 小分類是中分類中進(jìn)一步細(xì)分出來的類不。要緊分類標(biāo)準(zhǔn)有： ()按功能用途劃分。如“畜產(chǎn)”大分類中、“豬肉”中分類下,可進(jìn)一步細(xì)分出“排骨”、“肉米”、“里肌肉”等小分類。 ()按規(guī)格包裝劃分。如“一般食品”大分類中、“飲料”中分類下，可進(jìn)一步細(xì)分出“聽裝飲料”、“瓶裝飲料”、“盒裝飲料”等小分類。(3)按商品成份分類。如“日用百貨”大分類中、“鞋”中分類下，可進(jìn)一步細(xì)分出“皮鞋”、“人造革鞋”、“布鞋”、“塑料鞋”等小分類。 (4)按商品口味劃分。如“糖果餅干”大分類中、“餅干”中分類下，可進(jìn)一步細(xì)分出“甜味餅干”、“咸味餅干”、“奶油餅干”、“果味餅干”等小分類。 四、單品 單品

24、是商品分類中不能進(jìn)一步細(xì)分的、完整獨(dú)立的商品品項(xiàng)。如上海申美飲料有限公司生產(chǎn)的“355毫升聽裝可口可樂”、“1.25升瓶裝可口可樂”、“2升瓶裝可口可樂”、“2升瓶裝雪碧”，就屬于四個(gè)不同單品。 需要講明的是，商品分類并沒有統(tǒng)一固定的標(biāo)準(zhǔn)，各超市公司可依照市場(chǎng)和自身的實(shí)際情況對(duì)商品進(jìn)行分類。但商品分類應(yīng)該以方便顧客購(gòu)物、方便商品組合、體現(xiàn)企業(yè)特點(diǎn)為目的。具體分類如下表所示：食品日用品1.糧油1.日化產(chǎn)品糧食米面淀粉食用油主食熟食豆制品其他糧油.日雜用品2.果蔬.家居用品新奇蔬菜新奇水果食用菌蔬菜制品干果|堅(jiān)果果蔬深加工其他果蔬4 清潔用品及用具3.水產(chǎn)5.餐具鮮活水產(chǎn)品粗加工水產(chǎn)品精加工水產(chǎn)品

25、其他水產(chǎn)6.廚具畜產(chǎn).日用小家電鮮活畜禽鮮肉類鮮蛋類鮮奶類肉制品蛋制品乳制品蜜制品.家用塑料制品 .糖酒飲料9.首飾糖類酒類茶葉軟飲料沖飲品冷飲咖啡豆|可可其他糖酒飲料10.衣物5.加工食品11.箱包,袋，皮具保健食品休閑食品方便食品罐頭食品特色食品調(diào)味品其他加工食品12. 文體用品6煙草13日用小五金煙葉香煙其他煙草14休閑家具7添加劑15個(gè)人護(hù)理用品食品添加劑 添加劑發(fā)酵制品16.衛(wèi)浴用品8.包裝機(jī)17.炊具加工設(shè)備食品包裝其他機(jī)械包裝制冷設(shè)備.灶具表2-6 商品品種3 家樂福超市配送現(xiàn)有路線問題分析家樂福的配送系統(tǒng)和信息系統(tǒng)是較落后的.家樂福至今沒有在中國(guó)建立起統(tǒng)一的配送體系,且計(jì)算機(jī)系

26、統(tǒng)的開發(fā)和建立,要落后于競(jìng)爭(zhēng)對(duì)手沃爾瑪好幾年.家樂福這種”滯后”的配送系統(tǒng)與信息系統(tǒng)是其戰(zhàn)略規(guī)劃的成果,因?yàn)樯唐返募信渌褪沁B鎖商業(yè)帶來的,然而目前中國(guó)連鎖商業(yè)基礎(chǔ)特不薄弱,只有通過大的配送系統(tǒng)的完善和整合才能形成規(guī)模的,高效的,社會(huì)化的物流配送系統(tǒng).家樂福配送路線的分配存在以下幾方面的問題：物流公司與門店之間的分布太分散，難以形成固定的配送線路送貨難以達(dá)到及時(shí)難以保證適量的庫(kù)存而不壓貨路線里程未達(dá)最短費(fèi)用消耗大勞力消耗大,運(yùn)力難以適當(dāng)分配，難以調(diào)度車輛配送車輛噸位公里數(shù)大配送未實(shí)現(xiàn)自動(dòng)化配送未實(shí)現(xiàn)網(wǎng)絡(luò)化配送服務(wù)未實(shí)現(xiàn)系列化3.配送路線優(yōu)化建模與求解3.1 研究對(duì)象目標(biāo)設(shè)定物流配送常考慮以最小

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

28、利，旅游和娛樂費(fèi)用,房屋維修費(fèi)，牌照費(fèi),職工培訓(xùn)費(fèi),宣傳費(fèi)及業(yè)務(wù)手續(xù)費(fèi)。車輛運(yùn)營(yíng)成本:燃料(燃油,潤(rù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íng)業(yè)成本的29.4%；維修費(fèi)和折舊費(fèi)占總營(yíng)業(yè)成本的19.5%；其它的運(yùn)營(yíng)費(fèi)用占總營(yíng)業(yè)成本的.6%;燃料費(fèi)占總營(yíng)業(yè)成本的1.5；表上所述：公司車輛運(yùn)營(yíng)成本占據(jù)了總運(yùn)輸成本的78。隨著道路服務(wù)政策的變化,車輛營(yíng)業(yè)成本在公司總成本中所占比例日益增大。距離是阻礙運(yùn)輸成本的要緊因素,因?yàn)樗苯訉?duì)勞動(dòng)、燃料和維修保養(yǎng)等變動(dòng)成本發(fā)生作用。針對(duì)公司當(dāng)前成本構(gòu)成狀況,能

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

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

31、;（3）不考慮每輛車為每個(gè)客戶的服務(wù)時(shí)刻,即不考慮每個(gè)客戶的卸貨時(shí)刻；（4）一個(gè)配送中心依照配送條件能夠負(fù)責(zé)多個(gè)客戶,即一個(gè)配送中心服務(wù)多個(gè)客戶；(5)車輛由配送中心動(dòng)身，服務(wù)被指定的需求點(diǎn)后，再返回配送中心，區(qū)域內(nèi)的需求點(diǎn)假設(shè)為固定數(shù)量且位置已知，不發(fā)生變動(dòng)。(6）配送中心擁有一定數(shù)量的單一車型的配送車輛,且每輛車的容量已知。（）每條配送路徑上各客戶需求量之和不超過配送車輛的容量;(8）每個(gè)客戶只能由一輛配送車輛送貨；(9）每輛車配送總里程不超過其最大行駛距離;（10)各道路均順暢，不考慮交通堵塞擁擠等專門情況。將配送中心編號(hào)為,車輛編號(hào)為，任務(wù)編號(hào)為i1,2,所有車型載重量單一，每輛汽車的

32、最大載重量為,需要向L個(gè)需求點(diǎn)送貨，每個(gè)需求點(diǎn)的需求量為，同時(shí)滿足，需求點(diǎn)i到j(luò)的運(yùn)距為，配送中心到各個(gè)需求點(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) 在上述模型中各個(gè)公式所代表的涵義如下:(31）式為目標(biāo)函數(shù),求總的配送費(fèi)用最低;(-2）式用于保證每條路徑上各個(gè)需求點(diǎn)的需求量和不超過汽車的

33、載重量；(3-3）式表明每條路徑上的需求點(diǎn)數(shù)不超過總需求點(diǎn)數(shù);(3-4）式表明每個(gè)需求點(diǎn)都得到配送服務(wù);(3-5)式表示每條路徑的需求點(diǎn)的組成；(6)式表示當(dāng)?shù)谳v汽車服務(wù)的客戶數(shù)大于或等于時(shí)，講明該輛汽車參加了配送，則取,當(dāng)?shù)趉輛汽車服務(wù)的客戶數(shù)小于1時(shí),表示未使用該輛汽車，因此?。?.3節(jié)約算法3.3.1節(jié)約算法的差不多原理節(jié)約算法的核心思想是將運(yùn)輸問題中存在的兩個(gè)回路(0,，0)和(0,j， ,)合并成一個(gè)回路(， ，i,，0)。在上面的合并操作中,整個(gè)運(yùn)輸問題的總運(yùn)輸距離會(huì)發(fā)生變化,假如變化后總運(yùn)輸距離下降，則稱節(jié)約了運(yùn)輸距離。相應(yīng)的變化值,叫做節(jié)約距離，如式（）所示。 （1）調(diào)整過程如

34、圖3所示。jji 00i 調(diào)整前 調(diào)整后 圖3-節(jié)約算法的圖像描述3.3.2節(jié)約里程算法要緊步驟已知條件:需求點(diǎn)集=1，2，n,各點(diǎn)需求量,各點(diǎn)間最短距離。第一步,形成一個(gè)初始解。確定各車輛配送點(diǎn)集令, ,2,(先采取單點(diǎn)配送)。第二步,進(jìn)行節(jié)約度的計(jì)算。計(jì)算所有點(diǎn)對(duì)的節(jié)約度，然后對(duì)計(jì)算結(jié)果進(jìn)行升序排列。第三步，進(jìn)行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始,直到節(jié)約里程的隊(duì)列空為止,重復(fù)下列步驟：按照節(jié)約里程隊(duì)列從大到小的順序，分析客戶和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過2),將i, j連接起來,即可令。假如不是如此,則從節(jié)約里程隊(duì)列中去除當(dāng)

35、前的節(jié)約里程，分析下一個(gè)客戶對(duì)。3.3.3基于節(jié)約算法的配送路線優(yōu)化表32 每個(gè)分店（一年365天）平均每天的需求量分店234678910需求量(噸）2324121分店11213141516718920需求量(噸)23422132現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表3-求得,配送中心與商店之間,商店與商店之間的距離分析如下表:表33 配送中心與分店之間，分店與分店之間的距離(0點(diǎn)表示配送中心)013456791011213511192000126.5230.17921716315648.51119.15.5112137.811.8217.1.42153623711365626.4

36、306.121611611961418131037.15.17.21234.7860184513114119.09.4515192196.1211118501454311103826153317146173635074564143402056243413913369.22.1051378.3.6.44.22412124.2114.5234.5717616135.4458.06.23.1220921248.5311289.2111332618202725237.11816171217719424192.2205.3219.813201328.10361618464.6255.80223117.2

37、261158.589.211131.4.210404.5.12.12.20915248.1.6.111518203820242.32312014245.103421341513922625122011818114011119117141.914.5610.5131.2189.7.252110193612523.61123131533242022282645.11191611911191657.1.1117344.211118.52913.616105.1195.11711135.19.24111141620154211218007.215187254394.8.51738.572445.171

38、048.51915521623311228269.21221192240198.51261734.127927.12.93.61.15.5190設(shè)每個(gè)車輛的運(yùn)輸能力是8噸,依照案例可知,家樂福平均每天所用車輛數(shù)為12輛。現(xiàn)在用節(jié)約算法對(duì)該配送線路問題進(jìn)行求解。依照配送中心與分店之間,分店與分店之間的距離距離表，計(jì)算出用戶間的節(jié)約里程， 表34 節(jié)約值矩陣表12478910111213415171819102038.74804237.45030.4.50618.45.68.7.22.2077.48.53.6217.98024.7.213.20.4.209.475712-0.80102.6.49.

39、5301882940.227.201.5.48.253189-0.83.926.80103.4-0.5-125027100-01.4-0.2.721.43.63465.4.4.4.4116.94.98.5.52516.716.3-0.3161716.5-0.53.954.50.2118.01020.6406-0.14.85101010290.50.39.97014.36.509.214.28121030.47.5401815.28.48.7170.23.17.413.6.15.10.21.1271.2.132192.40.5131.2112.43220114151500202014.52.96

40、.913.5.3.13.716.3.314.40.13.40.58.44.59.24.0 從表3中選出節(jié)約值最大值為33.6，其對(duì)應(yīng)的兩點(diǎn)為4、。4、7兩處的需求量之和為,未超過一輛車的運(yùn)輸能力8,因此，連接4、7成回路，即0-7-0.再將頂點(diǎn)和的節(jié)約值賦為0結(jié)果如表3-5所示。表3-1234678911112134151617190102.403.80437.48.530.40.20685.8.172.2073.8.5217.908024.6070.13.2.0.09227527174.8-0.014.6.9.53318.82940.227.201123.65.83231249-82.926

41、.801203.4-0.5-12502017.100-13.4-0.1.7.143.634.5.443.411.4.98.5.2.516.7163-0.317.16.-.90154.4.2002118.20020.940.50161438.11010.2919.502.3.00714.36.31509.44282030.7.581528.48717.2021.917.1413.2167.1.2.21.71.29.11.21920.40.5301211224320.14.5100.202014.52.9613.55.51.23.50.716.315.31.40.561345.4.59.24.5

42、從表3-5中選出節(jié)約值最大為30,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為4、。假如連接4和10 ,則與上述線路合并，其總需求量為10，超過一輛車的運(yùn)輸能力8,因此,4和不能連接 ,7和1也不能連接，則將、1與7、10的節(jié)約值賦為0。接著選出節(jié)約值最大為3,其對(duì)應(yīng)兩個(gè)頂點(diǎn)為5、1。5和19兩處的需求量之和為,未超過一輛車的運(yùn)輸能力8,因此,連接,5、成回路，即0519-再將頂點(diǎn)和19的節(jié)約值賦為。接著選出節(jié)約值最大為2.,其對(duì)應(yīng)兩個(gè)頂點(diǎn)為9、0。9和10兩處的需求量之和為,未超過一輛車的運(yùn)輸能力8,因此，連接9、0成回路,即09-10.再將頂點(diǎn)9和10的節(jié)約值賦為0。選出節(jié)約值最大為2，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為4、9。假

43、如連接4和9，則與上述兩條線路合并,其總需求量為,超過一輛車的運(yùn)輸能力8,因此,4和9不能連接 ，7和也不能連接，則將4、9與、9的節(jié)約值賦為0。選出節(jié)約值最大為26.，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為0、1。假如連接0和1，則與上述線路合并,其總需求量為6,未超過一輛車的運(yùn)輸能力8，因此,連接0-91-110成回路 ,則將9、1與10、1的節(jié)約值賦為0。同時(shí)，由于頂點(diǎn)1成回路的中間點(diǎn)，則與頂點(diǎn)10相關(guān)的節(jié)約值都賦為0，表示頂點(diǎn)10不可能再與其他點(diǎn)相連,其結(jié)果如下表所示。表3624568910111213115161718192025.403.4.804237.053.0.5208.45.6717.22.0

44、727.48.5 0.080.2.6.70.213.20.40.092.4751008000000000011265.4325824.-0.8001203.4-05-25.17.100-13.4-0.2.72.41143.645.40.7.40141694855.52.5167130.31606.5-0.53.9010.4.5020.211.200020.96.40.5016-0.1438.5100100.29.52.9.001701436.3159.14.280103.47.460185.2.8.71720.213.9.713.2510.2122.29.113201920.40.511.11

45、2.24020.811.41.515100.004.5.96.91.5.513.2150.716.301.401.40.58.44.9.2450 選出節(jié)約值最大為5,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為、11。假如連接4和11,則與上述兩條線路合并，其總需求量為3,超過一輛車的運(yùn)輸能力8,因此,4和11不能連接 ,7和11也不能連接,則將4、11與7、1的節(jié)約值賦為。選出節(jié)約值最大為25，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為、12。假如連接5和2,則與上述線路合并，其總需求量為6,未超過一輛車的運(yùn)輸能力8,因此,連接0-12-5-19-0成回路,則將5、12與1、19的節(jié)約值賦為。同時(shí),由于頂點(diǎn)5成回路的中間點(diǎn),則與頂點(diǎn)相關(guān)的節(jié)

46、約值都賦為0，表示頂點(diǎn)5不可能再與其他點(diǎn)相連，其結(jié)果如下表所示。表371245689101112114116181920102.403874.80423.48.5050618.4.68.717.200237.48 00.98.24.7.20.0.209224.47.500170-.80000000000112365.4830180-0.00013.4-.00.217.00-101334-0.21.7.403.63.4.6.43.47.40416.94.855.016.716.-0161.0.53.9104.5000.2118.20009640.501-0.14.5100100299.50.39

47、9017014.3509.4.01030.560181528.477.013.17.7143.20.101.2.129.301920.40.5101211242011.115100.20214596.913.5013.21.76.3014.40.513.4.584.59.24.50 從表3-7中選出節(jié)約值最大為3,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為1、11。假如連接和1,則與上述線路合并，其總需求量為8,未超過一輛車的運(yùn)輸能力，因此，連接0-91-0成回路,則將與頂點(diǎn)1、9、10、1相關(guān)的節(jié)約值都賦為0，表示頂點(diǎn)、9、0、1不可能再與其他點(diǎn)相連,其結(jié)果如下表所示。表3-81245678911121314151

48、617819200200.84074.50500005.687.2007485 7.9004700.40.20900000000000000001100000001203.40.5-10.201.10000130-0.212.4063446007.401404.98.55.016716.3-0.3000-.53.154.05000.2118.00020.9.405016.351000100.200002.30171436109.144.2000.47546018048.7170.917.1.00002.22.71.29.10004.510112200011.4.15100.20202.9133

49、213.50.700005613.5.45924.50從表3-8中選出節(jié)約值最大為09，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為1、15。假如連接2和15,則與上述線路合并,其總需求量為7，未超過一輛車的運(yùn)輸能力8,因此，連接012-5-19-成回路,則將、15;1、15與15、19的節(jié)約值賦為0。同時(shí),由于頂點(diǎn)2成回路的中間點(diǎn),則與頂點(diǎn)12相關(guān)的節(jié)約值都賦為0，表示頂點(diǎn)12不可能再與其他點(diǎn)相連，其結(jié)果如下表所示。表3-9123468910112131451617181921200304007.4.50000568.717.20707.48.5 0017.908060.0.40.090000000000000110

50、0000000000100000000000130-212.403.644.6000001404.98.55.5676.30.3003.90150.500.11.20006.40.0164.38.1000100.200002.3.90014.36.109.21.20000.474680.4.717.2013.917.400001.21.71.29.13.29.40.10.11.20.4150100.02002.96.13.53.21.50.000061.4.58.459.4.50從表3-9中選出節(jié)約值最大為18，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為、1。假如連接8和15，則與上述線路合并，其總需求量為1，超過一

51、輛車的運(yùn)輸能力8,因此, 8、19；8、5;8、2和8、15也不能連接，則將、19;8、5；、12和8、15的節(jié)約值賦為0.接著選出節(jié)約值最大為79,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為6、7。假如連接6和7，則與上述線路合并,其總需求量為9,超過一輛車的運(yùn)輸能力8,因此,6和7不能連接 ,和6也不能連接，則將6、7和4、6的節(jié)約值賦為0。選出節(jié)約值最大為17,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為7、。假如連接7和1,則與上述線路合并,其總需求量為10，超過一輛車的運(yùn)輸能力,因此，7和18不能連接 ，4和8也不能連接，則將7、18和4、8的節(jié)約值賦為。選出節(jié)約值最大值為16.7,其對(duì)應(yīng)的兩點(diǎn)為6、1。6、14兩處的需求量之和為4

52、,未超過一輛車的運(yùn)輸能力8，因此，連接6、4成回路,即6-14-再將頂點(diǎn)6、14的節(jié)約值賦為.選出節(jié)約值最大為16.3,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為7、14。假如連接7和14，則與上述兩條線路合并,其總需求量為11,超過一輛車的運(yùn)輸能力,因此，7和4不能連接 ,4和14也不能連接,則將、和、14的節(jié)約值賦為0選出節(jié)約值最大為5,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為、17。假如連接4和1,則與上述線路合并，其總需求量為,未超過一輛車的運(yùn)輸能力,因此,連接0-17-4-0成回路，則將與頂點(diǎn)4、7、7相關(guān)的節(jié)約值都賦為0，表示頂點(diǎn)4、7不可能再與其他點(diǎn)相連,其結(jié)果如下表所示。表3-10123456789111121341561

53、71192002003080050000605.68.700700 00004.0.700040900000000000000000100000000000000000001300.1.0.6060001404.98.5000-.30003.9004.40.500.2000040.0160438.5000200002.39.9700000000001808.48.01901.400001.2.71.2910019004050.0.20001.41.501002020029.0013.207003.058.0.24.50選出節(jié)約值最大為13.9，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為、18。假如連接6和8，則與上述

54、線路合并，其總需求量為7，未超過一輛車的運(yùn)輸能力，因此，連接-18-1-0成回路，則將6、18與14、18的節(jié)約值賦為。同時(shí),由于頂點(diǎn)6成回路的中間點(diǎn)，則與頂點(diǎn)6相關(guān)的節(jié)約值都賦為，表示頂點(diǎn)6不可能再與其他點(diǎn)相連,其結(jié)果如下表所示。表3-1123467801123141516718920003480400050000060000007000 0008.600000000001000000001100000020000000030-0.21.700600001404.98.5000-03003.01504.40.50000004050164.50000200.39.900170000000000

55、0000018088.70001.400.201.29.10190.40.500012.2001.4.0100.20202.96.90000.7000613.40.58.409.5選出節(jié)約值最大為13.,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為1、2。假如連接4和0，則與上述線路合并，其總需求量為9,超過一輛車的運(yùn)輸能力，因此,4和0不能連接 ，和20;8和20也不能連接,則將6、2;4、20和18、20的節(jié)約值賦為0.選出節(jié)約值最大值為11.4,其對(duì)應(yīng)的兩點(diǎn)為13、1。假如連接13和19，則與上述線路合并，其總需求量為1，超過一輛車的運(yùn)輸能力8,因此,1和19不能連接，1、；1、5；1、1和1、5也不能連接，則將

56、13、1;13、5；3、1和13、1的節(jié)約值賦為0選出節(jié)約值最大為.9，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為、16。假如連接14和16,則與上述線路合并，其總需求量為9，超過一輛車的運(yùn)輸能力8，因此,14和1不能連接 ，6和1；1和16也不能連接,則將6、16；1、6和18、16的節(jié)約值賦為0.選出節(jié)約值最大為8.7，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為3、1。假如連接3和8,則與上述線路合并,其總需求量為9,超過一輛車的運(yùn)輸能力,因此，3和18不能連接 ,3和8；3和6;3和1也不能連接,則將3、18;3、和3、1的節(jié)約值賦為0.選出節(jié)約值最大為8,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為3、1。假如連接3和16，其總需求量為,未超過一輛車的運(yùn)輸能

57、力8，因此，連接3、16成回路，即0-3-6-0.再將頂點(diǎn)3和16的節(jié)約值賦為.選出節(jié)約值最大為84,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為2、18。假如連接和8,則與上述線路合并，其總需求量為1，超過一輛車的運(yùn)輸能力8,因此，2和1；2和6;2和14也不能連接,則將2、1；2、6和2、14的節(jié)約值賦為0.選出節(jié)約值最大為84,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為1、20。假如連接1和20，其總需求量為6，未超過一輛車的運(yùn)輸能力8，因此,連接16、2成回路，即036-20-0再將頂點(diǎn)、2和3、20的節(jié)約值都賦為. 同時(shí),由于頂點(diǎn)16成回路的中間點(diǎn),則與頂點(diǎn)16相關(guān)的節(jié)約值都賦為0,表示頂點(diǎn)1不可能再與其他點(diǎn)相連,其結(jié)果如下表所示。

58、表3-213456789011111516178192010203.84000050000600070 00800.7000090000000010000000110000000001000000030-.1.700004.6000004000000-000.90504.40.50000000.010000000000000001000000000000018000.400012.00090040.50000001.5000.2200.00000.0000600005選出節(jié)約值最大為6，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為3、20。假如連接13和2,則與上述線路合并,其總需求量為0，超過一輛車的運(yùn)輸能力，因此,

59、3和0不能連接 ,3和3;1和16也不能連接，則將13、；13、1和13、20的節(jié)約值賦為0.選出節(jié)約值最大為.8,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為2、。假如連接2和3，則與上述線路合并,其總需求量為,超過一輛車的運(yùn)輸能力8，因此，2和3不能連接 ,2和1；2和20也不能連接，則將2、3;2、16和2、20的節(jié)約值賦為0.選出節(jié)約值最大為4.6，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為2、8。假如連接2和8,其總需求量為,未超過一輛車的運(yùn)輸能力,因此,連接，2、8成回路,即-80.再將與頂點(diǎn)和8相關(guān)的節(jié)約值都賦為0,表示頂點(diǎn)2和8不可能再與其他點(diǎn)相連。選出節(jié)約值最大為4.,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為19、0。假如連接19和,則與上述兩條

60、線路合并，其總需求量為1，超過一輛車的運(yùn)輸能力8，因此，15、3;1、6；5、20;19、3;、16和9、20也不能連接，則將8、3；8、16；、20；1、;19、1和19、20的節(jié)約值賦為0.選出節(jié)約值最大為3.9，其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為1、1。假如連接1和1,則與上述線路合并,其總需求量為1，超過一輛車的運(yùn)輸能力8,因此,3和14不能連接，13和1；13和6也不能連接，則將3、6；、14和13、18的節(jié)約值賦為0.選出節(jié)約值最大為1.5,其對(duì)應(yīng)的兩個(gè)頂點(diǎn)為4、19。假如連接1和19,則與上述兩條線路合并,其總需求量為1，超過一輛車的運(yùn)輸能力8,因此，5、;15、14;9、8;19、和9、14也