CFLP法

CFLP法(Capacitated Facility Location Problem)

目录 1 什么是CFLP法[1] 2 CFLP法的基本原理[2] 3 CFLP法案例分析 3.1 案例一：[2] 4 相关条目 5 参考文献

　　CFLP法是反町洋一先生创造并发表的方法，即用LP(线性规划)运输法，确定各配送中心的市场占有率，求出配送分担地区的重心，再用混合整数计划法的“筹划型”确定场址的建设位置。其目标函数和约束条件表示如下。

minZ =	∑	∑	CijXij +	∑	FiYi
	i	j		i

式中　　N——需要地的个数；

　　M——配送中心建设候补地的个数；

　　K——建设配送中心的个数；

　　D_j——需要地(j)的需要量；

　　F_i——配送中心建设候补地(i)的不变建设费；

　　A_i——配送中心建设候补地的建设容量；

　　C_ij——从候补地(i)到需要地(j)的运输单价；

　　X_ij——从配送中心到需要地(j)的运输量；

　　Y_i——假定在候补地(i)建设配送中心时为1，否则为0。

　　当配送中心的能力有限制，而且用户的地址和需求量及设置多个配送中心的数目均已确定的情况下，可采用CFLP法(Capacitated Facility Location Problem)，从配送中心的备选地点中选出总费用最小的由多个配送中心(假设有m个)组成的配送系统。这个方法的基本步骤如下。

　　首先，假定配送中心的备选地点已定，据此假定在保证总运输费用最小的前提下，求出各暂定配送中心的供应范围。然后，再在所求出的供应范围内分别移动配送中心至其他备选地点，以使各供应范围的总费用下降。当移动每个配送中心的地点都不能继续使本区域总费用下降时，则计算结束；否则，按可使费用下降的新地点，再求各暂定配送中心的供应范围，重复以上过程，直到费用不再下降为止。

　　(1)初选配送中心的地点。通过定性分析，根据配送中心的配送能力和用户需求分布情况适当地确定配送中心的数量及其设置地点，并以此作为初始方案。这一步骤非常重要，因为它将直接影响整个计算的收敛速度。

　　(2)确定各暂定的配送中心的供应范围。设暂定的配送中心有k个，分别为s₁，s₂，…，s_k；用户有n个；从配送中心s_i到用户j地的单位运输费用为；以运输费用U最低为目标，则可构成的运输问题模型如下：

式中：——配送中心s_i到用户j的运输量；

　　——配送中心s_i的容量；

　　D_j——用户j的需求量。

　　解以上运输问题，就可求得各暂定配送中心的供应范围。这可表述为如下的用户集合：

　　(3)在以上各配送范围内，移动配送中心到其他备选地点，寻求可能的改进方案。设在原定配送中心s_i的配送范围为N_i，除s_i之外，可做配送中心备选地点的还有L_i个，在这些地点设置配送中心的固定费用分别为F_il。其中t_l∈L_i；则以t_l为新的配送中心时，N_i配送范围内的总费用为： 令：

　　若,说明步骤(3)求出的目标函数值是步骤(2)求出的第i个配送中心目标函数值的一部分，则令s_i'=t_i'；否则令s_i'=s_i。对所有k个区域重复上述过程，得到新的配送中心的集合。

　　(4)比较新、旧配送中心集合的总费用。若前者大于或等于后者，说明已经得到了所要求的解，计算可停止；若前者小于后者，说明新得到的配送心地点可使总费用下降，通过改善配送中心的供应范围，还有可能进一步降低总费用。为了进一步降低总费用，以新的配送系统代替原有的配送系统，重复步骤(2)至步骤(4)，直到总费用不能再下降为止。

　　按以上步骤得到的收敛解，虽然没有得到理论上的证明，但是由于费用总是在下降的，因此在实际应用中，可以充分相信所得到的解。

　　现有选址问题如图1所示，要求在该地域范围内12个需求点中选出3个作为配送中心的地址。同时，假设各配送中心的固定费用均为10个单位，容量为13个单位，运输费率为一个常数，即运输费用与运输距离成正比。

　　解：根据图1可得各需求点之间的最短运输距离如表1所示。

表1 各需求点之间的最短运输距离

需求点j＼需求点i	1	2	3	4	5	6	7	8	9	10	11	12
1	O	1	6	7	4	3	4	6	6	9	8	9
2	1	0	5	6	5	4	5	7	7	10	9	10
3	6	5	0	3	6	9	10	12	12	15	14	15
4	7	6	3	O	3	10	11	13	13	16	15	12
5	4	5	6	3	0	7	8	10	10	13	12	9
6	3	4	9	10	7	0	6	4	9	10	6	6
7	4	5	10	1l	8	6	O	2	9	5	4	9
8	6	7	12	13	10	4	2	0	10	6	2	7
9	6	7	12	13	10	9	9	10	O	4	8	13
10	9	10	15	16	13	10	5	6	4	O	4	9
11	8	9	14	15	12	6	4	2	8	4	O	5
12	9	10	15	12	9	6	9	7	13	9	5	0

　　(1)根据需求量的分布情况，可将配送中心的初始位置暂定在4、6、9三个节点上。

　　(2)以点4、6、9为配送点，其他各节点为需求点，求运输问题的最优解，如表3一12所示。于是得到初始方案，总费用为179个单位。(具体求解过程略)

　　(3)根据以上求得的初始解，可以看出配送中心4的配送范围为用户1、2、3、4、5的集合，配送中心6的配送范围为用户1、6、8、12的集合，配送中心9的配送范围为用户1、7、9、10、11的集合。

表2 配送中心布局的初始方案

配送中心\需求点	1	2	3	4	5	6	7	8	9	10	11	12	供应量
4	2	4	2	3	2								13
6	2					4		5				2	13
9	1						3		4	3	2		13
需求量	5	4	2	3	2	4	3	5	4	3	2	2	39

　　对于集合{1，2，3，4，5}，配送中心的位置设在4时配送费用为：

　　如果配送中心的位置从4移到其他需求点，则配送费用分别为：

　　如果移到1，则；

　　如果移到2，则；

　　如果移到3，则；

　　如果移到5，则。

　　所以，移到配送中心2时，配送费用最少。

　　同理，通过计算，可知对于用户集合{l，6，8，12}，配送中心移到6，配送费用最小；对于用户集合{1，7，9，10，11}，配送中心移到10，配送费用最小。于是，新的配送系统应由用户集合{2、6、10}组成。

　　(4)对新的配送系统{2，6，10}重复步骤(2)至步骤(4)，重新计算。经计算，再次计算所得配送中心方案与前一次结果相同，说明方案已达到最优，所以最终解决方案就是配送中心选择在{2，6，10}，供应方案如表3所示，总费用为152个单位。

表3 配送中心布局的最终方案

配送中心\需求点	1	2	3	4	5	6	7	8	9	10	11	12	供应量
2	2	4	2	3	2								13
6	3					4		4				2	13
10							3	1	4	3	2		13
需求量	5	4	2	3	2	4	3	5	4	3	2	2	39

　　CFLP法的前半部分属于线性规划运输问题的解法，但其又在后半部分对线性规划进行了进一步的完善。虽然该方法实际意义明显，但缺乏理论上的证明。

• 运输规划法
• 鲍姆尔—沃尔夫法