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

1、天津大学管理与经济学部夏令营学术论文展示学校：四川大学姓名：赵欢专业：工程管理申请专业：管理科学与工程研究方向：工程管理申请类型：学术型硕士一、研究目的1. 了解配送中心运输配送系统相关的数量方法在管理决策中的有效运用。2. 锻炼运用节约算法法处理实际问题的能力3. 加强商业调查能力的训练二、研究内容与研究步骤1、数据调查我选择的调查对象是成都市的红旗连锁红旗超市 , 成都红旗连锁有限公司成立于 2000 年 6 月。 2010 年 5 月 20 日，成都红旗连锁股份有限公司正式创立。公司现已发展成为中国西部地区最具规模的以连锁经营、 物流配送、电子商务为一体的商业连锁企业。 目前在四川省内已

2、开设上千家连锁超市， 就业员工上万人，累计上缴税收 6 亿以上 ; 拥有两座现代化的物流配送中心 ; 与上千家供货商建立了良好的互利双赢的商业合作关系。我就近选择了位于成都市武侯区簇马路 2 段 11 号的配送中心，对其半径三公里范围内的红旗超市配送进行了具体的数据调查和记录。红旗连锁配送中心： 成都市武侯区簇马路 2 段 11 号（选址如图 1，A 为该配送中心）配送范围：半径3000m图 1：2、模型建立第一步： 据调查出的配送中心及网点分布图，绘制出配送网点模型图如下：图 2：第二步 ：由实地咨询及资料查阅后收集到的各网点和配送中心之间的路程数据，给出配送中心与分店，商店与商店之间的距离

3、，0 表示配送中心（完整数据见附表 1：网点距离表）第三步 ：车辆数分析（完整数据见附表 1：车辆调度情况）第四步 ：分店需求量分析（完整数据见附表 1：每个分店平均每天的需求量）三、背景据介绍，自红旗连锁成立以后，其公司决策层就提出为适应市场发展需要，必须跟上先进零售企业信息化管理的步伐，完成对各分店的 POS/MIS自动化管理系统，实现配送中心与财务中心的联网，以达到对单列商品准确的进、销、存的科学信息化管理，合理安排和使用流动资金， 加快商品及资金周转率， 以形成一套健全的、高效的商品自动化管理系统， 包括商品的进销存管理系统、 供应链管理系统，同时逐渐提升公司内部的信息化管理。 据悉，

4、为了实现这一系列的信息化目标，公司每年在信息化上的投入就达到了几百万； 公司领导更是亲自着手企业各流程的改造与管理，使企业能够更好的往信息化道路上发展。业务流程图 ?该超市配送中心物流管理系统主要包括采购、进货、退货、销售几个方面。其中与供应商、连锁店、仓库、顾客之间有着实际联系。图 3本次实验是在武侯区的红旗超市店面和配送中心进行的，主要是实地采访、询问的方法，进行路线优化的方法是节约里程计算法。节约里程算法：节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大， 直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式

5、两种。利用节约法确定配送路线的主要出发点是， 根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；（ 1）所有用户的要求；（ 2）不使任何一辆车超载；（ 3）每辆车每天的总运行时间或行驶里程不超过规定的上限；（ 4）用户到货时间要求。 其基本优化思想是为达到高效率的配送， 使配送的时间最小距离最短成本最低，而寻找的最佳配送路线。假如一家配送中心（ DC）向两个用户 A、B 运货，配送中心到两用户的最短距离分别是 La 和 Lb，A 和 B 间的最短距离为 Lab，A、B 的货物需求量分别是 Qa和 Qb，且（ Qa+

6、Qb）小于运输装载量 Q，如果配送中心分别送货，那么需要两个车次，总路程为： L1=2（ La+Lb）。如果改用一辆车对两客户进行巡回送货，则只需一个车次, 行走的总路程为：L2=La+Lb+Lab由三角形的性质我们知道：Lab<（ La+Lb）所以第二次的配送方案明显优于第一种，且行走总路程节约：L=（La+Lb） Lab如果配送中心的供货范围内还存在着：3,4,5 ， ， n 个用户，在运载车辆载重和体积都允许的情况下，可将它们按着节约路程的大小依次连入巡回线路，直至满载为止，余下的用户可用同样方法确定巡回路线，另外派车。四、过程与分析步骤一 ：根据附表 1：网点距离表中的网点距离图

7、，计算各商店之间的节约里程（完整数据见 附表 2：节约里程表）节约值矩阵表步骤二 ：由节约里程表可知， 根据最大的里程节约和各点的需求量限制， 所以我们把顺序连接起来，因为 8 的需求量是 3，而货车只能限载 5T，所以不能连在里。在节约里程表里把 14、 15 两列和两行的节约里程都改为 0。（完整数据见附表 2：节约里程附表 1）节约里程附表 1：因为 12到 13 节约里程最大 L（ 12,13 ）=4050，其次是 13 到 4 节约的里程大 L（4,13） =2500，若 13 连接 12 点那么根据车辆的限载 5T 和各点的需求，只能 P-5-16-P 和 P-4-8-P, 此时总

8、的节约里程 L1=22460；若 13 连接到 4，那么线路为 P-4-P 和 P-11-12-8-P 。此时的 L2=23660，因为 L2> L1 所以选择第二种方案：车辆 1： P-4-P车辆 2： P-11-12-8-P,总里程总里程 =2200+750+645+1400=4995m=1400+1600+570+430+845+2700=7545m配送量 =配送量 =步骤三 ：在节约里程表里把 4、11、 12、13、14、15、16、 8 的横列和纵列全部改成 0 得到节约里程附表 1。通过排序得到节约里程顺序附表（完整数据位于附表 2：节约里程附表 1）。节约里程附表 1：因

9、为 18-19 节约里程最大，把 18-19 连接起来，把 18-19 改为 0，得到 17-18 最大，把 17-18 连接起来，得到 17-18-19,17-18 改为 0，在这附近，所有的点的需求量 Q加起来是，所以为了使里程节约最大和配送量最大， 得把边缘的一个点放在其他路线去，根据步骤 1，只能把 20 或者 10 这两个点中的一个排在外面去。若把 10 放在左边区域去，那么 20 与 19 连接， 10 就与 21 连接，节约的里程为 L10=2500+4000=6500；若把 20 放到左边区域，那么 10 与 19 连接， 20 与 21 连接，节约的里程 L20=3985+3

10、100=7085，因为 L20>L10，所以把 20 放到左边去。得到，此时这几点的需求量 Q已经达到了，不能再与其他点连接，所以直接 17-P,10-P, 得到路线 P-P。此时节约的总里程 L3=4210+4320+3985=12515m车辆 3：P-P，总里程 =2100+2990+680+715+2100=5885m,配送量 =。步骤四 ： 在节约里程车辆 3：P-P附表 1 里面把 10、17、 18、总里程 =2100+2990+680+715+2100=5885m19 的横列和纵列都改为 0配送量 =得到节约里程附表 2，通过排序得到节约里程顺序附表 2。（完整数据位于 附

11、表 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=，不能与附近其他点连接，所以直接与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：P-7-22-21-20-P附表 2 里把 7

12、、22、21、总里程 =1800+890+695+1500+2400=7285m20 的横列和纵列改为 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

13、。车辆 5：P-5-9-6-3-P ，总里程 =1400+470+660+670+1100=4300m，配送量 =5T步骤六：在节约里程附表3 里把 5、 9、 6、 3 的横列和纵列都改为0 得到节车辆 5： P-5-9-6-3-P约里程附表4，按顺序排列得到节约里总里程 =1400+470+660+670+1100=4300m程顺序附表 4。（完配送量=5T整数据位于 附表 2：节约里程附表 4）节约里程附表 4：由表可得只有 1-2 ，连接 1-2 ，再与 P 连接得到线路 P-1-2-P 。此时节约的总里程 L6=56m。车辆 6：P-1-2-P ，总里程 =31+800+825=16

14、56m，配送量 =5T。综上：该模型车辆 6：P-1-2-P优化后的最终线路总里程 =31+800+825=1656m分别是：P-4-P P-11-12-8-P配送量 =5TP-PP-7-22-21-20-P P-5-9-6-3-P P-1-2-P 。P-4-PP-11-12-8-PP-PP-7-22-21-20-PP-5-9-6-3-PP-1-2-P 。L5+ L6=23660+12515+10915+8100+56=55246m。车辆=6辆总配送量 =+5+5+=总里程31666m总节约里程55246m车辆6 辆总配送量五、结果总结总里程L=7545+4995+5885+7285+4300

15、+1656=31666m。总节约里程 L=L2+L3+L4+利用节约里程算法进行路线优化， 结合配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离信息， 从而制定使总的车辆运输的吨公里数最小的配送方案。实验小组经过科学、 严谨的逻辑推理和计算， 得出最佳配送路线为线路分别是： P-4-P P-11-12-8-P P-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=5524

16、6m。车辆=6 辆总配送量 =+5+5+=优化后的结果路线如下如：正确合理地安排车辆的配送线路， 实现合理的线路运输， 有效地节约了运输时间，增加车辆利用率， 从而降低运输成本， 提高企业的经济效益与客户服务水平，使企业达到科学化的物流管理， 能够更好地提升企业自身竞争力。 对大部分企业来说，配送成本最低和满足客户对时间的高要求是配送中心急需解决的问题。如果可以通过比较科学的路径优化模型和算法来实现企业的人工调度和车辆安排，使得物流中心本身运作效率更高，成本控制得当， 企业的效益也会不断增加。这一研究结果体现了运筹学的思想与实际项目的有机结合， 对红旗连锁超市的货物配送的供应链优化具有现实的指导意义。 在物流快速发展大背景下， 红旗连锁要充分利用物流理论， 与实践相结合，同时考虑到时代赋予产品的特殊意义，积极拓展自身的经营方式， 与客户保持积极的合作， 给企业注入新的血液和