Dijkstra's algorithm is one of the foundational methods in graph theory. Given a graph with nonnegative edge weights, it computes shortest paths with well-established correctness guarantees. A* extends shortest-path search through heuristic guidance, while RAPTOR addresses the specialized requirements of timetable-based public transportation.
These methods are natural candidates for a travel route optimization engine.
However, the algorithmic problem changes considerably when the transportation network is incomplete, edges arrive during computation, and the objective is to return several practically useful journeys rather than a single minimum-cost path.
While developing Routavio, a multimodal travel planning and route optimization platform, we encountered precisely these conditions.
This article examines the theoretical assumptions behind conventional routing algorithms, explains the bounded heuristic search architecture adopted in Routavio's evaluated pilot implementation, and discusses the resulting trade-offs in completeness, computational efficiency, and itinerary quality.
1. Classical Shortest-Path Formulation
Consider a directed transportation graph:
G = (V, E)
Here, V represents locations such as airports, railway stations, and transport terminals, while E represents directed transportation connections.
For a path P consisting of edges e1, e2, ..., ek, the classical shortest-path objective is:
minimize C(P) = sum(c(e))
for every edge e in P
The function c(e) assigns a nonnegative cost to each edge.
Dijkstra's algorithm identifies a minimum-cost path under this formulation [1].
When an admissible heuristic estimates the remaining cost to the destination, A* can guide search toward the target without sacrificing optimality under the appropriate assumptions [2].
Both approaches are highly effective when the optimization objective is well-defined and the graph representation is sufficiently complete.
Multimodal travel planning introduces additional complications.
A traveler may simultaneously consider monetary cost, duration, number of transfers, transport preference, and connection reliability.
These criteria are not always reducible to one universally meaningful scalar objective.
Martins (1984) studied multicriteria shortest-path problems, demonstrating the relevance of nondominated solutions when competing objectives must be considered [3].
For travel planning, this means that multiple itineraries may be reasonable recommendations even when their relative rankings depend on user preferences.
2. The Difference Between Network Optimality and Journey Optimality
An important assumption in classical graph optimization is that the graph represents the network being optimized.
In travel technology, this assumption is often weakened by the data acquisition process.
A transportation platform may receive:
- Flight fares from commercial pricing APIs.
- Scheduled railway or coach connections from GTFS feeds.
- Route availability from operator catalogues.
- Historical price observations without confirmed current inventory.
- Date-specific connections discovered during an active search.
These sources differ in temporal granularity, completeness, freshness, and reliability.
As a result, a transportation graph is not necessarily a complete representation of every real-world travel option.
An algorithm may compute the optimal path within the represented graph while omitting an objectively better journey whose connections were unavailable to the system.
Formally, let:
G_observed = (V_observed, E_observed)
G_actual = (V_actual, E_actual)
If the observed network is incomplete, an optimal path in G_observed does not necessarily correspond to an optimal path in G_actual.
This does not invalidate Dijkstra or A*.
It limits the scope of the optimality claim.
For Routavio, this distinction was central to the engineering problem.
At the evaluated August 2026 repository revision, the transportation graph contained 24,774 nodes and 228,060 directed edges, assembled from heterogeneous transportation data.
The objective was not to prove optimality over a complete European transportation network.
It was to discover a limited set of plausible, structurally distinct itineraries using the information available within an interactive computation budget.
3. Why RAPTOR Was Also Considered
RAPTOR, or Round-Based Public Transit Routing, was introduced by Delling, Pajor, and Werneck as a routing approach designed specifically for scheduled public transportation [4].
Rather than applying conventional graph traversal through a priority queue, RAPTOR processes public transit routes in rounds.
This structure supports criteria such as earliest arrival time and number of transfers.
It is particularly relevant for transportation systems where timetable information is sufficiently available and consistent.
However, Routavio's data environment differed in several respects.
Some transport connections were represented by exact scheduled departures. Others were represented by observed fares, approximate durations, or published corridor information.
Furthermore, flight-pricing responses could introduce previously unavailable connections during the computation.
RAPTOR remains a strong candidate for well-modeled timetable networks, but adopting it as the central method would not eliminate the problems associated with incomplete cross-modal supply, dynamically acquired flight segments, and heterogeneous fare evidence.
The broader transportation routing literature, reviewed by Bast et al. (2016), provides useful context for understanding these distinctions [5].
The question was therefore not which algorithm was universally superior.
It was which computational strategy best matched our available data, expected outputs, and operational constraints.
4. Bounded Heuristic Depth-First Search
Routavio's evaluated route computation engine used a budget-bounded, heuristically pruned depth-first traversal.
The search maintained two principal termination constraints:
- A wall-clock computation budget.
- A maximum number of completed candidate paths.
Traversal terminated when either limit was reached.
The discovered candidate paths were subsequently subjected to validation, ranking, and diversity selection.
The design deliberately separated path discovery from the final evaluation of itineraries.
Conceptually, the search can be described as:
INPUT:
origin
destination
travel date
transfer budget
computation budget
INITIALIZE:
candidate paths
visited locations
search deadline
SEARCH:
expand outgoing connections
reject invalid departure dates
reject infeasible connections
reject excessive geographic detours
reject cycles and invalid route shapes
prioritize promising destinations
if destination reached:
retain candidate
stop at path or time budget
POSTPROCESS:
validate complete itineraries
rank by multiple criteria
promote structural diversity
OUTPUT:
bounded set of plausible itineraries
This pseudocode illustrates the computation strategy. It is not a verbatim reproduction of the production implementation.
The central trade-off is straightforward.
Restricting traversal reduces the amount of computation required, but it can also exclude feasible paths that a more exhaustive algorithm would discover.
Consequently, the approach cannot claim global shortest-path optimality.
Its effectiveness must instead be assessed through practical itinerary quality, feasibility, diversity, and computational cost.
5. Reverse-Graph Lower Bounds for Search Pruning
One of the more useful mechanisms in Routavio's route engine was a lower bound on the minimum remaining number of traveler-visible legs.
Consider a partial route that has already consumed k legs.
Let h(v) denote an optimistic lower bound on the number of additional visible legs required to reach the destination from the current node v.
If the user permits a maximum of L visible legs, a branch can be rejected whenever:
k + h(v) > L
Routavio estimated this lower bound using a 0-1 breadth-first computation over reverse adjacency.
This matters because some local connectors do not consume the same traveler-visible leg budget as an intercity connection.
The reverse search assigns the appropriate zero or one cost to each connection category when calculating the estimate.
Unlike purely heuristic geographic pruning, this lower-bound check has a specific correctness property.
Provided that h(v) does not overestimate the minimum required remaining legs, the search does not discard a route that could satisfy the leg-count limit solely because of this check.
This is an important distinction between safe constraint-based pruning and heuristic pruning that deliberately sacrifices completeness.
6. Geographic Progress and the Airport Access Problem
Geographic heuristics were introduced in response to actual routing defects.
During development, a search from Istanbul to Colmar produced an itinerary involving geographically implausible coach movements through cities including Milan, Rome, Geneva, and Basel.
The connections were individually represented in the graph, but the overall itinerary was not a sensible recommendation.
The engine therefore introduced geographic-progress constraints to suppress excessive detours.
However, a purely destination-oriented constraint creates another problem.
Consider a traveler starting in Maastricht who needs to reach a distant destination by air.
An appropriate journey may initially involve traveling to a larger airport in Düsseldorf or Cologne.
That first ground connection may move away from the final destination or fail to produce immediate geographic progress.
A strict progress heuristic could reject it.
Routavio therefore introduced a bounded origin-access exception, subject to constraints on access distance, endpoint type, and geographic direction.
The purpose was to preserve reasonable access to nearby airports without allowing the search to return to unconstrained geographic exploration.
This illustrates a recurring problem in applied heuristic optimization.
A constraint that eliminates one class of invalid results can also eliminate legitimate solutions.
The design task is to identify the structural distinction between the two cases and encode an appropriately limited exception.
7. Time-Dependent Connection Feasibility
A multimodal itinerary is not valid simply because consecutive transport edges share a location.
The timing of the connection matters.
A simplified transfer feasibility requirement is:
departure(next_leg)
>= arrival(previous_leg)
+ minimum_connection_time
The minimum connection time depends on the type of transfer.
Changing trains within one station is different from transferring between an airport and a railway terminal in another part of the city.
Routavio therefore used mode-aware minimum connection times and transfer feasibility evaluations.
The route engine also considered date scope, excessive waiting, negative prices, invalid durations, and total itinerary duration.
A key distinction is that scheduled connectivity does not imply guaranteed inventory.
GTFS provides standardized structures for public transport schedules [6]. It does not, by itself, guarantee that a ticket remains available for purchase at a particular price.
Preserving this distinction is essential when integrating planning data with commercial travel inventory.
8. Dynamic Graph Updates During Search
Another constraint involved how new transportation edges entered the graph.
Some flight connections were acquired on demand.
The initial approach invalidated the cached graph and attempted a complete reload when new flight information became available.
This created a resource problem.
While an existing computation retained references to the old graph, the reload could construct a second full graph in memory.
In the pilot environment, the resulting memory pressure caused worker failures.
The implementation was changed to incrementally splice newly persisted flight edges into the existing adjacency representation, replacing stale entries with matching segment identifiers.
This reduced the need to reconstruct the full transportation graph after each acquisition.
It also demonstrated how algorithm design and runtime architecture interact.
An operation that appears inexpensive in abstract graph theory may carry substantial memory and lifecycle costs in a production service.
9. Multicriteria Ranking and Route Diversity
After candidate discovery and feasibility validation, Routavio ranked itineraries using multiple factors.
These included monetary cost, duration, transfer count, and confidence derived from the source and freshness of transportation data.
The ranking process also considered structural diversity.
A result containing five nearly identical flight connections may offer less decision-making value than a smaller collection of genuinely different travel strategies.
For example, a traveler may reasonably want to compare:
- A faster air-plus-rail journey.
- A cheaper air-plus-coach combination.
- A ground-only itinerary with fewer travel modes.
The relevant optimization objective is therefore not just to minimize one scalar value.
It is to present useful alternatives across several dimensions.
The approach relates to multicriteria optimization, but it does not enumerate the complete Pareto frontier.
Because path discovery is bounded and heuristically pruned, the final ranking operates only over the candidates actually discovered.
That qualification is necessary when interpreting the algorithm's output.
10. Limitations and Future Evaluation
The evaluated implementation established that a bounded heuristic approach could produce plausible multimodal itineraries over heterogeneous transportation data.
It did not establish that the selected search strategy was universally superior to Dijkstra, A*, RAPTOR, or other routing algorithms.
A more rigorous comparative evaluation would require:
- A labeled corpus of origin, destination, and departure-date combinations.
- Complete reference subgraphs for controlled algorithm comparisons.
- Independent validation of transfer feasibility and route quality.
- Measurements of recall relative to reference nondominated solutions.
- Controlled latency and resource-consumption benchmarks.
- Coverage and data-freshness measurements across transportation modes.
Such an evaluation would help distinguish computational efficiency from route quality and data coverage.
It would also support a more precise assessment of the circumstances under which heuristic search provides sufficient practical value.
Conclusion
Classical shortest-path algorithms remain fundamental to transportation network optimization.
Their guarantees are meaningful within their mathematical assumptions.
Building a multimodal travel planner introduces additional operational constraints: incomplete supply, dynamic data acquisition, competing objectives, temporal feasibility, and limited computation budgets.
Routavio's evaluated implementation used bounded heuristic search to address those constraints and retrieve plausible, diverse itineraries without claiming global optimality.
The broader engineering lesson is that algorithm selection should begin with the structure and quality of the available data, the required output, and the operational environment.
For real-world multimodal route planning, the most useful mathematical solution is not always the one obtained from the simplest abstraction of the network.
Related Engineering Article
Engineering a Multimodal Travel Planner on a 228,060-Edge Graph
References
[1] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. https://doi.org/10.1007/BF01386390
[2] Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
[3] Martins, E. Q. V. (1984). On a multicriteria shortest path problem. European Journal of Operational Research, 16(2), 236–245. https://doi.org/10.1016/0377-2217(84)90077-8
[4] Delling, D., Pajor, T., & Werneck, R. F. (2015). Round-Based Public Transit Routing. Transportation Science, 49(3), 591–604. https://doi.org/10.1287/trsc.2014.0534
[5] Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016). Route Planning in Transportation Networks. In Algorithm Engineering, Lecture Notes in Computer Science, 9220, 19–80. https://doi.org/10.1007/978-3-319-49487-6_2
[6] MobilityData. (2026). GTFS Schedule Reference. https://gtfs.org/documentation/schedule/reference/
[7] Çınar, H. (2026). Design and Implementation of a Multimodal Door-to-Door Travel Metasearch Platform with a Bounded Graph-Based Route Computation Engine and an Observability-Driven Deployment Pipeline. Sabancı University, public technical edition, repository revision 71e8cd39, Sections 2.1.5 and 5.1.1–5.1.4.
Project: Routavio | Multimodal Travel Planner and Route Optimization
Implementation details refer to the evaluated August 2026 pilot architecture. They should not be interpreted as guarantees about the current production system.
Top comments (0)