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

1、天津大學管理與經(jīng)濟學部夏令營學術(shù)論文展示學校：四川大學姓名：趙歡專業(yè)：工程管理申請專業(yè)：管理科學與工程研究方向：工程管理申請類型：學術(shù)型碩士實驗報告書、研究目的1 .了解配送中心運輸配送系統(tǒng)相關(guān)的數(shù)量方法在管理決策中的有效運用2 .鍛煉運用節(jié)約算法法處理實際問題的能力3 .加強商業(yè)調(diào)查能力的訓練二、研究內(nèi)容與研究步驟1、數(shù)據(jù)調(diào)查我選擇的調(diào)查對象是成都市的紅旗連鎖紅旗超市，成都紅旗連鎖有限公司成立于2000年6月。2010年5月20日，成都紅旗連鎖股份有限公司正式創(chuàng)立。公司現(xiàn)已發(fā)展成為中國西部地區(qū)最具規(guī)模的以連鎖經(jīng)營、物流配送、電子商務為一體的商業(yè)連鎖企業(yè)。目前在四川省內(nèi)已開設上千家連鎖超市，就

2、業(yè)員工上萬人，累計上繳稅收6億以上；擁有兩座現(xiàn)代化的物流配送中心；與上千家供貨商建立了良好的互利雙贏的商業(yè)合作關(guān)系。我就近選擇了位于成都市武侯區(qū)簇馬路2段11號的配送中心，對其半徑三公里范圍內(nèi)的紅旗超市配送進行了具體的數(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表示

3、配送中心（完整數(shù)據(jù)見附網(wǎng)點即寓表（單位；AFS配送中出12345g7B91011PS318251100140014011BQ2100L4OQ18OQ11501300145010501900215020002200L3OQ21800160023002300140027002700政0190032300340670210023QQ9251300200Q425003100170020003100朝。的Q553024001迎470130020006220D溝Q沏T95250074000290020003200822003500110091400230Q103200111213

4、實驗報告書表1:網(wǎng)點距離表）第三步：車輛數(shù)分析（完整數(shù)據(jù)見附表1:車輛調(diào)度情況）車輛調(diào)度情況車輛運用數(shù)（輛）81010910798運月天數(shù)2530364246494838總數(shù)20030036037846034343230431958.753425平均每天所用車輛數(shù)為9輛第四步：分店需求量分析（完整數(shù)據(jù)見附表1:每個分店平均每天的需求量）每個分店平均每天的需求量紅旗超市網(wǎng)點1234567Eg鴕送量（t）322111231經(jīng)施超市網(wǎng)點二1314151617161920品送量Ct）0.710,60.70.310.80.90.6據(jù)介紹，自紅旗連鎖成立以后，其公司決策層就提出為適應市場發(fā)展需要，必須跟上

5、先進零售企業(yè)信息化管理的步伐，完成對各分店的POS/MIS自動化管理系統(tǒng)，實現(xiàn)配送中心與財務中心的聯(lián)網(wǎng)，以達到對單列商品準確的進、銷、存的科學信息化管理，合理安排和使用流動資金，加快商品及資金周轉(zhuǎn)率，以形成一套健全的、高效的商品自動化管理系統(tǒng)，包括商品的進銷存管理系統(tǒng)、供應鏈管理系統(tǒng)，同時逐漸提升公司內(nèi)部的信息化管理。據(jù)悉，為了實現(xiàn)這一系列的信息化目標，公司每年在信息化上的投入就達到了幾百萬；公司領導更是親自著手企業(yè)各流程的改造與管理，使企業(yè)能夠更好的往信息化道路上發(fā)展。業(yè)務流程圖該超市配送中心物流管理系統(tǒng)主要包括采購、進貨、退貨、銷售幾個方面。其中與供應商、連鎖店、倉庫、顧客之間有著實際聯(lián)系

6、。本次實驗是在武侯區(qū)的紅旗超市店面和配送中心進行的，主要是實地采訪、詢問的方法，進行路線優(yōu)化的方法是節(jié)約里程計算法。節(jié)約里程算法：節(jié)約里程法核心思想是依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。利用節(jié)約法確定配送路線的主要出發(fā)點是，根據(jù)配送中心的運輸能力和配送中心到各個用戶以及各個用戶之間的距離來制定使總的車輛運輸?shù)膰嵐飻?shù)最小的配送方案。另還需滿足以下條件；（1）所有用戶的要求；（2）不使任何一輛車超載；（3）每輛車每天的總運行時間或行駛里程不超過規(guī)定的上限；（4）用戶

7、到貨時間要求。其基本優(yōu)化思想是為達到高效率的配送，使配送的時間最小距離最短成本最低，而尋找的最佳配送路線。假如一家配送中心（D。向兩個用戶A、B運貨，配送中心到兩用戶的最短距離分別是La和Lb,A和B間的最短距離為Lab,A、B的貨物需求量分別是Qa和Qh且（Qa+Qb小于運卒&裝載量Q,如果配送中心分別送貨，那么需要兩個車次，總路程為：L1=2（La+Lb）。如果改用一輛車對兩客戶進行巡回送貨，則只需一個車次，行走的總路程為：L2=La+Lb+Lab由三角形的性質(zhì)我們知道:Lab<（La+Lb）所以第二次的配送方案明顯優(yōu)于第一種，且行走總路程節(jié)約：AL=（La+Lb）Lab如果

8、配送中心的供貨范圍內(nèi)還存在著：3,4,5,n個用戶，在運載車輛載重和體積都允許的情況下，可將它們按著節(jié)約路程的大小依次連入巡回線路，直至滿載為止，余下的用戶可用同樣方法確定巡回路線，另外派車。四、過程與分析步驟一：根據(jù)附表1：網(wǎng)點距離表中的網(wǎng)點距離圖，計算各商店之間的節(jié)約里程（完整數(shù)據(jù)見附表2:節(jié)約里程表）FS（配送中。12345&73910111213156-19131-19-ig-6931-69-69131311312125625-7E3251225325253253K325435320021602230SOO1000207519005007005004300ICO1500SOO2

9、00-10021502400250052670800170028302200SOO10000006140014003040JL0580070070eoo190000319Q0MD250035503500q26OD10W13001100ID300WO300ii28552E00二40501314節(jié)約值矩陣表步驟二：由節(jié)約里程表可知，根據(jù)最大的里程節(jié)約和各點的需求量限制，所以我們把13-14-15-16順序連接起來，因為8的需求量是3,而貨車只能限載5T,所以不能連在13-14-15-16里。在節(jié)約里程表里把14、15兩列和兩行的節(jié)約里程都改為0o(完整數(shù)據(jù)見附表2:節(jié)約里程附表1)節(jié)約里程附表1:

10、FS配送中心12345e7156-190-19-19-6921250-7532512253021602230S00400052670300e14007n因為12到13節(jié)約里程最大L(12,13)=4050,其次是13到4節(jié)約的里程大4L(4,13)=2500,若13連接12點那么根據(jù)車輛的限載5T和各點的需求，只能P-11-12-13-14-15-16-P和P-4-8-P,此時總的節(jié)約里程L1=22460;若13連接到4,那么線路為P-4-13-14-15-16-P和P-11-12-8-P。此時的L2=23660,因為L2>4L1所以選擇第二種方案：車輛1:P-4-13-14-15-16

11、-P車輛2:P-11-12-8-P,總里程=1400+1600+570+430+845+2700=7545r配送量=4.1T總里程=2200+750+645+1400=4995m1配送量=4.5T步驟三：在節(jié)約里程表里把4、11、12、13、14、15、16、8的橫列和縱列全部改成0得到節(jié)約里程附表1。通過排序得到節(jié)約里程順序附表(完整數(shù)據(jù)位于附表2:節(jié)約里程附表1)o節(jié)約里程附表1:89101112131415160-69-6900000002532500000002075190000000000000000023302200000000030403105000000800190000000

12、0000000002600000000000000000000000000000因為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é)約的里程為L10=2500+4000=6500若把20放到左邊區(qū)域，那么10與19連接，20與21連接，節(jié)約的里程L20=3985+

13、3100=7085因為L20>L10,所以把20放到左邊去。得到17-18-19-10,此時這幾點的需求量Q已經(jīng)達到了4.7,不能再與其他點連接，所以直接17-P,10-P,得到路線P-17-18-19-10-P。此時節(jié)約的總里程L3=4210+4320+3985=12515m車輛3:P-17-18-19-10-P,總里程=2100+2990+680+715+2100=5885mE送量=4.7T。車輛3:P-17-18-19-10-P總里程=2100+2990+680+715+2100=5885m配送量=4.7T步驟四：在節(jié)約里程附表1里面把10、17、18、19的橫列和縱列都改為0得到

14、節(jié)約里程附表2,通過排序得到節(jié)約里程順序附表2。（完整數(shù)據(jù)位于附表2:節(jié)約里程附表2）節(jié)約里程附表2:101112131415ie17IB190000001C0000li1:0000000000000000000000000000000000000000000000Q0liQ0000Q00Zo0000000000000000000000000001.1000000000000000000000000000QQ1.00n00因為21-22節(jié)約里程最大，所以連接21-22,把21-22改為0,7-22最大,連接7-22，得至IJ7-22-21，把7-22變?yōu)?,21-20最大，連21-20得到7-

15、22-21-20,此時需求量Q=4.1,不能與附近其他點連接，所以直接與P連接，得到線路P-7-22-21-20-P。此時節(jié)約的總里程為L4=4205+3610+3100=10915m車輛4:P-7-22-21-20-P，總里程=1800+890+695+1500+2400=7285甫已送量=4.1T。車輛4:P-7-22-21-20-P總里程=1800+890+695+1500+2400=7285m配送量=4.1T步驟五：在節(jié)約里程附表2里把7、22、21、20的橫列和縱列改為0得到節(jié)約里程附表3,通過排序得到節(jié)約里程順序附表3。（完整數(shù)據(jù)位于附表2:節(jié)約里程附表3）節(jié)約里程附表3:T782

16、02122由節(jié)約里程順序附表3可得，因為6-9節(jié)約里程最大，所以連接6-9,把6-930,5-9最大，再連接5-9得到6-9-5,把5-930,3-6最大,妾得到線路00300000100000i000003000000000000001000i000I000I0003000JI000000000000-3000-30001000000000連接3-6得到3-6-9-5,附近沒有需要配送的點，所以1與P連才P-5-9-6-3-P。此時節(jié)約的總里程L5=2830+3040+2230=8100m車輛5:P-5-9-6-3-P,總里程=1400+470+660+670+1100=4300m配送量=5

17、T車輛5:P-5-9-6-3-P總里程=1400+470+660+670+1100=4300m配送量=5T步驟六：在節(jié)約里程附表3里把5、9、6、3的橫列和縱列都改為0得到節(jié)約里程附表4,按順序排列得到節(jié)約里程順序附表4。（完整數(shù)據(jù)位于附表2:節(jié)約里程附表4）節(jié)約里程附表4:34507S9rop00000000000000。00000000°000°0000°°由表可得只有1-2,連接1-2,再與P連接得到線路P-1-2-Po此時節(jié)約的總里程L6=56m車輛6:P-1-2-P,總里程=31+800+825=1656m配送量=5T。車輛6:P-1-2-P總

18、里程=31+800+825=1656m配送量=5T綜上：該模型優(yōu)化后的最終線路分別是: P-4-13-14-15-16-PP-11-12-8-PP-17-18-19-10-PP-7-22-21-20-PP-5-9-6-3-PP-1-2-P。P-4-13-14-15-16-PP-11-12-8-PP-17-18-19-10-PP-7-22-21-20-PP-5-9-6-3-PP-1-2-P。總里程L=7545+4995+5885+7285+4300+1656=31666m總節(jié)約里程L=AL2+AL3+AL4+AL5+AL6=23660+12515+10915+8100+56=55246m車輛=6

19、輛總配送量=4.1+4.5+4.7+5+5+4.1=27.4T總里程31666m總節(jié)約里程55246m車輛6輛總配送量27.4T五、結(jié)果總結(jié)利用節(jié)約里程算法進行路線優(yōu)化，結(jié)合配送中心的運輸能力和配送中心到各個用戶以及各個用戶之間的距離信息，從而制定使總的車輛運輸?shù)膰嵐飻?shù)最小的配送方案。實驗小組經(jīng)過科學、嚴謹?shù)倪壿嬐评砗陀嬎悖贸鲎罴雅渌吐肪€為線路分別是：P-4-13-14-15-16-PP-11-12-8-PP-17-18-19-10-PP-7-22-21-20-PP-5-9-6-3-PP-1-2-P。總里程L=7545+4995+5885+7285+4300+1656=31666m總節(jié)約里程L=AL2+AL3+AL4+AL5+AL6=23660+12515+10915+8100+56=55246m車輛=6輛總酉己送