裴立秋

(吉林建筑工程学院教务处，长春130118)

人们外出旅游或在一个城市内由甲地到乙地如何选择乘车线路，这是每位出行者所关心的问题，也是最优化算法中有待研究的一类新问题.因此，在已有公共交通条件下，设计出合理的公交出行路线将有助于人们选择出发时间、出行路线和换乘方案等.公交出行路径选择，实质上是研究乘客出行在公交网上的分布规律，即研究乘客给出起讫点后，如何自动生成最优的出行路径方案.在乘客出行时，“换乘次数”是大部分乘客在选择出行方案时首先考虑的因素，“出行距离最短”(一般即代表时间最短)为第二目标.乘客基于车票花费问题一般主要以公交车为主要通行工具，当所耗时间过多时采用地铁.当步行距离小于一定距离时还可步行.本文主要讨论的问题就是从给出的公汽路线中求出任意两站点之间的最优路线，以满足查询者的不同要求.此时，问题实质上是图论中的一种到有特殊权的最优路径问题［1］，此权就是要依次满足文中对最优解定义的条件.

1 问题分析与基本假设

1.1 问题分析

首先将实际公交网络抽象成拓扑网络图，路径搜索时不同属性的边之间在节点处的连通对应实际通勤的换车.换车要在公交站点处进行，这就要求把适当距离内可能换车的多个站点抽象成一个节点.把空间位置相临近的公交站点归并，并抽象成图的节点，是生成交通网络图的关键［2］.

对……