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

简论物流网络设计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在当前禁忌表中的