国大便利店路线规划问题 - 图文

物流规划课程设计 第 1 页 共 16 页

1 前言

随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域”。配送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。

配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因此对于配送问题的研究可分为对 “配”和“送”两方面的研究。“配”主要为配送中心选址问题，“送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。由于选址的外部因素（经济，基础设施，环境等）及内部因素（企业战略，劳动力成本和素质等）的影响，单纯考虑距离问题的选址是不合理的，因此在本文中不对“配”进行研究，主要对“送”进行研究。

配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。

配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合的理配送路线，对企业和社会都具有很重要的意义。

对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 。

本文将以国大商贸连锁有限公司当前的配送线路的优化问题作为研究对象，

物流规划课程设计 第 2 页 共 16 页

对石家庄市内连锁便利店的需求量及运距进行分析计算，建立VRP数学模型，运用聚类算法和单回路法对建立的模型进行求解，对国大连锁的配送路线进行优化。致力于为该公司提供较合理的配送方案，以期减少配送里程，降低物流运输成本，提高该公司物流运作效率，客户服务质量和整体竞争力。

物流规划课程设计 第 3 页 共 16 页

2 问题的提出与描述

2.1国大连锁商贸有限公司的配送现状

河北国大连锁商业有限公司是河北省较早成立并实行规范化管理的现代化商业连锁企业。总部拥有先进的商业MIS系统、物流配送系统、视觉识别系统、专业培训兼管理系统。2002年通过ISO9001-2000国际质量管理体系认证，“36524便利店”商标经国家商标局注册，曾连续三年跻身全国连锁百强企业之列。公司以便利店为核心业态，经过多年的运作，现有便利店300多家，开省内24小时营业之先河，并建立了电话网、INT网、人力营销网、店铺网，在省内首创了“四网并行”的商业模式。该公司是在“四网并行”的基础上，结合企业实际，提出了信息驱动发展战略

配送中心的配送对象是分布于石家庄的加盟国大连锁商贸有限公司的便利店，这些店基本覆盖了二环的大部分地区，也有部分二环以外部分，这些便利店的需求在时间、数量上比较确定，一般采用自有车辆每天对这些店进行配送，配送时间一般选择在车流量较小的时段，大部分是选择在晚上。配送车辆为东方小霸王厢式车，由于所配送货物一般为日用品和食品，车辆满载一般为一吨。各便利店需求量比较稳定一般为0.1—0.3吨之间，因为便利店店面较小，储藏间也较小，因此需要每天配送。每天配送的电子系统根据各店的销售情况自动向配送中心订货，生成配货拣货单，配送中心根据配货单向各店进行定时配送。每台配送车辆配送的超市却不是固定的，而且对各个超市进行配送时的路线选择不固定，这样就有很大的随机性，造成时间和费用的浪费。

2.2 提出问题

我们组针对国大便利店物流配送线路有很大的随机性，造成了人力物力时间的浪费这一现象，对其配送线路进行科学的优化和整合，达到降低成本的目的。

通过对国大便利店的调查，我们得到： 已知条件

1.所有零售便利店的集合N为已知，N=1、2、3、、、32，为便利店所在地 2、从配送中心出发的配送车辆，经过所有需要配送的便利店，并把货物卸下，并返回配送中心，配送车辆所经过的零售户的顺序称为路线。

物流规划课程设计 第 4 页 共 16 页

3、配送中心配送车辆统一，按载重量为1吨。

4、便利店数量、地理位置为已知，且每一个便利店的需求量为已知。 5、各零售点之间的距离为已知。

目标 车辆应用台数、各车行走的路径，使总的距离最少，用车较少。 约束条件

1、配送车辆的车载辆，一辆车的载重辆为一吨。 2、地理上相对集中的零售户由一辆送货车进行送货。 3、送货车辆按每天的订单数量出库。 4、配送车辆尽可能满载

5、每天送货路线的工作线路基本均衡 解决思路

以聚类算法为基础，以车载量和路线最短为约束条件，运用spss软件的K—均值聚类分析形成聚类区域，最后用单回路运输—TSP模型的最近插入法进行配送路线的优化。

物流规划课程设计 第 5 页 共 16 页

3 方法介绍

3.1聚类算法简介

聚类算法是一种新兴的多元统计方法，是当代分类学与多元分析的结合。聚类分析是将 分类对象置于一个多维空间中，按照其空间亲疏进行分类。通俗地讲，聚类分析就是根据事 物彼此不同的属性进行辨认，将具有相似属性的事物聚为一类，使得同一类事物具有高度的 相似性。相似或不相似的度量基于数据对象的描述的取值来确定的，通常是利用距离进行描 述，常见的聚类分析方法有(1)切割的聚类方法。代表算法有：K-MEANS算法、ISODATA 算法 等。(2)层次的聚类方法。代表算法 CURE 算法。(3)基于密度的聚类。代表算法 DBSCAN算法 等。(4)基于网格的聚类。代表算法 CLIQUE 算法等。

零售行业配送线路优化需要对零售户的空间地理数据进行聚类分析，由于数据量较大，需要一个效率高的算法，而且 K-MEANS 算法 适合于数据型数据，对数据输入顺序不敏感等特点，为比较适合的一种算法。 K-MEANS 聚类算法的基本思路是：首先从 n 个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到所有中心都不在变化为止。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

3.2 K-MEANS 聚类法

K-MEANS 聚类算法有两个关键问题需要解决，一是初始聚类中心的个数，二是初始聚类中心的位置。

（1）初始聚类中心的个数，也是配送区域划分的个数，也就是为这些配送区域送货的送货量配送车辆的台数。即 k=配送车辆的台数 车载量+1，加1 主要考虑车辆配装时不可能完全满载。

（2）初始聚类中心的位置，原算法是随机的，为提高聚类的效果，优化聚类的结果，依照密度的分布，对初始聚类中心优化生成。以每个零售户的地理数据点为圆心，以数据库中零售户地理信息表中所有地理数据之间距离的平均值为半径

物流规划课程设计 第 11 页 共 16 页

图4-3 聚类分布图

由spss软件进行聚类分析得到聚类中心的坐标位置为下表4-5

表4-5 最终聚类中心

最终聚类中心 x轴 y轴 1 4.0 8.9 2 9.0 8.0 3 12.5 6.4 聚类 4 5.0 2.4 5 11.6 3.3 6 2.9 5.7 7 7.9 4.7 4.2对聚类结果进行调整

聚类完成后，还应根据车载量这个约束条件对聚类结果进行判断调整。

Step1：计算每一个聚类内的便利店需求量的总和；

Step2：判断每一聚类内便利店的需求量的总和是否超过车载量； 如果未超过，说明符合条件。

如果超过车载量，选择该聚类中距离质心最远的点，将其拟归入距离其他类质心距离最近的类，归入某一类前，还必须判断如归入后该类的便利店需求量的总和是否小于车载量。如果小于，即将该数据归入该类，否则，选择欧式距离再次之的类作为拟归入的类，同样判断该类便利店需求量是否小于车载量是否小于车载量，如果小于则归，否则选择距离再次之的。

Step3：当所有的类零售户订单量总和都小于车载量时，暂告一段落。 调整完毕以后，每一类的便利店地理位置相对集中，且订单量总量小于车载

物流规划课程设计 第 12 页 共 16 页

重量。

聚类1：总需求量Q1=0.15+0.18+0.22+0.2+0.23=0.98<车载量 聚类2：总需求量Q2=0.25+0.27+0.13+0.22=0.87<车载量 聚类3：总需求量Q3=0.22+0.23+0.17+0.26=0.88<车载量 聚类4：总需求量Q4=0.28+0.19+0.18=0.65<车载量 聚类5：总需求量Q5=0.12+0.27+0.16+0.11=0.66<车载量 聚类6：总需求量Q6=0.18+0.25+0.25+0.29+0.22=1.19>车载量 聚类7：总需求量Q7=0.15+0.2+0.16+0.2+0.18+0.15+0.16=1.2>车载量

聚类6需求量总和超过车载量，选取聚类6中距离其质心最远的点为便利

店30，其需求量为0.25吨，将其归入距离其他其他聚类质心距离最近的类，为聚类4，计算将便利店30归入聚类4中后，聚类4的需求总量为0.9吨，小于车载量，所以聚类4为11、12、28、30:；

聚类7需求量总和超过车载量，选取聚类7中距离其质心最远的点为便利店23，其需求量为0.15吨，将其归入距离其他其他聚类质心距离最近的类，为聚类5，计算便利店23归入聚类5中后，聚类5的需求总量为0.81吨，小于车载量，但聚类7去掉点23后总需求量仍大于车载量，所以继续选取聚类7中距离其质心最远的点为便利店20，其需求量为0.18吨，将其归入距离其他其他聚类质心距离最近的类，为聚类5，计算便利店20归入聚类5中后，聚类5的需求总量为0.99吨，小于总车载量，同时此时聚类7的总需求量为0.87吨，也小于车载量，所以聚类5为20、22、23、24、25、26，聚类7为7、10、15、16、28。

对聚类进行调整后，新得到的聚类如下表4-6：

表4-6 改进后的聚类中心

聚类 1 2 3 4 5 6 7 所包含1、2、3、8、9、13、17、18、11、12、20、22、5、6、31、7、10、的便利4、29 14 19、21 27、30 23、24、32 15、16、店 25、26 28 4.3 对得到的聚类区域进行路线规划

首先对聚类1运用最近插入法：

物流规划课程设计 第 13 页 共 16 页

聚类1中各个便利店之间的距离为：

表4-7 聚类1各便利店的距离

便利店 v1 v2 v3 v4 v29 v1 v2 2.3 V3 1.6 0.9 v4 2.6 1.8 1.3 V29 1.3 2.5 1.5 1.8 从v2出发的所有路径的大小，c2/3=0.9为最小，这样，就由节点v2、v3构成一个子回路，T=（v2，v3）。

然后考虑剩下节点v1、v4、v29到v2和v3中某一个节点最小的距离：

c3/4=1.3，由于对称性，无论将4插到2和3之间往返路径中，结果都是一样的，构成一个新的子回路T=（v2，v3，v4，v2）。

接着考虑剩下节点v1、v29到v2、v3、v4中某一个节点的最小距离c3/29=1.5，节点v29有3个位置可以插入。现在分析将v29插到那里合适。 （1）插到（3，4）间 距离=1.5+1.8-1.3=2 （2）插到（2，3）间 距离=2.5+1.5-0.9=3.1 （3）插到（2，4）间 距离=2.5+1.8-1.8=2.5

比较上面3种情况的增量，插到（3，4）之间的增量最小，所以应将v29加入到（3，4）间，结果为：T=（v2，v3，v29，v4，v2）

重复上面的步骤，再将节点v1加入到回路中，就可以得到最近插入法所得的解，

T=（v2，v3，v1，v29，v4，v2） 这就是行驶最短路径的相对最优解。 对聚类2用最近插入法，同上，得最优路径。 T=（v8，v14，v13，v9，v8）

对聚类3用最近插入法，同上，得最优路径。 T=（v17，v18，v21，v19，17）

对聚类4用最近插入法，同上，得最优路径。 T=（v11，v30，v12，v27，v11）

物流规划课程设计 第 14 页 共 16 页

对聚类5用最近插入法，同上，得最优路径。 T=（v20，v22，v24，v26，v25，v23，v20） 对聚类6用最近插入法，同上，得最优路径。 T=（v5，v6，v32，v31，v5）

对聚类7用最近插入法，同上，得最优路径。 T=(v7，v15，v16，v28，v10，v7) 最终优化路线如表4-8,

表4-8 最终优化路线

聚类1 聚类2 聚类3 聚类4 聚类5 聚类6 聚类7 根据上表绘制最终优化线路图4-4。

优化后路线 2—3—1—29—4 8—14—13—9 17—18—21—19 11—30—12—27 20—22—24—26—25—23 5—6—32—31 7—15—16—28—10

图4-4 最终优化线路图

物流规划课程设计 第 15 页 共 16 页

5 小结

本文对国大便利店配送线路的优化问题提出了一个比较完整的解决方案，在实用方面实现了车辆的合理调度，减少了不必要的出车次数，提高了车辆的满载率，实现了配送车辆送货线路的最优化生成。基本上完成了本次课程设计的任务。在科学方面我们对国大配送路线进行了层层分析、细化，减少了问题的规模，得到可行解，具有可行性；在配送区域划分中采用了K均值聚类法，并对初始聚类点的确定方法进行优化改进，使聚类结果更加合理，效率更高；在配送区域划分时加上车载量限制条件，使最终结果真正有使用价值。

在此次课程设计中，我们学会了K均值聚类法及其应用，复习并巩固应用了最近插入法，并学习了spss软件的用法，同时也感到一些看似简单的问题在实际运用中还是会遇到很多困难，如数据的收集，聚类法在实际问题上的应用等。我们学习的理论在实际运用中有很大的局限性，在应用理论时，必须紧密联系实际，在基本理论的基础上突破陈规，最终使得理论和实际完美结合。

通过这次课程设计使我们认识到，一个人的力量是有限的，思维方式也存在很大的局限性，只有通过团队的合作才能更全面地去发现问题、思考问题、解决实际问题，得到的最终方案才会更具实际意义。同时，感谢李老师和靳老师对我们组的悉心指导，使我们的思路更加开阔，最终的方案也更加完善。

物流规划课程设计 第 16 页 共 16 页

参考文献

1. 董千里.物流工程，大连:东北财经大学出版社，2007。 2．蒋长兵.物流系统与物流工程，北京:中国物出版社资，2007。 3. 刘昌祺.物流配送中心系统选址选择与设计，机械工业出版社，2006。 4. 毛良伟.物流系统规划与方法，机械工业出版社，2006。 5. 蔡临宁.物流系统规划-建模及实例分析，机械工业出版社，2008 6．张可明.物流系统分析．北京:清华大学出版社．2004

7. 孙焰.现代物流管理技术—建模理论及算法设计.上海:同济大学出版社.2004 8. 张晓川.物流配送系统规划.北京:水利水电出版社.2007

物流规划课程设计 第 16 页 共 16 页

参考文献

1. 董千里.物流工程，大连:东北财经大学出版社，2007。 2．蒋长兵.物流系统与物流工程，北京:中国物出版社资，2007。 3. 刘昌祺.物流配送中心系统选址选择与设计，机械工业出版社，2006。 4. 毛良伟.物流系统规划与方法，机械工业出版社，2006。 5. 蔡临宁.物流系统规划-建模及实例分析，机械工业出版社，2008 6．张可明.物流系统分析．北京:清华大学出版社．2004

7. 孙焰.现代物流管理技术—建模理论及算法设计.上海:同济大学出版社.2004 8. 张晓川.物流配送系统规划.北京:水利水电出版社.2007

本文来源：https://www.bwwdw.com/article/u0k.html