A flight search engine answers a well-defined question: which available flights connect two airports? A door-to-door travel planner must answer a more difficult one: which sequence of flights, trains, coaches, and ferries can plausibly connect two places, even if the destination has no airport?
I encountered that distinction while building Routavio, a multimodal travel metasearch and route planning platform. This article documents the engineering approach evaluated in our August 2026 pilot system. It does not claim to introduce a new shortest-path algorithm. The contribution is the integration of incomplete transportation supply, bounded route optimization, explicit data provenance, and a deployable computation architecture.
1. Problem Formulation
Represent the transport network as a time-aware directed graph (G=(V,E)). Locations such as airports, railway stations, terminals, and city anchors are vertices; potential transport movements are edges. An edge can have a mode, duration, provider, departure information, price evidence, and a timestamp indicating when its information was verified.
A conventional shortest-path problem might minimize a scalar cost (C(p)) over all feasible paths (p). A travel planner has competing objectives:
- Monetary cost
- Elapsed travel time
- Number of transfers
- Connection feasibility
- Confidence in price and schedule information
- Structural diversity among suggested itineraries
Martins (1984) established foundational results for multicriteria shortest-path problems, where competing objectives may produce multiple nondominated solutions. This is relevant to journey planning: a low-cost route with four risky transfers may be less attractive than a moderately more expensive journey with a single connection [1].
Moreover, the supplied graph is incomplete. A timetable may provide known departures, while a flight-pricing API returns date-specific offers on demand. Some edges have price observations but no guaranteed seat inventory. The assumption that all feasible routes are already contained in a complete, static graph does not hold.
2. The Pilot Network and Its Constraints
At the evaluated repository revision, Routavio represented 24,774 nodes and 228,060 directed transport edges. The integration layer contained 17 heterogeneous source adapters or integrations. These included pricing interfaces, scheduled-data feeds, catalogues, and timetable services. Importantly, not every implemented integration was an active source of live inventory.
The engineering problem was not finding just any sequence of connected edges. Early route discovery for Istanbul to Colmar, for example, produced a geographically implausible coach itinerary zig-zagging across European cities. Individual legs were graph-valid, but the itinerary was unsuitable for travelers.
This motivated constraints covering geographic progress, maximum first-hop displacement, limited ground legs after flying, visited-node checks, and minimum connection times.
A different defect arose when a small origin city needed a short journey to a nearby major airport. Pure destination-oriented pruning would have incorrectly rejected that initial access leg, so the design admitted a carefully bounded exception.
These corrections illustrate a distinction in applied optimization. Network feasibility is necessary, but it is not sufficient for user-level plausibility.
3. Why We Used Bounded Heuristic Search
Dijkstra's algorithm and A* remain foundational methods for shortest-path search [2, 3]. Round-Based Public Transit Routing, or RAPTOR, addresses schedule-based public transportation with multiple criteria, notably arrival time and transfer count [4]. Bast et al. provide a comprehensive account of the algorithmic landscape for transportation network routing [5].
We evaluated these approaches against a different operational objective. The pilot sought a small, structurally diverse set of plausible journeys within a strict time budget.
The graph was heterogeneous and could acquire new flight edges while a search was running.
Routavio therefore used a budget-bounded, heuristically pruned depth-first search. It imposed both a wall-clock budget and a cap on completed candidate paths.
Exploration order preferred edges progressing toward the destination, diversified outgoing connections across candidate hubs, and pruned branches that could not fit the remaining visible-leg budget.
One lower bound used a reverse-graph 0-1 breadth-first computation to estimate the minimum remaining travel legs. That prune is sound relative to the leg budget.
Other geometric and product-shape heuristics deliberately sacrifice completeness.
Consequently, the engine does not guarantee the globally shortest, fastest, or cheapest real-world journey.
That limitation is part of the algorithm's specification, not a detail to conceal.
4. Separating Route Discovery from Ranking
Graph traversal, ranking, and persistence were separate pipeline stages.
Search produced candidate paths. Subsequent validation checked schedules, durations, transfers, and unrealistic sequences.
Ranking then considered price, journey duration, transfer count, source confidence, and itinerary diversity.
The diversity requirement is particularly important.
Five minor variations of the same airport transfer may be less useful than alternatives with genuinely different travel patterns, such as air plus rail, air plus coach, or ground-only travel.
This design follows the broader multiobjective-routing literature, while acknowledging that a bounded search cannot claim to enumerate the entire Pareto frontier.
5. The Compute System Is Part of the Optimization Problem
The user-facing layer used Next.js, while a separate Node.js worker owned provider acquisition and CPU-heavy graph traversal.
PostgreSQL carried durable computation requests. Work claims used FOR UPDATE SKIP LOCKED, and LISTEN/NOTIFY provided a wake-up signal.
This architecture was intentionally compact.
It also had a measurable limitation: four logical work slots shared a single JavaScript event loop for synchronous traversal.
More logical slots did not produce more CPU parallelism.
Search budgets, worker service time, and queue growth consequently became closely coupled.
In one pilot incident, extending a difficult route search substantially improved the best discovered itinerary for that search while starving unrelated requests in the shared queue.
The change was reverted.
Better ordering and pruning were preferable to simply increasing every search's execution time.
This illustrates a fundamental systems engineering principle: local improvements in computation quality must be evaluated against their effects on shared system capacity.
6. What the Measurements Support
The August 2026 evaluation reported a warm-cache median of 927 ms for the first search pass and a cold-cache median of 22,838 ms.
The distinction was primarily attributable to graph loading, not the graph traversal itself.
These were observations of a pilot deployment with active traffic and scheduled jobs, not a controlled comparison establishing universal speedups.
Two separate low-load read-endpoint tests with five virtual users reported zero HTTP errors.
The application saturation point remained unknown, because the CDN rate-limited the load generator before the origin saturated.
The tests did not establish a maximum search throughput.
These limitations matter when interpreting performance claims. Measured latency distributions, throughput baselines, and system capacity are different properties that require different evaluation methods.
7. Implications for Multimodal Travel Planning
The experience suggests three broader considerations for transportation software engineering.
First, route computation should distinguish graph connectivity from journey feasibility. A mathematically valid sequence of transport edges can still violate physical, temporal, or geographic constraints.
Second, multicriteria itinerary selection requires an explicit treatment of trade-offs. Price, duration, transfers, and confidence are not interchangeable dimensions.
Third, system architecture affects the quality of optimization under operational constraints. A sophisticated routing algorithm provides limited value if data acquisition, caching, or queue contention prevents results from reaching users within an acceptable response window.
For multimodal travel planners, optimization must therefore be considered at both the algorithmic and system levels.
Conclusion
A useful route optimization engine is not just a graph algorithm.
It is a system that connects incomplete transportation evidence to feasible itineraries, manages uncertainty in schedules and fares, and preserves usable response times under limited resources.
For Routavio, the most consequential design choice was to optimize for plausible, diverse, explainable travel options under bounded computation, rather than claiming perfect optimization over a network that was neither complete nor fully live.
The next articles examine the search heuristics, cache investigation, queueing failure, provider resilience, and language-model-assisted planning boundary individually.
Project: Routavio | Multimodal Travel Planner & Route Optimization
References
[1] 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
[2] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. https://doi.org/10.1007/BF01386390
[3] 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
[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] Çı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, pp. 9–17, 30–33, 44–48.
Engineering measurements refer to the August 2026 pilot evaluation and should not be interpreted as guarantees of current platform performance.
Top comments (0)