郭 宇

（沈阳理工大学，辽宁 沈阳 110168）

1 问题描述

带有容量约束的选址问题是指，在物流配送网络中，根据客户的位置、客户对产品的需求量以及各配送中心的最大容量，确定配送中心的位置，以及由选定的配送中心发往不同客户的发货量，使得总的运输费用和管理费用达到最小。一般可描述为如下的混合整数规划：

其中：m表示客户数，n表示备选的配送中心数量，di表示客户i对某种特定物品的需求量，sj表示配送中心j的最大容量，cij表示将单位物品由配送中心j运往客户i的单位运输费用，fj表示建造配送中心j的固定费用。变量yj表示是否开放配送中心j，xij表示由配送中心j运往客户i的货物量。

2 算法设计

Benders分解算法是J.F.Benders[1]在1962年首次提出的，目的是用于求解线性混合整数规划的算法，该算法将线性混合整数规划分解成只包含连续变量的子问题和只包含整数变量的主问题，首先通过确定复杂变量（即整数变量）将原问题转化成只包含连续变量的易于求解的线性规划，再根据对偶理论利用解的的连续变量构造Benders割反作用于主问题，通过连续反复地求解主问题和子问题，最终获得原问题的最优解。

针对本文中的带有容量约束的选址问题，设计Benders分解算法如下。

子问题用于求解货物运输量的问题。

2）（SPy）的对偶问题可以表示为

3）根据对偶理论构造Benders割，则可得到如下的主问题（MPT）：

3 算例测试

为测试算法的有效性，选取了Beasley[2]中提供的三组不同规模的问题集进行测试。三组规模分别为：①10个客户，10个备选配送中心；②20个客户，30个备选配送中心；③50个客户，50个备选配送中心。实验结果表明，本文设计的算法可以在合理的时间内获得较高质量的近似解。