简论物流网络设计的CSA算法框架设计

【摘要】 CSA算法框架主要是给出了一种新的离散型设施选址问题的求解思路，并设计了新的SSA算法中进行随机搜索的领域生成方法。本文简述了内层和外层的优化算法的邻域构造，并且分别描述了CSA算法框架中，内层优化算法与外层优化算法的具体步骤。

【关键词】 物流；网络；CSA；算法

对于物流网络设计的设施选址问题，其解的形式包括两部分：一个是表示是否修建设施的决策变量Xi，另一个则是客户需求的分配决策变量Yij。而且两者之间是相互联系和相互影响的。一般来讲，需求必须分配给已经决定修建的设施，因此可以说Xi最终确定Yij。对于物流网络设计问题的邻域搜索算法而言，从目前的相关研究文献来看，对算法中的邻域构造，几乎都是由Yij的改变来产生，即任意选择一个Yij，将其改变值后，再根据Xi=∑Yij，确定各个Xi的值，这样就将决策变量之间的相互影响降低了到了最低程度。[1]但是，对于规模较小的问题，上面的邻域构造方法还是有效的，但是对于较大规模的问题，则使用上述方法，在短时间内并不能求取高质量的全局最优解。[2]究其原因，是因为随着规模的增大，变量Yij的数量也会急剧增大，此时若同温度下循环迭代的次数较小，则不能充分遍历解空间，这对于全局最优解的求取，显然是不利的，但是若增加循环迭代次数，无疑又会增加算法的运算时间。设施选址问题的解中，Xi最终确定Yij。因此我们可以在设计算法时，将问题分为两个阶段进行求解，第一个阶段(外层)对设施选址变量进行优化，第二个阶段(内层)则是在第一个阶段确定的设施决策的基础上，进行需求分配的优化计算，其中内层嵌于外层之中进行循环迭代优化。[3]而对于两个阶段的优化，均使用通用型强且改进后的SSA算法，从而就构成了设施选址问题的组合模拟退火算法――SSA算法。下面分别讨论CSA算法中两个求解阶段中SSA算法的邻域构造问题。

1 外层优化算法的邻域构造

外层SSA算法是针对设施选址进行优化，这里将解中选择修建的设施，表示为一个整数的集合F，在其中枚举了决定建设的位置(Xi)，例如，F={0，1，4，12}，则其代表了被建设的设施为0，1，4，12，其他的设施则被关闭。从而对外层SSA算法的邻域构造，允许用来修改解的状态的邻域函数，可以进行如下三种不同的操作：

(l)将集合F中的一个整数与另一个未修建设施的状态互换，即为进行互换(Exchange)操作；

(2)随机的选择一个未修建的设施，将其添加进入集合F中，即新建一个设施，既为添加(Add)操作；

(3)将集合F中的一个整数移除，即关闭一个已决定修建的设施，即为移除(Remove)操作。

在实际中算法每次执行时，可以根据实际情况，选择其中一项操作即可。例如，对于P中心问题，就只能选择操作(l)进行邻域解的生成。另外在每次执行上述操作后，都需要在集合F的基础上，重新进行需求的随机分配，即重新生成一次初始解。

为了增强操作的可控性，在具体的实施中，可以根据下面的规则随机的选择一项操作：

其中λ(F)为链表F的长度，ρ为算法中统一产生的随机数，m为系统最大允许修建的设施数目。这样一个解的状态的变化类型，是由其链表的长度λ(F)和随机参数ρ所决定的。例如，如果λ(F)>1，则任何一个操作均可根据ρ的大小来决定，另一方面，如果λ(F)=m，则只有移除操作Remove可以被允许执行。

通过实施上面的邻域函数，我们则可以从当前解转换到一个邻域解，这是一个预防性的邻域函数，通过上述操作保证了解的可行性。在每一次执行外层邻域函数的新的邻域结构后，都需要以集合F中的设施为选择修建的设施，重新生成一次初始解。

2 内层优化算法的邻域构造

对于内层SSA算法，其邻域构造也有两种方法：

(1) 任选一个需求分配决策变量yij，且满足yij=l，再任选一个设施j‘∈ F，设置yij’=1，yij=0，即将客户的需求随机分配给另一个设施；

(2) 任选两个需求分配决策变量yi1，j1，yi2，j2，满足yi1，j1=1，yi2，j2=1，然后设置yi1，j2=1，yi2，j1=1，yi1，j1=0，yi2，j2=0，即将客户i1，i2需求的供应设施互换。

同样的，在实际操作中，任选其中一项即可完成邻域解的生成。而且对于邻域解，需要检查其是否满足所有约束条件，不满足则需要返回原解，并重新按照上述方法构造邻域解。

3 CSA算法框架设计

CSA算法框架的内外层可以采用同样的退火计划表，即算法所使用的参数可都在外层SSA算法中进行设置。定义S，S‘，S’‘，S，为问题的相关解的向量表示，C(S)为解S的目标函数值，算法中使用的禁忌表定义为Ω，且λ(S)为解S在当前禁忌表中的禁忌长度。

下面分别描述CSA算法框架中，内层优化算法与外层优化算法的具体步骤。

外层优化算法的具体计算步骤如下：

步骤1：设置模拟退火计划表，令初始温度为t，升温系数γ=1，生成问题的初始解S，同时令当前记忆最优解S，同时令当前记忆最优解S=S，ΩΩ∪S，且令λ(S)=n；

步骤2：执行外层领域函数，得到新解S’，若λ(S‘)>0，则重复步骤2，否则，ΩΩ∪S’，同时更新禁忌表中各对象的禁忌长度，即对于∨S∈Ω，执行λ(S)λ(S)-1，若λ(S)=0，则ΩΩ/S，转步骤3；

步骤3：执行内层优化算法；

步骤4：若C(S‘)

步骤5：若C(S‘)

步骤6：若未满足同温度下的抽样稳定准则，返回步骤2；否则执行降温操作，即令tupdate(t)；

步骤7：若未满足升温条件，则返回步骤2；否则，执行升温操作，即令

γγ+C/K；

步骤8：收敛性检验。若未满足算法终止准则，则返回步骤2；否则算法终止，输出最优解S。

上面外层SSA算法中的步骤4，是将算法迄今为止所求的最优解保存下来，而不考虑概率性选择，这样就避免了算法概率性的跳出当前最优解的问题，最大程度的利用算法所求取的最优解。

步骤1：以S'为当前初始解和最优解，构造内层层邻域解，得到新解S''；

步骤2：若C(S'')

步骤3：若未达到同温度下的抽样稳定准则，则返回步骤2；否则算法终止，返回外层优化算法；

上面描述的内外层的SA算法步骤，实际上仅仅是CSA算法的框架或思想，算法所要使用的各种参数的具体设置，还需根据问题的规模等再作确定。

另外对于内层SSA算法中的C(S'')1>ρ'，即此时必然会进行S'=S''操作。同时对于前面所提到的SSA算法的各种改进措施，也可以单独的应用在内层SSA中。但是在上面描述的CSA算法框架中，为描述简便起见，我们将只把这些措施应用在外层SSA中。

该算法框架可以说适用于所有离散类型的设施选址问题，这一方面是由于SSA算法的通用性所决定的，另一方面也在于巧妙的邻域函数设置，至于对于具体问题的不同点，只是在于邻域函数的使用上，例如对于P-中心问题，外层SSA算法中只能采用第一种邻域函数，而对于CFLM模型和UFLM模型，则所有的邻域函数均可使用。[4]

对于CSA算法框架中使用到的退火计划表，即初始温度、温度下降控制规则、同温度下的迭代步长以及算法终止准则等的设置，可根据所研究的问题的具体情况而定。

另外对于标准的3层(工厂-物流中心或配送中心-客户)物流网络问题的初始解，可使用下面简单的算法生成：

步骤1：将所有设施按照其能力大小排序，按照对修建设施数目或建设资金的限制，选择前若干个满足该约束条件的设施(若无此约束，则选择所有设施)，构成设施的集合F，其中的设施即为初始解中决定修建的设施，令J'=F；

步骤2：对于客户i∈I，任选设施j∈J'，若设施j的剩余能力bj不小于客户i的需求di，转步骤3；否则，转步骤4；

步骤3：令决策变量Yij=1，bjbj-di，II/i，若I=Φ，算法终止，输出初始解X，Y，若I≠Φ，则令J'J'/j，若J'=Φ，则原问题无解，算法终止；否则返回步骤2；

这里要注意的是，每一次由外层邻域函数生成邻域设施集合后，都需要再次利用上面的初始解生成算法重新生成一个初始解，但是此时该算法中的集合F不再是由所有设施按能力排序后选取其中前若干个而构成，而是由当前决定修建的设施集合经外层邻域变换后，得到的新的决定修建的设施集合，而且，若上述初始解求取算法得出无解，则表明该邻域不可行，不能满足客户需求，需要返回原解，重新构造外层邻域。

综上所述，CSA算法框架主要是给出了一种新的离散型设施选址问题的求解思路，并设计了新的SSA算法中进行随机搜索的邻域生成方法，但是这里并没有就算法中具体参数的设置和标定进行进一步的研究，这些参数主要是SSA算法的冷却进度表，如算法的初始温度、抽样稳定准则、温度下降函数等，需要根据问题的实际需要，进行具体设置，而且对这些参数的具体设置，CSA算法框架没有任何限制，完全可以参考其他算法如SSA算法中的多种设置方法。

参考文献

[1] 孟大伟，吴慧德，王向安.多目标多配送中心选址问题[J].物流技术.2002(10)

[2] 邹辉霞，高伟.单配送中心的离散选址模型[J].科技进步与对策.2004(1)

[3] 付朋辉，康立山.用多目标演化优化算法解决约束选址问题[J].计算机工程与设计.2003 (13)

[4] 鲁晓春，詹和生.关于配送中心重心法选址的研究[J].北方交通大学学报.2000 (3)

收稿日期：2008-01-12