We consider an ad hoc Floyd-A∗ algorithm to determine the a priori least-time itinerary from an origin to a destination given an initial time in an urban scheduled public transport (USPT) network. The network is bimodal (i.e., USPT lines and walking) and time dependent. The modified USPT network model results in more reasonable itinerary results. An itinerary is connected through a sequence of time-label arcs. The proposed Floyd-A∗ algorithm is composed of two procedures designated as Itinerary Finder and Cost Estimator. The A∗-based Itinerary Finder determines the time-dependent, least-time itinerary in real time, aided by the heuristic information precomputed by the Floyd-based Cost Estimator, where a strategy is formed to preestimate the time-dependent arc travel time as an associated static lower bound. The Floyd-A∗ algorithm is proven to guarantee optimality in theory and, demonstrated through a real-world example in Shenyang City USPT network to be more efficient than previous procedures. The computational experiments also reveal the time-dependent nature of the least-time itinerary. In the premise that lines run punctually, “just boarding” and “just missing” cases are identified.
展开▼
机译：我们考虑一个ad hoc floyd-a *算法，以在城市预定公共交通（USPT）网络中的初始时间，从原点到目的地确定先前的最低时间行程。网络是Bimodal（即，ustpl）和行走的时间，时间依赖。修改的USPT网络模型导致更合理的行程结果。行程通过一系列时间标签弧连接。所提出的Floyd-A *算法由指定为Itinerary Finder和成本估算器的两种程序组成。 A *基于的Itinerary Finder确定实时依赖于时间，最小时间的行程，由基于弗洛伊德的成本估算器预先计算的启发式信息，其中策略形成为将时间依赖的电弧行程时间预期相关的静态下限。弗洛伊德-A *算法被证明是在理论上保证最佳状态，并通过沉阳市的真实界限证明了网络的网络比以前的程序更有效。计算实验还揭示了最低时间的时间依赖性。在前提下，线路正常运行，“只是登机”和“刚刚缺少”案件。
展开▼
