选址重心法和鲍尔曼法

1、配送中心选址常用的方法1、解析方法（重心法、混合整数规划法）、解析方法（重心法、混合整数规划法） 建立数学模型，求精确解。建立数学模型，求精确解。2、模拟方法、模拟方法 利用数学方程和逻辑关系，求满意解。利用数学方程和逻辑关系，求满意解。3、启发式方法（鲍尔曼、启发式方法（鲍尔曼沃尔夫法）沃尔夫法） 针对求解，逐次逼近最优解。针对求解，逐次逼近最优解。单一配送中心的选址方法重心法（ x3 , y3）（ x2 , y2）（ x0 ,y0）（ x1 , y1）（ xn , yn）（ xn-1 , yn-1）零售店零售店配送中心配送中心确定配送中心的位置，以使得从配送中心到各零确定配送中心的位置，以

2、使得从配送中心到各零售店的总的发送费用为最小。售店的总的发送费用为最小。重心法模型 如前图所示，设有如前图所示，设有n个零售店，他们的坐标个零售店，他们的坐标是是 ，配送中心的坐标，配送中心的坐标是是 ：), 3 , 2 , 1)(,(niyxii),(00yx 11njjCHH从配送中心到各零售店从配送中心到各零售店/供货点的总运输费用供货点的总运输费用,cj 从配送中心到各零售店从配送中心到各零售店/供货点的运输费用供货点的运输费用,重心法模型2jjjjdwhC hj 从配送中心到零售店从配送中心到零售店 j 的的单位数量、单单位数量、单位距离运输费用，位距离运输费用，wj 从配送中心向零

3、售店从配送中心向零售店 j 的发送量的发送量,dj 从配送中心到零售店从配送中心到零售店 j 的距离的距离 （直线距离？实际距离？直线距离？实际距离？）。）。 3)()(212020jjjyyxxd直线距离！直线距离！从配送中心到零从配送中心到零售店售店j的距离的距离待定待定重心法模型将(2)代入(1)得 41njjjjdwhH 50/ )(100njjjjjdxxwhxH令 60/ )(100njjjjjdyywhyH重心法模型 7/11*0njjjjnjjjjjdwhdxwhx得到 8/11*0njjjjnjjjjjdwhdywhy用迭代法求出使用迭代法求出使H 为最小的为最小的),(00

4、yx迭代法的计算步骤：1、以所有零售店的重心坐标为配送中心的初始、以所有零售店的重心坐标为配送中心的初始地点地点2、利用式、利用式(3)和和(4) ，计算与，计算与 相应的总运相应的总运输费用输费用),(0000yx),(0000yx0H 3)()(21200200jjjyyxxd 410njjjjdwhH迭代法的计算步骤：3、把、把 分别代入式分别代入式(3) ， (7)和和(8)中，计中，计算配送中心的改善地点算配送中心的改善地点),(0000yx),(1010yx21)()(2020jjjyyxxd(3)njjjjnjjjjjdwhdxwhx1110/njjjjnjjjjjdwhdywh

5、y1110/(7)(8)迭代法的计算步骤：4、利用、利用(3)和和(4) ，计算与，计算与 相应的总发送相应的总发送费用费用),(1010yx1H21)()(210210jjjyyxxd(3)njjjjdwhH11(4)迭代法的计算步骤：5、把把 和和 进行比较，如果进行比较，如果 ，则说明，则说明 就是最优解；如果就是最优解；如果 ，则返回第，则返回第3步进行计算，步进行计算，直至直至 ， 说明说明 就是最优解。就是最优解。 NNHH11H0H01HH 01HH ),(0000yx),(00NNyx重心法的优缺点重心法模型是解决配送中心最佳地址的连重心法模型是解决配送中心最佳地址的连续型模型

6、。续型模型。优点：其配送中心的选择是不加特定限优点：其配送中心的选择是不加特定限制的，有自由选择的长处。制的，有自由选择的长处。缺点：自由度过多，最佳地点很难在实缺点：自由度过多，最佳地点很难在实际中找到。此外，迭代复杂也是模型缺际中找到。此外，迭代复杂也是模型缺点之一。点之一。5 例例：某公司由两个工厂向仓库供货，由仓库供应：某公司由两个工厂向仓库供货，由仓库供应三个需求中心。工厂和市场的空间分布如图。寻找使三个需求中心。工厂和市场的空间分布如图。寻找使运输成本最小的单一仓库的位置。产品运输成本最小的单一仓库的位置。产品A由由P1负责供负责供应，产品应，产品B由由P2供应，这些产品随后再被运

7、到市场。供应，这些产品随后再被运到市场。各点坐标、货物运输量和运输费率如表各点坐标、货物运输量和运输费率如表1。 表表1 市场和供应地的货物运输量和运输费率市场和供应地的货物运输量和运输费率地点地点 产品产品运输量运输量运输费率运输费率hi坐标值坐标值iwi(美元美元/担担/英里）英里）XiyjP1A20000.05038P2B30000.05082M1A/B25000.07525M2A/B10000.07564M3A/B15000.075880 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1P1P2M3M2M1工厂工厂P1、P2和市场和市场M1、M2、M3

8、及建议的仓库位置图及建议的仓库位置图y*x* 利用公式，确定仓库的初始位置或大致位置，以表利用公式，确定仓库的初始位置或大致位置，以表格形式求解方程。格形式求解方程。ixiyjwihiwi hiwi hi xiwi hi yi1382000 0.050100.00300.00800.002823000 0.050150.001200.00300.003252500 0.075187.50375.00937.504641000 0.07575.00450.00300.005881500 0.075112.50900.00900.00 625.00 3225.00 3237.50 得得 x0* =

9、3225.00/625.00=5.16 y0*=3237.50/625.00=5.18 运输运输费率费率运输量运输量与该位置相关的总运输成本可以从表与该位置相关的总运输成本可以从表2得出。得出。表表2 某公司仓库的运输成本的计算某公司仓库的运输成本的计算ixiyi（4）wi（5）hi（6）di（英里）（英里）（7）=4 5 6成本（美元）成本（美元）13820000.05035.52355228230000.05042.63639532525000.07531.65593546410000.07514.48108658815000.07540.024503 总运输成本总运输成本 21471=3

10、5.52英里英里运输运输费率费率运输量运输量22118.5816.5310d修正后的坐标值如下：修正后的坐标值如下： x0* =102.009/20.249=5.038 y0* =102.388/20.249=5.057总成本为总成本为21.431美元。美元。 迭代迭代11次后总成本不再下降，选址位置的坐标次后总成本不再下降，选址位置的坐标变化也很小。变化也很小。多个配送中心的选址方法:鲍尔曼沃尔夫(Baumel-wolfe)方法鲍尔曼鲍尔曼沃尔夫网点布局方法是针对下图所示沃尔夫网点布局方法是针对下图所示的网络结构提出的一种启发式方法。的网络结构提出的一种启发式方法。网络结构图:A1AmD1D

11、qB1BjBn资源厂(i=1m)网点(k=1q)用户(j=1n)Cik（运输费率）Ck（存储费率）Ckj（运输费率）鲍尔曼沃尔夫方法这里所要考虑的问题是：这里所要考虑的问题是：各个资源厂向哪些网点运输多少商品？各个资源厂向哪些网点运输多少商品？各个网点向哪些用户发送多少商品？各个网点向哪些用户发送多少商品？以使得总的费用为最低。以使得总的费用为最低。鲍尔曼沃尔夫方法网点规模存储费用网点存储费用函数表网点存储费用函数表鲍尔曼沃尔夫方法鲍尔曼鲍尔曼沃尔夫方法引入了非线性函数，沃尔夫方法引入了非线性函数，使计算求解变得复杂了。为了简单化问使计算求解变得复杂了。为了简单化问题，鲍尔曼法在迭代求解过程中

12、对非线题，鲍尔曼法在迭代求解过程中对非线性函数采取分段线性化的的做法，即在性函数采取分段线性化的的做法，即在每次迭代过程中用边际成本表示存储费每次迭代过程中用边际成本表示存储费率，边际成本表示在一定网点规模下的率，边际成本表示在一定网点规模下的单位货物存储费用，可与单位运输成本单位货物存储费用，可与单位运输成本直接相加，然后利用运输规划的方法求直接相加，然后利用运输规划的方法求解。解。鲍尔曼沃尔夫方法假定：网点的存储成本与规模的关系为：假定：网点的存储成本与规模的关系为：KKKdSKS表示网点K存储成本Kd为网点规模K为常系数（1）鲍尔曼沃尔夫方法设dk为1/2吞吐量，网点K在某一规模时的边际

13、成本 （一定网点规模下的单位货物存储费用）为：KCKKKKKKdddSC22（2）鲍尔曼方法的计算步骤（一）求初始方案令： 因此，资源点i和需求点j之间的最小费率为：则有，0Kd), 2 , 1(00qKCK0ijCmi, 2 , 1nj,2, 1)min(0000KKjiKijCCCC（3）鲍尔曼方法的计算步骤（一）各资源点的资源和需求点的需求量均为已知，以 为运价系数构成运输模型：0ijC000minijijXCFinjijaX10jmiijbX1000ijXmi, 2 , 1nj, 2 , 1表示由资源点i经网点k向需求点j调运物资的数量。鲍尔曼方法的计算步骤（一）由公式（3）中 与 的

14、关系，求出各网点的中转量 ，即一组网点设置方案0ijC0KC), 2 , 1(0qKdKqkKd10)min(0000KKjiKijCCCC（3）鲍尔曼方法的计算步骤（二）计算网点的边际成本：以 表示网点规模的大小，计算此规模下的边际成本（存储费率） ：0Kd1KC0012KKKKddCqK,2, 1鲍尔曼方法的计算步骤（三）用用 替代替代 ，与求初始方案的过程完，与求初始方案的过程完全一样，求出一组新方案全一样，求出一组新方案1KC0KCqkKd11鲍尔曼方法的计算步骤（四）比较新旧方案，确定最终解将新方案 与旧方案 进行比较，如果两个方案完全相同，则新方案为最终解；否则返回步骤二，反复进行

15、步骤二至步骤四，直到 与 完全相同时为止，即获得满意解。1Kd0Kd1NKdNKd鲍尔曼沃尔夫方法的优点1、在求解过程中只需运用一般运输规划的计算方法，避免了混合整数规划模型的求解困难，大大降低了计算成本。2、鲍尔曼沃尔夫方法较好的解决了网点存储费用非线性的问题。鲍尔曼沃尔夫方法的缺陷1、它是一种启发式方法，与其它启发式方法一样，不能保证得到最优解，而且最终解的满意程度与备选点选择的合理与否关系密切。2、网点设置的固定投资成本在计算过程中没有涉及。鲍尔曼方法的一个例子有两个资源厂A1和A2，可供资源量分别为：a1=40单位， a2=50单位；有8个需求点Bj(j=1,2,8)，各点需求量如下表

16、所示；已选定5个备选网点Dk(k=1,2, ,5)存储费用和网点规模的关系为一方根函数 。其中 为1/2吞吐量，各备选网点存储费用函数以及它与源、汇点之间的运费率分别列于下表。KKKdSKd各需求点需求量1B2B3B4B5B6B7B8B 需需求求点点需需求求量量101010155151015存储费用函数KKKdS1D2D3D4D5DKd75Kd80Kd75Kd80Kd70KKdd275KKdd280KKdd275KKdd280KKdd270备选网点存储费用边际成本KKKKKKdddSC22资源厂至备选点运费率1AKD1D2D3D4D5D1A2A 77812111412968备选点至需求点运费率

17、KDiB1B2B3B4B5B6B7B8B1D2D3D4D5D 51138510111114 16894744101135259515 139672102973265128案例：解：设 为仓库的边际成本，因网点的吞吐量为2 ，则KCKdKKKKKdddSC22由上面的各表汇成费率表费率表1D2D3D5D1B2B3B4B5B6B7B8B1A2A1DKKdd2752DKKdd2803DKKdd2754DKKdd2805DKKdd270 7781211 1412968 511385101111 1416894744 10113525959732651284D步骤一：求解初始方

18、案1B2B3B4B5B6B7B8B1A1D5D1D5D3D3D2D2D2A5D5D5D5D5D4D4D4D 12 18 10 13 10 13 11 11 17 15 11 10 11 8 16 8 开始时，我们不需要考虑存储成本，可以假设各备选网点的边际成本均为0。求出资源点i到需求点j之间的最小费率及其相应的中转网点。)min(KjKiKijCCCC5K1供需平衡的运输规划模型1B2B3B4B5B6B7B8B1A2A 汇源资源量1218101310131111401715111011816850需求量101010155151015 求解运输问题的结果1B2B3B4B5B6B7B8B1A1D

19、1D3D2D2D2A5D5D4D4D 汇源 10 10 5 10 5 40 10 15 15 10 50 101010155151015 初始方案1D2D3D4D5D 中转量201552525存储费用336310168400350边际成本（四舍五入）8101787中转量为网点的设置规模，该方案总成本为2499元KKKdSKKKKKKdddSC22步骤二：第一次迭代（费率表）步骤二：第一次迭代（费率表）1D2D3D4D5D1B2B3B4B5B6B7B8B1A2A1D2D3D4D5D 7781211 1412968 8 511385101111 10 1416894744 17 101135259

20、5 87973265128新的运输规划模型1B2B3B4B5B6B7B8B1A1D5D1D5D1D4D2D2D2A5D5D5D5D4D4D4D4D 汇源 20 25 18 20 20 22 21 21 4024 22 18 17 21 16 24 16 50 101010155151015 )min(KjKiKijCCCC5K1根据上式求得新的费用系数如下表所示：模型的结果1B2B3B4B5B6B7B8B1A1D1D5D1D2D2A5D5D4D4D 汇源 10 10 5 5 10 40 10 10 15 15 50 101010155151015 第一次迭代方案1D2D3D4D5D 中转量251003025存储费用3752530439350边际成本（四舍五入）81377改进后的方案总成本为改进后的方案总成本为2362元。该方案与初始方元。该方案与初始方案不一样，且总成本下降了案不一样，且总成本下降了137