Good Enough Instead of Optimal

On the day I started designing RotaAkıl I wrote the problem down in a single sentence: “One depot, thirty stops, two vehicles; find the shortest route.” The sentence looks that innocent. A few days later I realized the most expensive word in it was “shortest.”

The vehicle routing problem (VRP), and its simpler form the traveling salesman problem (TSP), sit in the NP-hard class in computer science. What that means in practice is this: as the number of stops grows, finding the exact solution stops being a gap you can close by buying a faster computer.

How many possibilities is thirty stops?

You leave the depot, visit every stop and return to the depot. Since the order in which the stops are visited can change, the number of possible routes is the factorial of the number of stops. The numbers leave human intuition behind very quickly.

The real message in the table is not the durations but the jump between them. When you add one stop, the workload is roughly multiplied by that number: the 21st stop makes the number of orderings to try twenty-one times larger. Making the machine twice as fast means nothing next to that. This is not a curve you can chase with hardware.

You can replace brute force with smarter exact methods — dynamic programming, branch and bound. These improve the table considerably and genuinely solve mid-sized instances. But what they do is not reduce the steepness of the curve; they push the point where the explosion starts a little further out. On a large enough instance you hit the same wall again.

Is the exact solution a goal or a luxury?

At this point the question stops being technical and turns into a product question. I thought about who would use RotaAkıl: someone standing in their depot at eight in the morning, wanting to plan the day's deliveries. That person has two options.

• The mathematically shortest route. No telling when it will be ready.
• A route close to the shortest. On screen in a few seconds.

I could not think of a single user who would not pick the second one. Because every minute spent waiting for the route comes out of the minutes the route is supposed to save. Past a certain point, looking for a “better solution” makes the solution itself worthless.

Once that was clear, my goal sentence changed: not “find the shortest route” but “give me the shortest route you can find within three seconds”. These two versions of the same problem mean two completely different pieces of software. The first is a computation whose end you cannot predict; the second is a function you can measure, budget for and place in an interface.

The skeleton of the heuristic approach: first a solution, then improvement

The shared logic behind heuristic methods is simple. Instead of scanning every possibility, you start with a reasonable answer and then improve that answer step by step. You give up the guarantee and buy time in return.

The first stage is the nearest neighbor rule: from wherever you are, go to the closest unvisited stop. It produces a route in under a second, but the result is usually bad. Because it acts greedily, it skips a few stops along the way; in the end it has to drive back to the other side of the map to collect them.

The second stage corrects that mistake. The local improvement known as 2-opt detaches two links in the route and reverses the segment between them; if the total distance got shorter, it accepts the change. You can think of it as untangling the paths that cross each other on the map, one at a time.

# Stage 1 — fast initial solution (nearest neighbor)
rota  = [depo]
kalan = duraklar[:]
while kalan:
    d = en_yakini(rota[-1], kalan)
    rota.append(d)
    kalan.remove(d)

# Stage 2 — local improvement (2-opt)
# Detach two edges, reverse the segment between them, accept it if shorter.
for i in range(1, len(rota) - 2):
    for j in range(i + 1, len(rota) - 1):
        eski = mesafe(rota[i-1], rota[i]) + mesafe(rota[j], rota[j+1])
        yeni = mesafe(rota[i-1], rota[j]) + mesafe(rota[i], rota[j+1])
        if yeni < eski:
            rota[i:j+1] = rota[i:j+1][::-1]

At the end of these two stages you have a route that is good locally: no single small change on its own makes it shorter. But that does not mean the route is the best one overall. The algorithm falls into a pit and stays there.

Turn time into a parameter

The way out of the pit is to deliberately break the good solution you have a little and then put it back together. You move a few stops around at random, then apply 2-opt again. Sometimes the result is worse and you throw it away; sometimes it is better and you keep it.

What decides when this loop stops is no longer mathematics but the time budget you set:

en_iyi = baslangic_cozumu(duraklar)
bitis  = simdi() + butce_saniye        # for example 3 seconds

while simdi() < bitis:
    aday = rastgele_sars(en_iyi)       # perturb the route a little
    aday = yerel_iyilestir(aday)       # clean it up with 2-opt
    if uzunluk(aday) < uzunluk(en_iyi):
        en_iyi = aday

return en_iyi                          # whatever is in hand when time runs out

My favorite thing about this structure is that the algorithm has a valid answer at every moment. You can stop it at any second you like and you are left with a working route. You cannot cut an algorithm that is searching for the exact solution in half; it either finishes or gives you nothing.

On the product side this difference shows up directly in the interface. Instead of showing a “loading” spinner, you can say “here is your route, I am still improving it in the background.” The user is not waiting, they are watching. Two different presentations of the same computation, and the difference between them is a design decision, not an algorithmic one.

You are giving a perfect answer to an estimated input anyway

This is what really broke the obsession with the optimal solution. The distances and durations you use while computing the route are not real, they are estimates. Traffic changes in the late afternoon. At one stop the customer takes a while to open the door. Looking for parking takes five minutes. A street is closed because of roadworks.

So even the exact solution is not really “exact.” You have drawn a mathematically flawless line on top of a wrong map. The small gap the heuristic leaves behind disappears under the uncertainty of the input. If nobody in the field can tell the difference between two numbers, the time you paid to close that gap is wasted.

Do not write “best route” in the interface

This decision has a side that shows up directly in the interface. If you put “best route” on the screen, two things happen: you make a promise you cannot keep, and you silence the user. Yet the person who knows the field is the user. The algorithm does not know that you cannot park on that street around midday.

In the design I settled on these three things:

• Wording: not “best” but suggested order.
• Intervention: let the user drag the stops and change the order.
• Feedback: when they change it, let them see immediately how much the total time went up or down.

The third item is what makes the first two meaningful. The user can argue with the algorithm and see the result of the argument as a number. That is far stronger than saying “trust us.” And it is honest: a heuristic solution cannot claim to be the best anyway, so the interface should not claim it either.

The same trade-off is not specific to routing

Once I noticed this way of thinking, I started seeing it in work I had done earlier too. In Social Connect I had built video calling on top of JitsiMeet, hosted on my own server. The question there was the same: the highest possible video quality, or a connection that does not drop when the network gets weak even if the resolution falls? For the user the right answer is the second one. Nobody wants a sharp frozen frame.

When you sort a crowded list, lay out search results or generate a recommendation, the same question keeps coming up: do you want the perfect answer, or the good answer that arrives within the time the user is willing to wait? The product's answer is almost always the second one.

The professional lesson, I think, is this: “optimal” is not a goal, it is a budget line. You are the one who decides how much optimality you want, based on the time you have and the quality of the data. Making that decision consciously is engineering. Not making it and saying “let it run until it finds the best one” usually means shipping nothing at all.

RotaAkıl is still at the design stage; I have not written its code. But the real thing this work gave me was not an algorithm, it was a question: “What does good enough mean for this problem?” Projects started without answering that question up front never get released, because of improvements that never end.

• Algorithms
• Route Optimization
• NP-Hard
• Heuristics
• R&D