6．4．3．1 算法策略的确定
根据6．4．2节中对禁忌搜索算法的构成要素的介绍，本书在构造求解LAP的禁忌搜索算法时，采用了以下算法策略。
（1）解的表示方法（编码）
本书直接使用实数编码，采用客户与设施共同排列的表示方法。设施用1，2，…，L表示，客户用L＋1，L＋2，…，L＋k表示。例如，对于一个有3个潜在候选设施和7个客户的问题，则可以用1，2，3，4，5，6，7，8，9，10这10个自然数编码（其中， 1，2，3表示潜在设施）。
（2）生成初始解的方法
本书采用贪婪取走启发式算法（Greedy-Drop Heuristic Algorithm）获得初始解。其基本思想是从所有候选选址点中，逐个将对目标函数影响最小的选址点去掉直到剩余的选址点只剩下m个。
算法的基本步骤如下：
第一步：初始化，令循环变量k＝n，将所有潜在仓库全部选中，按照运输成本最低的原则将客户需求点指派到相应的仓库。
第二步：选择取走一个仓库，满足以下条件：假如取走它并将客户重新指派后，总费用增加量最小。然后令k＝k－1。
第三步：重复第二步，直到k＝p。p为给定的可建立的设施的个数。
贪婪取走算法不一定能得到问题的最优解，但是当数据量很大时计算速度比较快。
（3）解的评价方法
在用禁忌搜索算法求解LAP时，需要对解进行评价，以比较解的优劣，使算法在迭代过程中，不断搜索得到质量更优的解，并最终得到问题的最优解或近似最优解。根据2．1节所介绍的LAP的数学模型，对于某个解要判定其优劣，首先要得到该解所对应的方案，然后要判断该方案是否满足问题的约束条件，同时计算该方案的目标函数值，在满足问题的约束条件的前提下，其目标函数值越优，则方案越优，解的质量越高。根据LAP的特点，采用客户与设施共同排列的解的表示方法对解进行评价，该种方法生成的解所确定的方案，隐含能够保证每个客户都得到服务及每个客户仅由一台车辆配送的约束条件，但不能保证满足每条路线上的各客户需求之和不能够超过车辆的最大载重量的约束条件。为此，对某个解所对应的方案确定设施位置后，采用就近原则将客户分配给已开放的仓库，然后要对各条路径逐一进行判断，看其是否满足约束条件，若不满足，则将该方案定为不可行解，最后还要计算出该解对应的目标函数值。对于某个解，设其对应的方案的不可行数为M （M＝0，表示该解为一个可行解），该方案的目标函数值为Z，并设对每个不可行方案的惩罚权重为Pw（该权重可根据目标函数的取值范围取一个相对较大的正数），则该解的评价值为E（E值越小，表示解的质量越高）。这种解的评价方案，体现了用罚函数法处理约束条件的思想。
E＝Z＋M×Pw（6-3）
（4）邻域操作策略
对仓库采用两两交换法（2-Swap）实施邻域操作，即随机选取一个被选仓库和一个未被选仓库进行交换。设S为初始的选址点集，N－S为未选点集，则让S与N－S交换一个点所能产生的所有S*的集合，即为我们的邻域。例如，对于一个潜在候选设施n＝4，要从中选取p＝2个设施的问题，初始解为（1，2），则它的邻域包含以下解：（1，3）、（1，4）、（2，3）、（2，4）。我们可以计算，2－Swap产生的邻域有p（n－p）个解集。
（5）禁忌对象的确定
禁忌搜索算法利用标记已得到的局部最优解，让它在一定的迭代步数内禁忌与之相关的解状态，以跳出局部最优解。当解从S转变成S*时，我们设定从S中换出去的点为禁忌对象。如，若解从（1，2）转变成（1，3），则点2为禁忌对象，这样，点2在禁忌长度的步骤内将不能被选取（除非被特赦）。
（6）禁忌长度的确定：根据问题的规模取一个常数。
（7）候选集合的确定：从当前解的邻域中随机选择若干个邻居。
（8）特赦规则：当出现迄今为止最好的解时特赦相应的禁忌点。
（9）终止准则：采用迭代指定步数的终止准则。
6．4．3．2 算法流程
设定N为网络中所有n个潜在候选仓库节点的集合，S为所选点集，N（S）＝｛S1，S2，…，Sp（n－p）｝为与之相对应的邻域，p为给定的选址数量。最后我们令tabu＿ tag（i）表示节点i所处的禁忌状态，如tabu＿ tag（i）＝t表示节点i在接下去的t步内将处于禁忌状态。
第一阶段：采用贪婪取走启发式算法获得初始解。
第二阶段：禁忌搜索改进算法。
（1）输入算法的运行参数，包括终止迭代步数T，每次迭代搜索当前解的邻居的个数M，禁忌长度l，对不可行方案的惩罚函数Pw等；初始化迭代步数、禁忌状态和禁忌表，令t ＝0，tabu＿tag（i）＝0，H＝∅；确定当前最好解S0，令S0＝S，利用解的评价方法计算S的评价值E。
（2）对当前最好解S用两两交换法（2-Swap）实施邻域操作，如果两个交换的点不是禁忌表H中的元素，则得到S的一个邻域S*，利用解的评价方法计算解S*的评价值E*，然后采用蚁群算法求解路径安排问题，更新禁忌表。
（3）判断是否满足终止迭代步数T。如果满足，输出结果，算法停止。否则继续步骤二。
其算法流程如图6-2所示。
图6-2 禁忌搜索算法求解LAP流程图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
