论文部分内容阅读
物流规划由于在现实世界的大量应用一直受到广泛关注。现实世界的物流规划问题中存在着许多动态、随机的变化，因此不确定环境下的物流规划问题成为了物流领域的研究热点。进化算法能有效解决许多物流规划问题，因而研究者提出了许多进化算法来解决不确定环境下的物流规划问题。然而，这些进化算法在应对一些不确定环境下物流规划问题时的性能、效率方面仍存在不足。为此，本文针对性地提出了多种有效的新型进化算法来求解两类典型的不确定环境下的物流规划问题，分别为不确定道路网络下的避难所选址问题(USLP:shelter location problem under uncertainty of road networks)和有动态客户请求的动态车辆路径问题(DVRP:dynamic vehicle routing problem)。本文的主要工作由以下四个部分组成：
(1)本文提出了基于聚类的代理辅助多目标进化算法AR-MOEA+SA求解USLP。在使用进化算法优化USLP时，个体评价需要计算的疏散距离具有高昂的计算成本，因此本文在AR-MOEA+SA中提出了基于聚类的代理建模方法来近似计算个体评价时需要计算的疏散距离，以显著减少计算成本。并且，由于在USLP中常需要将大量居民区的居民疏散到避难所，本文还提出了聚类策略将高维代理问题转换为低维代理问题，从而高效地建立代理模型。实验结果表明，相比求解USLP的现有方法，使用AR-MOEA+SA求解USLP具有更优的解质量和计算效率。
(2)本文提出了基于需求覆盖多样性的进化算法ACO-CD求解DVRP。蚁群优化算法(ACO:ant colony optimization)在求解各种路径优化问题时十分有效，因而ACO-CD在蚁群算法的基础上设计。尽管基于多样性的方法是解决DVRP的经典方法之一，现有的基于多样性的方法却难以应对远离规划路径的新客户，而这类新客户往往会导致执行规划路径的行驶成本骤增。因此，本文提出需求覆盖多样性自适应方法来保持被路径覆盖客户的多样性，以便有效应对远离规划路径的新客户。在27个DVRP测试用例上的实验结果表明，使用需求覆盖多样性自适应方法解决DVRP能有效削减行驶成本，且ACO-CD相比现有的DVRP求解方法在解质量上也展现出了一定优势。
(3 )本文提出了基于成对相似性学习的蚁群算法PPL-ACO求解DVRP。尽管ACO-CD能有效应对路径规划中新出现的客户，但却无法快速地追踪动态变化的最优路径。因此，本文还提出了PPL-ACO高效追踪最优路径。在PPL-ACO中，成对相似性学习方法首先学习动态变化前的最优路径，预测变化后最优路径上的局部访问顺序，然后将预测的局部访问顺序融入ACO的搜索，大幅度缩小ACO的搜索空间，从而使ACO高效地追踪最优路径。在27个DVRP测试用例上的实验结果表明，PPL-ACO在效率和有效性上都明显优于四个现有的DVRP求解方法，且能快速有效地解决高达1000个客户的大规模DVRP。同样，在中国天津市南开区实际案例上的实验结果表明，PPL-ACO在解决现实世界DVRP时也比现有的DVRP求解算法更加高效、有效。
(4)本文提出了一种标准测试问题生成器为在线动态优化问题(OL-DOP:online dynamic optimization problem)生成标准测试问题集，并刻画了DVRP这类在线动态优化问题的特性。在OL-DOP中，动态问题常被认为由一系列的静态问题构成，而在过去环境里发现的静态问题的解会对未来环境里的问题产生影响。尽管OL-DOP在现实世界中广泛分布，却鲜有动态优化测试问题能表现出过去环境中发现的解对未来环境中问题的影响，因而也未能设计出针对OL-DOP的标准测试问题。因此，本文提出的OL-DOP测试问题生成器将设计不同类型的函数来定义每个环境中发现的解对下一个环境中问题的不同类型的影响，且动态程度可通过这些函数中的几个参数来调节。然后，本文使用OL-DOP生成器创建了一套OL-DOP标准问题测试集，该测试集由十个连续OL-DOP和两个离散OL-DOP组成。实验结果表明，OL-DOP测试集与现有DOP测试集不同，具有一种特殊的属性：时间欺骗性。并且，OL-DOP标准测试问题也能测试动态优化算法在处理过去环境中发现的解对未来环境中问题影响时的性能。
(1)本文提出了基于聚类的代理辅助多目标进化算法AR-MOEA+SA求解USLP。在使用进化算法优化USLP时，个体评价需要计算的疏散距离具有高昂的计算成本，因此本文在AR-MOEA+SA中提出了基于聚类的代理建模方法来近似计算个体评价时需要计算的疏散距离，以显著减少计算成本。并且，由于在USLP中常需要将大量居民区的居民疏散到避难所，本文还提出了聚类策略将高维代理问题转换为低维代理问题，从而高效地建立代理模型。实验结果表明，相比求解USLP的现有方法，使用AR-MOEA+SA求解USLP具有更优的解质量和计算效率。
(2)本文提出了基于需求覆盖多样性的进化算法ACO-CD求解DVRP。蚁群优化算法(ACO:ant colony optimization)在求解各种路径优化问题时十分有效，因而ACO-CD在蚁群算法的基础上设计。尽管基于多样性的方法是解决DVRP的经典方法之一，现有的基于多样性的方法却难以应对远离规划路径的新客户，而这类新客户往往会导致执行规划路径的行驶成本骤增。因此，本文提出需求覆盖多样性自适应方法来保持被路径覆盖客户的多样性，以便有效应对远离规划路径的新客户。在27个DVRP测试用例上的实验结果表明，使用需求覆盖多样性自适应方法解决DVRP能有效削减行驶成本，且ACO-CD相比现有的DVRP求解方法在解质量上也展现出了一定优势。
(3 )本文提出了基于成对相似性学习的蚁群算法PPL-ACO求解DVRP。尽管ACO-CD能有效应对路径规划中新出现的客户，但却无法快速地追踪动态变化的最优路径。因此，本文还提出了PPL-ACO高效追踪最优路径。在PPL-ACO中，成对相似性学习方法首先学习动态变化前的最优路径，预测变化后最优路径上的局部访问顺序，然后将预测的局部访问顺序融入ACO的搜索，大幅度缩小ACO的搜索空间，从而使ACO高效地追踪最优路径。在27个DVRP测试用例上的实验结果表明，PPL-ACO在效率和有效性上都明显优于四个现有的DVRP求解方法，且能快速有效地解决高达1000个客户的大规模DVRP。同样，在中国天津市南开区实际案例上的实验结果表明，PPL-ACO在解决现实世界DVRP时也比现有的DVRP求解算法更加高效、有效。
(4)本文提出了一种标准测试问题生成器为在线动态优化问题(OL-DOP:online dynamic optimization problem)生成标准测试问题集，并刻画了DVRP这类在线动态优化问题的特性。在OL-DOP中，动态问题常被认为由一系列的静态问题构成，而在过去环境里发现的静态问题的解会对未来环境里的问题产生影响。尽管OL-DOP在现实世界中广泛分布，却鲜有动态优化测试问题能表现出过去环境中发现的解对未来环境中问题的影响，因而也未能设计出针对OL-DOP的标准测试问题。因此，本文提出的OL-DOP测试问题生成器将设计不同类型的函数来定义每个环境中发现的解对下一个环境中问题的不同类型的影响，且动态程度可通过这些函数中的几个参数来调节。然后，本文使用OL-DOP生成器创建了一套OL-DOP标准问题测试集，该测试集由十个连续OL-DOP和两个离散OL-DOP组成。实验结果表明，OL-DOP测试集与现有DOP测试集不同，具有一种特殊的属性：时间欺骗性。并且，OL-DOP标准测试问题也能测试动态优化算法在处理过去环境中发现的解对未来环境中问题影响时的性能。