下载掌阅APP，畅读海量书库
立即打开
经典路径优化问题中一个最基本的变形为考虑服务时间窗的路径优化问题（Vehicle Routing Problem with Time Window），即访问每个客户的时间受到时间窗[a i ，b i ]的约束，早于a i 晚于b i 均无法完成配送。自从20世纪60年代开始，大量学者开始对考虑服务时间窗的路径优化问题进行了深入研究。现有文献提出了各种精确求解算法（Exact Algorithm）、启发式算法（Heuristics）及元启发式算法（Metaheuristics）。然而，只有一部分小规模的考虑服务时间窗的路径优化问题可以通过精确算法进行求解，其中可以求解的最大规模问题包括135个客户。因此，这一问题较为活跃的方向为启发式算法和元启发式算法。接下来，将分别介绍求解考虑服务时间窗的路径优化问题的各类经典算法，主要包括：构造启发式算法、局部改进搜索算法、元启发式算法、并行和协同启发式算法。
这一类算法旨在通过启发式算法逐步构造可行解及最优解，其最主要的特征是秉承了贪婪算法（Greedy Algorithm）的主要思想。以下将分别介绍4种经典的构造启发式算法：CW算法、Sweep算法、先排序后分配算法、先分配后排序算法。
（1）CW算法。
Clarke和Wright于1964年在其论文“Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”中提出了经典的CW算法。该算法主要基于成本缩减的思想。由于其思想简单且易于实现，CW算法已成为在实际应用中最为有效且简单的初始解构造算法。首先，为每个客户构造一条路线，即v 0 —v i —v 0 ，其中v 0 为车场，然后对已有线路进行合并。选取合并线路的标准为在保证合并后线路满足所有约束的前提下最大化成本缩减，即max s ij = c i0 +c j0 -c ij 。该算法由于其思想简单且易于实现，一直被路径优化领域的后续文献大量引用和应用。之后的研究者也从不同角度对经典的CW算法进行了一系列改进。其中，Gaskell（1967）和Yellow（1970）通过加入权重的方法对s ij 进行了改进，即max s ij = c i0 +c j0 -λc ij 。CW算法的实现过程中存在平行和顺序两种实现方法。其中，平行实现方法中总是将产生最大成本缩减的两条路线进行合并，而在顺序实现过程中，算法关注于将其他路线与特定的一条路线进行不断合并，直到合并后的路线不可行为止。
总体来说，CW算法思想简单、易于实现，并且算法速度较快。在经典算法中没有涉及任何参数，同时编程也相对容易。该算法的缺点是缺乏灵活性。虽然CW算法也可以求解考虑其他约束的路径优化问题，但所求得的解的质量会大大下降。其原因是该算法的贪婪思想，这使得合并后的路线不具有可逆性，无法将其他的约束条件更好地融入合并过程中。Solomon（1986）将CW算法应用于考虑服务时间窗的路径优化问题中去，但并未得到较好的求解效果。
其他改进算法则将较为复杂的数据结构和排序算法引入到经典的CW算法中，以期望能更好地度量成本缩减。还有一部分学者关注于对路线合并过程进行改进，他们多采用匹配（Matching）的方法。虽然这一方面的改进提高了求解质量，但是也牺牲了经典算法的简单易实现特性和较快的计算速度。
（2）Sweep算法。
Sweep算法最早由Gillett和Miller在其1974年的论文“A Heuristic Algorithm for the Vehicle-Dispatch Problem”中提出，但该算法的基本思想则可以追溯到Wren和Holliday的论文“Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points”。该算法主要应用于路径优化问题中的平面算例。该算法主要通过旋转一条从车场开始的射线从而将客户逐个添加到现有路线中来，直到该路线违反了如载重约束等限制为止。该方法重复执行以构造新的路线。Sweep算法的思想也非常简单，但是在解的质量和计算速度方面不及CW算法。同时，跟CW算法一样，Sweep算法并不够灵活，其贪婪算法的本质使其很难将其他约束融入路线构造过程中，尤其是平面结构的假设很大程度上限制了Sweep算法的应用范围。
有一部分启发式算法先构造一些可行路线（通常称为花瓣），然后利用集合划分问题对已有可行路线进行优化组合从而得到最终路径优化问题的解。例如，Foster和Ryan提出的单花瓣算法和Renard等提出的双花瓣算法。在双花瓣算法中，可行解库中不仅包含单条路的可行解，还包括两条路的可行解。这些改进大大提高了算法的精确度。同时，计算速度也有一定的提升。但是由于需要产生大量的花瓣可行解，导致算法不再像基础的Sweep算法那样简单。就灵活性而言，花瓣算法可以适用于一系列不同约束的问题，但是都是以牺牲算法的简单性为前提。其实，这一类算法可以看成是列生成算法的删节版本。路径优化问题的本质是带有排序的分配问题，所以其解的构造过程包括两个主要元素：分配和排序。分配，即将客户分配到不同的车辆或路线上；排序，即每辆车或每条路线上的客户服务的先后顺序。CW算法和Sweep算法的实施过程将分配和排序融合在一起。除此之外，还有一类算法将分配和排序这两个元素分离开来，分阶段实现。这类算法的两个主要分支为先排序后分配和先分配后排序。
（3）先排序后分配算法。
Newton和Thomas于1974年在其论文“Bus Routing in a Multi-school System”中提出了先排序后分配的算法。具体来说，首先利用旅行商问题（Traveling Salesman Problem）的算法构造一条包含所有客户的环形路线，然后将该路线分成多条从车场出发的路线。这一部分可以利用求解最短路问题来进行求解。
（4）先分配后排序算法。
Fisher和Jaikumer于1981年在其论文“A Generalized Assignment Heuristic for Vehicle Routing”中提出了先分配后排序的算法。具体来说，首先将客户按照地理位置进行聚类，然后对每一组客户利用求解旅行商问题的算法进行排序形成一系列路线。聚类问题的求解可以采用一般的分配问题（Assignment Problem）的求解方法。该方法跟实际中人工视觉路径优化方法很类似。由于该算法更加关注分配部分的决策，这使得该算法能够较好地解决约束相对严格且可行解较少的算例。因此，该算法与之前的算法的最大不同在于对载重等约束的处理不再是考虑地理因素的副产品，而是作为主要因素来考虑。
局部改进搜索算法通常应用于基于序列的组合优化问题中，并且取得了较好的效果。给定一个初始解，局部改进搜索算法会对该初始解的某一邻域进行搜索，通常称之为对当前解s的扰动，以寻找更好的解s′。在下一个迭代过程中，s′将取代s成为新的当前解。该算法的终止条件为：在该邻域内无法找到更好的解。这一过程可以找到该邻域内的一个局部最优解。由相邻关系这一属性相连接的解的集合称为搜索集。局部改进搜索算法每一次迭代所找到的解的集合称为搜索轨迹。现有路径优化问题的文献中定义了不同类型的邻域。接下来，我们将分别介绍几类常用的邻域及对应的局部改进搜索算法。
第一类邻域来自旅行商问题的文献，主要基于边的互换，从而对每条路线分别进行优化。Lin（1965）将λ-opt邻域定义为通过去除和插入λ条边而得到的解的集合，该邻域的规模为|N λ-opt |。文献中常见的此类邻域包括2-opt、3-opt和Or-exchange，其中Or-exchange邻域是通过对多个有限长度的客户访问序列进行重新排序，从而组成一些3-opt邻域的子集。图2-1给出了2-opt和Or-exchange的一些例子。
图2-1 典型邻域（1）
其他的局部改进搜索算法则通过路线之间的边的互换或客户位置调整从而对多条线路同时进行改进。最常见的调整方式为将一条路线上的一个客户插入到另外一条路线中，这种方式所产生的邻域被称为插入邻域。而对调邻域则是互换两条路线上的两对客户位置。2-opt * 邻域是通过对两条路线上两对边的删除和重新插入而形成的。该邻域有时也被称为cross邻域。图2-2给出了以上三种邻域一些例子。以上三种邻域的规模为O（n 2 ）。
图2-2 典型邻域（2）
最后一类邻域是交叉互换（Cross-exchange）邻域（Taillard等，1997），主要通过将两组客户序列进行互换。这一邻域也可以看作插入、对调和2-opt
*
的一般形式。还可以对s
1
、s
2
两个客户序列进行逆序处理从而得到更大的邻域，该邻域称为ICross邻域（Braysy，2003）。Cross和ICross邻域的规模为O（n
4
），所以搜索成本也相对较大。因此，在实际应用中，通常会将互换的客户序列限制为L
max
，这样整个邻域的规模也就变成O
。由于都涉及将两条路上少于λ个客户的一组客户序列进行互换，Cross和ICross邻域也可以看作是λ互换邻域（Osman，1993）的两个特例。图2-3给出了其他一些常用邻域的例子。其中，a为一点移动（One-point Move），即将现有的一个节点（客户）移动到一个新的位置；b为两点移动（Two-point Move），即互换两个节点（客户）的位置；c为2-opt；d为Or-opt；e为3-opt；f为三点移动（Three-point Move），即从当前路径中移除三条边，然后用新的三条边来代替；g为Cross互换。
图2-3 典型邻域（3）
对于大规模路径优化问题而言，即使是对规模为O（n 2 ）的邻域进行评估也极为困难，因此现有文献通常会引入邻域的精简过程。常用的一种邻域精简方法是粒状搜索，即只对一组空间相关的邻域列表中的点进行计算，同时只考虑该邻域里表中各个点之间的位置改变（Move）（Gendreau等，1992；Johnson和McGeoch，1997；Toth和Vigo，2003）。另外一种对邻域规模的限制方法是顺序搜索，最早由Christofides 和Eilon（1972）在旅行商问题文献中提出，并由Irnich（2006）将其推广到考虑时间窗的路径优化问题中去。该方法的主要思想基于以下事实：所有改进的λ-opt邻域都可以分解为一系列边的互换（φ 1 ，φ 2 ，…，φ k ），与之对应的解的改进为（g 1 ，g 2 ，…，g k ）。其中，所有前k（≤λ）个边的互换构成的子集都具有正向的改进。该方法可以迅速去除很多未来不会带来改进的解的邻域。
局部改进搜索算法中备受关注的问题就是位置改变（Move）、线路可行性和成本的评估，这也是多数局部改进搜索算法所面临的瓶颈问题。文献中也提出了一些减少CPU计算时间的技术方法，如可以将路线或客户的评估存储到列表和哈希表中。类似的方法常用来求解不同种类的多属性路径优化问题。
大规模邻域在现有文献中也有广泛的应用。Lin和Kernighan（1973）提出了解决旅行商问题的大规模邻域方法。Glover（1992、1996）提出的Ejection Chain的方法在考虑时间窗的路径优化问题中得到了广泛的应用。该方法的主要思想是通过将现有解中的一些边和其他的一些边交替构成一个闭环从而找到一个可行且比当前解更好的解。该方法可以看成是大规模λ-opt邻域。与此类似的方法是由Thompson和Psaraftis（1993）提出的环形转移算法，主要通过对b条路中的k个客户进行环形转移来搜索更好的解。可以利用负成本环去除问题来求解改进邻域搜索问题。虽然负成本环去除问题也是NP难问题，但是可以通过现有的启发式算法有效求解。
其他破坏再重建邻域（Shaw，1998）主要通过删除序列中的部分客户并将其重新插入其他序列从而构成新的解。由于破坏和重建的方法不同，这种邻域的性质也有所不同。重建过程可以通过启发式算法、约束规划或整数规划来完成。De Franceschi等（2006）和Toth（2008）将Sarvanov和Doroshko（1981）提出的求解旅行商问题的算法进行扩展，提出了一种通过固定部分客户，然后将其他客户插入到固定客户序列而产生的邻域，该邻域可以通过整数规划来求解。
元启发式算法最早由Glover（1986）提出，指代所有在首次找到局部最优解后继续进行搜索的启发式算法的集合。简而言之，元启发式算法就是指导启发式算法进行搜索的启发式算法。从现有文献中可以看出，元启发式算法也已成为组合优化领域的一个核心研究方向。根据算法中新解产生的机制可以将元启发式算法分为三类：基于邻域的元启发式算法；基于群体的元启发式算法；混合元启发式算法。其中，基于邻域的算法主要通过不断探索某一局部最优解周围的邻域从而产生新的解；而基于群体的算法则通过现有解的不同组合进而产生新的解；混合算法则是将不同类型的元启发式算法进行综合利用。
（1）基于邻域的元启发式算法。
模拟退火算法（Simulated Annealing）最早由Kirkpatrick等（1983）和Cerny（1985）提出。该算法的主要思想是通过按照一定概率来接受比当前解更差的解从而克服局部改进算法快速收敛于局部最优解的缺点。算法主要通过温度参数来控制新解被接受的概率。温度越高，差的解被接受的可能性越大。算法通过降温机制来调节温度参数。算法开始阶段，较高的温度有利于算法通过接受比当前解更差的解来搜索更广的邻域，逐渐降温使得算法更倾向于接受比当前解更好的新解，从而提高解的质量。对于考虑时间窗的路径优化问题，较为有效的算法是Record-to-Record Travel（RTR）算法。该算法记录当前找到的最优解，同时在多样化阶段接受比当前解稍微差一些的解，但是拒绝那些差很多的解。
禁忌算法（Tabu Search）是最早由Glover（1986）提出的一种局部搜索元启发式算法。算法的具体细节可以参考Glover（1989）、Glover（1990）、Herz等（1987）、Glover 和Lagure（1997），以及Gendreau（2003）。禁忌算法通过在每一次迭代中从当解移动到邻域中最好的解来对解的空间进行搜索。与经典的下降算法不同的是，当前解可能会在迭代过程中变差。接受新的较差的解是为了避免重复搜索之前已经搜索过的解。这样就可以确保继续对新的区域进行搜索，从而避免算法停止于局部最优解，进而找到更理想的解。为了避免循环出现，最近搜索过程中发现的解的一些属性会被列入禁忌列表中作为禁忌属性。这些属性被列为禁忌属性的时间长度称为禁忌周期，它可以有多种变化。在某些条件满足时，禁忌状态可以被撤销，它被称为特赦准则。例如，当禁忌解比之前所有的解都好的时候。
禁忌算法的搜索轨迹是以高质量的邻域为基础，同时该算法具有短期、中期和长期记忆等学习能力，这一学习能力可以起到类似于其他算法中随机性的效果。禁忌算法的决策过程包括两种机制：一是通过短期记忆拒绝那些最近搜索过程中已经访问过的解的元素（禁忌元素），从而避免搜索过程中出现循环；二是接受新解的标准为目标函数最好或是包含某些特定元素。中期和长期记忆在强化阶段和多样化阶段都很关键。在强化阶段，通常会在高质量解的邻域进行搜索，并且主要关注那些具有高质量元素的解。而在多样化阶段，中长期记忆可以帮助算法探索很多未知邻域或是不常出现的元素所在的解。目前，强化阶段和多样化阶段的权衡仍是一个至关重要的问题。
禁忌搜索算法在考虑时间窗的路径优化问题中有较好的应用，并以此为基础出现了一系列有效的元启发式算法，包括禁忌路线（Gendreau等，1994）、自适应记忆算法（Taillard，1993），以及联合禁忌搜索（Cordeau等，1997）。禁忌路线和联合禁忌搜索算法主要通过经常出现在解中的元素进行惩罚和奖励来达到强化和多样化的效果。自适应记忆算法则是通过记忆不断指引算法去搜索包含高质量序列的新解附近的邻域。
此外，禁忌算法的思想也对其他元启发式算法具有一定的启示作用。导向性局部搜索由Vondouris 和Tsang（1999）提出，并应用到考虑时间窗的路径优化问题中。该算法就是利用长期记忆对经常出现的解的元素进行惩罚。在这种情况下，通过惩罚函数来改进搜索空间，避免算法收敛到局部最优解的一个有效方法。类似的有，特赦准则在基于属性的爬山法中也起到了至关重要的作用。
Garcia等（1994）首先将禁忌算法应用到了考虑时间窗的路径优化问题中。作者展示了该算法的一种并行计算算法的实现。他们提出的禁忌算法相对简单。首先利用Solomon 的I1插入式启发式算法来构造初始解，然后利用2-opt * 和Or-opt互换对初始解进行改进。自此之后，很多学者利用更为复杂的多样化和强化技术对禁忌算法进行改进，如研发更有效的最小化路径数量的策略，更为复杂的后期优化算法，与其他启发式算法（模拟退火算法和遗传算法）相结合，并行计算及允许不可行解出现等。
初始解通常利用成本最低插入式算法，常用的有Solomon I1插入式启发式算法。Chiang和Russell（1997）是一个例外，他们利用Russell（1995）中的插入式启发式算法的平行版本来进行初始解的构造。De Backer和Furnon（1997）及Sohulze和Fahle（1999）则利用Clarke 和Wright（1964）中的成本缩减算法来构建初始解。Tan等（2000）应用改进的Solomon插入式启发式算法，Cordeau等（2000）则应用由Gillett和Miller（1974）最早提出的改进版的Sweep算法来构建初始解。Lan等（2003）首次提出了Holding-list 的概念，即一种存放未服务客户的数据结构。在算法开始时，所有的客户都在Holding-list中，然后利用简单的重置和互换操作将客户分配到不同的路线中去。
在构建初始解之后，则要通过一种或多种邻域结构及最好接受策略来对初始解进行改进。前面的介绍中已经提到了较为广泛和效果较好的邻域搜索算法。这样的算法包括：2-opt、Or-opt、2-opt * 、重置、互换、以及Cross-，GENI-等。
为了降低搜索的复杂度，许多文献提出了限制搜索领域规模的特殊策略。例如，Garcia等（1994）只允许在当前解一定距离内的边的互换操作。Taillard等（1990）则利用每条线路中心对应极角，将当前解分解成一系列互斥的子线路。然后利用禁忌算法对子线路进行搜索。最后将利用禁忌算法找到的新解进行组合构成最终的解。另外一种可以提高搜索速度的方法就是在多个处理器上进行并行算法。例如，Badeau等（1990）将Taillard等（1997）中的算法进行了两级并行计算，结果表明并行计算在不降低解的质量的前提下大大提高了运算速度。其他描述并行算法的例子可以参考Garcia等（1994）及Sohulze和Fahle（1999）。另一方面，为了突破由于时间窗约束带来的邻域之间的壁垒，一些学者允许在搜索过程中接受不可行解。例如，Brandau（1999）、Cordeau等（2001），以及Lau等（2003）都允许当前解违反各种约束，如载重、工作时长、时间窗约束。违反约束的程度在目标函数中作为惩罚函数出现，对应的惩罚参数则根据算法进程进行动态调整。
由于线路数量通常被认为是最重要的目标，一些学者则利用不同的策略来对路线数量进行优化。例如，Garcia等（1994）和Potvin等（1996）中的算法都通过利用Or-opt互换将路线中的客户进行合并和整合。类似的，Sohulze 和Fahle（1999）中的算法也试图将少于3个客户的路线中的客户移动到其他路线中从而减少路线数量。在Lau等（2003）中，作者在搜索过程中对路线数量设置了上限。
多数禁忌算法都利用特殊的多样化和强化策略来指导搜索。例如，Rochat和Taillard（1995）首先提出了“自适应记忆”的概念。自适应记忆是用来存储搜索过程中最优解的路线库。它的作用是从该库中选择一些路线并对其进行组合从而构造新的初始解。选择过程是依据概率进行的，一条线路被选到的概率与其对应的解的优劣程度成正比。之后将利用禁忌算法对被选中的线路进行改进。此后，Taillard等（1997）利用相同的策略对将时间窗作为软约束的路径优化问题进行求解。在这个问题中，配送延迟是允许的。只是配送延迟程度会作为惩罚函数出现在目标函数中。Taillard等（1997）也通过对经常出现的互换操作进行惩罚来对搜索进行多样化，并且通过Solomon I1插入式启发式算法对最优解中的客户顺序进行调整来对搜索进行强化。Chiang 和Russell（1997）、Sohulze 和Fahle（1999）及Cordeau等（2001）采用了相同的方法来进行多样化的搜索，但Chiang和Russell（1997）中的强化阶段则是通过禁止某些客户移动到某些路线来降低等待时间。Sohulze和Fahle（1999）也提出了一种类似于自适应记忆的策略，即所有由禁忌算法产生的路线都被放到一个库中，然后在局部优化结束后，最差的解会被新解代替。而新解则是通过利用Beasley（1990）中基于拉格朗日松弛算法的启发式算法对集合覆盖问题进行求解得到的。
Carlton（1995）、Chiang和Russell（1997）对一种互动式的禁忌算法进行了测试。该算法根据当前搜索状态，动态调整其中参数的取值，从而避免循环和过度限制的搜索路径。具体而言，如果相同的解频繁出现，则禁忌列表的长度要增加；而如果无法找到可行解，则禁忌列表的长度要减小。Tan等（2000）在每次找到局部最优解后会通过一系列随机的λ-互换和2-opt * 算子对搜索进行多样化。同时，搜索过程中找的精英解会作为初始解重新开始新一轮的强化搜索。Lau等（2001）讨论了一种基于约束的多样化技术，将带有时间窗约束的路径优化问题建模成为一个线性的约束模型，并通过简单的局部搜索进行求解。
最后，也有许多学者利用各种后期优化来进行求解。例如，Rochat和Taillard（1995）利用精确求解一个集合划分问题，将自适应记忆中的最优解进行整合从而得到最后的解。Taillard等（1997）利用GENIUS启发式算法的一种变形算法来求解带时间窗的路径优化问题。类似的，在Cordeau等（2001）中，对于n次迭代之后得到的最优解，后期优化采用了对每条路线应用带有时间窗的旅行商问题的启发式算法。下表中总结了禁忌算法的主要特点，其中列出了初始解的启发式算法、邻域搜索算子及是否利用特殊策略对路线数量进行优化。
表 禁忌算法主要特点
变邻域搜索算法（Mladenovic和Hansen，1997）的理论基础是局部最优解与邻域之间的对应关系。因此，在搜索过程中改变邻域的性质，至少改变部分参数，就可以帮助找到更高质量的解。其中，邻域评估和解的接受准则既可以为确定性的也可以依据概率分布而产生。此外，额外的扰动机制和长期记忆在求解考虑时间窗的路径优化问题中也经常用到。因此，基于变邻域搜索算法的混合元启发式算法也极为常见。
由Pisinger和Ropke（2007）提出的大规模邻域搜索算法通过破坏再重建的方式利用不同邻域的优势进行求解。该算法根据搜索过程中的表现从而自适应调整不同邻域的使用频率。此外，迭代局部搜索算法交替进行局部改进搜索和扰动。局部改进搜索最终可以找到一个局部最优解；而扰动阶段可以使算法跳出局部最优解，探索更广的邻域而避免算法收敛到局部最优解。然而扰动的火候掌握对算法的成功至关重要。Prins（2009）将迭代局部搜索巧妙地应用到考虑时间窗的路径优化问题中并取得了较好的效果，其算法主要通过对当前解进行局部搜索和扰动得到更多的解，而其中最好的解将作为下一轮的当前解。
（2）基于群体的元启发式算法。
基于群体的元启发式算法多来源于自然界中一些演化机制。遗传算法和演化算法在20世纪50年代末提出，并由Holland（1975）进一步发展。这一类算法通过优胜者选拔、交叉和变异等方式将自然法则和优胜劣汰的规则应用到解的产生过程。在演化算法中，搜索策略也常随着解的变化而发生演变。经典的遗传算法和演化算法计算速度较慢，因此会通过其他一些机制来改善计算速度，如局部搜索，这些机制也被称为“教育算子”。这样的混合算法被称为遗传局部搜索算法或是文化基因算法。
有些加强的遗传算法在考虑时间窗的路径优化问题基础算例中表现非常好。许多成功的遗传算法首先创建一条巨型路线，然后通过聚类算法将其划分成多条路线。该算法基于先排序后分配的构造算法，这样可以大大缩减可行域。同时，也可以利用简单的交叉对解进行扰动。在遗传算法的应用中，群体多样性是一个至关重要的问题。
其他的基于群体的算法包括路径重连算法和散射搜索算法（Glover，1977；Resende等，2010）。这两种算法主要是利用解的重新组合。这两种算法的思想更倾向于在已有解的基础上进行重新组合而非随机扰动。同时，它们与遗传算法最大的不同在于候选解的数量和用来交叉的解的数量较小。路径重连算法通过初始解和导向解进行重新组合。其中，初始解和导向解都来自精英解库。这一过程使得导向解的属性不断被融合到初始解中，从而产生一条连接这两种解的轨迹，然后算法可以从该轨迹上寻找更好的解。而散射搜索算法则是将多个解进行重新组合而寻找更好的解。
蚁群优化算法的思想来源于蚂蚁觅食的群体行为。其中，蚂蚁的个体行为（即通过搜索历史来收集信息）用来进行初始解的构造。该类群优化算法同时也利用特定的学习机制，如神经网络和人工免疫系统等，有时也会与局部搜索相结合。
遗传算法是基于群体遗传学的一种适应性搜索启发式算法。这一算法真正应用于求解复杂的实际问题则是在De Jone（1975）和Goldberg（1999）中。具体的算法细节可以参考Muhlenbein（1997）和Alander（2000）。遗传算法通过一组个体组成的群体的演化，利用迭代来创造新一代的后代，直到特定的收敛条件满足时停止。这一类的条件可以是演化代数的数量或者是群体中相同个体的同质性。产生的染色体中最好的将被解码，从而得到相应的解。
新一代个体产生的过程通常包括4个阶段：表示阶段、选择阶段、重组阶段和变异阶段。对于解集的表示，主要包括将一个解的主要特征编码成染色体，以及对群体中的单个个体成员进行定义。选择阶段主要是随机从群体中选取两个父辈个体以进行组合。单个群体成员被选取的概率与其在保持遗传多样性前提下的遗传质量的适合程度成正比。这里，适合程度通常用来度量在搜索过程中的利润、效用，或是最优化的特性。重组阶段主要是利用所选取的父辈个体的基因来产生后代个体。而变异阶段主要是通过对新产生的后代个体的基因进行改进，从而进一步搜索解空间以保持遗传多样性。变异的概率是相对较小的。新一代个体的产生是通过重复进行选择、重组和变异过程，直到产生一组特定的新的染色体集合。新产生的染色体集合，以及将要被取代的染色体集合取决于选择策略及所应用的遗传算法的类型。有些情况下，所有的染色体都将被新的染色体集合所取代，而另外一些情况下，则会保留部分父辈群体中的染色体。因此，为了进行更有效的搜索，算法需要在遗传质量和群体多样性之间找到一个较好的平衡点。
Thangiah等（1991）首先将遗传算法应用到带时间窗约束的路径优化问题中。其提出了一种利用遗传算法找到一些客户集合，然后利用先分类后路径优化的方法进行求解。首先利用成本最低插入式启发式算法进行初始解的构造，然后通过λ-互换对初始解进行改进。此后，很多学者对于利用遗传算法来求解带时间窗约束的路径优化问题都进行了研究。几乎所有的文献都是将遗传算法与构造启发式算法、局部搜索算法，以及其他元启发式算法进行结合。
Homberger和Gehring（1999）利用两种演化算法对带时间窗约束的路径优化问题进行求解。遗传算法、演化编程和演化策略共同构成了一类演化算法。根据定义，这三种算法的差别在于表示阶段和变异阶段。在Homberger和Gehring（1999）的演化策略中，个体的表示形式包括一个被称为“策略参数”的向量和一个解向量，而这两个组成部分都是通过重组和变异进行演化的。在带时间窗约束的路径优化问题的应用中，策略多数指的是选取的局部搜索算子的使用频率及指代最小化车辆数量和最小化距离的目标选择的0-1变量。在重组阶段，每一对父母只产生一个后代，这样，总共产生λ>μ个后代，其中μ为群体规模参数。最后根据适合性选取λ个后代构成新的群体。
（3）混合元启发式算法。
混合元启发式算法通常将多种元启发式算法结合起来，利用每种算法的优点从而达到更好的求解效果。各种算法的混合形式多种多样，可以是多个算法顺序进行，也可以将一种算法的某种元素加入到另外一种算法中去。此外，混合元启发式算法也可以将多种元启发式算法和数学规划、约束规划及树搜索等方法结合起来。就像前面提到的元启发式算法本身就是指导其他启发式算法的启发式算法，其本质就是混合算法。而我们这里将混合元启发式算法单列出来，是想讨论一类可以利用不同算法的思想进行融合从而探索更为广泛的求解策略以找到更好的解的方法。许多算法将邻域搜索的概念与其他方法融合。最近的研究中常在邻域搜索算法中加入重新开始、依照概率接受较差解、变邻域搜索或是长期记忆等元素。基于群体的算法和基于邻域的算法也常常进行混合从而得到更好的算法。
（4）并行和协同启发式算法。
并行和协同启发式算法主要是通过利用多个处理器进行并行计算从而更有效地对问题进行求解。这对于求解路径优化问题而言非常有效。根据并行计算的机制不同、不同任务之间的沟通方式及全局搜索如何进行可以对并行算法进行分类。最简单的可以将其分为低层次和高层次的并行算法。低层次的并行算法通常是将问题分解为多个相对独立的部分，从而利用并行资源进行计算。为了提高算法效率，并行计算主要是针对计算中的瓶颈步骤。这通常是指对位置改变的评估等。而高层级的并行算法则包括将决策进行划分，从而将问题进行分解，或是对一个或多个搜索空间利用多个处理器进行并行搜索。后一类算法中最常见的是并行独立搜索算法，主要通过多个独立算法分别进行并行搜索，然后在所有最优解中找到最好的解。并行算法的优势除了可以将顺序求解变为并行作业外，更主要的是通过计算过程中的信息共享来建立合作算法。在更高阶的算法中，甚至可以利用数据交换从而得到新的信息以供算法进行利用。合作策略的主要特征包括共享信息的性质、信息沟通的频率及接受信息的利用率等。