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:
-
Lis the mean number of jobs in the system. -
λis the mean effective throughput. -
Wis 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.
Top comments (0)