Warm Start, Local Search and Neighbourhoods: how our engine continuously re-optimises routes

Published on 1 June 2026 • Reading time: 8 min read

In vehicle routing optimisation problems, producing an initial solution is rarely the main challenge. The real difficulty emerges when a schedule must evolve in response to operational events such as the addition of a new job, a delay, a cancellation, a change in customer requirements, vehicle reassignment, or local route saturation.

In this context, the engine is no longer working on an initial problem. It must adapt a system that has already been built, is already constrained, and is often already partially optimised, while preserving as much of its overall quality as possible. This ability to efficiently evolve an existing schedule is precisely what distinguishes dynamic optimisation problems from more traditional theoretical approaches.

This article deliberately focuses on the re-optimisation mechanisms used in dynamic routing engines: warm start, local search, neighbourhood structures and exploration heuristics. For a broader overview of route optimisation challenges in last-mile logistics, you can also read our comprehensive guide to route optimisation.

In real-world operations, a high-performing engine cannot start again from scratch every time an event occurs. Optimisation algorithms must be capable of locally re-optimising a live schedule without unnecessarily disrupting existing routes.

At AntsRoute, this challenge sits at the core of our optimisation engine architecture.

What you’ll learn in this article:

• Why starting from scratch is not viable in real-time operations
• The role of warm starts in dynamic routing
• Why every insertion must be evaluated globally
• How local search works
• Why not all neighbourhoods deserve the same level of exploration
• First-improvement vs Best-improvement: two optimisation strategies
• Why exact methods quickly reach their limits

Why starting from scratch is rarely a good strategy

In theory, completely rebuilding a schedule after every change might seem like the best approach. In practice, however, this strategy quickly becomes impractical due to the explosion in the number of possible solutions to explore, the computational effort involved, and the operational instability it creates for field teams.

As explained by Ammar Oulamara, Head of R&D at AntsRoute:

“A real-time optimisation engine cannot fully rebuild routes every time a new event occurs. The computational cost and the resulting instability would simply be too high.”

This is precisely why modern routing engines rely on warm-start approaches.

Warm Starts: building on an existing optimised solution

The principle of a warm start is to use the current schedule as the starting point for optimisation. Rather than searching for an entirely new solution, the engine seeks to improve a solution that is already coherent, making targeted local adjustments while minimising any degradation that could affect the overall balance of the system.

This approach offers several important advantages:

• A dramatic reduction in the search space;
• Greater operational stability;
• Response times compatible with real-time operations;
• Fewer unnecessary schedule disruptions.

As Ammar Oulamara explains:

“Warm starts allow the engine to focus its computational power on the areas that are genuinely affected by a scheduling change.”

This fundamentally changes the way the problem is explored.

An insertion should never be evaluated in isolation

When a new job, τ, is inserted into a schedule, the engine does not simply evaluate its immediate marginal cost. In reality, that insertion can have consequences across the entire plan by affecting:

• Time-related constraints;
• Operational buffers and slack time;
• The balance between routes;
• Future re-optimisation opportunities;
• The geographical compactness of the schedule.

The engine must therefore explore not only the insertion itself, but also the local reorganisations that the insertion may subsequently enable. It is precisely this ability to improve an existing solution that lies at the heart of local search mechanisms.

Local Search: exploring the neighbourhood of a solution

In vehicle routing problems, it is impossible to exhaustively explore every possible solution. Modern optimisation engines therefore rely primarily on neighbourhood search techniques.

The principle is straightforward:

• Start from an existing solution;
• Apply targeted local modifications;
• Evaluate whether the resulting solution improves the overall schedule.

At AntsRoute, the local search algorithm relies on several operators that efficiently explore these neighbourhoods.

Relocate: moving a job to a better position

The relocate operator is one of the most fundamental mechanisms in local search. It consists of removing a job from a route and reinserting it in a different position, either within the same route or in another route.
This operation can be used to:

• Restore scheduling flexibility and time buffers;
• Rebalance workloads across routes;
• Reduce certain cascading effects caused by earlier planning decisions.

In dynamic routing systems, relocate often plays a central role in rapid re-optimisation because it enables local improvements to be made with a relatively low computational cost.

Or-opt: moving sequences of jobs

In some situations, moving a single job is not enough to restore a well-balanced schedule. The engine then uses Or-opt operators, which involve moving a sequence of one, two or three consecutive jobs to a different position within a route or elsewhere in the schedule.

This approach is particularly useful when:

• Several jobs share a strong geographical relationship;
• A local reorganisation requires certain route continuities to be preserved.

As Ammar Oulamara explains:

“Moving a coherent group of jobs can sometimes restore the balance of a schedule far more effectively than a series of isolated changes.”

2-opt and 3-opt: reshaping the geography of routes

The 2-opt and 3-opt operators serve a different purpose. They involve reversing specific subsequences within a route in order to improve its geographical structure.

These mechanisms can be used to:

• Eliminate route crossings;
• Improve geographical compactness;
• Reduce unnecessary detours.

They are particularly effective when:

• Routes become fragmented over time;
• A series of successive insertions gradually degrades their spatial structure.

Even in systems heavily constrained by time-related requirements, the geographical quality of routes remains a key factor in operational robustness.

Cross-Exchange: rebalancing multiple routes simultaneously

In highly constrained systems, some insertions cannot be absorbed through simple local adjustments. The engine must then reorganise multiple routes simultaneously using cross-exchange operators, which involve swapping entire route segments between routes in order to restore a better overall balance.

These mechanisms become particularly valuable when:

• Critical resources are approaching saturation;
• Multiple routes are becoming vulnerable from a scheduling perspective;
• Opportunities for local reorganisation are becoming increasingly limited.

At this stage, the engine no longer reasons solely at the level of an individual route. Instead, it evaluates the schedule as a whole in order to identify the most effective rebalancing opportunities.

Not all neighbourhoods deserve the same computational cost

Exploring every candidate insertion in depth would be far too costly from a computational standpoint. The engine must therefore prioritise its efforts and focus its processing power on the most promising solutions. At AntsRoute, this exploration is based on a hierarchy of neighbourhoods, allowing the depth of the search to be adjusted progressively according to the quality of the insertions being evaluated.

Degree 1 Neighbourhood

The first neighbourhood level is based solely on simple local modifications within a single route. The aim is to quickly filter out clearly unfavourable insertions while keeping computational cost low.

Degree 2 Neighbourhood

At this stage, the engine allows exchanges between routes, as well as broader rebalancing operations. This exploration makes it possible to assess the wider consequences of certain insertions and identify improvements that would not be visible at the level of a single route.

Degree 3 Neighbourhood

The third neighbourhood level allows much deeper reorganisations, which may include multi-day restructuring or significant changes to the schedule. These more costly explorations are reserved for the most promising insertions or for particularly constrained situations.

This hierarchy of neighbourhoods enables processing power to be allocated intelligently by adapting the depth of the search to the quality of the solutions encountered.

First-improvement vs Best-improvement

One of the most important trade-offs in local search concerns the strategy used to explore the neighbourhood of a solution. Two main approaches are commonly employed: first-improvement and best-improvement.

First-improvement

With the first-improvement strategy, the engine accepts the first improvement it encounters during neighbourhood exploration. This approach offers several advantages:

• Fast convergence;
• Low computational cost;
• Good efficiency during the early stages of exploration.

Best-improvement

By contrast, the best-improvement strategy explores the entire neighbourhood before selecting the best available improvement. It generally makes it possible to:

• Achieve higher-quality solutions;
• Explore optimisation opportunities more thoroughly.

The trade-off, however, is a significantly higher computational cost.

As Ammar Oulamara explains:

“The choice between first-improvement and best-improvement depends heavily on schedule density and the available computational budget.”

At AntsRoute, the engine dynamically alternates between these two strategies based on the quality of the solutions observed, the level of convergence reached, and the degree of schedule saturation.

Why exact methods quickly reach their limits

Dynamic vehicle routing problems belong to a particularly complex class of combinatorial optimisation problems. As constraints multiply, routes become denser, and real-time events occur more frequently, the size of the search space grows dramatically. At that point, exact methods quickly become incompatible with operational requirements, both in terms of computation time and responsiveness.

As Ammar Oulamara points out:

“The engine is not looking for the theoretically perfect solution. It is looking for the best solution that can be deployed within a computation time compatible with real-world operations.”

This is precisely why modern optimisation engines rely on a combination of heuristics, warm-start mechanisms, local search operators and adaptive exploration strategies to rapidly produce solutions that are both robust and operationally relevant.

Conclusion

In modern route optimisation systems, the challenge is not simply to build an initial schedule. The real difficulty lies in continuously adapting that schedule without compromising its robustness, stability or operational quality.

Warm starts, local search operators and multi-neighbourhood exploration techniques are specifically designed to address this challenge. In last-mile logistics, a route is never truly fixed. It must constantly adapt to changing field conditions while maintaining a high level of operational performance.