货物配送及优化

1、货物配送及线路优化相关问题摘要本文以梦想连锁公司近年来的业务状况以及市场销售为主题，研究该公司具体的销售配送方案，未来市场需求，连锁店产地选址等问题，进一步的完成公司规划。我们运用运筹学图论、时间序列法、模型优化等相关知识，将、等数学软件运用于模型求解，从而解决具体问题。对于问题一，首先建立销售连锁店的坐标位置分布图，找出23家连锁店所在的城镇，其次根据分布图和生产基地，由最短路径问题的求解方法，做出城镇间道路的赋权矩阵，运用软件求出最短距离，从而得出最低运输成本。例如7号连锁店，所在城镇编号为65，最短路径为从63城镇出发，途径64，65城镇，总路程为19.09公里，运输成本为133.75元

2、。由此进行所有路线的求解和运输成本运算，得23家销售连锁店最低运输成本为:10540.82元。对于问题二，首先制作全省近五年月度鲜猪肉需求的时间序列图，并绘制自相关和偏自相关函数图，确定模型阶数。其次用指数平滑法进行数据拟合和预测，得出在未来三年内，该公司在2015年10月全省鲜猪肉需求达到峰值。最后，对各个城镇近五年来的猪肉需求数据进行筛选，将筛选后的城镇进行拟合，预测在2015年10月需求量达到峰值时，各城镇的需求量。将结果进行排序，得出峰值时各城镇预测需求的前五位与后五位。得出结论如下表：前五（按降序排列）120号城镇后五（按升序排列）102号城镇31号城镇84号城镇106号城镇30号城

3、镇63号城镇74号城镇101号城镇118号城镇对于问题三，为使全省销售量达到最大，在设立连锁店时采用算法顺序，首先将原有销售连锁店的各城镇进行需求量自行满足，当该地原有销售量不小于需求量时，将多余销售量按从小到大满足10公里内的需求量为50%的其他城镇并将这些城镇删除。其次，把剩余城镇重新进行编号，根据原需求量最大原则进行增设销售连锁店。销售量由本城镇及周边城镇算出。最后，将总囤积量与未满足需求总量进行比较，得出是否还需要再设立连锁店。得出，还需要增设10家连锁店，每家连锁店的销售水平都为40吨，所在的城镇编号为：31、56、68、79、100、101、104、110、121、150。对于问题

4、四，要求设立新的生产基地，达到运输成本最低，首先将运输到原有连锁店的运输成本超过150元或路程超过100公里的城镇筛选出来，与新设连锁店一起考虑，综合日生产量达到250吨以上约束条件，做出优化模型，得出：在31号城镇设立新的生产基地。关键词:算法 时间序列 指数平稳模型 最短路线 选址问题一、问题重述梦想连锁是一家肉类食品加工与销售公司，主营：鲜猪肉。公司在全省县级及以上城镇设立销售连锁店。全省县级及以上城镇地理位置及道路连接见数据文件：全省交通网络数据.xlsx问题：1、目前公司现有2个生产基地、23家销售连锁店，生产基地设在120号和63号城镇，为23家连锁店提供鲜猪肉，连锁店的日销售量见

5、相关表格。若运输成本为0.45元/吨公里，请你为公司设计生产与配送方案，使运输成本最低。2、公司收集了近5年全省各城镇的鲜猪肉月度需求数据（文件：各城镇月度需求数据.txt）请你分析各城镇需求特征，并预测未来数年，何时全省鲜猪肉需求达到峰值，达到峰值时需求达到前5位和后5位的城镇是那些？3、通过广告宣传等手段，未来几年公司在全省的市场占有率可增至3成左右（各城镇对公司产品每日需求预测数据见文件：公司未来各城镇每日需求预测数据.txt），调查还发现，公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量与销售量相同，若在不足10公里的其他城镇的销售连锁店购买，则这一部分

6、需求量只能实现一半（成为公司产品销售量，由于距离的原因，另一半需求转向购买其他公司或个体工商户的产品），而在超过10公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三成。于是，公司决定在各城镇增设销售连锁店，基于现有条件、成本等的考虑，原有的23家销售连锁店销售能力可在现有销售量的基础上上浮20%，增设的销售连锁店销售能力控制在每日20吨至40吨内，并且要求增设的销售连锁店的销售量必须达到销售能力的下限。同一城镇可设立多个销售连锁店。请你为公司设计增设销售连锁店方案，使全省销售量达到最大。4、在增设销售连锁店的基础上，公司决定增加生产基地，地址设立在城镇所在地，每日产品生产必须达到250

7、吨以上，在生产与销售各环节不能有产品积压。请你为公司设计生产基地增设方案，使运输成本最低。5、公司产品若采用载重1.5吨的小货车从生产基地运往销售连锁店，小货车在高速公路上限速100公里/小时，在普通公路上限速60公里/小时，销售连锁店需要的产品必须当日送达。假设：每日车辆使用时间不超过8小时，小货车装满或卸完1.5吨的货物均需要半小时，本市运输车辆行驶时间可忽略不计。在公司增设销售连锁店、增加生产基地后，为完成每日运输任务，请你为公司确定小货车的最小需求量，及各车辆的调运方案。二、问题分析2.1对于问题一的分析对于问题一，首先根据坐标位置图，将连锁店按距离两个生产基地的路程长短分为三类。类：

8、编号为1、3、10、18的连锁店所在城镇有生产基地，可不考虑道路运输问题。类：编号2、15的连锁店所在城镇与两个生产基地的距离差不多，通过比较再得出最低成本路线。类：编号5、9、11、13、14、19、21、22的连锁店由在120城镇的生产基地发货；编号4、6、7、8、12、16、17、20、23的连锁店由在63城镇的生产基地发货。其次，我们运用运筹学图论中的最短路径法，对两定点间最短路径用算法在程序中实现并求解。最后，得出我们所需要的生产与配送方案，并得到最低成本费用。2.2对于问题二的分析对于问题二，首先对全省的近五年每月的需求数据进行处理，运用时间序列相关知识，用所得数据绘制序列图，根据

9、序列特征初步确定模型。其次运用绘制相关函数图，确定模型阶数。最后用指数平滑法进行数据拟合与预测，得到近几年预测值及峰值。用同样的方法，单独对各个城镇近五年来的猪肉需求数据进行拟合并预测其近三年的需求数据，由前半题得到的峰值时间去找对应各个城镇数据，然后进行排序，得出峰值时各城镇预测需求的前五与后五。2.3对于问题三的分析对于问题三，为达到全省销售量最大的目标，首先将原有销售连锁店的各城镇进行需求量自行满足。当该地原有销售量需求量时，将多余销售量按从小到大满足10公里内的需求量为50%的其他城镇并将这些城镇删除。其次，将删去后留下的城镇重新进行编号，根据原需求量最大原则进行增设销售连锁店。增设销

10、售连锁店后，销售连锁店所在的城镇进行需求量自行满足。该地增加了销售量之后，销售量现有的需求量时，删去已满足的该城镇，并对该地10公里内的其他城镇进行满足。算出总囤积量，将囤积量总和与所有存在销售连锁店城镇未被满足的部分需求量的总值加上增设点10公里以内尚未被满足需求量50%的城镇的和10公里以外所有城镇交集的需求量的30%的总量进行比较。若：总囤积量<该总量，则说明仍需增设销售连锁店；若：总囤积量该总量，则说明无需增设销售连锁店，则算出所有增设点数量及其具体的位置。增设点具体增设的销量由该地需求量决定。三、模型假设结合本题的实际，为了确保模型求解的准确性和合理性，在排除了一些因素的干扰之

11、后，提出以下几点假设：1 本题所给数据基本真实可信。2 问题一不考虑车辆数量及载重等相关因素。3 问题一可用各城镇坐标位置间距离初步估计其真实道路路程长短，且道路为双向行驶。4 问题二中各城镇猪肉需求在未来几年没有其他因素的影响。四、符号说明符号说明最短路问题起点最短路问题终点顶点集从到的路路的权从起点到的路程长度的真子集路时间温特线性和季节性指数平滑模型的水平性温特线性和季节性指数平滑模型的叙事性温特线性和季节性指数平滑模型的季节性季节周期长度季节调整因子温特线性和季节性指数平滑模型的初始参数平稳序列时间间隔序列的自协方差函数序列的自相关函数五、模型的建立与求解经过以上的分析和准备，我们将逐

12、步建立以下数学模型，进一步阐述模型的实际建立过程。5.1问题一的模型建立与求解5.1.1问题分析与处理对于问题一，我们首先建立城镇坐标及道路图，根据坐标位置图，将连锁店按距离两个生产基地的路程长短分为三类。具体图表（图1）与结果如下：图1：各城镇道路连线图类：编号为1、3、10、18的连锁店所在城镇有生产基地，可不考虑道路运输问题。类：编号2、15的连锁店所在城镇与两个生产基地的距离差不多，通过比较再得出最低成本路线。类：编号5、9、11、13、14、19、21、22的连锁店由在120城镇的生产基地发货；编号4、6、7、8、12、16、17、20、23的连锁店由在63城镇的生产基地发货。其次，

13、根据不同类别进行模型求解，运用运筹学图论中的最短路问题的解决方法，分别求各个连锁店与生产基地这两个定点间的最短路径，运用算法在中的实现，得出运输成本最低的生产配送方案。5.1.2模型导入与解释问题一本文运用的是运筹学中图论的相关知识及算法，最短路问题一直是图论中的一大问题，解决该问题的一大算法（戴克斯特拉）算法就是本题运用的模型。以下为模型的具体解释：为了叙述清楚起见，把赋权图中一条路的权称为它的长，把路的最小权称为和之间的距离，并记作。在下面的算法中，假定所有的权均为正，并且若，则规定。算法不仅找到了最短的路，而且给出了从到的所有其他顶点的最短路，其基本思想如下：假设是的真子集且，记。若是从

14、到得最短路，显然，且的节必然是最短路，所以，并且从到的距离由下面的公式给出：。 （1）上式是算法的基础。从集开始，用下述方法构造一个由的子集组成的递增序列，使得在第步结束时，由到得所有顶点的最短路均已知：先确定距最近的一个顶点。为此，只要算出，并选取顶点，使得即可。由式（1）容易算出为。然后置，并用记路。显然，这是最短的路。一般来说，若集以及相应的最短路已经确定，则可用式（1）来计算，并选取顶点，使得。根据式（1）有对某个成立。将边连接到路上，即得最短路。对上述过程改进得下述算法1） 置。置。2） 置。记，置。3） 若，则停止（就是需要计算的最短路）；否则，置，转2）。5.1.3模型求解与结果

15、本题考虑的是双向行驶的道路，不存在有向性。首先定义顶点集和边集，然后给出赋权矩阵，因为为了简便运算及程序输入，解决方案不采取将154个城镇的道路转化为矩阵输入电脑，而是通过坐标图找出所需运送连锁店所在城镇和生产基地附近的城镇，并将这些城镇的道路转化为赋权矩阵。以14号连锁店为例，分析其所在42号城镇附近城镇，发现其距离在120号城镇的生产基地更近，随后选取120号城镇到42号城镇线路上经过的附近城镇，具体为：13、40、41、43、44、45、119，将其具体道路及距离转换为赋权矩阵，如下： 13 40 41 42 43 44 45 119 120得出矩阵后将其编进程序（具体见附录一），最后得

16、出结果，具体线路如下：，总路程110.58公里，消耗成本472.18元。通过上述方法，对其余连锁店进行赋权矩阵的书写，然后带入编程，求得生产与配送方案具体如下：由63号城镇的生产基地配送：表1：63号城镇生产基地配送路线表连锁店编号运送路线路程（公里）消耗成本（元）3号直送18号直送23号63-647.316.057号63-64-6519.09133.758号63-6-66-7928.15490.984号63-6-51-51-10-31114.661235.596号63-6-51-50-10108.36413.5512号63-6-51-50-10-29-28-27135.1563.2717号6

17、3-6-66-67-68-69-3-24128.94188.6320号63-6-66-67-68-69-3-21-22168.95484.6816号63-6-66-67-68-69-3-21-23-11179.15492.01由120号城镇的生产基地配送：表2：120号城镇生产基地配送路线表连锁店编号运送路线路程（公里）消耗成本（元）1号直送10号直送22号120-1235.1141.5813号120-119-13-45-44-43-34119.5424.2619号120-123-134-139-149-146-14572.851299.925号120-125-124-133-132-1416

18、1.72257.1311号120-119-13-45-40-41-42-35-36151.19782.6121号120-125-124-133-132-141-15-142-143-16103.64689.459号120-125-124-133-132-141-15-142-143-16-1134.31891.122号120-125-131-130-10663.71095.9515号120-125-131-130-106-91-90-2-84-93-94170.17978.1114号120-119-13-45-40-41-42110.58472.185.2问题二的模型建立与求解5.2.1数据初

19、步处理及模型分析本文将各城镇的数据进行求和处理，得出近五年来每月的总需求，运用所得数据进行拟合并进行预测，定义预测未来三年，画出曲线后找出峰值。在需求量达到峰值的时间点，先筛选出城镇的需求排名，将筛选后的各个城镇的数据进行拟合和预测，得出峰值所在时间的各城镇需求。时间序列最显著的特点就是数据有着严格的先后顺序，并且与一定的时间点或时间段相对应，所以数据必须指明其所对应的时间点或时间段，以及整个数据多对应的期间。所谓数据期间的选取是指，如果分析过程中只希望选取部分时段数据进行分析，则应首先制定该时间段的起止时间。时间序列的图形化观察需要绘制序列图、自相关函数图等图。序列图是按照时点顺序将数据展现

20、出来的一种图形，它是时间序列分析当中用得最多也最为有用的图形工具，可用于对序列直观特性的观察。自相关函数图和偏自相关函数图是以自相关函数和偏自相关函数为依据绘制而成的图形。所谓自相关是指序列与其自身经过某些阶数滞后形成的序列之间存在某种程度的相关性。对自相关的测度往往采用自协方差函数和自相关函数。自协方差函数：设是平稳序列。由平稳性可知，对任意整数有式中，是时间间隔的函数，称为序列的自协方差函数。自相关函数定义为由上述图形来确定阶数，此题中采用指数平滑模型来求解。指数平滑法因权数选择和平滑方法的不同而分成多种模型形式。此题我们采用三次指数平滑法中的温特线性和季节性指数平滑。温特线性和季节性指数

21、平滑模型的一般形式为上式包含三种成分，它们分别是水平性、趋势性和季节性。为季节周期长度，为季节调整因子，分别为模型的三个初始参数。其中温特线性和季节性指数平滑模型适用于同时具有趋势性和季节性的时间序列，且只适用于短期预测。5.2.2模型求解与结果首先，绘制和观察全省猪肉需求（月季度）的序列图。图2：全省猪肉需求（月季度）序列图由图2可知，全省猪肉需求量存在明显的上升趋势，同时还存在季节周期。据此，尝试采用Winters可乘性模型，分析结果如下表3与表4。表3：全省猪肉需求量指数平滑模型结果（一）模型统计量a模型预测变量数模型拟合统计量Ljung-Box Q(18)离群值数平稳的 R 方R 方统

22、计量DFSig.吨数-模型_10.737.96018.31615.2460a. 根据平稳 R 方的最佳拟合模型（值越大表示拟合越好）。表4：全省猪肉需求量指数平滑模型结果（二）指数平滑法模型参数a模型估计SEtSig.吨数-模型_1无转换Alpha (水平).074.0362.054.045Gamma (趋势).399.2181.827.073Delta (季节).001.111.009.993a. 根据平稳 R 方的最佳拟合模型（值越大表示拟合越好）。由表3表4可知，指数平滑模型的拟合效果较为理想，残差序列不存在相关性。序列的水平、趋势和季节的平滑值分别为0.074、0.399、0.001，

23、且统计上显著。具体模型为。需要说明的是：指数平滑法的不足在于模型具有一定的不确定性，参数的初始值以及变化步长都可能影响最终的模型结果。其次，绘制自相关函数图（ACF）和偏自相关函数图（PACF），作为观察序列自身特征的工具，主要目的是结合序列特点设置模型阶数（具体程序实现相关图见附录二）。本题相关图如下（图3、图4）。图3：自相关函数图图4：偏自相关函数图最后，得出拟合与预测图形（图5）。图5：已有数据拟合与未来三年预测图数据表如下（表5）。表5：全省未来三年猪肉需求预测数据表单位：公斤2013年1月2月3月4月5月6月预测119486.90119385.47119907.64119725.0

24、6120240.99120311.38UCL121074.42120981.50121517.62121355.66121899.94122007.32LCL117899.39117789.45118297.65118094.46118582.04118615.432013年7月8月9月10月11月12月预测120052.39119958.59120419.44120820.11119791.49120333.00UCL121794.69121757.11122284.33122761.62121819.77122458.02LCL118310.08118160.07118554.551188

25、78.61117763.21118207.982014年1月2月3月4月5月6月预测120071.67119970.24120492.40120309.83120825.76120896.14UCL122303.53122317.74122964.41122914.79123571.68123790.63LCL117839.81117622.74118020.40117704.87118079.84118001.652014年7月8月9月10月11月12月预测120637.15120543.35121004.20121404.88120376.26120917.77UCL123687.4312

26、3756.27124386.27124962.31124114.96124843.41LCL117586.88117330.44117622.14117847.46116637.56116992.132015年1月2月3月4月5月6月预测120656.44120555.01121077.17120894.60121410.53121480.91UCL24774.88124871.00125595.73125620.56126348.57126635.55LCL116537.99116239.01116558.61116168.63116472.49116326.272015年7月8月9月10月

27、11月12月预测121221.92121128.12121588.97121989.65120961.03121502.54UCL126597.55126728.99127419.23128053.33127262.07128044.79LCL115846.30115527.25115758.71115925.97114659.98114960.28注：UCL为上控制线，LCL为下控制线。由上表及上图可知，未来三年该省市在2015年10月达到峰值，需求为121989.65公斤。经此，确认了峰值出现的时间，由此，去求各个城镇在2015年10月的预测需求值，并进行排序，因为运算量的巨大，本文对已知

28、数据进行处理，挑出了需求平均排前二十和后二十的城镇，对这些城镇进行未来三年的数据预测，以2号城镇为例，用指数平滑法得出等于0.929的拟合曲线并进行预测，得出2015年10月其猪肉需求量为197.48公斤。得出需求前五位和后五位的城镇如下表（表6）：表6：峰值时需求前五与后五的城镇编号及需求预测数据表需求前五位（按降序排列）需求后五位（按升序排列）城镇编号峰值时的需求预测（公斤）城镇编号峰值时的需求预测（公斤）1208620.8110289.90314601.878498.941063388.5330109.15633290.8474109.821013053.76118123.075.3问题

29、三的模型建立与求解5.3.1模型的建立1 将原先有销售连锁店的各城镇进行需求量自行满足。当该地原有销售量需求量时，删去已满足的该城镇，并将多余部分先满足10公里内的其他城镇（按需求量从低到高进行满足，满足10公里内的各城镇需求量的50%）。具体情况如下：当多余部分该地10公里以内的各城镇50%需求量的总和时，多出来的部分，将其视为囤积量，将所有已满足其需求量50%的城镇删去。当多余部分该地10公里以内的各城镇50%需求量的总和时，对未满足需求量50%的城镇不进行满足，并将这部分多余量视为囤积量。2 将删去后留下的城镇重新进行编号，根据原需求量最大原则进行增设销售连锁店。每增设一个销售连锁店后，

30、该地先进入第3步。3 增设销售连锁店后，销售连锁店所在的城镇进行需求量自行满足。该地增加了销售量之后，销售量现有的需求量时，删去已满足的该城镇，并按1的步骤对该地10公里内的其他城镇进行满足。4 将第3步算出的囤积量与之前的囤积量相加。判定：囤积量总和与所有存在销售连锁店城镇未被满足的部分需求量的总值加上增设点10公里以内尚未被满足需求量50%的城镇的和10公里以外所有城镇交集的需求量的30%的总量进行比较。若：总囤积量<该总量，则说明仍需增设销售连锁店，进入第2步若：总囤积量该总量，则说明无需增设销售连锁店，则算出所有增设点数量及其具体的位置。增设点具体增设的销量由该地需求量决定。5.

31、3.2模型具体求解及结果图6：题三模型流程图首先，找出23家连锁店所在城镇，比较城镇日需求量和连锁店销售量，若销售量大于日需求量后，还能满足该城镇10公里范围内其他城镇的50%需求量，则将满足需求量的城镇及该连锁店所在城镇删去。删去结果为：22、20、42、41、63、62、7、53、64、65、6、78、79、66、106、107、123、120、141、15这20个编号的城镇。其次，将剩余城镇按日需求量降序排序后重新编号，在需求量最大处新建连锁店，选取合适的销售量。最后，判断总囤积量是否大于需求总量，若满足，则说明无需增设连锁店。若不满足上述条件，则继续增设连锁店。得出，还需要增设10家连

32、锁店，所在的城镇编号为：31、56、68、79、100、101、104、110、121、150。六、模型的评价与改进6.1模型的评价6.1.1模型的优点1 问题一事先对线路有所了解，进行分类，并在赋权矩阵的选取时进行了简化，便于我们程序的实现，减少了计算量。2 问题二运用三次指数平滑法，可以更好的拟合数据，不局限于单纯的将数据进行多项式拟合，从而忽略了季节性变化等数据特点。3 问题三流程清晰，采用多步筛选，来保证增设连锁店的可行度。6.1.2模型的缺点1. 问题三只考虑了局部最优解，忽略了最优解的整体性。2. 问题二各个城镇的峰值时预测需求数据，因为坐标等原因，会存在偏差。3. 问题一在赋权矩

33、阵的书写时，对于点的选取存在主观性。6.2模型的改进问题一中，我们可以在赋权矩阵的选取时，直接采用154*154的大矩阵来进行计算，在初步输入时比较复杂，但是在里实现时，却能更快更直接更准确的得出最短路径。模型的具体思路不变，可以在模型实现时进行算法的优化，会使结果更准确。七、参考文献1薛毅，数学建模基础（第二版），北京：科学出版社，2011；2薛薇，SPSS统计分析方法及应用，北京：电子工业出版社，2013.1；3姜启源等编，数学模型（第三版），高等教育出版社，2003年08月；附录一：model:sets:nodes/A,B,C,D,E/;arcs(nodes,nodes):w,x;endsetsdata:w= 0 17.27 10000 10000 10000 17.27 0 7.33 10000 10000 10000 7.33 0 40.53 10000 10000 10000 40.53 0 8.89 10000 10000 10000 8.89 0 ; enddatamin=sum(arcs:w*x);s=1;t=5;sum(nodes(j):x(s,j)=1;sum(