Case study
Optimal routing in a transportation network

https://doi.org/10.1016/0377-2217(95)00177-RGet rights and content

Abstract

This paper investigates a routing problem in a public transportation network, more precisely the problem of finding an optimal journey plan in a transportation network, given a timetable. The following issues are discussed: a graph model of a transportation network that takes into account changes of means of transport in a non-zero time; reduction of a large network to a network with a smaller number of nodes and arcs, and algorithms that find an optimal connection by different optimality criteria given. It is shown that the routing problem is closely related to the shortest-path problem in a weighted graph. However, well-known graph-theory algorithms cannot be directly applied as the time factor and the effect of changing means of transport require a specific approach. Moreover, miscellaneous constraints may be imposed on the set of acceptable routes. An implementation of the presented approach in a commercial routing program has been described.

References (7)

  • E.H. Reingold et al.

    Combinatorial algorithms. Theory and Practice

    (1977)
There are more references available in the full text version of this article.

Cited by (32)

  • Modeling traveler's speed-route joint choice behavior with heterogeneous safety concern

    2023, Analytic Methods in Accident Research
    Citation Excerpt :

    Almost all traffic-assignment techniques are built based on the assumption of travelers’ disutility-minimization criterion (Wardrop, 1952). Besides the least cost travel time (Goczyłla and Cielatkowski, 1995), many other types of cost-effective criteria in route choice have been studied, such as the eco-friendly routes (Tzeng and Chen, 1993; Nie and Li, 2013) and the most reliable routes (Lo et al., 2006). In recent years, several studies have found that traffic safety is a significant criterion when making travel decisions.

  • Incorporating safety reliability into route choice model: Heterogeneous crash risk aversions

    2020, Analytic Methods in Accident Research
    Citation Excerpt :

    Researchers postulate that travelers tend to choose the most effective route to minimize their travel cost. Different types of cost-effective routes have been studied, such as the least cost travel time (Goczyłla and Cielatkowski, 1995), eco-friendly routes (Tzeng and Chen, 1993; Rilett and Benedek, 1994; Nie and Li, 2013) and the most reliable routes (Lo and Tung, 2003; Shao et al., 2006; Chen and Zhou, 2010). However, few studies have been reported for how safety aspects could be quantified into trip planning of travelers, even though travel safety is undoubtedly an essential for travelers to measure the performance of candidate routes.

  • Models and algorithms for network reduction

    2016, European Journal of Operational Research
    Citation Excerpt :

    These results demonstrate that our procedure is able to effectively exploit the local sparsity of the original network and the low proportion of required nodes (around 1.5 percent or less of the original nodes) to bypass nodes and eliminate arcs. Such characteristics are often found in physical networks such as road, rail, or electricity distribution systems (e.g., Chardy et al., 2012; Goczyła & Cielatkowski, 1995). Of course, preprocessing may be less effective for networks that are denser or have a higher proportion of required nodes.

  • Safety-based path finding in urban areas for older drivers and bicyclists

    2014, Transportation Research Part C: Emerging Technologies
  • Optimizing itineraries in public transportation with walks between rides

    2013, Transportation Research Part B: Methodological
    Citation Excerpt :

    However, in the cases where walking is considered as one of the travel modes, the set of walks that possibly can be made is more or less considered as given and consists only of a small part of the walks that can possibly be made in practice. The possibility to make short walks between closely situated stations is briefly mentioned, without any further analysis, by Goczyla and Cieltkowski (1995). Ziliaskopoulos and Wardell (2000) study the problem of computing intermodal time-dependent least-time paths on multimodal transportation networks.

View all citing articles on Scopus
View full text