配送中心選址及网点布局的启发式方法.docVIP

5．4 配送中心选址及网点布局的启发式方法 5．4．1 Cluster法 Cluster法的基本思路是先将配送中心定位在各个需求点，然后通过对需求点进行组合以降低配送中心的数目，并根据组合后的需求点的几何重心安排新的配送中心地址，直到总费用不再降低为止。 下面举一个具体例子说明Cluster法的解决步骤。假设要设计一个配送中心网络负责5个主要市场的配送，5个主要市场之间的距离如表5—4所示。该网络的配送中心个数不限，建造各个配送中心的建造费用和运营费用都是相同的，分别为100万元和50万元。另外运输费率是0．1元／9公里。每个市场的需求量都是50万吨。问应如何设计此配送中心网络? (1)在每个市场建造一个配送中心。这样总共需要建造5个配送中心，由于距离各市场的距离是0，所以运输成本为0。总费用由建设成本、运营成本以及运输成本构成，因此在这个方案中总费用是： 5*100万元+5*50万元+0=750万元 (2)将市场1和市场2组合成一组，并在两个市场直线距离的中点设置新的配送中心，同时服务这两个市场。这样配送中心的总数目可以减少到4个，建造成本和运营成本减少100万元+50万元=150万元，而运输成本增加0．1*100*5*2=100万元，所以与初始方案相比，总费用下降了50万元，即为700万元，优于初始方案。 (3)进一步分组，检验总费用是否还可以继续下降。由于其他几个市场之间距离均大于或等于300公里，所以方案无法继续改进。 因此此配送中心网络应设计为在市场1和市场2直线距离的中点设置一个配送中心，另外在市场2、市场4和市场5所在地分别设置1个配送中心。 5．4．2 CFLP法 当配送中心的能力有限制，而且用户的地址和需求量以及设置多个配送中心的数目均已确定的情况下，可采用CFLP法(Capacitated Facility Location Problem)，从配送中心的备选地点中选出总费用最小的由多个配送中心(假设有m个)组成的配送系统。 这个方法的基本步骤如下： 首先假定配送中心的备选地点已定，据此假定在保证总运输费用最小的前提下，求出各暂定配送中心的供应范围。然后再在所求出的供应范围内分别移动配送中心至其他备选地点，以使各供应范围的总费用下降。当移动每个配送中心的地点都不能继续使本区域总费用下降，则计算结束；否则，按可使费用下降的新地点，再求各暂定配送中心的供应范围，重复以上过程，直到费用不再下降为止。 (1)初选配送中心地点。通过定性分析，根据配送中心的配送能力和用户需求分布情况适当的确定配送中心的数量及其设置地点，并以此作为初始方案。这一步骤非常重要，因为它将直接影响整个计算的收敛速度。 (2)确定各暂定的配送中心的供应范围。设暂定的配送中心有k个，分别为sl，s2，…，sk；用户有n个；从配送中心si到用户j地的单位运输费用为hsij；以运输费用U最低为目标；则可构成运输问题模型如下： (4)比较新、旧配送中心集合的总费用。若前者大于或等于后者，说明已经得到了所要求的解，计算可停止。如果前者小于后者，说明新得到的配送中心地点可使总费用下降，通过改善配送中心的供应范围，还有可能进一步降低总费用。为了进一步降低总费用，以新的配送系统代替原有配送系统，重复步骤(2)至步骤(4)，直到总费用不能再下降为止。 按以上步骤得到的收敛解，虽然没有得到理论上的证明，但是由于费用总是在下降的，因此在实际应用中，可以充分相信所得到的解。 下面举一实例加以说明。 现有一选址问题如图5—3所示，要求在该地域范围内12个需求点中选出三个作为配送中心的地址。同时假设各配送中心的固定费用均为10个单位，容量为13个单位，运输费率为一常数，即运输费用与运输距离成正比。 (1)根据需求量的分布情况，将配送中心的初始位置暂定在4，6，9三个节点上。 (2)这样，以点4，6，9为配送点，其他各节点为需求点，求运输问题的最优解见表5—6，于是得到初始方案，总费用为179个单位。(具体求解过程略) (3)根据以上求得的初始解，可以看出配送中心4的配送范围是用户1，2，3，4，5的集合，配送中心6的配送范围是用户1，6，8，12的集合，配送中心9的配送范围是用户1，7，9，10，11的集合。 所以配送中心移到2，配送费用最小。 同理通过计算，可知对于用户集合{1，6，8，12}，配送中心移到6，配送费用最小。对于用户集合{1，7，9，10，11}，配送中心改设在10，配送费用最小。于是新的配送系统应由2，6，10组成。 (4)对新配送系统{2，6，10}重复步骤2～4，