以最小换乘次数和站数为目标的公交出行算法

Algorithms for public transit trip with minimal transfer times and stops

提供两点乘车的最优公交路径是ATIS的核心功能。文中建立了以最小换乘次数为第一目标,最小途经站数为第二目标的公交出行最优路径模型。提出了可行路径的最小换乘次数动态规划算法,依此确定换乘次数上界;设计了搜索算法确定最优公交线路序列,分析了线路相交的四种情况,给出了换乘点选择方法,由公交线路序列和换乘点共同组成最优路径。

Providing optimum route for public transit trip is a core function of ATIS. A model of optimum route with the minimal transfer times as primary goal and the minimal stops as second goal was built. Based on the principle of optimality, a dynamic programming algorithm of minimal transfer times for a viable route was designed and this could be used to determine the upper bound. A BFS algorithm was designed to find the lines serial of the optimum route. Transfer was determined based on the analysis of four class of interconnectivity of lines. The optimum route was comprised of lines serial and transfers.