基于重心法和动态规划方法求解出美的销售物流车辆路径安排
- 格式：doc
- 大小：1.41 MB
- 文档页数：6
基于重心法和动态规划方法求解出美的销售物流车辆路径安排
一．重心法概述
（1）重心法(The centre-of-gravity method)是一种选择销售中心位置，从而使销售成本降低的方法。
它把销售成本看成运输距离和运输数量的线形函数。
此种方法利用地图确定各点的位置，并将一坐标重叠在地图上确定各点的位置。
重心法是一种设置单个厂房或仓库的方法，这种方法主要考虑的因素是现有设施之间的距离和要运输的货物量，经常用于中间仓库或分销仓库的选择。
商品运输量是影响商品运输费用的主要因素，仓库尽可能接近运量较大的网点，从而使较大的商品运量走相对较短的路程，就是求出本地区实际商品运量的重心所在的位置。
（2）重心法 - 重心法计算公式
重心法首先要在坐标系中标出各个地点的位置，目的在于确定各点的相对距离。
坐标系可以随便建立。
在国际选址中，经常采用经度和纬度建立坐标。
然后，根据各点在坐标系中的横纵坐标值求出成本运输最低的位置坐标
X和Y，重心法使用的公式是：
公式中
Cx-- 重心的x坐标；
Cy-- 重心的y坐标；
Dix--第i个地点的x坐标；
Diy--第i个地点的y坐标；
Vi--运到第i个地点或从第i个地点运出的货物量。
最后，选择求出的重心点坐标值对应的地点作为要布置设施的地点。
二．重心法在本题中的运用。
由于要使用动态规划的方法进行路径优化，则需明确动态规划求最短路问题中的起点S和终点T。
在美的邯郸生产基地的实际问题中，起点明显为邯郸，而终点需要作进一步的假设确定（因为把销售网点中的每个城市作为终点来计算路径并没有意义）。
逆用重心法可以初步确定对整个销售网络重心最有影响力的几个点。
2007年美的北方主要销售商销售量分布表单位（万元）
比较各个销售网点之间的f(d,v)=D*V=距邯郸的距离*估计销售量
可知北京f=381.1*（825.64+561）
哈尔滨f=1501.9*358.7
青云f=1074.6*190.79
分列f(d,v)最大的三个城市，故由重心法的原理可知，这三个城市对销售重心的影响力最大，且各自代表了一个销售方向和片区。
下一步在做动态规划时，将优先将这三个城市作为各自的终点。
三．动态规划法
（1）动态规划的基本思想
在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。
动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。
贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。
相比而言，动态规划则可以处理不具有贪心实质的问题。
在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。
动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。
由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。
（2）动态规划的基本步骤
动态规划算法通常用于求解具有某种最优性质的问题，本次运用动态规划求解，就是为了找到适合美的销售物流的最优路径。
在这类问题中，可能会有许多可行解。
每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。
设计一个动态规划算法，通常可以按以下几个步骤进行：
（1）找出最优解的性质，并刻画其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
其中（1）——（3）步是动态规划算法的基本步骤。
在只需要求出最优值的情形，步骤（4）可以省去。
若需要求出问题的一个最优解，则必须执行步骤（4）。
此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造
出一个最优解。
（3）在解决美的销售路径设计时的操作方法 1.初步确定3个方向：
将去往哈尔滨方向的销售线路定义为H 线，将去往北京方向的销售线路定义为B 线，将去往青云方向的销售线路定义为Q 线，每条线分4个城市。
2.找到下一个适宜的城市
公式可为}.......min{)(2321++++=k D D D D k fx ，x=H,B,Q k=0，1，2，3
以B 线为例，第0阶段仅有邯郸和北京两个城市，往返的总路程为2)0(∙=ad D fB =762.2km ，此时城市范围VB={a ，d},同理知
2)0(∙=ak D fH =1501.9*2=3003.8km ，VH={a ，k}。
2)0(∙=ag D fQ =1074.6*2=2149.2km ，VQ={a ，g}。
第一阶段，找出下一个城市y ，使}m i n {)1(ya dy ad D D D fB ++=，得到
km D D D fB ea de ad 9.8544.3644.1091.381)1(=++=++=，VB={a ，d ，e}
同理可知}min{)1(ya ky ak D D D fH ++=得到
km D D D fH ja kj ak 4.30074.12841.2219.1501)1(=++=++=，VH={a ，j ，k} km D D D fQ ca gc ag 2.21982.2384.8856.1074)1(=++=++= ，VQ={a ，c ，g}
第 二 阶 段，找出下一个城市z ，使}min{)2(za ez de ad D D D D fB +++=，得到
km D D D D fB ma em de ad 4.9239.1492834.1091.381)2(=+++=+++=，
VB={a ，d ，e ，m} 同理可知
km D D D D fH ia ji kj ak 7.29791.9986.2581.2219.1501)2(=+++=+++=，
VH={a ，i ，j ，k}
km D D D D fQ ba cb gc ag 6.24902.2014.3294.8856.1074)2(=+++=+++=，
VQ={a ，b ，c ，g}
第 三 阶 段，找出下一个城市r ，使}min{)3(ra mr em de ad D D D D D fB ++++=，得到
km D D D D D fB fa mf em de ad 9.13305.2489.3082834.1091.381)3(=++++=++++=
VB={a ，d ，e ，f ，m}，即B 线路为：邯郸---石家庄---北京---天津---济南---邯郸 同理可知
km
D D D D D fH ha ih ji kj ak 5.29811.7448.2556.2581.2219.1501)3(=++++=++++=VH={a ，h ，i ，j ，k}，即H 线路为：邯郸---哈尔滨---长春----沈阳----大连---邯郸
km
D D D D D fQ la bl cb gc ag 9.32947.5498.4554.3294.8856.1074)2(=++++=++++=VQ={a ，b ，c ，g ，l}，即Q 线路为：邯郸---太原---青云----西安---郑州----邯郸
3.确定总的线路
将三条线路合在一起，则总的路径长度为Z 。
Z=)3()3()3(fQ fH fB ++=1330.9+2981.5+3294.9=7607.3km
利用重心法和动态规划法选择出的美的销售物流路线图。
