双重时间依赖的行车路线规划方法研究

发布时间：2024-06-05 05:15

　　传统的路线规划者通常专注于寻找路网上两点之间距离最短的路线或花费时间最短的路线。然而,在实际情况下,特别是在智能城市的时代,许多与交通相关的数据可以被容易获得,近几年人们对基于不同标准进行路线规划的需求不断增加,例如在不超过给定的旅行时间预算(成本)的前提下,寻找一条累积风景值(效益值)最高的路线,这种问题可以看作弧定向问题(AOP)的变体,众所周知,这是一个NP难问题。本文针对一个更为实际的AOP问题展开研究,其中,路网中各路段的效益值和通过路段的行驶时间具有时间依赖性,这个问题被定义为双重时间依赖的弧定向问题(2TD-AOP)。在本文中,针对2TD-AOP展开了深入的研究,提出了两个解决方案。首先,本文提出使用模因算法来解决2TD-AOP,具体而言,给定旅行时间预算,规划了一条累积风景值(效益值)高的路线。这个过程大致分为两个阶段:初始化阶段和局部搜索阶段。在初始化阶段,通过搜索区域缩减、染色体编码和染色体解码操作产生种群中的个体;在局部搜索阶段,通过染色体选择、交叉和变异操作提高了种群中个体的质量。通过种群的迭代使种群中优秀个体所占的比例不断提高,最终在不超过时间预算的前提下,选...

【文章页数】：64 页

【学位级别】：硕士

【部分图文】：

图2.2搜索区域缩减示例

重庆大学硕士学位论文2基于模因算法的双重时间依赖的风景行车路线规划方法11t0时刻车辆的平均速度。圆区域中包含的路段是从起点出发在时间预算内可达的路段，如图2.2中所示左边的圆。使用同样的方式我们以终点为中心画一个相同大小的圆，得到在t0时刻从在终点出发在时间预算内可达的路段。因....

图2.3初始种群的生成Fig.2.3Thegenerationoftheinitialpopulation

重庆大学硕士学位论文2基于模因算法的双重时间依赖的风景行车路线规划方法11t0时刻车辆的平均速度。圆区域中包含的路段是从起点出发在时间预算内可达的路段，如图2.2中所示左边的圆。使用同样的方式我们以终点为中心画一个相同大小的圆，得到在t0时刻从在终点出发在时间预算内可达的路段。因....

图2.4染色体编码示例

重庆大学硕士学位论文2基于模因算法的双重时间依赖的风景行车路线规划方法13为了更好的理解每条染色体的编码过程，我们给出了一个例子，如图2.4所示，在初始化阶段有效区域中有7条有效的风景路段（a,b,c,d,e,f,g），如图2.4（a）所示，随着染色体不断的编码，有效风景路段的数....

图2.5染色体交叉Fig.2.5Chromosomecrossover

重庆大学硕士学位论文2基于模因算法的双重时间依赖的风景行车路线规划方法15个参数控制，即Pc和ρc，其中Pc是用户指定的常数，通常称作交叉概率；ρc是在[0,1]范围内随机生成的值，当Pc>ρc时，对选中的染色体执行交叉操作。图2.5染色体交叉Fig.2.5Chromosomec....

本文编号：3989700