论文部分内容阅读
路径规划问题（Routing Planning Problems，RPP）在航线设计、管道铺设和改善城市交通等现实应用中有着十分重要的作用。根据不同的限制条件和求解要求，RPP问题又可以细分为最优路径问题（Optimal Path Problems，OPP）、旅行商问题（Travelling Salesman Problem，TSP）以及带时间窗的旅行商问题（Travelling Salesman Problem with Time Windows，TSPTW）等多个子问题。RPP问题的求解属于典型的NP-HARD问题，因此其最优结果难以使用精确算法获得。由于群集智能搜索算法具有鲁棒性强，易获得全局解的特点，使得以蚁群算法为代表的群集智能算法，开始越来越多地被应用在RPP问题中，并取得了显著的成果。但是蚁群算法在求解大规模组合优化问题时，仍存在易陷入局部最优，收敛速度较慢，最终解质量不高等问题。为此，本文对蚁群算法求解RPP问题进行了深入细致的研究，主要工作包括：(1)提出了一种基于香味诱导和道路分级的蚁群算法求解OPP问题。该算法针对OPP问题具有唯一目标点的特性，首先通过模拟食物源（目的地点）散发出的一种吸引蚂蚁不断向其靠近的香味素，使蚂蚁的搜索具有指向性；然后对城市中的实际交通状况进行模拟，根据拥堵系数将路网中的道路分为不同的等级，使算法更加贴近现实问题，并结合动态的分级策略防止算法过早成熟。实验表明，本文算法相比基本蚁群算法，在最优解的质量及稳定性方面具有一定的优势。(2)针对TSPTW问题中最为突出的时间窗限制，首先结合物理学中的磁场理论设计出一种基于磁场描述的TSPTW问题模型，将复杂的路网规划问题转化为已有成熟体系的磁力计算问题，并依此修正传统蚁群算法的启发函数，使其迎合客户在时间方面的需求，降低算法陷入局部最优的可能性；其次，在得到最终解后，通过变异策略对未达到时间窗标准的顾客节点进行优化，提升最终解的质量。仿真实验结果表明，本文算法是积极有效的。论文通过蚁群算法和生物界新发现以及磁场理论的融合，完成了利用蚁群算法求解RPP问题的新探索，不仅是对RPP问题求解方法的丰富和完善，也促进了蚁群算法的发展。