序言随着社会主义市场经济的不断发展，作为“第三收益源泉”的货运对经济活动的影响日渐显著，导致了人们越来越多的注重，成为当前“最重要的竞争领域”。配送是联接生产与消费之间的一种中介服务。它是指按顾客(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在货运中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收件人的货运活动。配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因而对于配送问题的研究可分为对和“送”两方面的研究。“配”主要为配送中心选址问题，“送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。因为选址的外部诱因（经济，基础设施，环境等）及内部诱因（企业战略，劳动力成本和素养等）的影响，单纯考虑距离问题的选址是不合理的，因而在本文中不对“配”进行研究，主要对“送”进行研究。配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速率、成本、效益影响很大。设计合理、高效的配送路线方案，除了可以降低配送时间，减少作业成本，提升企业的效益，但是可以更好地为顾客服务，提升顾客的满意度，维护企业良好的形象。
配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使汽车有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，汽车容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用汽车尽可能少）。但配送作业情况复杂多变，不仅剩在配送点多、货物种类多、道路网复杂、路况多变等情况，但是运输服务地区内需求网点分布也不均匀便利店送货，致使线路优化问题是一个无确定解方程困局，须要启发算法去求得近似最优解。配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合的理配送路线，对企业和社会都具有很重要的意义。对社会来说，它可以节约运输汽车，降低汽车空载率，增加了社会货运成本，对其他企业尤其是生产企业具有重要意义。与此同时，能够减轻交通紧张状况，降低噪音、尾气排放等运输污染，对民生和环境也有不容忽略的作用本文将以国大工贸连锁有限公司当前的配送线路的优化问题作为研究对象，货运规划课程设计对广州市内连锁便利店的需求量及运距进行剖析估算，构建VRP物理模型，运用降维算法和单回路法对完善的模型进行求解，对国大连锁的配送路线进行优化。旨在于为该公司提供较合理的配送方案，以期降低配送里程，增加货运运输成本，提升该公司货运运作效率，顾客服务质量和整体竞争力。
货运规划课程设计问题的提出与描述2.1国大连锁工贸有限公司的配送现况山东国大连锁商业有限公司是陕西省较早创立并推行规范化管理的现代化商业连锁企业。总部拥有先进的商业MIS系统、物流配送系统、视觉辨识系统、专业培训参予理系统。2002年通过-2000国际质量管理体系认证，“36524便利店”商标经国家商标局注册，曾连续两年荣登全省连锁百强企业之列。公司以便利店为核心业态，经过多年的运作，现有便利店300多家，开省内24小时营业之先河，并完善了电话网、INT网、人力营销网、店铺网，在省内首创了“四网并行”的商业模式。该公司是在“四网并行”的基础上，结合企业实际，提出了信息驱动发展战略配送中心的配送对象是分布于广州的加盟国大连锁工贸有限公司的便利店，这种店基本覆盖了内环的大部份地区，也有部份内环以外部份，这种便利店的需求在时间、数量上比较确定，通常采用自有汽车每晚对这种店进行配送，配送时间通常选择在车流量较小的时段，大部份是选择在凌晨。配送汽车为东方小霸王厢式车，因为所配送货物通常为日用具和乳品，汽车满载通常为一吨。各便利店需求量比较稳定通常为0.1—0.3吨之间，由于便利店门店较小，储存间也较小，因而须要每晚配送。
每晚配送的电子系统按照各店的销售情况自动向配送中心订货，生成配货拣货单，配送中心依据配货双向各店进行定时配送。每台配送汽车配送的商场却不是固定的，并且对各个商场进行配送时的路线选择不固定，这样就有很大的随机性，导致时间和费用的浪费。2.2提出问题我们组针对国大便利店货运配送线路有很大的随机性，导致了人力物力时间的浪费这一现象，对其配送线路进行科学的优化和整合，达到减少成本的目的。通过对国大便利店的调查，我们得到：已知条件1.所有零售便利店的集合N为已知，N=1、2、3、、、32，为便利店所在地2、从配送中心出发的配送汽车，经过所有须要配送的便利店，并把货物卸下，并返回配送中心，配送汽车所经过的零售户的次序称为路线。货运规划课程设计4、便利店数目、地理位置为已知，且每一个便利店的需求量为已知。5、各零售点之间的距离为已知。目标汽车应用台数、各车行走的路径，使总的距离最少，用车较少。约束条件1、配送汽车的车载辆，一辆车的载重辆为一吨。2、地理上相对集中的零售户由一辆送货车进行送货。3、送货汽车按每晚的订单数目领料。4、配送汽车尽可能满载5、每天送货路线的工作线路基本均衡解决思路以降维算法为基础，以车载量和路线最短为约束条件，运用spss软件的K—均值降维剖析产生降维区域，最后用单回路运输—TSP模型的近来插入法进行配送路线的优化。
货运规划课程设计方式介绍3.1降维算法简介降维算法是一种新兴的多元统计方式，是当代分类学与多元剖析的结合。降维剖析是将分类对象放在一个多维空间中，根据其空间尊卑进行分类。浅显地讲，降维剖析就是按照事物彼此不同的属性进行鉴别，将具有相像属性的事物聚为一类，促使同一类事物具有高度的相像性。相像或不相像的测度基于数据对象的描述的取值来确定的，一般是借助距离进行描述，常见的降维剖析方式有(1)切割的降维方式。代表算法有：K-MEANS算法、算法次的降维方式。代表算法CURE算法。(3)基于密度的降维。代表算法算法等。(4)基于网格的降维。代表算法算法等。零售行业配送线路优化须要对零售户的空间地理数据进行降维剖析，因为数据量较大，须要一个效率高的算法，但是K-MEANS算法适宜于数据型数据，对数据输入次序不敏感等特征，为比较适宜的一种算法。K-MEANS降维算法的基本思路是：首先从个对象作为初始降维中心；而对于所剩下其它对象，则按照它们与那些降维中心的相像度（距离），分别将它们分配给与其最相像的（降维中心所代表的）降维；之后再估算每位所获新降维的降维中心（该降维中所有对象的均值）；不断重复这一过程直至所有中心都不在变化为止。
k个降维具有以下特性：各降维本身尽可能的紧凑，而各降维之间尽可能的分开。3.2K--MEANS降维算法有两个关键问题须要解决，一是初始降维中心的个数，二是初始降维中心的位置。（1）初始降维中心的个数，也是配送区域界定的个数，也就是为那些配送区域送货的送货量配送汽车的台数。即k=配送汽车的台数车载量+1，加主要考虑汽车配装时不可能完全满载。（2）初始降维中心的位置，原算法是随机的，为提升降维的疗效，优化降维的结果，根据密度的分布，对初始降维中心优化生成。以每位零售户的地理数据点为圆心，以数据库中零售户地理信息表中所有地理数据之宽度离的平均值为直径货运规划课程设计means降维算法须要的初始中心就由以上算法生成，而无需用户进行事先指定.整个过程包括以下几个基本步骤：1）将数据库中的每位点都看成一个类，估算所有点之间的距离，生成距离矩阵，两点之间欧式距离为：2）选定2个整数，通常R2=2*R1，其中R1为数据库中所有点之宽度离的平均值，3）以每位点为圆心，以R1为直径作圆便利店送货，估算落在每位圆内的点的数量，即样本密度；如求R1为直径的圆内，其判定方的样本密度，否则判定下一点，重复第二步。
4）将样本密度按从大到小的次序排列，取密度最大者作为第一个降维中心Z1，选择密度次大的数据点与第一凝聚点Z1之宽度离小于R2，即作为第二个凝聚点Z2，否则继续判断下一密度最大者，若下一密度最大者的点与上面若干个凝聚点之宽度离均小于R2，则将之作为又一新的凝聚点，这么反复迭代直至要求降维的数量K。3.3单回路运输—TSP模型的近来插入法单回路运输问题是指在路线优化中，设存在节点集合D，选择一条合适的路径遍历所有的节点，但是要求闭合。单回路运输模型在运输决策中，主要用于单一汽车的路径安排。目的在于在该汽车遍历所有用户的同时，达到所行驶距离最TSP模型是单回路运输问题的最为典型的一个模型，它的全称是货运规划课程设计(TSP),英文称作旅行商问题它是一个典型的NP—Hard问题，对于大规模的线路优化问题，未能获得最优解，只有通过启发式算法获得近优解。TSP模型可以如下描述:在给出的一个n定点网路（有向或无向），要求找出一个包含所有n个定点的具有最小花费的支路。任何一个包含网路中所有n点的支路被叫做一个回路。
在旅行商问题中，要设法找到一条最小花费的回路。既然回路是包含所有顶点的一个循环，故可以把任意一个点作为起点（因而也是终点），这也是TSP模型的一个特性。近来插入法是和等人在1977提出的另外一种用于解决TSP问题的算法，可以找到相对比较满意的解。近来插入法由4步来完成：之间，用两条新弧（i，k）（k，j）取代原先的弧（i，j），并将节点重复步骤（2）（3），直至所有的节点都加入到子回路中。货运规划课程设计国大便利店配送路线优化据了解，国大36524便利店在广州城区共有304店，我们依照其需求量及各门店地理位置共取32个主要门店来做线路优化，各便利店分布如右图4-1图4-1长春国大便利店家要店铺分布图4.1对国大便利店进行降维剖析构建直角座标系如图4-2确定各个便利店的具体座标位置如表4-1。图4-2便利店直角座标系货运规划课程设计表4-1国大便利店具体座标位置101112131415165.34.44.63.33.86.27.88.65.84.35.110.49.48.97.99.79.49.07.77.25.16.08.09.44.82.92.97.67.15.33.41718192021222324252627282930313211.51311.99.913.6119.112.310.712.35.67.22.93.91.22.57.07.06.05.15.44.52.93.42.82.71.45.18.54.06.55.5确定配送汽车台数k=送货量/车载量+1，调查得国大便利店用车载重量为吨，调查各个便利店的平均需求量为下表4-2。
表4-2国大各便利店的日平均需求量编号需求编号需求编号需求编号需求0.27170.22250.160.18100.2180.23260.110.22110.28190.17270.180.20120.19200.18280.160.18130.13210.26290.230.25140.22220.12300.250.15150.16230.15310.290.25160.2240.27320.22可知各便利店日平均需求量总和为Q=6.43吨，所以配送汽车台数k=6.43/1+1=7.43，约为K=7运用上面所述K均值降维法步骤借助spss软件进行K均值降维剖析，可得结果为表4-3。货运规划课程设计表4-3降维成员及距离降维成员编号距离编号1.337171.37118.386191.288201.582211.026222.033231.250241.447251.034102.06226.97411.860271.16612.51028.792131.415291.19514.989301.918151.225311.912161.25832.468整理表4-3可得便利店的降维结果表4-4表4-4降维结果所包含的便利4、298、9、13、1417、18、19、2111、12、2722、24、25、265、6、30、31、327、10、15、16、20、23、28依据表4-4在图中画出降维分布图4-3货运规划课程设计图4-3降维分布图由spss软件进行降维剖析得到降维中心的座标位置为下表4-5表4-5最终降维中心最终降维中心4.09.012.55.011.62.97.98.98.06.42.43.35.74.74.2对降维结果进行调整降维完成后，还应按照车载量这个约束条件对降维结果进行判别调整。
Step1：估算每一个降维内的便利店需求量的总和；Step2：判定每一降维内便利店的需求量的总和是否超过车载量；倘若未超过，说明符合条件。若果超过车载量，选择该降维中距离刚体最远的点，将其拟划入距离其他类刚体距离近来的类，划入某一类前，还必须判定如划入后该类的便利店需求量的总和是否大于车载量。假如大于，正式该数据划入该类，否则，选择欧式距离再次之的类作为拟划入的类，同样判定该类便利店需求量是否大于车载量是否大于车载量，假如大于则归，否则选择距离再度之的。Step3：当所有的类零售户订单量总和都大于车载量时，暂告一段落。调整完毕之后，每一类的便利店地理位置相对集中，且订单量总数大于车载货运规划课程设计重量。降维1：总需求量Q1=0.15+0.18+0.22+0.2+0.23=0.98
免责声明：部分文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性，如本站文章和转稿涉及版权等问题，请作者在及时联系本站，我们会尽快为您处理。
