路径选择中合理路径集的研究与应用

摘要

一个城市的路网往往有上百甚至上千个节点，任何一对OD点之间可能存在路径数目极其巨大。在实际出行中，出行者对路径的选择通常只会考虑几条有效的路径。本论文研究基于前K条最短路径算法，根据出行者路径选择行为的特性，求解出城市道路网络中起讫点间的合理路径集。其研究的意义在于：一方面，得到一个合理路径集，可以将其用于动态路径诱导系统，为司机提供一个合理的候选路径集，以便司机根据需要与经验从中选择自己心目中的最优路线；另一方面，在研究出行者的路径选择行为时，为路径选择模型提供适当数量的合理的路径集。本论文研究结合出行者选择偏好的多个影响因素对前K条最短路径进行分析。首先根据城市交通网络的特性，利用椭圆来限制最短路径的搜索范围；其次对城市道路进行分级，删除起讫点之间不被出行者所使用的低等级道路，从而减少计算工作量；再采用在简化的道路网络上计算前K条最短路得到有效路径；然后利用出行者的选择偏好，对所得前K条最短路集合进行合理性进行分析，得到合理路径集。总而言之，求合理路径集的方法就是不断缩小可选路径集的范围，从而得到合理路径集。最后，利用广州市天河区的出租车路径集的GPS数据，以广州市天河区路网为例，根据本论文的研究方法求解出符合实际的合理路径集。

目录

文摘

英文文摘

声明

1绪论

1.1合理路径集的研究背景

1.2合理路径集的研究现状

1.3本文的主要研究工作

2问题分析及经典回顾

2.1合理路径集问题分析

2.2经典理论与算法回顾

3合理路径集的求解

3.1工作流程综述

3.2将路网抽象成图

3.3限制最短路径的搜索范围

3.4简化路网

3.5计算前K条最短路得到有效路径

3.6求解合理路径集

4利用GPS数据进行实例验证

4.1合理路径集的求解

4.2合理路径集的验证

4.3合理路径集的验证结论

5总结

致谢

参考文献

附录:简化路网部分源程序