货物配送问题的研究1资料.doc

货物配送问题摘 要针对货物配送问题，本文在深入研究货物配送过程中的配送路线、连锁店的增设和生产基地的增建问题的基础上，对所提供的数据进行了分析和处理，建立了与各问题相关的数学模型，制订了相应的优化方案。针对问题一，本文利用作出了全省各个城镇位置的分布图，再用算法求得各个城镇间的最短距离，从而得出2家生产基地到23家连锁店的最短距离，最后用优化模型得到2家生产基地所供货的连锁店。针对问题二，本文详细探讨了各城镇对鲜猪肉的需求特征，利用对数据进行处理，并进行回归分析，建立二次回归模型，通过编程确定出二次回归曲线方程，并绘出了拟合曲线。由曲线预测得到2016年4月时，全省鲜猪肉需求量出现峰值，再对各城镇月需求建立回归模型，得出2016年4月各城镇猪肉需求量，需求量处于前5位的城镇为120号、31号、63号、106号和68号城镇，处于后5位的城镇为102号、84号、30号、74号和129号城镇。针对问题三，本文通过建立整数规划模型，确立约束条件，运用软件进行编程求解，得出使全省的总销售量达到最大的最佳增设方案（共增设18家连锁店）。针对问题四，由于各连锁店需求一定，本文也将其转化为最短路线求解问题。根据问题一得到的矩阵，运用软件编程求出各连锁店到各生产基地的最短距离矩阵，建立线性规划模型，确定出了最佳增设方案。针对问题五，分别深入讨论了货车运输路线和装卸方式对车辆调运方案的不同影响。首先，通过划片的形式，根据运输时间最短的原则找出了最优工作路线；然后，通过分析两种不同的装卸方式的优缺点，以所用货车数量最少为前提，选择最优装卸方案。二者相结合，得出货车的最小需求量为153辆。 本文建立的模型具有一定的合理性，准确性和可行性，在一般条件下具有参考价值。关键字 算法；整数规划；回归模型；优化模型 1 问题重述梦想连锁是一家肉类食品加工与销售公司，主营：鲜猪肉。公司在全省县级及以上城镇设立销售连锁店。全省县级及以上城镇地理位置及道路连接见数据文件：全省交通网络资料.xlsx问题：1、目前公司现有2个生产基地、23家销售连锁店，生产基地设在120号和63号城镇，为23家连锁店提供鲜猪肉，连锁店的日销售量见附录1。若运输成本为0.45元/吨公里，请你为公司设计生产与配送方案，使运输成本最低。2、公司收集了近5年全省各城镇的鲜猪肉月度需求数据（文件：各城镇月度需求数据.txt）请你分析各城镇需求特征，并预测未来数年，何时全省鲜猪肉需求达到峰值，达到峰值时需求达到前5位和后5位的城镇是那些？3、通过广告宣传等手段，未来几年公司在全省的市场占有率可增至3成左右（各城镇对公司产品每日需求预测数据见文件：公司未来各城镇每日需求预测资料.txt），调查还发现，公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量与销售量相同，若在不足10公里的其它城镇的销售连锁店购买，则这一部分需求量只能实现一半（成为公司产品销售量，由于距离的原因，另一半需求转向购买其它公司或个体工商户的产品），而在超过10公里的其它城镇的销售连锁店购买，销售量只能达到需求量的三成。于是，公司决定在各城镇增设销售连锁店，基于现有条件、成本等的考虑，原有的23家销售连锁店销售能力可在现有销售量的基础上上浮20%，增设的销售连锁店销售能力控制在每日20吨至40吨内，并且要求增设的销售连锁店的销售量必须达到销售能力的下限。同一城镇可设立多个销售连锁店。请你为公司设计增设销售连锁店方案，使全省销售量达到最大。4、在增设销售连锁店的基础上，公司决定增加生产基地，位址设立在城镇所在地，每日产品生产必须达到250吨以上，在生产与销售各环节不能有产品积压。请你为公司设计生产基地增设方案，使运输成本最低。5、公司产品若采用载重1.5吨的小货车从生产基地运往销售连锁店，小货车在高速公路上限速100公里/小时（高速公路见附录2），在普通公路上限速60公里/小时，销售连锁店需要的产品必须当日送达。假设：每日车辆使用时间不超过8小时，小货车装满或卸完1.5吨的货物均需要半小时，本市运输车辆行驶时间可忽略不计。在公司增设销售连锁店、增加生产基地后，为完成每日运输任务，请你为公司确定小货车的最小需求量，及各车辆的调运方案。2 模型假设1. 每辆车的运输能力相同2. 运输过程只与运输距离有关，不受其它因素影响3. 所确定的最短路线均为可行路线4. 每个连锁店由一个特定生产基地供货3 符号说明序号符号符号说明1月数2全省各城镇的鲜猪肉月需求量3运输成本4运量5运输距离6新增的所有连锁店的销售能力723家连锁店现有的销售能力8未来号城镇的需求9不足10公里的城镇的连锁店的销售量10超过10公里的城镇的连锁店的 销售量1123家连锁店原有的销售能力12基地到连锁店之间的最短距离13基地中到连锁店的最短距离14城镇连锁店连锁店的需求量15新增连锁店生产基地后的最低总运费16货车行驶完所用时间17货车沿普通公路送货路程18货车沿高速公路送货路程19货车在普通公路上的行驶速度20货车在高速公路上的行驶速度21某条路线上所需货车数量22某条路上所有连锁店的货物需求总量23货车一天所能运行的时间24货车载重量上限25第个连锁店的货物需求量26货车从第个连锁店到其供货生产基地4 模型的建立与求解4.1 问题一4.1.1 问题一的分析 考虑到每个连锁店的日销量和每辆车的运输成本都是确定的并且各生产基地必须满足其供货连锁店的需求，因此该题可以转化为求各生产基地到其供货连锁店的总路线最短问题。这里拟将城镇的面积对连锁店与生产基地之间的距离的影响忽略不计，则可将各城镇看做质点，所以120号城镇和63号城镇中连锁店和生产基地之间的距离可看做零。由于两城镇之间存在有无直接路线的问题，尝试通过软件对全省交通网络资料进行处理，将其转换成矩阵形式，运用算法得出任意两直接相连的城镇之间的距离矩阵，按照最短路线优先的原则，挑选出各生产基地的供货连锁店，4.1.1 问题一模型的建立4.1.1.1模型的建立据运输成本的计算公式： 可知要求运输成本最低，只需求运输距离最短即可。此题转化为最短路径求解问题，由于算法是一种动态规划，稠密图效果最佳，边权可正可负，且此算法简单有效，所以本文选用算法模型解决此类问题。4.1.1.2模型理论依据核心思想: 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵开始，递归地进行次更新，即由矩阵，按一个公式，构造出矩阵；又用同样的公式由构造出；.；最后又用同样的公式由构造出矩阵。矩阵的行列元素便是号顶点到号顶点的最短路径长度，称为图的距离矩阵，同时引入一个后继结点矩阵来记录两点间的最短路径。采用松弛技术，对在和之间的所有其它点进行一次松弛，时间复杂度为；其状态方程为：表示到的最短距离，是穷举的断点，初始值通常为，如果道路不通，需特殊处理。算法过程： 从任意一条单边路径开始，所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 对于每一对顶点和，看看是否存在一个顶点使得从到再到比已知的路径更短。若是，则更新它。把图用邻接矩阵表示出来，如果从到有路可达，则，表示该路的长度；否则。定义一个矩阵用来记录所插入点的信息，表示从到需要经过的点，初始化。把各个顶点插入图中，比较插入点后的距离与原来的距离，若的值变小，则。在中包含有两点之间最短道路的信息，而在中则包含了最短路径信息。4.1.2 问题一模型的求解 为更加直观的表现出各城镇的位置，根据所给全省交通网络资料，通过软件画出了全省交通网络连接图，见图1。程序见附录一。图1 全省交通网络图（字号） 运用软件将全省交通网络数据转换成矩阵形式，程序见附录二，据模型理论依据可知，两城镇之间没有直接路径时，最短路径为无穷大，通过分析题意，此处可用1000代替无穷大，对程序的运行没有影响，运用算法求出一个的矩阵，用以表示任意两城镇之间的最短距离，程序见附录三。根据所求矩阵，比较各连锁店到两生产基地的距离，根据最短路线优先原则即离谁近，由谁供货的原则确定出了各生产基地的供货方案，见表。表1 运输成本最小配送方案（字号）生产基地连锁店所在城镇最短距离/公里日销售量/千克运费/元城镇63210663.7382231095.662295514161.7292582573114744891.1199881136151.1911503782.61235651334119.5445124.2606431442110.589489472.1821291594170.1712773978.11163451914572.85396531299.9244732116103.6414783689.449554221235.111808141.5772595城镇120431114.66239471235.593359610108.368481413.55052276519.0915570133.75408587928.1738759491.32846351227135.19265563.2656751611179.156103492.00860251724128.943251188.6327732022168.956375484.675312523647.3118406.05268注：3号和18号连锁店在63号城镇，1号和10号连锁店在120号城镇，则运费忽略不计。表1说明位于63号城镇的生产基地为2号、3号、5号、9号、11号、13号、14号、15号、18号、19号、21号、22号12家连锁店配送货物；位于120号城镇的生产基地为1号、4号、6号、7号、8号、10号、12号、16号、17号、20号、23号11家连锁店配送货物，此时该公司的运费达到最低为10540.8935元。运用软件通过编程得到配送路线，见图2.程序见附录四。图2 最优配送路线图4.2 问题二4.2.1 问题二的分析考虑到要求何时全省鲜猪肉需求达到最大量，我们认为可将问题转化为求极值问题，打算对其进行回归分析，建立回归曲线模型，此回归曲线的极值即为题目中所需求的量。由于所给各城镇月度需求数据量较大，且据题目要求需求出各城镇的年需求量，所以拟用对其进行处理，并欲利用软件画出散点图，初步确定出全省各城镇对鲜猪肉的大致需求特征，然后进行回归模拟，进一步确定回归曲线方程，从而据该方程预测出全省鲜猪肉需求量达到峰值的时间，和达到峰值时需求达到前5位和后5位的城镇。4.2.2 问题二模型的建立4.2.2.1 数据处理与分析对于问题二，根据题目中所给出的近5年全省各城镇的鲜猪肉月度需求量数据，运用对其进行处理，求出近5年全省各城镇的鲜猪肉年需求量，结果见表2。表2 近五年全省各城镇的鲜猪肉年需求量年份2008年月份1月2月3月4月5月6月7月8月9月10月11月12月销售量/千吨10.71790810.61166610.78084510.68848110.93088210.93058310.87258310.79742910.90047211.08689411.05319211.052373年份2009年月份1月2月3月4月5月6月7月8月9月10月11月12月销售量/千吨11.00660610.97142211.07651311.21957111.15606111.2362411.27067411.34108211.41587611.37306811.25069811.336254年份2010年月份1月2月3月4月5月6月7月8月9月10月11月12月销售量/千吨11.41135611.47149711.48761711.21957111.15606111.2362411.27067411.34108211.41587611.37306811.47061611.699121年份2011年月份1月2月3月4月5月6月7月8月9月10月11月12月销售量/千吨11.61393711.68773811.670011.74841511.73199711.63703711.80059211.79074611.79074611.91985111.71810811.943359年份2012年月份1月2月3月4月5月6月7月8月9月10月11月12月销售量/千吨11.77546411.81554811.88726411.7563212.04001212.06513311.84564811.84564811.96753511.86085212.01683811.832173 由表2可以清晰的得知近五年全省各城镇的鲜猪肉的年需求量，但难以看出各城镇的需求特征，为更加直观的得到各城镇的需求变化趋势特点，本文运用软件，据表2数据画出了近五年全省各城镇的鲜猪肉年需求量的散点图，结果见图3。程序见附录五。图3 近5年全省各城镇的鲜猪肉需求量图3表明近5年全省各城镇的鲜猪肉需求量大致呈现出波动增长的趋势，但是增长幅度逐渐减小，最后几乎呈水平增长趋势。4.2.2.2 模型的建立通过对数据进行处理和分析，联系实际情况可知全省的需求量不会一直增长，总会达到一个最大值，最后呈现出下降趋势，所以本文认为应拟合出一条二次曲线，选用二次回归模型：4.2.3 问题二模型的求解运用软件进行多次回归曲线的拟合，最终选择拟合度最好的图形，见图4。图4表明此回归模型为二次回归模型，通过软件编程，程序见附录六求解得：运行结果为：p = -0.0083 1.2733 70.6449即： 所以该回归曲线方程为：图4 全省鲜猪肉需求量二次回归拟合曲线 图4表明全省需求量在时，达到峰值，即在2016年4月全省鲜猪肉需求量达到最大。现将154个城镇的未来目标方程拟合，求出他们在全省鲜猪肉需求量出现峰值时（即2016年4月）的预测值，再在表格中将他们在这个月的需求量预测值进行排序得到达到峰值时需求达到前5位和后5位的城镇。为避免计算量过大的问题，本文按照2012年的12个月各个城镇的需求量的均值在表格中进行排序，抽取前十位城镇和后十位城镇，对其猪肉需求量进行回归，并计算出时，这20个城镇的猪肉需求量，再在表格中将他们在这个月的需求量预测值进行排序，得到当达到峰值时需求量位于前5位和后5位的城镇。2012年各城镇猪肉需求量月均值处于后十位的是：84号、102号、74号、30号、17号、129号、143号、16号、118号、122号城镇。2012年各城镇猪肉需求量月均值处于前十位的是：120号、31号、63号、106号、101号、150号、104号、68号、76号、100号城镇。根据以上20个城镇的资料画出它们各自的散点图，并进行拟合，发现84号、17号、30号、31号、74号、100号、106号、118号、120号、122号、143号城镇的数据没有明显上升或下降的趋势，预测值与2012年月平均值不大，所以在此取其均值作为达到峰值时的预测值。然而城镇16号、68号、76号、102号、101号、104号、150号、129号城镇的二次曲线的拟合度和102，63城镇的线性拟合度都很高，模型如下：63城镇：68城镇：76城镇：101城镇：102城镇：104城镇：129城镇：150城镇：本文以129号城镇为例计算拟合各城镇的未来销售量，详情见附录七。将带入以上方程，得出结果如下：、 、 、 然后结合其它城镇的2012年月均猪肉需求量列出2016年4月20个城镇的猪肉需求量表4，详情见附录八。从中筛选出全省鲜猪肉需求达到峰值时需求达到前5位和后5位的城镇，见表5表5 达到峰值时需求量达到前五位和后五位的城镇需求量前五位城镇需求量/吨需求量后五位城镇需求量/吨1208702.19666710293.9862314573.23666784102.3025633544.9130107.0951063494.43916774108.7075682286.73129119.4549表5表明全省鲜猪肉需求达到峰值时需求达到前5位的城镇是120号、31号、63号、106号、68号城镇，后5位的城镇是102号、84号、30号、74号、129号城镇。4.3 问题三4.3.1 问题三的分析 本题旨为公司设计增加销售连锁店的方案，使得全省销售量达到最大。通过调查分析可知公司的需求量和销售量并不完全一致，且在不同条件下，位于不同城镇的连锁店的需求量和销售量均发生不同程度的变化。考虑到未来几年各城镇需求量和销售量的不同，及其相互间的不同影响，此处存在是否在某城镇增设连锁店，若增设连锁店，要增设几个的问题，所以本题可转化为线性规划问题，又由于本题中的自变量全部为整数，所以拟建立整数规划模型进行求解。4.3.2 问题三模型的建立通过分析可知，本题要解决的是在某城镇是否增设连锁店和增设几个的问题，因为自变量均为整数，所以本题为整数规划模型，整数代表所增设连锁店的个数，建立模型如下： （公式编辑器中不要有汉字，字符问题） 约束条件： 4.3.3 问题三模型的求解运用软件实现上述算法，程序见附录九。据程序结果可知：在该省的12号,46号,53号,56号,68号,71号,76号,100号,101号,104号,110号,116号,121号,128号,150号,154号城镇增设一个连锁店，只在120号城镇增设两个连锁店，共新建了18所连锁店，此时，全省的总销售量将达到最大，值为：918586公斤。4.4问题四4.4.1 问题四的分析要求运输成本最小，由于各连锁店的需求一定，所以成本只与路线有关，亦即也是最短路问题。所以拟在除了原来的生产基地所在的城镇外的城镇中任意设置生产场地。然后求各个生产基地到各自覆盖的连锁店之间的最短路，我们假设增设一个生产基地，如：增设城镇为新的生产基地，则共有，120，63三个生产场地，然后求出此三者各自所覆盖的连锁店，求出总的最短路以及最小运输成本，同时判断是否符合日产量在250吨以上。如此，求出除去120，63之外的所有城镇最小运输费用，再对152个数据进行比较，求出其中运费最少的并且满足约束条件的一组，便是问题的解。4.4.2问题四模型的建立我们假设了任何一个连锁店由一个特定的生产基地进行货源供给，所以，我们首先要确立120，63，三个生产基地分别提供供给的连锁店。以表示两点之间的最短路，其中表示新设的生产场地，表示连锁店，表示在，63,120三个产地中到连锁店的最短路，以此确定各生产基地所覆盖的连锁店若，并且，则，表示基地到连锁店的距离最小。若，并且，则，表示基地63到连锁店的距离最小。若，并且，则，表示基地120到连锁店的距离最小。若，并且，则，表示基地63到连锁店的距离最小。若，并且，则，表示基地120到连锁店距离最小。以表示地连锁店的需求量，表示新增产地后的最小总费用，则有：比较152个，得到运费最小且的日销量大于250吨的，则其方案为增加城镇为产地，运费为。4.4.3 问题四模型的求解根据第一题的矩阵，找出各个连锁店到其它生产基地的最短路。用求解得新增加一个生产基地，在第142号城镇。4.5 问题五4.5.1 问题五的分析考虑到本题中车辆的调运方案与运输路线和装卸方式两个因素有关，但装卸时间固定，我们可以做如下两种考虑：在不考虑运输路线的极限情况下，小货车的最多能够进行8次货物的装卸，所以汽车装卸货物所用时间极限情况下可以为8小时；在考虑运输路线的情况下进行货物的装卸时，则存在路线最优和装卸方式最优两个问题，其中对于最优运输路线问题，由于全省城镇较多，不易寻找，所以打算将这154个城镇划分成不同的几个区域，根据问题一得出的全省交通网络图在各区域内找出最佳路线；对于最优装卸方案问题，又可以有两种装卸方式，一种是货车满载后，为沿途的多家连锁店送货，直到将货物全部送完；另一种是货车为指定的一家连锁店送货，送完后便返回生产基地。比较这两种方式，选择最佳方式。4.5.2 问题五模型的建立4.5.2.1 运输路线的优化由第三问和第四问可知，增建一个生产基地，18个销售连锁店，即全省共3个生产基地，37个有连锁店的城镇。同时由第四问的结果我们可以得到三个生产基地对37个连锁店的供货情况，按此标准我们将该37个连锁店所在城镇划分为3个区域。然后，利用问题一中得出的城镇交通路线图，找到生产基地到连锁店的线路，同时对比各条线路，挑选出时间最短的线路作为货车的供货线路。通过计算，三个片区的货车供货线路如下面三个图所示（图5、图6、图7）：走完每条路的时间计算公式为： 则目标函数： 通过程序画出基地120、63、142三个片区的货车供货线路如下面三个图所示：图5 以120号城镇为生产基地的片区路线图 图6 以63号城镇为生产基地的片区路线图 图7 142号城镇为生产基地的片区路线图4.5.2.2 货车的运输与装卸方案的优化一：货车在生产基地装满后，沿途在各个连锁店卸下一部分货物，直到把货物卸完，再返回生产基地装货；二，货车在生产基地装满后，只到指定的连锁店时把货物卸完，然后返回生产基地再装货，即一辆货车只给指定的一个生产基地供货；现在我们来比较两种供货方式所需要的货车数量：对于第一种供货方式，由第三问的计算结果可以得到，31个有连锁店的城镇中比较少出现装运一车就可以满足供货量的，也就是说货车极有可能是空车要返回生产基地，并再去装第二次货物的。现在，我们考虑生产基地到连锁店的其中一条线路，并假设这条线路上除终点外还有其他的连锁店。那么，我们可以知道，在这条线路上，货车的最大运输时间和载货重量的上限是确定的，这条线上的所有连锁店的货物需求总量也是确定的。如果我们采用第一种方式，则车子每次运输都需要走完整段路程，那么车辆往返一次的时间就增加了，并且，对于单个连锁店来说，每