超市最短路徑運輸配送問題

?大學(xué)管理與經(jīng)濟(jì)學(xué)部夏令營學(xué)術(shù)論文展示學(xué)校：大學(xué)：歡專業(yè)：工程管理申請專業(yè)：管理科學(xué)與工程研究方向：工程管理申請類型：學(xué)術(shù)型碩士一、研究目的了解配送中心運輸配送系統(tǒng)相關(guān)的數(shù)量方法在管理決策中的有效運用。鍛煉運用節(jié)約算法法處理實際問題的能力加強(qiáng)商業(yè)調(diào)查能力的訓(xùn)練二、研究容與研究步驟1、數(shù)據(jù)調(diào)查我選擇的調(diào)查對象是市的紅旗連鎖紅旗超市,紅旗連鎖成立于2000年6月。2010年5月20日，紅旗連鎖股份正式創(chuàng)立。公司現(xiàn)已發(fā)展成為中國西部地區(qū)最具規(guī)模的以連鎖經(jīng)營、物流配送、電子商務(wù)為一體的商業(yè)連鎖企業(yè)。目前在省已開設(shè)上千家連鎖超市，就業(yè)員工上萬人，累計上繳稅收6億以上;擁有兩座現(xiàn)代化的物流配送中心;與上千家供貨商建立了良好的互利雙贏的商業(yè)合作關(guān)系。我就近選擇了位于市武侯區(qū)簇馬路2段11號的配送中心，對其半徑三公里圍的紅旗超市配送進(jìn)行了具體的數(shù)據(jù)調(diào)查和記錄。紅旗連鎖配送中心：市武侯區(qū)簇馬路2段11號（選址如圖1,A為該配送中心）配送圍：半徑3000m圖1：

2、模型建立第一步：據(jù)調(diào)查出的配送中心及網(wǎng)點分布圖，繪制出配送網(wǎng)點模型圖如下：圖2：第二步：由實地咨詢及資料查閱后收集到的各網(wǎng)點和配送中心之間的路程數(shù)據(jù)，給出配送中心與分店，商店與商店之間的距離，0表示配送中心（完整數(shù)據(jù)見附網(wǎng)點距宮表〔單位：Q三:配式或12345781：'二PS31達(dá)5110014001400UM1800股。。二口；21X1L4CC1800115013001450110iSCi口工?-ccc22001GCC21B001000230014CiZ7Xi2700￡jXi二口；3Z300340j702100ZjXi盟1IjXi2CCC42500jK'O170028003100■jXi僦5jjj汕Ijjj47CIjjj2iii02200如。U：C"U；7Gjjj29DD￡jjj32ii0中，3500__LL91Ji.i10XI.1.1112LS.可修編表1：網(wǎng)點距離表）每個分店q均甸天的需求量二面超市網(wǎng)點12345678g鴕送量⑴322111231紅旗超市網(wǎng)點121314151617181920配送量㈤D.71n.nD.7fi.M11.乂0.9(1.r三、背景據(jù)介紹，自紅旗連鎖成立以后，其公司決策層就提出為適應(yīng)市場發(fā)展需要，必須跟上先進(jìn)零售企業(yè)信息化管理的步伐，完成對各分店的POS/MIS自動化管理系統(tǒng)，實現(xiàn)配送中心與財務(wù)中心的聯(lián)網(wǎng)，以達(dá)到對單列商品準(zhǔn)確的進(jìn)、銷、存的科學(xué)信息化管理，合理安排和使用流動資金，加快商品及資金周轉(zhuǎn)率，以形成一套健全的、高效的商品自動化管理系統(tǒng)，包括商品的進(jìn)銷存管理系統(tǒng)、供應(yīng)鏈管理系統(tǒng)，同時逐漸提升公司部的信息化管理。據(jù)悉，為了實現(xiàn)這一系列的信息化目標(biāo)，公司每年在信息化上的投入就達(dá)到了幾百萬；公司領(lǐng)導(dǎo)更是親自著手企業(yè)各流程的改造與管理，使企業(yè)能夠更好的往信息化道路上發(fā)展。業(yè)務(wù)流程圖該超市配送中心物流管理系統(tǒng)主要包括采購、進(jìn)貨、退貨、銷售幾個方面。其中與供應(yīng)商、連鎖店、倉庫、顧客之間有著實際聯(lián)系。

節(jié)約里程算法：節(jié)約里程法核心思想是依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時，再進(jìn)行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。利用節(jié)約法確定配送路線的主要出發(fā)點是，根據(jù)配送中心的運輸能力和配送中心到各個用戶以及各個用戶之間的距離來制定使總的車輛運輸?shù)膰嵐飻?shù)最小的配送方案。另還需滿足以下條件；（1）所有用戶的要求；（2）不使任何一輛車超載；（3）每輛車每天的總運行時間或行駛里程不超過規(guī)定的上限；（4）用戶到貨時間要求。其基本優(yōu)化思想是為達(dá)到高效率的配送，使配送的時間最小距離最短成本最低，而尋找的最佳配送路線。假如一家配送中心（口0向兩個用戶4、8運貨，配送中心到兩用戶的最短距離分別是1@和1匕，人和B間的最短距離為Lab,4、8的貨物需求量分別是Qa和Qb,且（Qa+Qb）小于運輸裝載量Q,如果配送中心分別送貨，那么需要兩個車次，總路程為：L1=2（La+Lb）。如果改用一輛車對兩客戶進(jìn)行巡回送貨，則只需一個車次,行走的總路程為：L2=La+Lb+Lab由三角形的性質(zhì)我們知道：Lab＜（La+Lb）所以第二次的配送方案明顯優(yōu)于第一種，且行走總路程節(jié)約：△L=（La+Lb）-Lab如果配送中心的供貨圍還存在著：3,4,5,…，門個用戶，在運載車輛載重和體積都允許的情況下，可將它們按著節(jié)約路程的大小依次連入巡回線路，直至滿載為止,余下的用戶可用同樣方法確定巡回路線,另外派車。四、過程與分析步驟一：根據(jù)附表1：網(wǎng)點距離表中的網(wǎng)點距離圖,計算各商店之間的節(jié)約里程（完整數(shù)據(jù)見附表2：節(jié)約里程表）

-、下二二U12345&7e91(11112131閔-19131-19-19_典31-691313113L2125635-51.樂-5：：5-5325325■:■3：：：11U：：：：：Ji:.：：：.：：：5二「：5二43001001500&00200-100215024002500526703001700282023308001W0￡0061400]?03Q4O31057DD陽D70D70：："0-300lc"l:；：：四二二二:匚：9260010001300110011：'200如口20011潞52800121314■iE*節(jié)約值矩陣表步驟二：由節(jié)約里程表可知，根據(jù)最大的里程節(jié)約和各點的需求量限制，所以我們把13-14-15-16順序連接起來，因為8的需求量是3,而貨車只能限載5T,所以不能連在13-14-15-16里。在節(jié)約里程表里把14、15兩列和兩行的節(jié)約里程都改為0。(完整數(shù)據(jù)見附表2：節(jié)約里程附表1)節(jié)約里程附表1：FS(配送中心1234567156-190-19-19-6921PS0-7532530.21602230800400052670SOO614007因為12到13節(jié)約里程最大41(12,13)=4050,其次是13到4節(jié)約的里程大41(4,13)=2500,若13連接12點那么根據(jù)車輛的限載51和各點的需求，只能P-11-12-13-14-15-16-P和P-4-8-P,此時總的節(jié)約里程411=22460；若13連接到4,那么線路為①P-4-到-14-15-16-P和②P-11-12-8-P。此時的△12=23660,因為412>411所以選擇第二種方案:車輛1：P-4-13-14-15-16-P車輛2：P-11-12-8-P,總里程=1400+1600+570+430+845+2700=7545m配送量=4.仃總里程=2200+750+645+1400=4995m配送量=4.51步驟三：在節(jié)約里程表里把4、11、12、13、14、15、16、8的橫列和縱列全部改成0得到節(jié)約里程附表1。通過排序得到節(jié)約里程順序附表（完整數(shù)據(jù)位于附表2：節(jié)約里程附表1）。節(jié)約里程附表1：89101112131415160-69-69000D00025325000D0U020751900000D00000000D00028302200000D00030403105000D00080D1900000D00D0000D002600000D00000D0000D0n0D00D00000因為18-19節(jié)約里程最大，把18-19連接起來，把18-19改為0，得到17-18最大，把17-18連接起來，得到17-18-19,17-18改為0，在這附近，所有的點的需求量Q加起來是10.3,所以為了使里程節(jié)約最大和配送量最大，得把邊緣的一個點放在其他路線去，根據(jù)步驟1，只能把20或者10這兩個點中的一個排在外面去。若把10放在左邊區(qū)域去，那么20與19連接，10就與21連接，節(jié)約的里程為4110=2500+4000=6500；若把20放到左邊區(qū)域，那么10與19連接,20與21連接，節(jié)約的里程4120=3985+3100=7085,因為4120>4110,所以把20放到左邊去。得到17-18-19-10,此時這幾點的需求量Q已經(jīng)達(dá)到了4.7,不能再與其他點連接，所以直接17孑,10孑,得到路線③P-17-18-19-10-P。此時節(jié)約的總里程^L3=4210+4320+3985=12515m車輛3：P-17-18-19-10-P，總里程=2100+2990+680+715+2100=5885印,配送1=4.7TO車輛3：P-17-18-19-10-P總里程=2100+2990+680+715+2100=5885m配送1=4.71（￡挈期就由夠4:2 ）"挈期義螂就宙夠2修撒冷挈期就宙夠2修撒04班他夠此俯靴用oz'%'笈、z俳宙z挈州就宙夠2丑：4瞽4ii'V=fSH山光〃=00點+009L+969+068+008尸就宙目d-02-L2-22-Z-d+的豐01L怔1SH'川光〃=00席+009L+969+068+008尸就宙目、-0%-%一直-2，：。的豐°W9L60L=00L￡+0L9￡+90Zl7=l7lV,就I.用夠2W即°50%-%一數(shù)-2,空現(xiàn)酩修撒‘哥耳d弓哥旦H幽’母耳草郵苴年期與雞W1尸。害*墨W即加-%-02修撒0LLZ型’Y獸0LL"04藁7Z-L俳’\Z~7Z~L修撒’笈一2班5'I獸ZLZ'O《犯公-%俳NLLZ哥耳Hr‘I曾就宙夠2ZLLZ&MLC0（.C0rr0DCC0D0rr0Dflil1CC0D000i.I0口II1.101.cc0D000ccLI0DUu0IIJcc.0Dn00cc.Lc0D000(.cJrr0Diln0rr:CC0DD00CCjrr0Dilii0rr■lCC0DD00CC3i.i.□Dilii0i.i.Jcc0DD00ccj6LEL21QILLEIA.1u.%挈期就宙夠2（Z挈期就宙夠2憶基刖工可辟賜需晉）%挈期義螂就宙夠2修撒義芥貝醺吃挈期就宙夠2修撒04通腥俯夠此俯靴用6L'8L'ZL'0L俳8!宙L挈州就宙夠2丑：恤署4（。挈期就宙夠2憶基刖工可辟賜需普）。。挈期田螂就宙夠2修撒仙推田螂母力挈期就由夠2修撒04班限他夠此俯靴用￡、9、6、9俳宙￡挈期就宙夠2丑：￥署419=1SH山00￡尸00LL+0Z9+099+0"+00。尸就宙目d-e-9-6-9-d+的豐19=1SH'川00￡尸00"+029+099+0"+00孔二就宙m、-￡-9-6-0丐的豐。川00L"0￡ZZ+0H）￡+0￡8ZF1▽就宙.用夠2W即°5￡-9-6-9,⑨現(xiàn)酩修撒哥IfdWH幽’草用黑徨盜墨旦祭年期冶-6-9-￡修撒9遙班耳'￥I9-￡'04?6-9俳J9-6-9―修撒6-9S5S'￥—I6V'0年犯6-9——俳’6-9哥_￥XJ幽'￥—獸就宙夠_46-9^8——'撒也￡挈_期明螂就由夠2申—000000000C _000C _000C _000C _000■_000C _000C _000C _0001_000C _000工 _000C _0000C _00000C _00000C _000001_00000C _00000C _007Z150E日L：￡挈期就宙夠2

34567S9000000000000000000000000000000000010由表可得只有1-2,連接1-2,再與P連接得到線路⑥P-1-2-P。此時節(jié)約的總里程416=56印。車輛6：P-1-2-P,總里程=31+800+825=1656印，配送量=51。車輛6：P-1-2-P總里程=31+800+825=1656m配送量=51綜上：該模型優(yōu)化后的最終線路分別是：①P-4-13-14-15-16-P②

P-11-12-8-P ③P-17-18-19-10-P④P-7-22-21-20-P⑤P-5-9-6-3-P⑥P-1-2-P。①P-4-13-14-15-16-P②P-11-12-8-P③P-17-18-19-10-P④P-7-22-21-20-P⑤P-5-9-6-3-P⑥P-1-2-P?？偫锍蘈=7545+4995+5885+7285+4300+1656=31666m。總節(jié)約里程△L=4L2+4L3+4L4+4L5+△L6=23660+12515+10915+8100+56=55246m。車輛=6輛總配送量=4.1+4.5+4.7+5+5+4.1=27.4T五、結(jié)果總結(jié)利用節(jié)約里程算法進(jìn)行路線優(yōu)化，結(jié)合配送中心的運輸能力和配送中心到各個用戶以及各個用戶之間的距離信息，從而制定使總的車輛運輸?shù)膰嵐飻?shù)最小的配送方案。實驗小組經(jīng)過科學(xué)、嚴(yán)謹(jǐn)?shù)倪壿嬐评砗陀嬎?，得出最佳配送路線為線路分別是：①P-4-13-14-15-16-P ②P-11-12-8-P ③P-17-18-19-10-P ④P-7-22-21-20-P ⑤P-5-9-6-3-P⑥P-1-2-P?？偫锍蘈=7545+4995+5885+7285+4300+1656=31666m?？偣?jié)約里程△L=AL2+AL3+AL4+AL5+AL6=23660+12515+10915+8100+56=55246m。車輛=6輛總配送量=4.1+4.5+4.7+5+5+4.1=27.4T

優(yōu)化后的結(jié)果路線