详情

原文传递车辆导航中多路径推荐算法研究

论文题名：	车辆导航中多路径推荐算法研究
关键词：	车辆导航;多路径推荐算法;时间划分;路网模型
摘要：	随着社会经济的发展和综合国力的增强，如何降低交通堵塞所带来的负面影响成为了我国目前迫切需要解决的问题。本文从实用的角度出发，提出了一种基于遗传算法的能够求解多条准最优路径的混合算法（Hybrid Algorithm,HA）。并在此基础上对它进行改进和提高，以使其更加适应实际的交通现状。由于本文提出的算法给司机提供了多条较优的导航路径，这提高了司机选择路径的主观性，避免了都走同一路径而可能导致的路段堵塞，从而使得司机尽量在预计的时间内到达目的地。　　本文的主要贡献主要有以下几个方面：　　①在对多路径问题（Multi-Route Problem,MRP）的数学模型进行分析和研究的基础上，确定了本文中多路径问题所采用的数学模型。同时，对于交通路径诱导系统中的多条准最短路径问题（Multi-Quasi-Shortest Route Problem,MQSRP），介绍并分析了当前主要算法的优缺点，包括Dijkstra算法、Floyd算法、K最短路径算法、A算法和遗传算法等。　　②对于交通路径诱导系统中的MQSRP问题，提出了混合算法。此算法主要结合了Floyd算法和A算法的优点，能有效的解决遗传算法应用于最短路径问题的搜索空间大而导致的瓶颈问题。　　③为了把本文提出的混合算法应用到实际的交通路网，引入了一种时间划分的路网模型（Time-division Road Network Model,TDRNM）。为了使混合算法能更好以解决实际的交通情况，对引入的模型上增加了一个矩阵变量(S)。　　④针对MQSRP问题的合理性提出了一种考虑了合理性的混合算法（Considered Rationality Hybrid Algorithm,CRHA）。当前的求解多条导航路线的算法虽然很多，但它们并没有考虑多条路径的合理性，针对这个问题本文提出了CRHA。　　⑤分别用静态的和基于TDRNM模型对本文提出的混合算法的有效性和效率进行了测试，取得了较好的效果。同时也对CRHA算法的有效性进行了实验，取得了比较满意的结果。
作者：	叶金平
专业：	计算机软件与理论
导师：	朱征宇
授予学位：	硕士
授予学位单位：	重庆大学
学位年度：	2011
正文语种：	中文