定向问题(Orienteering Problem,OP)是一类特殊的NP-hard组合优化问题,其基本定义为:在指定的时间限制内有序的经过部分带有一定收益的点,使形成的路径最终获得的收益最大。由于良好的模型特性,定向问题越来越受到国内外研究学者的关注,其基本模型及变体被广泛应用于旅行规划、物流运输、救灾救险、选址规划等实际应用场景中,以优化资源分配,减少成本,获取最大利益。按照求解的路径个数,定向问题可分为单路径定向问题(OP)和多路径团队定向问题(team Orienteering Problem,TOP)。本文主要研究单条路径的优化问题。在介绍完国内外研究现状后,引出本文研究的收益可变定向问题,考虑收益变化的两种情况:一类是在整个时间限制内收益可变的定向问题,称为收益可变泛化定向问题;另一类是在时间窗内收益变化的定向问题,称为带时间窗收益可变定向问题。考虑收益可变情况的定向问题,进一步丰富了该领域的研究,同时将收益可变的定向问题应用到实际应用场景中,体现了其应用价值。具体的,考虑实际灾后搜救场景中,每个救援点有多种不同类型、不同重要程度的待救物资,且其价值会随着救援时间的延长而面临被毁的风险。需要在有限的时间内规划出最优搜救路线,以降低损失,确保利益最大化。因此有必要研究多类型收益随时间下降变化的优化问题—收益可变泛化定向问题(Generalized Orienteering Problem with Variable Profit,GOPVP)。此外,在旅游行程规划场景中,由于景点开放时间的限制,游客无法游完推荐的游玩时间,导致不能获得该景点的全部收益。针对这一情况,提出的带时间窗收益可变定向问题(Orienteering Problem with Time Windows and Variable Profits,OPTWVP)可以对该应用场景进行很好的模拟。分别对GOPVP和OPTWVP进行问题描述后,确立不同的收益最大化目标函数,并建立相关的数学模型。提出改进的遗传算法(Improved Genetic Algorithm,IGA),从问题的特点和算法本身的缺点两方面改善遗传算法,有针对性的求解两种不同情况的收益可变定向问题。由于定向问题是一类复杂的路径优化问题,设计快速高效的求解算法是目前国内外研究的重点和难点。本文提出一种改进遗传算法,融合多种局部搜索技术,从两个方面来改善对问题的求解:1)基于问题收益可变的特点,采用有针对性的启发式信息来帮助算法选择新的点,以此来构造有竞争力的路径;2)针对遗传算法本身易早熟、陷入局部最优的缺点,融合小生境思想和多个局部搜索操作避免算法过早收敛,同时改善算法的局部精搜能力。在多个公开数据集上进行仿真实验,并分别与研究进展方法比较,表现出了较好的性能,验证了算法的有效性。同时将算法和模型应用到真实数据上,表明算法的可行性。两类收益可变定向问题,丰富了定向问题领域的研究。同时收益变化的两种情况,也分别能够很好的模拟灾后物资救援和旅游路径规划两种场景,为实际生活中类似的问题提供决策参考,和更加高效、快捷的规划路径。