How a time budget becomes a route.

The usual way to make a router pick nicer roads is a blanket penalty. A broad preference such as "avoid highways" changes the cost of that road class everywhere. It does not know whether a pleasant parallel road exists, whether the highway is the only practical bridge, or whether your remaining allowance is five minutes or fifty. Ask for it in the SF Bay Area and you can get a four-hour back-road odyssey that still crosses the one bridge it was trying to dodge.

astray asks a different question: what does each detour buy? The unavoidable bridge keeps its ordinary travel time because there is no useful alternative nearby. A forest road, ridge crossing, or coastal stretch can justify extra time when it adds enough value to the drive. The route is free to use fast roads as a spine and spend its limited allowance only where the map offers something worth buying.

None of this needs corridor-specific rules. It falls out of two commitments: time gets a hard limit, and desirable roads get value. The rest of this article follows that sentence down into the engine: the kind of problem it is, the algorithm that makes it interactive, and the first place the approach genuinely failed.

The ask can be stated as two rules: never exceed the driver's time allowance, and within that limit choose the route that accumulates the most scenic value. Routing research describes this as the Arc Orienteering Problem², part of the broader orienteering family^1,3. In plain terms, time is the constraint and the quality of the drive is the objective.

This class of problem is NP-hard⁴: the number of possible routes grows too quickly for an interactive product to compare all of them exactly. The engine therefore needs a bounded search that produces useful answers quickly, with limits we can measure and explain.

Take a trip that has to cross a bridge with no alternative. The bridge earns no scenic reward, but it pays no penalty either; it costs its actual travel time and nothing more. So the search crosses it at full speed and keeps the saved minutes for a detour later that actually earns them.

Route search is fastest when every edge carries a single cost to minimize. Our request has two quantities: travel time and scenic value. The move is to give scenery a price. One adjustable number, scenery_price, converts scenic value into time, so the search still minimizes a single cost. Set the price low and the engine behaves like any fast router; raise it and the engine willingly pays minutes for a better road. The formal name for this conversion is Lagrangian relaxation⁷, and the price is the Lagrange multiplier, written λ in the literature.

The first run sets scenery_price to zero and returns the fastest route. Its fastest_time establishes the ceiling: either fastest_time + extra_minutes or a percentage above the baseline. Later runs raise the scenery price and produce routes that trade more time for more scenic value. The engine keeps the best candidate that remains within the ceiling.

The direct formula is a trap. Subtracting the reward, travel_time − scenery_price·scenic_value, lets a sufficiently scenic road acquire a negative cost. The route searches doing the work here are Dijkstra's algorithm⁵ and its destination-directed refinement, A*⁶. They repeatedly extend the cheapest path discovered so far. Once a location is settled, they rely on every additional road increasing the total cost, so a later path cannot make that settled result cheaper.

A negative road cost breaks that guarantee. The search can settle a more expensive route while a route that becomes cheaper later is still waiting to be explored, returning the wrong answer without an error. A loop whose total cost is negative is worse: there is no shortest route because each lap makes the calculated cost lower. We avoid both cases by charging for the absence of scenery. The useful preference remains, while every road cost stays at least as large as its travel time:

scenic_value(edge) ∈ [0, 1]
cost(edge, scenery_price) = travel_time(edge) · (1 + scenery_price · (1 − scenic_value(edge)))

scenery_price ≥ 0  ⇒  cost(edge) ≥ travel_time(edge)

At a scenery price of zero, cost is travel time and the result is the fastest route. As the price rises, roads with little scenic value become relatively expensive while a road with the maximum scenic value keeps its actual travel time. The search changes its preference without ever receiving a negative edge.

The scenic value needs a reliable range, and here lives the second trap: user preferences are signed. A driver who gets carsick assigns negative value to sharp bends, which can drag the raw combined score below zero. So for each request the engine maps the middle 90 percent of actual road scores into [0, 1] and clamps the extremes. One bounding step, applied in one place, before anything touches the search.

A* avoids exploring the entire graph by estimating the least possible time still needed to reach the destination: straight-line distance divided by the fastest supported road speed. This estimate can never exceed the real remaining travel time, a property A* calls an admissible heuristic. Because our calculated road cost is always at least its travel time, that estimate remains safe at every scenery price. That one property is what keeps a multi-price search fast enough to feel interactive.

Our first implementation exposed a practical limitation in the price-based search. On a measured Richmond, CA to Occidental trip, it found routes taking 68, 71, 78, and 80 minutes, then nothing until 116. A driver could raise the allowance from 25 to 50 to 75 percent and receive the byte-identical 80-minute route every time. The budget slider was a no-op.

The reason becomes clearer if every possible route is plotted by travel time and scenic value. The useful routes form a boundary: for each amount of time, they show the most scenery available. This boundary is called the Pareto frontier. Changing one scenery price after another can reach only the outer, convex portion of that boundary. A useful middle route can sit inside a bend in the frontier and lose at every possible price, even when it is the best route for the driver's stated budget. Optimization literature calls this a duality gap⁷.

A fixed set of scenery prices made the gap larger by skipping the narrow price range that produced the 116-minute route. We addressed both problems with three additions to the same routing core:

• Search the price range adaptively. A fixed list of prices misses breakpoints. The engine splits the largest observed travel-time gap and tests the price between its endpoints, concentrating work exactly where a new route can appear.
• Generate routes through promising areas. Score map cells by reachable scenic value, then test routes from the origin through a promising cell to the destination. These intermediate waypoints produce useful middle routes that changing the scenery price alone cannot reach.
• Prefer alternatives that use different roads. Pool candidates from the fastest search, the price search, and the waypoint search. Choose the primary route by total scenic value within budget, then measure road overlap when selecting alternatives. The overlap measure is edge-set Jaccard distance⁸, but its product purpose is straightforward: each displayed option should be meaningfully different.

After the rework, the same trip responds to its allowance: +25% yields the 80-minute route, +75% yields 116 minutes, and +100% yields 130, each with distinct alternatives. The measured worst case on that long cross-region corridor is about 2.6 seconds of single-core work, or roughly 27 bounded A* searches.