第 1 章 绪论
1.1 课题研究背景及意义
伴随着物联网、云计算等应用领域新技术的飞速发展，越来越多的优化组合问题涌现在计算机科学家面前。在现有的计算复杂性理论下，大多数这类问题的时间复杂度是指数级的，传统的精确算法（Exact Algorithm）已不适合求解这类问题 1。因此，很多学者开始研究在较短时间内能获得近似最优解的启发式算法（Heuristic Algorithm）。启发式算法大致可分为简单启发式算法（如爬山法、贪心法等）和元启发式算法 2（如蚁群算法遗传算法、粒子群算法等）。现有问题的求解思路在各应用领域中面临着越来越大的挑战。现有启发式算法对算法设计者有较高要求，他们既要掌握各种算法的设计技巧，又要具有足够的领域知识；传统做法是针对某一问题设计一种专门算法，并在一组测试实例上进行评价（包括最好结果、平均结果、解的方差等）。实际上，对于求解问题的具体实例，这种做法存在着不足之处。单一算法无法保证在所有问题（实例）上始终优于其他算法。由于具体实例千差万别，总有某些算法性能较差。针对上述问题，一种被称为超启发式算法（Hyper-Heuristic Algorithm）的概念被提出，并迅速引起国际学术界的高度关注。最近两年，智能计算领域的三大著名国际会议（GECCO'09、PPSN'10 和 CEC'10）分别举办了专门针对超启发式算法的研讨会（Workshop 或 Session）。另外，智能计算领域的两大学报《启发法（Journal of Heuristics）》和《演化计算（Evolutionary Computation）》也组织了专刊，集中介绍超启发式算法的研究进展。
超启发式算法具有较好的移植性，被广泛应用于各个领域，因此本文将超启发式算法应用在 LRP 问题上。在传统的 LRP 问题研究中，多数的研究人员在选取目标函数时，只考虑了选址成本，运输成本，客户需求等单一目标或者简单目标，而随着国家对节能减排的要求不断增加，实现碳排放的降低更加符合我国现在的国情，符合我国碳排放市场的建立，碳排放已经成为传统物流公司必须解决的关键问题。本研究即是基于绿色角度的 LRP问题研究，将配送中心选址问题和配送车辆选择和路径调度等子问题集成，以减少碳排放量为主旨，深入挖掘配送中心选址、客户需求量、车辆行驶距离、车载量，道路情况等因素对车辆运行过车的碳排放量、总运输运营成本的影响。并通过对超启发式算法的研究，
使得在短时间内获得一个碳排放量降到一个理想的值，从而让企业获得更大的收益，同时污染排放得到降低，因此，其成果具有很重要的现实意义。
.............................
1.2 国内外的研究现状及趋势
1.2.1 超启发式算法研究现状
超启发式算法[1]（Hyper-heuristic Algorithms）是近年才发展起来的一种新型的启发式算法，可以简单阐述为“寻找启发式算法的启发式算法，具有更高级智能系统的特征，是未来启发式优化领域研究的主流方向之一，其严格的定义如下：超启发式算法提供了一种高层次启发式方法，通过管理或操纵一系列低层次启发式算法（Low-Level Heuristics，LLH），以产生新的启发式算法。这些新启发式算法被用于求解各类组合优化问题。
图 1-1 为超启发式算法的概念模型，该框架分为两个层面，在问题域层面上，应用领域专家根据具体问题的性质，设计一系列的底层次启发式算法（即 LLH)，组成底层次启发式算法集（即 LLH 算法集），并提供问题定义、问题表示、初始解、评估函数等信息；在高层次启发式算法层面上，程序设计者设计高效的超启发式算法管理操纵机制，在每一个决策点，运用问题域所提供的算法集和问题特征信息（一般为评估函数的返回值），构造出新的或选择已有的启发式算法，应用到具体的问题实例上。由于两个层面之间实现了领域信息的屏蔽，高层的超启发式算法是不知道问题域层的问题实例的，换句话说，超启发式算法是不知道现在所处理的是哪种问题的哪个实例的。因此，只要修改问题域的算法集和问题定义、问题表示、初始解、评估函数等信息，超启发式算法可以方便地移植到新的问题上。图 1-2 为超启发式算法的框架，图中底层启发式算子是领域专家设计的各种针对具体问题的算子，上层的选择策略和接受准则是智能计算专家设计的调用底层算子的算法。该框架将一个初始解通过选择算子、应用算子和接受准则来生成新的解，在这些新的解当中选出最优解。图 1-3 为超启发式算法常见选择方法和接收准则，例如选择方法有简单随机、选择函数、贪婪选择等等，接受准则有接受所有解、只接受改进解、门槛接受法等等。
..........................
第 2 章 基于构造的选择式超启发算法
2.1 引言
车辆路径问题属于组合优化问题，也是一类 NP 完全问题，选址路径问题更是包含了车辆路径问题。一般求解这类 NP 完全问题，人们通常采用启发式算法来求解。基于构造的选择式超启发算法能够快速获得问题的可行解，在小规模案例时能获得质量较优的解。
基于构造的选择式超启发式算法的目的是构建目标问题的可行解，一般从一个空的解集开始，通过高层的策略从一组特定的底层构造启发式算法中（特定问题领域）选择算法逐步建立问题的可行解。当成功生成一个可行解后，算法即终止。传统的基于构造的选择式超启发算法已经在生成调度问题（Production schedule）、教育排课问题（Education schedule）、装箱问题(Pinpacking)等问题领域得到了成熟的应用，但对于车辆路径问题这一领域还没有被广泛的应用和研究。
VRP 是 LRP 的子问题，TSP 是 VRP 的基本问题，这三者存在相似之处，也存在不少差异。而蚁群算法在 TSP 问题上取得了诸多成果，根据文献[52]，当城市规模在 30 以下时，遗传算法比蚁群算法有较好的结果，当城市规模在 30-70 之间时，用蚁群算法可以得到比遗传算法更理想的解，当遇到更大规模的 TSP 问题时，就要考虑改进的蚁群算法或者是蚁群算法和其他算法结合的新算法。因此，将蚁群算法的一些策略和算法提取出来，成为一个超启发式算法框架下的一个算子是十分有必要的，这也是本章的主要工作之一。
.........................
2.2 自适应蚁群构造算子
2.2.1 转移规则和信息素更新规则
传统应用于 TSP 问题的蚁群算法无法直接应用到 VRP 问题和 LRP 问题，主要存在以下差异。首先在 TSP 问题中，每只蚂蚁要经过所有的结点，而每只蚂蚁的起始地点可以是任意结点，而在 VRP 问题和 LRP 问题中每只蚂蚁承担一个“送货”责任，所以起始地点必定是固定的，而且终点也是固定的，必定会回到最初的起点（即仓库）。其次，鉴于每只蚂蚁的负载有限，所以每只蚂蚁并不是要遍历所有结点，而是把是否返回起点作为结束标志，这一个差异在算法中的具体体现就是allowedk 的确定问题。在 VRP 问题和 LRP 问题中，allowedk 中的结点必须满足蚂蚁容量的硬性约束，
.......................
3.1 引言 ....................................... 23
3.2 算子的介绍 .................................... 23
3.3 基于初始解表的超启发式算法 ............................ 24
第 4 章 基于元启发的超启发式算法 .................................. 35
4.1 引言 .............................. 35
4.2 算子的介绍 ................................... 35
4.3 基于蛙跳算法的选择策略 ........................... 36
第 5 章 超启发式算法在低碳 LRP 问题上的应用 .................................... 49
5.1 前言 ................................. 49
5.2 问题与模型 ................................ 49
5.3 数值仿真与分析................................ 50
第 6 章 超启发式算法原型系统设计开发
6.1 前言
目前我国现实中存在大量的车辆路径类问题，而大多数实际情况都依靠每一位从业人员通过个人的经验和直观感受去判断和选择所行驶的路径。因此，存在大量的不确定性和不稳定性。随着物流行业的不断发展，对智能路径提出了更高的要求，随着软件与硬件技术的飞速发展，越来越多的智能调度系统被应用于各类场景。本章基于上述的需求以及现有的计算机技术，设计实现了超启发式算法原型系统，介绍了系统的各个功能模块和设计思路，为以后做系统打下了基础。
根据本文前几张的介绍，鉴于超启发式算法独特的框架以及它良好的跨领域能力，因此该系统需要能反映出该算法的上层策略和低层算子提供我们选择，以及能够应对各种不同的物理模型和目标函数。最终给出直观易懂的计算结果。系统界面需要大方简约、易于操作、人机交互友好等特点。
该原型系统需要有模型导入功能、数据导入功能、智能算法调参功能、低层启发式算法导入选择功能等等。
.........................
第 7 章 总结与展望
7.1 总结
超启发算法相比于传统的启发式算法而言，从获得解的质量和效率上来讲，并没有优势，甚至可以说某些时候不如传统的启发式算法。但传统启发式算法的参数设置和对具体模型有相当程度的依赖性，即传统的启发式算法以某一参数对某一类模型的求解非常有效，而对其他模型类求解效果不佳。因此，对于 LRP 的不同变种模型，一般需要构造相应的启发式算法参数来求解。但超启发式算法它致力于在搜索过程的某一给定状态下正确的选择合适的启发式规则或搜索策略[68]，具有解决问题的通用性，高层策略用来搜索合适的启发式算子，底层的启发式算子用以构造目标解。本文基于国家自然科学基金项目课题“基于生物群落超启发算法的绿色物流选址-路径优化调度研究”项目。该项目致力于采用智能高效的方法和模型来实现车辆路径问题低碳化。本文对于超启发式算法进行研究，提出了基于蚁群算法的构造算子，基于初始解表的上层策略以及基于蛙跳算法的上层选择策略。为不同车辆路径问题的模型提供了决策支持，具体工作如下：
1. 鉴于 VRP 问题和 LRP 问题的大多数实验都是通过随机生成的解来作为初始解的，使用自适应蚁群构造算子来构造初始解，该方法是来自于传统的蚁群算法，将它构造解的过程进行分解，放入超启发式框架，并提出了修复算子，解决蚁群构造算子构造过程中的不可行解的问题。用基于离线学习的上层策略来调用这些算子，生成的初始解比没有蚁群构造算子产生的初始解质量要高的多。
2. 针对构造式算法生成的初始解在大规模样例下质量不高的问题，提出了基于初始解表的上层策略，通过对初始解的迭代搜索，得到更高质量的解。初始解表的策略相比于单点搜索策略，能够在相同时间内，获得更高质量的解。
3. 对基于元启发的超启发式算法进行分析，研究蛙跳算法种群划分以及相似度的计算，提出了基于最长公共子序列的相似度计算方法。该方法更注重算子之间的相对排序而不是绝对排序，更能反映个体之间的相似性。实验表明该相似度计算方法使得蛙跳算法在相同时间内，能够获得更高质量的解。
参考文献（略）