传统的路线规划者通常专注于寻找路网上两点之间距离最短的路线或花费时间最短的路线。然而,在实际情况下,特别是在智能城市的时代,许多与交通相关的数据可以被容易获得,近几年人们对基于不同标准进行路线规划的需求不断增加,例如在不超过给定的旅行时间预算(成本)的前提下,寻找一条累积风景值(效益值)最高的路线,这种问题可以看作弧定向问题(AOP)的变体,众所周知,这是一个NP难问题。本文针对一个更为实际的AOP问题展开研究,其中,路网中各路段的效益值和通过路段的行驶时间具有时间依赖性,这个问题被定义为双重时间依赖的弧定向问题(2TD-AOP)。在本文中,针对2TD-AOP展开了深入的研究,提出了两个解决方案。首先,本文提出使用模因算法来解决2TD-AOP,具体而言,给定旅行时间预算,规划了一条累积风景值(效益值)高的路线。这个过程大致分为两个阶段:初始化阶段和局部搜索阶段。在初始化阶段,通过搜索区域缩减、染色体编码和染色体解码操作产生种群中的个体;在局部搜索阶段,通过染色体选择、交叉和变异操作提高了种群中个体的质量。通过种群的迭代使种群中优秀个体所占的比例不断提高,最终在不超过时间预算的前提下,选择一条累积风景值最高的路线返回给用户。本文在模拟数据集和真实路网数据集上进行了实验评估,并与其他两种算法进行了比较,实验结果证实了模因算法的优势。其次,本文深入分析了模因算法解决2TD-AOP存在的不足,提出了一个潜力路段编码算法。利用该算法规划不超过时间预算的前提下,累积效益值高的路线。这个过程大致分为两个阶段:潜力路段查询表的建立和路段序列树的生成。潜力路段查询表记录了所有有效路段的时间划分图,基于出发时间与旅行时间预算,每个路段的时间区域划分为无效区、临界区和有效区,其中临界区是考虑到行驶时间的时间依赖性而建立的,潜力路段查询表避免了编码过程中对于路段有效性的重复判断;在路段序列树的生成阶段,本文中提出了潜力路段的判定规则,通过对潜力路段进行编码生成多条路段序列,这些序列会解码成为具体的行车路线,最终选择一条累积效益值高的路线返回给用户。本文在模拟数据集进行了实验评估,并与其他两种算法进行了比较,实验结果表明本文的算法在较短的运行时间内,取得了较好的路线规划结果。