1.贪婪算法

带指定点集和时间依赖型定向问题的贪婪算法主要采用指定点集总等待时间最小和插入单位时间收益最大点两个启发式规则。根据指定点在不同时段的等待时间和点间的时间距离，对指定点集中的点进行排序，选择总等待时间最少的遍历方案，这样可以有更多的时间遍历其他点，从而获得更多的收益。由于指定点是必须被遍历到的点，且在不同时段有不同的等待时间，因此对其优先考虑。指定点的遍历方案间接选定了它们被遍历时的时间窗，并且这些时间窗没有交集。选择不同的时间窗组合，指定点集的总等待时间不同。总等待时间最小的指定点集序列和起点、终点组成了一条初始的不完整路径，路径中的部分点不相连。为了使路径完整并尽可能获得更多的收益，在不影响指定点的遍历时间窗、终点的到达时间不超过其最晚时间的条件下，将路径外单位时间收益最大的点插入到路径中，形成新的路径。循环这种插入操作，一直到不能插入为止。具体过程如下：

1）根据指定点在不同时段的等待时间特点和点间距离，寻找总等待时间最小前提下指定点集S的遍历时间窗排列组合。指定点一般不多，可以采用枚举法。总等待时间最小的指定点集序列、起点及终点组成了一条初始的不完整路径，其中v₁、v_n分别是起点和终点，k是指定点集S中点的个数，，，…，是总等待时间最小的指定点的排列。

2）若当前路径P₁为完整路径，输出当前路径，否则，从起点开始，沿着当前路径P₁，在v_i和v_j的时间空挡内，即当v_j不是v_i的紧后点时，进行插入操作。用表示路径P₁上的点的集合，为不属于的点的集合。在不影响v_j的遍历时间条件下，从中选取单位时间收益最大的点插入到v_i的后面，作为其紧后点，形成新的路径P₂。

3）将新路径代替当前路径，返回到②。

2.遗传算法

带指定点集和时间依赖型定向问题的遗传算法设计方案如下：

1）编码。采用路径编码，如1→5→3→2→9→4→10表示一条从v₁点出发，依次经过v₅、v₃、v₂、v₉、v₄点，并到达终点v₁₀的路径。这种编码方案最大的优点是易于解码。

2）初始种群。采用随机和启发式相结合的方法生成初始种群，使初始种群既具有多样性又具有较好的优良性。随机生成法不同于一般的随机生成法，它根据问题的特点，优先优化指定点集的遍历顺序和时间，然后在不影响指定点遍历的条件下，不断从尚未遍历的点中随机选择一个点插入到不完整路径中，从而形成一条完整的路径，也就是一个个体。启发式生成法指利用上一小节的贪婪算法先得到一个较优的解，然后对其进行多次微调，生成多个个体。随机和启发式生成法的比例为4：6，即随机法生成的个体数量占种群规模的40%，启发式法生成的个体数量占种群规模的60%。(www.daowen.com)

3）适应度评价。直接将目标函数作为适应度函数，适应度越大，总收益越大。

4）选择。最优解100%保留，而对其他个体则通过联赛竞争保留下来，进一步进行下面的交叉和变异操作。

5）交叉。采用蜜蜂进化思想和边重组法。将选择的最优的染色体当做自然界中的蜂王，其他染色体则作为雄蜂。将蜂王分别与雄蜂进行交配，即边重组。假如染色体X（0，2，4，1，3，8，0）、Y（0，6，9，10，5，3，8，0）分别为蜂王和某雄蜂，其中染色体中基因3和8是指定点。由X、Y得到一个10×4的矩阵

A的行依次代表0、1、2、3、4、5、6、8、9、10，第一列为0、1、2、3、4、5、6、8、9、10在X中的紧前点，第二列为0、1、2、3、4、5、6、8、9、10在X中的紧后点，第三列、第四列分别为0、1、2、3、4、5、6、8、9、10在Y中的紧前点和紧后点。A的每行中若有相同数字，则用0表示重复的数字。从起点v₀开始，v₀在A中所在的行为（8206），由于行中有指定点，因此，以概率1直接将指定点v₈作为v₀的紧后点。v₈在A中所在的行为（3000），由于仅有v₃，因此v₈的紧后点为v₃。v₃在A中所在的行为（1850），v₈已被选择，从v₁、v₅中以交叉概率p_c选择单位时间收益w_i/t_3i+τ_i最大的点作为v₃的紧后点。若单位时间收益最大的点未被选中，则以等概率从余下的点中选择一个作为v₃的紧后点。假设v₅被选择作为v₃的紧后点，v₅的紧后点为v₁，v₁的紧后点为v₄，v₄的紧后点为v₂。由于v₂在A中所在的行（0400）仅有v₄，而v₄已被选择过，因此随机从未被选择的点中选择一个作为v₂的紧后点。假设v₂的紧后点为v₉。v₉的紧后点为v₆，v₆的紧后点为v₁₀。从而产生一条新的染色体Z（0，8，3，5，1，4，2，9，6，10，0）。

6）变异。以变异概率p_m对交叉产生的染色体进行插入、删除、替代和交换操作。插入操作指随机从染色体外的其他基因中选择一个基因插入到染色体任意位置中。删除操作指随机从染色体中删除一个非指定基因。替代操作指随机从染色体外的其他基因中替代任意一个非指定基因。交换操作指从染色体中随机选择两个基因，彼此交换位置。对每一个操作均重复5次，选择（W_new-W_old）/（T_new-T_old）最小的染色体作为原染色体的变异体。W_old、W_new分别为插入操作前和插入操作后染色体的适应度值，也即路径的总收益，T_old、T_new分别为插入操作前和插入操作后路径所花费的时间。变异操作一方面增加了种群的多样性，另一方面使部分染色体的适应性更好。

7）修正不可行解。在交叉和变异操作中有不可行解的产生，因此，需要对它们进行修正，使其变成可行解。修正的方法是删除路径尾部中除指定点和终点以外的其他点，使路径总花费时间不超过最大时间限制。

8）控制参数。种群规模为50；进化的代数最大为50；交叉概率p_c=0.9-（0.9-0.65）G/G_max，其中，G、G_max分别为当前进化代数、最大进化代数，交叉概率随进化代数的增加而减小；变异概率p_m=0.001+（0.01-0.001）G/G_max。动态的交叉和变异概率可以加快收敛速度，同时在一定程度上防止“早熟现象”的发生，提高收敛效果。