摘要
与传统数学规划问题不同的是复杂优化问题更多的涉及到了现实应用中的复杂需求。这类问题通常包含着求解速度要求高、目标函数和多个约束条件之间关系复杂、以及环境的不确定或动态变化等复杂特性，因此传统的优化方法已经难以有效处理这些复杂优化问题。由于智能优化算法不依赖于精确的数学模型，并且已经成功应用于许多复杂问题领域，本文借助于智能优化算法的原理，通过设计具体的优化模型和高效的求解算法来有效应对复杂优化问题当中的复杂需求。具体的，本文主要研究了大规模连续优化问题、新高改走班排课问题、容量受限车辆路径规划问题、订单指派与取送货问题等实际案例。本文的主要工作致力于根据问题特性:设计高效的启发式规则和局部搜索策略;使用多阶段优化方法分解问题求解难点;采用多目标优化算法平衡问题的目标冲突;通过设计交互式在线优化框架来减轻实际应用情景中的不确定和动态变化带来的问题难度。本文的主要研究创新可以概括如下: 1.针对大数据多目标优化问题，提出了一种基于梯度方向的多目标密母算法。该算法中将分解后的目标函数的梯度信息引入到了局部搜索当中。借用低复杂度的梯度方向计算，有效降低了目标函数评价次数，提升求解速度。通过在大型优化问题测试集上实验，验证了提出的局部搜索算子适用于不同的多目标进化算法框架和分解函数。 2.在新高考改革的要求下，高中阶段的教学模式中出现了学生走班。已有排课方法面临学生上课冲突多、时段变换不灵活等困难。在这种模式下，现有求解算法很难满足老师教案平齐、课时分布均匀、以及同时上课等需求。提出了一种多阶段的排课方法，采用天课时分配的方式将课时冲突转化为是否可以排课的判定，降低了排课过程中课表变换的阻力。此外设计了一种针对课时分配的爬山算法。实验结果验证了提出算法的有效性，和在实际应用中的有效性。 3.灾后救援场景下，应急物资运输调度过程往往面临现场环境存在不确定或信息未知的困境。针对道路通行时间不确定这一现状，使用在线优化方法将不确定信息发现过程融入到车辆路径规划中，并采用多目标进化算法平衡车辆运行过程中信息增益和运输效用之间的冲突。为测试提出算法性能，构建了一个交互式优化实验环境，将运输实际效果和环境信息周期性的反馈给决策者，并以此为基础进行下一周期的车辆路径规划。实验结果表明，使用多目标进化算法和密母算法混合的策略，能够高效的满足实际应用需求。 4.现实中的城市小件物流配送过程是一个典型的多车动态取送货问题。订单的产生时刻、订单时限需求、和车辆的可用状态是此类问题考虑的核心因素。针对问题的这些特点，以多周期调度的方式建模了这一过程，使用分支限界方法实现了车辆路径规划，并提出了基于大规模邻域搜索和订单聚类的订单分配方法。搭建了一种适用于多周期优化的动态实验环境。结果表明订单聚类算法能够以较小的运算代价取得与邻域搜索相近的结果，同时压缩了订单累计超时。 本文采用理论研究和应用研究相结合的方式来处理现实中优化问题的复杂需求。从理论层面上提出了基于梯度方向的多目标密母算法，从应用层面上解决大规模数值优化问题、时间表排布问题、车辆调度与路径规划问题中的多种不同复杂需求。具体的，设计新的局部搜索算子提升了求解速度、设计了多阶段优化模式分解了复杂约束条件带来的求解难点、设计了多目标优化方法平衡了信息发现与运输效用最大化等不同目标、将聚类算法与多周期调度相结合以求解动态优化问题。最终验证了智能优化方法可以更加高效的满足这些现实问题的复杂需求。
NETL