基于路网的路径规划问题研究

《基于路网的路径规划问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2018届研究生博士学位论文分类号：081203学校代号:10269密级：公开学号:52131500007EastChinaNormalUniversity博士学位论文DOCTORALDISSERTATION论文题目：基于路网的路径规划问题研究院系:计算机科学与软件工程学院专业名称:软件工程研究方向:基于位置的服务指导教师:金澈清教授学位申请人:刘辉平2018年05月Dissertationfordoctoraldegreein2018SchoolCode:10269StudentID:52131500007EASTCHINANORMALUNIVERSITYRESEARCH

2、ONROUTEPLANNINGINROADNETWORKSDepartment:SchoolofComputerScienceandSoftwareEngineeringMajor:SoftwareEngineeringResearchdirection:Location-BasedServicesSupervisor:Prof.CheqingJinCandidate:HuipingLiu2018.05华东师范大学学位论文原创性声明郑重声明：本人呈交的学位论文《基于路Ｍ的路径规划问题研究》，是在华东师范大学攻读硕士／＃（请勾选）学位期间，在导师的指导下进行的研宄工作

3、及取得的研究成果。除文中己经注明引用的内容外，本论文不包含其他个人己经发表或撰写过的研究成果。对本文的研宄做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名曰期：年６月（曰华东师范大学学位论文著作权使用声明《苺于路网的路径规划问题研究》系本人在华东师范大学攻读学位期间在导师指导下完成的硕士请勾选）学位论文，本论文的著作权归本人所有。木人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和学校指定的相关机构送交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位

4、论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于（请勾选）“”“”（）１．经华东师范大学相关部门审查核定的内部或涉密学位论文＊，于年月＃解密，解密后适用上述授权。（２．不保密＼／ｆ，适用上述授权。导师签名：本人签名：＾１（３年６月曰１４“”＊应密涉学位论文是己经华东师范大学学位评定室委员会办公或保密委员“”（会审定过的学位论文需附获批的《华东师范大学研宄生申请文学位论涉密审批表》），经上方为有效未述部门审定的学位论文均为公。此开学

5、位论文声明栏不填，开的认，写默为公学位论文均上。适用述授权刘辉平博士学位论文答辩委员会成员名单姓名职称单位备注李战怀教授西北工业大学主席薛向阳教授复旦大学王国胤教授重庆邮电大学王长波教授华东师范大学贺樑教授华东师范大学华东师范大学博士学位论文摘要近年来随着移动互联网的迅猛普及和发展，日常生活中基于位置的服务变得无所不在。而路径规划作为基于位置服务中的一项基础功能，为人们出行提供了重要的路线参考。然而随着出行人数和物流运输规模的增加，新型的路径规划需求持续出现，而现有的电子地图应用中的路径规划查询过于单一，需要设计和处理满足个性化的日常生活和工业应用的新型路径规划查询

6、。另一方面，随着人们生活范围的不断扩展，路网规模持续增长，传统的路径规划算法面临着瓶颈和挑战，需要开发能够处理大型复杂网络的高效算法来满足新时代的数据规模。本文基于不同的路径规划需求，提出了3种常用的新型路径规划查询，并设计了相应的适用于大规模路网的高效查询算法，实验证明，与现有的方法相比，所提算法均具有良好的有效性和高效性。本文的主要工作和主要贡献概括如下：1.热门路径规划及其消耗估计。随着车载GPS设备的增加，越来越多的轨迹数据被实时生成，基于这些轨迹数据，一些城市应用变成可能，如路径规划。通常来说，频繁被经过的热门路径是出行线路的良好选择，特别是对于那些对道路或周边环

7、境不太熟悉的人来说。此外，对路径消耗（如行驶时间、费用、油耗等）的准确估计有助于更加精准的出行规划。为了达到上述需求和目标，研究基于轨迹数据的热门路径规划及其消耗估计。即给定起终点和出发时间，计算出发时刻从起点到终点的热门路径并估计其消耗。为了解决该查询，首先基于轨迹数据构建热门转换图，图中节点表示热门点，边表示热门点之间的热门路径。然后利用最小描述长度对每条边（热门路径）上的稀疏轨迹数据进行不同时段的消耗建模。最后，结合相邻路段间的消耗依赖，设计基于动态规划思想的路径规划算法，在热门转换图上计算给定时刻从起点到终