Ski itinerary optimization

Every year, my wife and I go skiing in the French Alps.

This time, we set our sights on something ambitious: skiing 100 kilometers in a single day. On a typical day, with breaks and a leisurely pace, we cover 40 to 50 kilometers.

So 100 felt like a stretch, but not impossible. The lifts run from roughly 9-17, giving us only eight hours. To make it work, we needed to properly plan for it.

We could not decide whether we should optimize for more red slopes (faster, but steeper and hence shorter) or blue slopes (slower, but longer). Hence, with help of a few LLM’s, we modelled and simulated the whole ski area to figure out the best approach.

Creating a graph model

It seemed most natural to model and solve this as a graph problem: specific points in the area are connected by edges, each with costs and rewards.

Nodes became the tops and bottoms of lifts and slopes.

Edges split into two types: slopes, where you get distance (the reward) but spend time (the cost), and lifts, which cost time but give no distance.

slopes = [
        ("Grizzly top", "Vallandry", 2.27, 'red', 'Aigle'),
        ("Le Derby Top", "Le Derby Bottom", 1.0, 'red', "Belette"),
        ("Bois de l'Ours Top", "Arc 1950", 1.5, 'black', "Bois de l'Ours")
        ...
]

lifts = [
    ("Vallandry", "Grizzly top", 8, "Grizzly Lift")
    ...
]

Getting the right data was trickier. Perplexity’s Deep Research looked promising for about 10 seconds, but the results were not usable. Barely a third was accurate, the rest was either wrong or outright invented: slopes that didn’t exist and distances that made no sense.

Next, I tried using an AI Agent called Operator, pointing it to an interactive map. Even with clear instructions, it stumbled. So I ended up taking 20 minutes to do manual data entry.

Finally, we used a few assumptions and boundary conditions:

• The time spent on a slope depends on its length and the skiing speed, the latter, we estimated based on its grading: 25km/h for blue slopes, and 35km/h for reds
• Correction for longer lift queues: based on our observations we corrected ski lift times upwards for crowded lifts
• A fixed start and end node, the place where we were staying
• My wife, who needs more mental stimulation than I do, didn’t want to ski the same slope more than 3 times in a row

This gave the following result (note that some edges are removed so that the image remains legible):

Solving the graph problem

Now that we had a model, the next step was solving it. We wanted the shortest-time path that maxed out distance (100km or more), within our eight-hour window.

I explained this to Claude 3.5 through Cursor, and it spat out a dynamic programming solution.

From the starting point it tracks time and distance, caps slope repeats at three, and memoizes (not to be confused with memorizes) the best paths to avoid redundant work. The goal? A sequence of slopes that hits the target and gets us home before the lifts close down for the day.

def find_best_ski_route(start_point, time_limit, distance_goal):
    queue = [(start_point, time=time_limit, distance=0)]
    best_route = None
    
    while queue not empty:
        current = get_next_path(queue)
        
        if current.distance > best_route.distance:
            best_route = current
            
        for each next_slope in possible_slopes:
            # Check whether slope stays within time limit
            # and does not repeat itself 3 times
            if is_valid_move(next_slope):
                new_path = current + next_slope
                add_to_queue(new_path)
                
    return best_route

Optimizing the AI slop

With this approach, the number of possible paths grows exponentially as the target distance increases. A solution for 30km was found within seconds, while 100km took tens of minutes as it had to investigate millions of options.

When using only generic prompts to make the approach more efficient, Claude 3.5 did not come up with a noticeably more efficient approach. Based on the requirements of the specific problem, I prompted it to try two specific items:

• Do not look for the global optimal path, just a path that has the minimal length (100k) within the time constraint (8 hours). This caused it to change the logic to terminate when a satisfying solution is found.
• If an efficient loop of slopes is discovered, a potential solution would likely include this loop multiple times (but not more than 3 times consecutively). After which it introduced a heuristic.

These two improvements made it about ±20x as fast and gave the output below.

As you can see it only brings us to 105km, so very little buffer.

Real-life testing

We largely followed the plan and achieved 110 kilometers (Strava as proof for the work).

We deviated slightly from the planned route to accommodate a bathroom break. We did more than compensate for that by setting some personal speed records.

Sample code here.