禁忌搜索算法公式.docx

基于均衡原理的LRP算法整体流程如下：
stepl：初始化，设置整体收敛性判断参数5；
step2：随机生成一组LRP选址问题的解D，

基于均衡原理的LRP算法整体流程如下：
stepl：初始化，设置整体收敛性判断参数5；
step2：随机生成一组LRP选址问题的解D，求出相应的目标值F ;
step3:根据上层解D ,利用Fiaiik-Wolfe算法（）求出各客户的 货物总量0/及客户在各配送中心的货物均衡分配量兀
step4：根据D及竝丿运用禁忌算法求解VRP问题（见624节），得出各配送
中对各客户的单位货物配送费用C :
step5：根据兀丁及公式（6-8）求出下层上‘•与的关系XlJ = Wdi+yi/
step6：将LRP模型上层目标函数中用代替,
并代入下层求得的Q 和厂 运用禁忌算法
求得新的LRP选址规划的解Z及目标函数尸’（见622节）;
step7：如果F - F <,算法结束，D、尸为LRP的最终解和解值；否则
D .= D\ F .= F\ 转 step3； stepS：算法结束。
LRP选址规划的禁忌算法
模型上层是基于0-1整数规划的选址问题。由于选址问题是NP-hard,如果 用精确算法求解，对节点数目的限制将有严格的要求。本章根据模型的特点， 采用禁忌算法优化产业选址问题。
解的构造和初始解的生成
采用二进制编码，编码长度为潜在的配送中心地点数量川7 ,对于编码中位置几1表示选
中i点作为厂址，0表示没有选中。对于解中任意点j,产生随机数5,如果6>N/NT，则 置i点为0,否则置1。重复以上步骤m次，得到初始解。
邻域的搜索
根据本章选址问题的特点，设计了三种邻域操作，分别为自身取反、2-swap交换和2-opt 交换。
1） .自身取反。为单点操作，即选择解中j点，对该点的值取反；
2） . 2-swap交换。为双点操作，选择解中两点进行交换，其它位置的值不变。例如解001101 中的2、6点被选中,则2-swap交换后变为：011100；
3） . 2-opt交换。为多点操作，选择解中两点进行交换，同时两点之间的值逆序改变。例 如解001101中的2、6点被选中，则2-swap交换后变为：010110；
.自身取反、2-swap交换操作能较快的搜索到局部最优解，2-opt交换则能扩人搜索空 间。自身取反、2-swap交换是每个循坏都进行的操作，进行局部寻优。当/代最优解没有 变化时，进行一次2-opt交换操作，跳出局部最优点。
将以上三种邻域结合，不仅保持了 TS局部”爬山”能力强的优点，同时也让它的全局寻 优能力大大加强。
约束的处理
本章LRP模型上层约束包扌舌分厂数量约束和总投资额约束。对于分厂数量限制，本章 在邻域操作中加以控制：如果当前解经过某邻域操作，违反分厂数量限制，则取消此邻域操 作。对于总投资额约束，本章采用惩罚函数的方式进行处理，把超出约束的量乘以一个惩罚 系数，作为一个惩罚项加入到解的适应度中。上层目标函数的适