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

大学管理与经济学部夏令营学术论文展示学校：大学：欢专业：工程管理申请专业：管理科学与工程研究方向：工程管理申请类型：学术型硕士 / 一、研究目的1. 了解配送中心运输配送系统相关的数量方法在管理决策中的有效运用2. 锻炼运用节约算法法处理实际问题的能力3. 加强商业调查能力的训练二、研究容与研究步骤1、数据调查 我选择的调查对象是市的红旗连锁红旗超市, 红旗连锁成立于2000年6月2010年5月20日，红旗连锁股份正式创立公司现已开展成为中国西部地区最具规模的以连锁经营、物流配送、电子商务为一体的商业连锁企业目前在省已开设上千家连锁超市，就业员工上万人，累计上缴税收6亿以上;拥有两座现代化的物流配送中心;与上千家供货商建立了良好的互利双赢的商业合作关系 我就近选择了位于市武侯区簇马路2段11号的配送中心，对其半径三公里围的红旗超市配送进展了具体的数据调查和记录 红旗连锁配送中心：市武侯区簇马路2段11号〔选址如图1，A为该配送中心〕 配送围：半径3000m图1：2、 模型建立第一步：据调查出的配送中心与网点分布图，绘制出配送网点模型图如下：图2：第二步：由实地咨询与资料查阅后收集到的各网点和配送中心之间的路程数据，给出配送中心与分店，商店与商店之间的距离，0表示配送中心〔完整数据见附表1：网点距离表〕第三步：车辆数分析〔完整数据见附表1：车辆调度情况〕第四步：分店需求量分析〔完整数据见附表1：每个分店平均每天的需求量〕三、 背景 据介绍，自红旗连锁成立以后，其公司决策层就提出为适应市场开展需要，必须跟上先进零售企业信息化管理的步伐，完成对各分店的POS/MIS自动化管理系统，实现配送中心与财务中心的联网，以到达对单列商品准确的进、销、存的科学信息化管理，合理安排和使用流动资金，加快商品与资金周转率，以形成一套健全的、高效的商品自动化管理系统，包括商品的进销存管理系统、供给链管理系统，同时逐渐提升公司部的信息化管理。

据悉，为了实现这一系列的信息化目标，公司每年在信息化上的投入就到达了几百万；公司领导更是亲自着手企业各流程的改造与管理，使企业能够更好的往信息化道路上开展业务流程图  该超市配送中心物流管理系统主要包括采购、进货、退货、销售几个方面其中与供给商、连锁店、仓库、顾客之间有着实际联系图3 本次实验是在武侯区的红旗超市店面和配送中心进展的，主要是实地采访、询问的方法，进展路线优化的方法是节约里程计算法 节约里程算法：节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到到达一辆车的装载限制时，再进展下一辆车的优化优化过程分为并行方式和串行方式两种 利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以与各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案另还需满足以下条件；〔1〕所有用户的要求；〔2〕不使任何一辆车超载；〔3〕每辆车每天的总运行时间或行驶里程不超过规定的上限；〔4〕用户到货时间要求其根本优化思想是为到达高效率的配送，使配送的时间最小距离最短本钱最低，而寻找的最正确配送路线。

假设一家配送中心〔DC〕向两个用户A、B运货，配送中心到两用户的最短距离分别是La和Lb，A和B间的最短距离为Lab，A、B的货物需求量分别是Qa和Qb，且〔Qa+Qb〕小于运输装载量Q，如果配送中心分别送货，那么需要两个车次，总路程为：L1=2〔La+Lb〕如果改用一辆车对两客户进展巡回送货，那么只需一个车次,行走的总路程为： L2=La+Lb+Lab 由三角形的性质我们知道： Lab<〔La+Lb〕 所以第二次的配送方案明显优于第一种，且行走总路程节约：ΔL=〔La+Lb〕－Lab 如果配送中心的供货围还存在着：3,4,5，…，n个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车四、 过程与分析步骤一：根据附表1：网点距离表中的网点距离图，计算各商店之间的节约里程〔完整数据见附表2：节约里程表〕 节约值矩阵表步骤二：由节约里程表可知，根据最大的里程节约和各点的需求量限制，所以我们把13-14-15-16顺序连接起来，因为8的需求量是3，而货车只能限载5T，所以不能连在13-14-15-16里。

在节约里程表里把14、15两列和两行的节约里程都改为0〔完整数据见附表2：节约里程附表1〕节约里程附表1： 因为12到13节约里程最大△L〔12,13〕=4050，其次是13到4节约的里程大△L〔4,13〕=2500，假设13连接12点那么根据车辆的限载5T和各点的需求，只能P-11-12-13-14-15-16-P和P-4-8-P,此时总的节约里程△L1=22460；假设13连接到4，那么线路为①P-4-13-14-15-16-P和②P-11-12-8-P此时的△L2=23660，因为△L2>△L1所以选择第二种方案：车辆1：P-4-13-14-15-16-P车辆2：P-11-12-8-P,总里程=1400+1600+570+430+845+2700=7545m配送量=4.1T总里程=2200+750+645+1400=4995m配送量=4.5T步骤三：在节约里程表里把4、11、12、13、14、15、16、8的横列和纵列全部改成0得到节约里程附表1通过排序得到节约里程顺序附表〔完整数据位于附表2：节约里程附表1〕节约里程附表1： 因为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连接，节约的里程为△L10=2500+4000=6500；假设把20放到左边区域，那么10与19连接，20与21连接，节约的里程△L20=3985+3100=7085，因为△L20>△L10，所以把20放到左边去得到17-18-19-10，此时这几点的需求量Q已经到达了4.7，不能再与其他点连接，所以直接17-P,10-P,得到路线③P-17-18-19-10-P此时节约的总里程△L3=4210+4320+3985=12515m 车辆3：P-17-18-19-10-P，总里程=2100+2990+680+715+2100=5885m,配送量=4.7T车辆3：P-17-18-19-10-P总里程=2100+2990+680+715+2100=5885m配送量=4.7T 步骤四： 在节约里程附表1里面把10、17、18、19的横列和纵列都改为0得到节约里程附表2，通过排序得到节约里程顺序附表2〔完整数据位于附表2：节约里程附表2〕节约里程附表2：因为21-22节约里程最大，所以连接21-22，把21-22改为0,7-22最大，连接7-22，得到7-22-21，把7-22变为0，21-20最大，连21-20得到7-22-21-20，此时需求量Q=4.1，不能与附近其他点连接，所以直接与P连接，得到线路④P-7-22-21-20-P。

此时节约的总里程为△L4=4205+3610+3100=10915m车辆4：P-7-22-21-20-P，总里程=1800+890+695+1500+2400=7285m，配送量=4.1T车辆4：P-7-22-21-20-P总里程=1800+890+695+1500+2400=7285m配送量=4.1T 步骤五：在节约里程附表2里把7、22、21、20的横列和纵列改为0得到节约里程附表3，通过排序得到节约里程顺序附表3〔完整数据位于附表2：节约里程附表3〕 节约里程附表3：由节约里程顺序附表3可得，因为6-9节约里程最大，所以连接6-9，把6-9改为0，,5-9最大，再连接5-9得到6-9-5，把5-9改为0,3-6最大，连接3-6得到3-6-9-5，附近没有需要配送的点，所以与P连接得到线路⑤P-5-9-6-3-P此时节约的总里程△L5=2830+3040+2230=8100m车辆5：P-5-9-6-3-P，总里程=1400+470+660+670+1100=4300m，配送量=5T车辆5：P-5-9-6-3-P总里程=1400+470+660+670+1100=4300m配送量=5T 步骤六：在节约里程附表3里把5、9、6、3的横列和纵列都改为0得到节约里程附表4，按顺序排列得到节约里程顺序附表4。

〔完整数据位于附表2：节约里程附表4〕节约里程附表4： 由表可得只有1-2，连接1-2，再与P连接得到线路⑥P-1-2-P此时节约的总里程△L6=56m 车辆6：P-1-2-P，总里程=31+800+825=1656m，配送量=5T车辆6：P-1-2-P总里程=31+800+825=1656m配送量=5T 综上：该模型优化后的最终线路分别是：①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=△L2+△L3+△L4+△L5+△L6=23660+12515+10915+8100+56=55246m车辆=6辆总配送量=4.1+4.5+4.7+5+5+4.1=27.4T总里程31666m总节约里程55246m车辆6辆总配送量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=△L2+△L3+△L4+△L5+△L6=23660+12515+10915+8100+56=55246m车辆=6辆总配送量=4.1+4.5。