DEV Community: Routavio

When Better Route Optimization Made Our Travel Planner Slower Copy

Halil Cinar — Sat, 17 Oct 2026 13:38:29 +0000

Route optimization is usually evaluated through the quality of the paths an algorithm discovers.

For a multimodal travel planner, this may involve minimizing journey duration, reducing monetary cost, limiting transfers, or identifying connections through nearby airports.

However, when route optimization is deployed as an interactive service, another objective becomes equally important: the system must produce useful results without preventing other users from completing their searches.

While developing Routavio, a multimodal travel planning and route optimization platform, we encountered a case where extending the graph search budget significantly improved the itineraries discovered for a difficult destination.

The optimization was technically successful when evaluated in isolation.

After deployment, however, the longer computations prevented the shared worker from draining its queue. Unrelated searches accumulated, and users began receiving empty result boards while their computations remained pending.

The change was reverted within an hour.

This article examines that incident through bounded graph search, queueing theory, service-time distributions, and the architectural constraints of a Node.js worker coordinated through PostgreSQL.

The implementation and measurements refer to the August 2026 pilot evaluation at repository revision 71e8cd39.

1. Route Optimization Under a Computation Budget

Multimodal travel planning differs from conventional shortest-path optimization in several important ways.

The transportation network is heterogeneous and incomplete. Some connections are represented by precise schedules, while others depend on externally acquired fare observations or route catalogues.

The objective is also multicriteria. Travelers may value lower prices, shorter durations, fewer transfers, and reliable connections differently.

As Martins (1984) demonstrated in the multicriteria shortest-path setting, competing objectives may produce multiple nondominated solutions [1].

The purpose of Routavio's routing engine was therefore not to find a single mathematically optimal path.

It was to retrieve a small, diverse set of plausible itineraries within a bounded computation window.

At the evaluated revision, the system operated over a directed transportation graph containing 24,774 nodes and 228,060 edges.

The search used heuristically pruned depth-first traversal with two termination conditions:

A maximum number of completed candidate paths.
A wall-clock computation budget.

The search terminated when either bound was reached.

Geographic-progress constraints, remaining-leg lower bounds, connection feasibility, and itinerary-shape restrictions reduced the candidate space.

Importantly, those restrictions affected which paths the engine could discover within its available execution time.

Increasing the search budget could therefore improve the quality of the best discovered result.

But it could also increase the time during which the worker remained occupied.

2. An Airportless Destination Exposed the Trade-off

The relevant experiment concerned a route to Ghent, Belgium.

Ghent does not have a major commercial airport serving conventional international flight search.

A practical journey may require reaching a nearby airport and completing the remaining distance using ground transportation.

This makes it a useful test case for multimodal route discovery.

The route engine must explore transportation combinations that are not represented by a direct airport-to-airport flight search.

During the August 2026 pilot investigation, we measured path discovery against a fixed destination and machine.

The following results were recorded:

Search elapsed time	Candidate paths found	Best discovered itinerary duration
4 seconds	20	3,536 minutes
15 seconds	20	3,536 minutes
20 seconds	80	2,965 minutes
30 seconds	390	310 minutes
45 seconds	390	310 minutes

The results showed a threshold-like discovery pattern.

During the first fifteen seconds, additional computation did not materially improve the best discovered itinerary.

Between twenty and thirty seconds, however, the search discovered substantially better candidates.

At thirty seconds, the shortest duration among the recorded discovered itineraries was 310 minutes.

Extending the observation to forty-five seconds did not improve that result.

This was not a controlled benchmark establishing global route optimality. It was a diagnostic observation of candidate discovery within a particular graph and workload.

Nevertheless, it raised a reasonable engineering question.

If additional search time improves the discovered journeys so substantially, why not increase the computation budget?

3. The Local Optimization

The immediate interpretation was that the existing search budget terminated certain computations before they reached productive regions of the search space.

Increasing the budget appeared to offer a direct improvement in itinerary quality.

The reasoning was straightforward.

Let:

Q(B) = quality of the best itinerary
       discovered within search budget B

If allowing additional computation improves the best discovered route, increasing B can improve Q(B) for that query.

This does not imply that quality increases continuously.

The Ghent measurement suggested a discontinuous or threshold-like relationship, with a relatively unproductive interval followed by rapid improvement.

Such behavior is compatible with bounded heuristic search, where traversal order strongly influences which candidates are discovered before termination.

Routavio increased the search budget substantially.

For the isolated case, the decision was supported by the observed discovery curve.

However, the search engine was not operating in isolation.

Every computation shared the same worker infrastructure with other incoming route requests.

The optimization had therefore changed not only the quality of an individual search, but also its potential service time.

That distinction became decisive.

4. The Shared Computation Architecture

Routavio separated its user-facing Next.js application from a Node.js worker responsible for route computation and transportation data acquisition.

Computation requests were persisted in PostgreSQL.

The worker claimed pending requests using:

FOR UPDATE SKIP LOCKED

PostgreSQL's LISTEN/NOTIFY mechanism provided event-driven notification of queued work.

The architecture supported four logical computation slots.

However, the graph traversal itself was synchronous JavaScript running inside one Node.js worker process.

All four slots shared the same JavaScript event loop.

Consequently, four logical slots did not represent four independently executing CPU-bound search workers.

This distinction matters because concurrency and parallelism are not equivalent.

The application could have several computations in different stages of execution, particularly while awaiting upstream I/O.

But a long synchronous graph traversal occupied the event loop and delayed other JavaScript work in that process.

Increasing logical concurrency could not independently increase available CPU execution capacity.

The worker was therefore vulnerable to computations that occupied the shared execution resource for excessive periods.

5. Queueing Theory and Service Time

The relationship between request arrival rates, processing time, and queue occupancy can be examined through queueing theory.

Define:

λ = mean arrival rate of computation requests

S = service time required by a computation

E[S] = mean service time

μ = effective service capacity

ρ = utilization of the constrained service resource

Under a simplified single-server model:

μ = 1 / E[S]

ρ = λ × E[S]

For a stable queue under the assumptions of this model, the average arrival rate must remain below the effective service capacity.

Equivalently:

ρ < 1

The actual Routavio worker included asynchronous provider I/O, multiple logical slots, and shared system resources. Therefore, the single-server model is an approximation of its synchronous CPU-bound execution bottleneck, not a complete performance model of the implementation.

Nevertheless, it illustrates the operational risk of increasing average service time without increasing effective processing capacity.

If incoming work arrives faster than the constrained resource can process it over a sustained interval, queued work accumulates.

A longer computation budget can therefore increase queue pressure, even when it produces better results for the individual request.

6. Little's Law and End-to-End Response Time

Little (1961) established the fundamental queueing relationship:

L = λ × W

Where:

L is the mean number of jobs in the system.
λ is the mean effective throughput.
W is the mean time a job spends in the system.

The relationship applies under appropriate steady-state and stability assumptions [2].

This qualification is important.

Little's Law does not directly predict the behavior of an overloaded transient queue, and it does not imply that increasing service time always produces a particular numerical increase in waiting time.

However, it clarifies how queue occupancy, throughput, and response time are related when the system operates in a stable regime.

For an interactive travel planner, total response time includes more than graph traversal.

A simplified decomposition is:

Response Time =
    Queue Waiting Time
  + Computation Service Time
  + Other Request Processing Time

An optimization that improves the quality of a route while extending computation service time may increase both the direct cost of that request and the waiting experienced by subsequent requests.

The second effect can dominate the user experience when the worker is operating close to its effective capacity.

7. Why Waiting Time Can Grow Nonlinearly

The relationship becomes more pronounced as resource utilization approaches saturation.

Kingman's work on single-server queues in heavy traffic provides an important theoretical basis for understanding increasing waiting time under high utilization [3].

For illustration, consider an idealized M/M/1 queue with Poisson arrivals and exponentially distributed service times.

Its expected total time in the system is:

W = 1 / (μ - λ)

Equivalently, using utilization:

W = E[S] / (1 - ρ)

These formulas depend on the specific M/M/1 assumptions.

They are not empirical measurements of Routavio.

Consider a hypothetical system receiving 0.08 jobs per second.

If mean service time is ten seconds:

λ = 0.08 jobs/s
E[S] = 10 s

ρ = 0.08 × 10
ρ = 0.80

W = 10 / (1 - 0.80)
W = 50 s

Now suppose mean service time increases to twelve seconds, with the same arrival rate:

λ = 0.08 jobs/s
E[S] = 12 s

ρ = 0.08 × 12
ρ = 0.96

W = 12 / (1 - 0.96)
W = 300 s

In this simplified hypothetical example, a 20% increase in mean service time produces a much larger increase in expected response time.

The values are illustrative and should not be interpreted as Routavio benchmarks.

The point is the nonlinear sensitivity of waiting time to utilization near saturation.

An apparently moderate increase in computation duration may have disproportionate consequences for a heavily utilized shared worker.

8. What Happened After Deployment

The longer search budget was deployed following the Ghent investigation.

Within approximately one hour, the pilot environment showed that the change was harmful at the system level.

Two passes operating under the higher budget roughly doubled worst-case computation time.

The single worker could no longer drain the incoming request queue effectively.

Requests unrelated to the original difficult destination accumulated in the pending state.

Users encountered empty result boards because their route computations had not completed in time.

The engineering report describes the problem as queue starvation caused by increased computation service time.

This is a critical distinction from an algorithm that simply becomes slower.

The increased budget improved the opportunity for one computation to discover a better itinerary, but it also reduced the worker's availability to serve other computations.

As a result, the overall system delivered a worse experience.

The optimization was reverted.

The evidence justified the reversal even though the original single-query measurement remained valid.

The mistake was not measuring the Ghent search incorrectly.

It was treating the result of an isolated search-quality experiment as sufficient evidence for a system-wide computation-budget policy.

9. Search Quality Must Be Evaluated as a System Objective

The incident suggests that search quality and service performance should not be optimized independently.

A simple formulation might consider:

maximize:
    Expected Itinerary Utility

subject to:
    Computation Budget
    Queue Stability
    Response Time Targets
    Provider Quotas
    Memory Constraints

Here, itinerary utility may incorporate journey duration, price, transfer count, connection feasibility, and candidate diversity.

The operational constraints limit the computation resources available to improve that utility.

One can also define a conceptual objective that penalizes system-level performance degradation:

J =
    Expected Route Utility
  - α × Expected Response Time
  - β × Resource Consumption

The coefficients α and β represent design trade-offs.

This expression is an analytical abstraction, not an objective function implemented or calibrated in Routavio.

Its purpose is to show why algorithmic improvements must be assessed against system-level costs.

In an interactive environment, users benefit from useful itineraries only if those itineraries are delivered within a practical waiting period.

The quality of an unfinished search is not equivalent to the quality of a delivered recommendation.

10. Improving Search Quality Without Extending the Budget

After reverting the longer search budget, the engineering approach shifted toward improving the usefulness of the paths discovered within the existing constraints.

Three mechanisms were particularly relevant.

10.1 Goal-directed edge ordering

Outgoing connections were ordered to prioritize promising progress toward the destination.

Because bounded search terminates before exploring the complete graph, discovery order affects the quality of the candidate set.

Exploring promising paths earlier can improve the available results without increasing the permitted execution time.

This is not equivalent to A* optimality guarantees.

The ordering is heuristic and does not establish that the globally best itinerary will be discovered.

10.2 Reverse reachability and remaining-leg lower bounds

The engine used reverse-graph information to estimate the minimum number of remaining traveler-visible legs required to reach the destination.

If a partial path could not satisfy the remaining transfer budget, its branch was rejected.

A simplified condition is:

legs_used
  + minimum_remaining_legs
  > maximum_allowed_legs

This avoids spending computation on branches that cannot produce an admissible itinerary under the leg constraint.

10.3 Nearby-hub pruning

Travel to airportless destinations often requires a nearby airport followed by a ground connection.

However, indiscriminately exploring nearby transportation hubs creates many implausible combinations.

The search therefore applied geographic-progress constraints and bounded airport-access or final-ground-leg rules.

These restrictions reduced unnecessary exploration while retaining common multimodal journey structures.

Together, the mechanisms improved candidate discovery efficiency without simply allocating more wall-clock time to every request.

11. PostgreSQL Queue Semantics and Their Limits

The incident also exposed an important difference between durable queue management and computation capacity.

PostgreSQL offered useful coordination mechanisms.

FOR UPDATE SKIP LOCKED allowed work claims to avoid waiting on rows already locked by another transaction.

LISTEN/NOTIFY provided a way for a worker to receive notifications that new work was available.

These primitives are well suited to the operational needs of a compact, database-backed work queue.

However, neither mechanism increases the CPU capacity of the application executing the claimed work.

Queue durability ensures that computation requests remain represented in persistent state.

It does not ensure that the worker has sufficient processing resources to complete them within an interactive time budget.

The same distinction applies to increasing the number of logical concurrency slots.

If the bottleneck is synchronous JavaScript execution on one event loop, additional slots cannot independently execute additional CPU-bound graph traversals.

The appropriate architectural extension would involve worker threads or separate computation processes, combined with explicit resource and provider-quota management.

Such parallel execution was identified as future work in the evaluated technical report.

The August 2026 pilot did not establish the capacity or performance of a horizontally replicated worker fleet.

12. What a More Rigorous Evaluation Would Require

The incident was diagnosed using operational observations.

It was not a controlled queueing experiment.

The technical report did not establish the exact effective arrival rate, service-time distribution, or utilization parameter required to fit a predictive queueing model.

It would therefore be inappropriate to calculate an observed Routavio utilization ratio or assert a specific saturation threshold.

A future controlled evaluation should collect at least the following measurements:

Variable	Engineering purpose
Request arrival rate	Quantify incoming search demand
Queue waiting time	Separate scheduling delay from computation
Computation service time	Characterize resource occupancy
Service-time percentiles	Identify long-running search behavior
Queue depth over time	Detect sustained backlog growth
Worker CPU utilization	Identify CPU-bound bottlenecks
Event-loop delay	Measure scheduling interference
Itinerary quality	Quantify the value of additional search
Completed requests per second	Estimate realized processing capacity

An isolated evaluation should also compare multiple search-budget configurations under equivalent workloads.

This would allow the engineering team to estimate whether quality improvements justify their operational cost.

The distinction between controlled experiments and observations of a live pilot system is important.

The published measurements establish that the longer budget improved the observed isolated search and that the deployed change produced queue starvation.

They do not establish a general numerical relationship between route quality, arrival rate, and queueing delay across all workloads.

13. Implications for Travel Planner Architecture

The findings have several consequences for the design of route optimization services.

First, a search budget is not solely an algorithmic parameter.

In a shared service, it also influences job service time and therefore effective system capacity.

Second, optimizing route quality for one difficult origin-destination pair can harm unrelated users when computation resources are shared.

Third, queueing behavior should be evaluated before extending worst-case execution limits.

Fourth, logical concurrency must be distinguished from actual CPU parallelism.

Finally, route optimization should be assessed in terms of useful completed results rather than candidate quality alone.

These considerations are particularly important for multimodal travel planners because different origin-destination pairs can have substantially different computational characteristics.

A direct flight corridor and an airportless destination requiring several transportation modes may impose very different search workloads.

Treating them as identical computational jobs can therefore create undesirable resource allocation behavior.

Conclusion

The Routavio incident demonstrated that an algorithmic improvement can be correct when measured locally and harmful when deployed globally.

Increasing the bounded search budget improved candidate discovery for a difficult multimodal route.

But the additional service time prevented the shared worker from processing other requests efficiently.

The resulting queue starvation made the overall travel planning experience worse.

The successful response was not to allocate progressively more computation time.

It was to improve search ordering, reverse reachability, and geographic pruning while preserving the service-time budget.

Queueing theory provides a useful framework for interpreting this outcome.

In interactive route optimization, computation quality cannot be separated from the capacity and latency of the system delivering it.

A route optimization engine must optimize not only which journeys it discovers, but also the computational resources required to deliver those journeys to users.

Related Research

Engineering a Multimodal Travel Planner on a 228,060-Edge Graph

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] Little, J. D. C. (1961). A Proof for the Queuing Formula: L = λW. Operations Research, 9(3), 383–387. https://doi.org/10.1287/opre.9.3.383

[3] Kingman, J. F. C. (1961). The Single Server Queue in Heavy Traffic. Mathematical Proceedings of the Cambridge Philosophical Society, 57(4), 902–904. https://doi.org/10.1017/S0305004100036094

[4] Kleppmann, M. (2017). Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media.

[5] Harchol-Balter, M. (2013). Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press.

[6] PostgreSQL Global Development Group. (2026). PostgreSQL 18 Documentation: SELECT. https://www.postgresql.org/docs/18/sql-select.html

[7] PostgreSQL Global Development Group. (2026). PostgreSQL 18 Documentation: LISTEN and NOTIFY. https://www.postgresql.org/docs/18/sql-listen.html

[8] Çı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 5.1.2–5.1.4, 6.2.4, 7.1.4, and 7.2.

Project: Routavio | Multimodal Route Optimization and Travel Planning

The reported route-discovery measurements and incident observations refer to Routavio's August 2026 pilot environment. Queueing models and illustrative calculations are theoretical explanations, not measured production benchmarks.

A 24.6x Latency Gap That Had Almost Nothing to Do With Graph Search Copy

Halil Cinar — Sat, 17 Oct 2026 13:34:14 +0000

During the performance evaluation of Routavio, a multimodal travel planning and route optimization platform, we encountered an unexpected latency pattern.

The same route computation engine sometimes completed its first search pass in less than one second, while other executions required more than twenty seconds.

The transportation graph contained 24,774 nodes and 228,060 directed edges. It represented flight, rail, coach, and ferry connections obtained from heterogeneous transportation data sources.

Given the computational characteristics of graph traversal, our initial investigation focused on the routing algorithm.

However, the evidence eventually showed that the dominant latency component was not graph search.

It was graph loading.

This article presents the performance investigation, the experimental evidence that distinguished competing explanations, and the architectural modifications introduced to address the problem.

The measurements refer to Routavio's August 2026 pilot implementation, evaluated at repository revision 71e8cd39.

1. The Computational Context

Routavio represents transportation supply as a directed, time-aware graph.

Nodes correspond to locations such as airports, railway stations, coach terminals, and city anchors.

Edges represent transportation connections with attributes including mode, duration, provider, price evidence, and schedule information.

The routing engine performs a budget-bounded, heuristically pruned depth-first search over this network.

Unlike conventional shortest-path implementations operating on a complete static graph, the engine must accommodate incomplete transportation data and connections acquired during search.

The relevant computation pipeline can be summarized as follows:

Computation Request
        |
        v
Graph Loading / Cache Lookup
        |
        v
On-Demand Transport Data Acquisition
        |
        v
Nearby Airport and Station Expansion
        |
        v
Bounded Graph Search
        |
        v
Connection Feasibility Validation
        |
        v
Multicriteria Ranking
        |
        v
Itinerary Persistence
        |
        v
Search Result

The implementation uses PostgreSQL to persist transportation segments and computation state.

An in-memory adjacency structure is constructed from the relational transport data and reused by the worker process.

This architecture avoids introducing a separate graph database, but it introduces a potentially expensive graph materialization stage.

The original performance investigation did not initially distinguish this stage sufficiently from graph traversal.

That distinction became central to explaining the latency variation.

2. Formulating Competing Hypotheses

The performance anomaly was initially attributed to three possible causes.

Hypothesis H1: Algorithmic regression

A recent change to search heuristics might have increased graph traversal work or altered pruning effectiveness.

If this hypothesis were correct, slower searches would be expected to traverse substantially more edges, expand more nodes, or exhibit less effective pruning.

Hypothesis H2: Growth of the search space

The transportation graph could have become computationally more expensive as new segments were imported.

An increase in graph density or the number of eligible connections might produce greater traversal costs.

Hypothesis H3: Worker resource contention

The Node.js worker processed route computations through multiple logical execution slots.

Because graph traversal was synchronous JavaScript, these slots shared a single event loop.

Resource contention or event-loop blocking could therefore affect response latency.

All three explanations were technically plausible.

However, selecting the most plausible explanation is not equivalent to identifying the actual cause.

As Jain (1991) discusses in the context of computer systems performance analysis, meaningful evaluation depends on workload characterization, measurement selection, and the distinction between observed behavior and causal interpretation [1].

We therefore introduced measurements designed to distinguish these competing hypotheses.

3. Stratifying Latency by Cache State

The decisive observation was that slow executions correlated with the amount of time elapsed since the previous computation.

The graph adjacency structure was cached inside the worker process with a time-to-live.

This meant that the next search could encounter either a warm graph or an expired cache requiring reconstruction.

We grouped first-pass latency measurements by the elapsed time since the previous computation.

The August 2026 pilot measurements produced the following results.

Time since previous computation	Samples	Median pass-1 latency	Share above 10 seconds
Less than 5 minutes	4,252	927 ms	12%
5 to 30 minutes	275	1,898 ms	36%
More than 30 minutes	99	22,838 ms	69%

The difference between the warm-cache and cold-cache medians was approximately:

Cold / Warm Median Ratio

22,838 ms / 927 ms = 24.6

The result revealed an important relationship between cache lifecycle state and first-pass execution time.

A request arriving shortly after a previous computation generally benefited from a resident graph.

A request arriving after cache expiration could incur the cost of rebuilding the complete adjacency structure.

However, this observation alone was not sufficient to prove the precise cause.

A change in request frequency might coincide with other factors, including provider latency, background jobs, or route complexity.

Further instrumentation was necessary.

4. Separating Graph Loading from Search Execution

The next step was to inspect the work performed by representative slow and fast computations.

The pilot telemetry recorded the following counters:

Measurement	Slow run	Fast run
Edges traversed	4.65 million	4.03 million
Nodes expanded	50,000	46,000
Prune ratio	98.9%	98.9%
Paths discovered	206	220
Event-loop lag, p95	23 ms	34 ms
Graph loading time	21,539 ms	Approximately 0 ms

These measurements were particularly informative.

The slow computation traversed somewhat more edges and expanded somewhat more nodes, but the difference in traversal work was insufficient to explain a latency gap exceeding twenty seconds.

Both runs exhibited the same reported pruning ratio.

The event-loop lag measurements did not support the hypothesis that increased event-loop contention was responsible for the large difference.

Instead, nearly the entire additional delay was concentrated in graph loading.

The analysis therefore shifted from algorithmic complexity to cache lifecycle behavior.

5. Latency Decomposition as a Diagnostic Method

A useful conceptual model separates the first computation pass into several components.

T_pass1 =
    T_graph_load
  + T_graph_search
  + T_validation
  + T_other

This is a conceptual decomposition rather than a claim that every component was independently measured with identical precision.

The distinction matters because a metric named search_duration can be misleading if it includes database acquisition, graph construction, and actual traversal.

In Routavio's investigation, the performance problem was initially examined as a search regression because the recorded phase timer did not make the graph-loading contribution sufficiently visible.

Separating the graph-loading term provided the evidence needed to reject the earlier explanations.

The case illustrates a broader methodological problem in performance engineering.

An aggregate latency measurement identifies the existence of a delay, but not necessarily the subsystem responsible for it.

Useful instrumentation should distinguish between competing causal explanations rather than simply confirming that an operation was slow.

This principle is consistent with the experimental methodology developed in Jain's The Art of Computer Systems Performance Analysis [1].

6. Why Graph Cache Lifecycle Matters

The adjacency structure was maintained as a process-local cache.

Transportation segments were stored in PostgreSQL, and the worker materialized the graph in memory when required.

This arrangement provided several architectural advantages:

Relational storage supported reporting, auditing, and data integrity.
Graph traversal operated on an in-memory representation.
A dedicated graph database was unnecessary.
The system avoided additional stateful infrastructure components.

However, the approach also created a substantial cold-loading cost.

The relevant distinction was not simply between cached and uncached data.

It was between a graph that remained resident inside the correct process and a graph that required reconstruction before an interactive computation could proceed.

A scheduled operation running in a different process could not warm the worker's module-scoped graph cache.

The cached object belonged to the worker's runtime.

This type of locality problem has conceptual connections to Denning's working-set model [2].

Denning's original work concerned virtual memory and program locality rather than application-level transportation graph caches. Nevertheless, the general principle that frequently required data should remain accessible within an appropriate memory residency policy is relevant.

For Routavio, the problem was especially visible because transportation graph materialization had a much higher cost than reusing an existing adjacency structure.

7. Correcting the Cache Lifecycle

The selected corrective approach consisted of two mechanisms.

7.1 Refresh-ahead

Rather than waiting for cache expiration to force an interactive request to rebuild the graph, the worker refreshes the graph ahead of expiry.

The existing cached representation remains available while the refresh operation is performed.

This approach reduces the probability that a user-facing computation encounters an expensive cold path.

It does not eliminate the underlying cost of graph construction.

Instead, it changes when that cost is incurred.

This distinction is important when interpreting a performance improvement.

Reducing user-visible latency is not necessarily equivalent to reducing the total computational work performed by the system.

7.2 Cache warming during worker startup

A second mechanism warms the graph cache when the worker process starts.

Without startup warming, the first request after deployment or process restart could become responsible for constructing the entire graph.

With an explicit warm-up mechanism, graph initialization can occur before an interactive route computation requires the structure.

The implementation therefore addresses two separate lifecycle events:

Routine cache expiration during operation.
Process startup following deployment or restart.

Both events previously risked exposing expensive graph loading to users.

8. Why Increasing the Cache TTL Was Not Sufficient

Extending cache lifetime would appear to be the simplest response to the problem.

If a longer TTL reduces cache misses, it should also reduce the frequency of expensive graph reconstruction.

However, transportation supply is not static.

Routavio periodically imports new transportation connections and acquires additional information from upstream providers.

A graph retained for too long may exclude newly available routes.

The application could continue operating without an exception while silently returning incomplete itinerary results.

This creates a trade-off between computation latency and transportation-data freshness.

Let A(t) represent the age of the graph since its last successful refresh.

Let L(t) represent the time required to access or reconstruct the graph.

A longer retention interval may reduce expected reconstruction frequency, but it can increase the age of the transportation data represented by the search.

The relevant engineering objective is therefore not simply to minimize cache misses.

It is to preserve an acceptable combination of response latency, data freshness, memory consumption, and itinerary quality.

For Routavio, increasing the TTL alone was rejected in favor of refresh-ahead and startup warming.

9. Dynamic Edge Insertion and Memory Pressure

The cache architecture also interacted with on-demand transportation data acquisition.

During an active search, an upstream provider could introduce flight connections that were not present in the initial graph.

These new edges needed to become visible to the ongoing computation.

The direct implementation approach was to invalidate the graph cache and reload the entire structure.

However, the old graph could still be referenced by an active computation.

Reconstructing a second graph under these conditions temporarily increased memory consumption.

In the pilot environment, this behavior caused worker crash loops.

The implemented correction was incremental graph splicing.

Newly persisted edges were incorporated into the existing cached adjacency structure, while stale entries for corresponding segment identifiers were replaced.

This avoided constructing a second complete graph merely to introduce newly acquired transportation connections.

The incident demonstrates why memory management must be considered alongside algorithmic complexity.

An operation with acceptable theoretical computational complexity may still be unsuitable when its allocation behavior exceeds the limits of a constrained runtime.

10. Interpreting the Results Through Tail Latency Research

Dean and Barroso (2013) discuss the importance of latency variability in large-scale interactive systems [3].

Their research emphasizes that average performance alone is insufficient when occasional slow operations can significantly affect user experience.

Routavio's pilot represents a different scale and architecture, but the measurement problem is related.

The overall latency distribution contained requests operating under different cache conditions.

Aggregating these observations without separating the relevant runtime states obscured an important source of variability.

The warm-cache median of 927 ms and the cold-cache median of 22,838 ms described substantially different operating regimes.

These were not measurements of two competing route optimization algorithms.

They were observations of the same system under different cache lifecycle conditions.

This distinction changes the interpretation of the result.

It would be incorrect to claim that Routavio's graph search algorithm became 24.6 times faster.

The evidence instead indicates that cold graph loading was responsible for a major component of first-pass latency variation.

The corrective mechanisms were designed to remove that expensive cold path from the normal user-facing experience.

11. Experimental Limitations

The investigation was conducted in a deployed pilot environment rather than under fully isolated laboratory conditions.

Measurements were recorded on 26 and 27 August 2026, using a single-host environment running application containers, PostgreSQL, background computation, and observability components.

Several limitations must be acknowledged.

First, the cache-state measurements were observational.

Request characteristics, scheduled jobs, and upstream data acquisition were not fully controlled across groups.

Second, the comparison between representative slow and fast runs supported the diagnosis but did not constitute a randomized experiment.

Third, the reported 24.6 ratio compared medians from different cache-state populations.

It was not a directly measured universal speedup produced by a subsequent deployment.

Fourth, the measured first-pass durations should not be confused with complete end-to-end user response times.

A separate seven-day sample of 2,864 interactive computation runs reported a median time to provisional result publication of 7,284 ms. That metric covers a different operational boundary and should not be compared directly with the first-pass medians.

Finally, the load-testing results did not establish the maximum capacity of the application.

At ten virtual users, the CDN began rate-limiting the load generator before the origin application reached saturation.

The actual application saturation point remained unmeasured.

These distinctions prevent performance measurements from being interpreted beyond the evidence available.

12. Implications for Route Optimization Systems

The investigation produced several practical conclusions for multimodal travel planning architectures.

12.1 Algorithmic optimization should follow latency attribution

A complex graph search system may contain expensive operations outside traversal itself.

Reducing path exploration is not necessarily useful if most user-visible latency originates from loading or constructing the graph.

12.2 Cache state should be treated as a measurement variable

Latency samples collected under different cache states should be separated where the difference is operationally meaningful.

Otherwise, changes in traffic frequency may appear to be changes in algorithm performance.

12.3 Freshness and performance must be evaluated together

Transportation data changes over time.

An aggressive caching policy that improves response speed while hiding newly available routes may reduce the practical quality of the travel planner.

12.4 Process boundaries determine cache behavior

A graph cached inside one worker process is not automatically available to another process.

Cache warming and invalidation policies must respect the runtime topology of the application.

12.5 Dynamic updates require explicit memory management

Reloading a complete graph after every on-demand data acquisition can introduce avoidable allocation pressure.

Incremental updates may offer a more appropriate trade-off, provided graph consistency is maintained.

Conclusion

The most important optimization in this investigation was not a modification to the route search algorithm.

It was identifying that the apparent search latency problem belonged primarily to graph-loading lifecycle management.

Once graph construction and traversal were measured separately, previously plausible explanations could be rejected.

The findings supported a revised cache architecture with refresh-ahead, worker startup warming, and incremental graph updates.

More broadly, the investigation demonstrates that performance engineering requires a precise understanding of what a measurement includes.

For multimodal route optimization systems, improving the quality of a pathfinding algorithm is only one part of delivering useful travel recommendations.

The system must also make transportation data available to that algorithm within a predictable computational budget.

Why Dijkstra Was Not Our Default for Multimodal Route Optimization

Related Engineering Research

Engineering a Multimodal Travel Planner on a 228,060-Edge Graph

References

[1] Jain, R. (1991). The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John Wiley & Sons. ISBN 978-0-471-50336-1. https://www.cs.wustl.edu/~jain/books/perfbook.htm

[2] Denning, P. J. (1968). The Working Set Model for Program Behavior. Communications of the ACM, 11(5), 323–333. https://doi.org/10.1145/363095.363141

[3] Dean, J., & Barroso, L. A. (2013). The Tail at Scale. Communications of the ACM, 56(2), 74–80. https://doi.org/10.1145/2408776.2408794

[4] Kleppmann, M. (2017). Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media.

[5] Çı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 5.1.1, 5.1.4, 6.2.2–6.2.3, and 7.1.2.

Project: Routavio | Multimodal Travel Planner and Route Optimization

All reported measurements refer to the evaluated August 2026 pilot environment. They are historical observations rather than guarantees of current platform performance.

Why Dijkstra Was Not Our Default for Multimodal Route Optimization Copy

Halil Cinar — Sat, 17 Oct 2026 13:29:22 +0000

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.

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.

Engineering a Multimodal Travel Planner on a 228,060-Edge Graph

Halil Cinar — Sat, 17 Oct 2026 13:26:17 +0000

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.

DEV Community: Routavio

When Better Route Optimization Made Our Travel Planner Slower Copy

1. Route Optimization Under a Computation Budget

2. An Airportless Destination Exposed the Trade-off

3. The Local Optimization

4. The Shared Computation Architecture

5. Queueing Theory and Service Time

6. Little's Law and End-to-End Response Time

7. Why Waiting Time Can Grow Nonlinearly

8. What Happened After Deployment

9. Search Quality Must Be Evaluated as a System Objective

10. Improving Search Quality Without Extending the Budget

10.1 Goal-directed edge ordering

10.2 Reverse reachability and remaining-leg lower bounds

10.3 Nearby-hub pruning

11. PostgreSQL Queue Semantics and Their Limits

12. What a More Rigorous Evaluation Would Require

13. Implications for Travel Planner Architecture

Conclusion

Related Research

References

A 24.6x Latency Gap That Had Almost Nothing to Do With Graph Search Copy

1. The Computational Context

2. Formulating Competing Hypotheses

Hypothesis H1: Algorithmic regression

Hypothesis H2: Growth of the search space

Hypothesis H3: Worker resource contention

3. Stratifying Latency by Cache State

4. Separating Graph Loading from Search Execution

5. Latency Decomposition as a Diagnostic Method

6. Why Graph Cache Lifecycle Matters

7. Correcting the Cache Lifecycle

7.1 Refresh-ahead

7.2 Cache warming during worker startup

8. Why Increasing the Cache TTL Was Not Sufficient

9. Dynamic Edge Insertion and Memory Pressure

10. Interpreting the Results Through Tail Latency Research

11. Experimental Limitations

12. Implications for Route Optimization Systems

12.1 Algorithmic optimization should follow latency attribution

12.2 Cache state should be treated as a measurement variable

12.3 Freshness and performance must be evaluated together

12.4 Process boundaries determine cache behavior

12.5 Dynamic updates require explicit memory management

Conclusion

Previous Article

Related Engineering Research

References

Why Dijkstra Was Not Our Default for Multimodal Route Optimization Copy

1. Classical Shortest-Path Formulation

2. The Difference Between Network Optimality and Journey Optimality

3. Why RAPTOR Was Also Considered

4. Bounded Heuristic Depth-First Search

5. Reverse-Graph Lower Bounds for Search Pruning

6. Geographic Progress and the Airport Access Problem

7. Time-Dependent Connection Feasibility

8. Dynamic Graph Updates During Search

9. Multicriteria Ranking and Route Diversity

10. Limitations and Future Evaluation

Conclusion

Related Engineering Article

References

Engineering a Multimodal Travel Planner on a 228,060-Edge Graph

1. Problem Formulation

2. The Pilot Network and Its Constraints

3. Why We Used Bounded Heuristic Search

4. Separating Route Discovery from Ranking

5. The Compute System Is Part of the Optimization Problem

6. What the Measurements Support

7. Implications for Multimodal Travel Planning

Conclusion

References