超市最短路径运输配送问题

»大学管理与经济学部夏令营学术论文展示学校：大学：欢专业：工程管理申请专业：管理科学与工程研究方向：工程管理申请类型：学术型硕士一、研究目的了解配送中心运输配送系统相关的数量方法在管理决策中的有效运用。锻炼运用节约算法法处理实际问题的能力加强商业调查能力的训练二、研究容与研究步骤1、数据调查我选择的调查对象是市的红旗连锁红旗超市,红旗连锁成立于2000年6月。2010年5月20日，红旗连锁股份正式创立。公司现已发展成为中国西部地区最具规模的以连锁经营、物流配送、电子商务为一体的商业连锁企业。目前在省已开设上千家连锁超市，就业员工上万人，累计上缴税收6亿以上;拥有两座现代化的物流配送中心;与上千家供货商建立了良好的互利双赢的商业合作关系。我就近选择了位于市武侯区簇马路2段11号的配送中心，对其半径三公里围的红旗超市配送进行了具体的数据调查和记录。红旗连锁配送中心：市武侯区簇马路2段11号（选址如图1,A为该配送中心）配送围：半径3000m图1：

2、模型建立第一步：据调查出的配送中心及网点分布图，绘制出配送网点模型图如下：图2：第二步：由实地咨询及资料查阅后收集到的各网点和配送中心之间的路程数据，给出配送中心与分店，商店与商店之间的距离，0表示配送中心（完整数据见附网点距宫表〔单位：Q三:配式或12345781：'二PS31达5110014001400UM1800股。。二口；21X1L4CC1800115013001450110iSCi口工।-ccc22001GCC21B001000230014CiZ7Xi2700£jXi二口；3Z300340j702100ZjXi盟1IjXi2CCC42500jK'O170028003100■jXi僦5jjj汕Ijjj47CIjjj2iii02200如。U：C"U；7Gjjj29DD£jjj32ii0中，3500__LL91Ji.i10XI.1.1112LS.可修编表1：网点距离表）每个分店q均甸天的需求量二面超市网点12345678g鸵送量⑴322111231红旗超市网点121314151617181920配送量㈤D.71n.nD.7fi.M11.乂0.9(1.r三、背景据介绍，自红旗连锁成立以后，其公司决策层就提出为适应市场发展需要，必须跟上先进零售企业信息化管理的步伐，完成对各分店的POS/MIS自动化管理系统，实现配送中心与财务中心的联网，以达到对单列商品准确的进、销、存的科学信息化管理，合理安排和使用流动资金，加快商品及资金周转率，以形成一套健全的、高效的商品自动化管理系统，包括商品的进销存管理系统、供应链管理系统，同时逐渐提升公司部的信息化管理。据悉，为了实现这一系列的信息化目标，公司每年在信息化上的投入就达到了几百万；公司领导更是亲自着手企业各流程的改造与管理，使企业能够更好的往信息化道路上发展。业务流程图该超市配送中心物流管理系统主要包括采购、进货、退货、销售几个方面。其中与供应商、连锁店、仓库、顾客之间有着实际联系。

节约里程算法：节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；（1）所有用户的要求；（2）不使任何一辆车超载；（3）每辆车每天的总运行时间或行驶里程不超过规定的上限；（4）用户到货时间要求。其基本优化思想是为达到高效率的配送，使配送的时间最小距离最短成本最低，而寻找的最佳配送路线。假如一家配送中心（口0向两个用户4、8运货，配送中心到两用户的最短距离分别是1@和1匕，人和B间的最短距离为Lab,4、8的货物需求量分别是Qa和Qb,且（Qa+Qb）小于运输装载量Q,如果配送中心分别送货，那么需要两个车次，总路程为：L1=2（La+Lb）。如果改用一辆车对两客户进行巡回送货，则只需一个车次,行走的总路程为：L2=La+Lb+Lab由三角形的性质我们知道：Lab＜（La+Lb）所以第二次的配送方案明显优于第一种，且行走总路程节约：△L=（La+Lb）-Lab如果配送中心的供货围还存在着：3,4,5,…，门个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止,余下的用户可用同样方法确定巡回路线,另外派车。四、过程与分析步骤一：根据附表1：网点距离表中的网点距离图,计算各商店之间的节约里程（完整数据见附表2：节约里程表）

-、下二二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*节约值矩阵表步骤二：由节约里程表可知，根据最大的里程节约和各点的需求量限制，所以我们把13-14-15-16顺序连接起来，因为8的需求量是3,而货车只能限载5T,所以不能连在13-14-15-16里。在节约里程表里把14、15两列和两行的节约里程都改为0。(完整数据见附表2：节约里程附表1)节约里程附表1：FS(配送中心1234567156-190-19-19-6921PS0-7532530.21602230800400052670SOO614007因为12到13节约里程最大41(12,13)=4050,其次是13到4节约的里程大41(4,13)=2500,若13连接12点那么根据车辆的限载51和各点的需求，只能P-11-12-13-14-15-16-P和P-4-8-P,此时总的节约里程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步骤三：在节约里程表里把4、11、12、13、14、15、16、8的横列和纵列全部改成0得到节约里程附表1。通过排序得到节约里程顺序附表（完整数据位于附表2：节约里程附表1）。节约里程附表1：89101112131415160-69-69000D00025325000D0U020751900000D00000000D00028302200000D00030403105000D00080D1900000D00D0000D002600000D00000D0000D0n0D00D00000因为18-19节约里程最大，把18-19连接起来，把18-19改为0，得到17-18最大，把17-18连接起来，得到17-18-19,17-18改为0，在这附近，所有的点的需求量Q加起来是10.3,所以为了使里程节约最大和配送量最大，得把边缘的一个点放在其他路线去，根据步骤1，只能把20或者10这两个点中的一个排在外面去。若把10放在左边区域去，那么20与19连接，10就与21连接，节约的里程为4110=2500+4000=6500；若把20放到左边区域，那么10与19连接,20与21连接，节约的里程4120=3985+3100=7085,因为4120>4110,所以把20放到左边去。得到17-18-19-10,此时这几点的需求量Q已经达到了4.7,不能再与其他点连接，所以直接17孑,10孑,得到路线③P-17-18-19-10-P。此时节约的总里程^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%-%一数-2,空现酩修撒‘哥耳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,⑨现酩修撒哥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。此时节约的总里程416=56印。车辆6：P-1-2-P,总里程=31+800+825=1656印，配送量=51。车辆6：P-1-2-P总里程=31+800+825=1656m配送量=51综上：该模型优化后的最终线路分别是：①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。总里程L=7545+4995+5885+7285+4300+1656=31666m。总节约里程△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五、结果总结利用节约里程算法进行路线优化，结合配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离信息，从而制定使总的车辆运输的吨公里数最小的配送方案。实验小组经过科学、严谨的逻辑推理和计算，得出最佳配送路线为线路分别是：①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。总里程L=7545+4995+5885+7285+4300+1656=31666m。总节约里程△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

优化后的结果路线