物流规划课程设计 第 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）初始聚类中心的位置，原算法是随机的，为提高聚类的效果，优化聚类的结果，依照密度的分布，对初始聚类中心优化生成。以每个零售户的地理数据点为圆心，以数据库中零售户地理信息表中所有地理数据之间距离的平均值为半径