Why adding a single delivery can disrupt an entire route

Published on 26 May 2026 • Reading time: 6 min read

In dynamic route optimisation problems, the hardest insertions to manage are not necessarily the most expensive.
Some are immediately invalid:

• skill mismatch,
• capacity exceeded,
• time window violation,
• regulatory impossibility.

These cases are relatively easy to rule out.

The truly complex situations are often far more ambiguous.
A new task may appear perfectly coherent from a geographical perspective — minimal detour, close to other jobs, a natural fit within the route — while still significantly degrading the overall quality of the schedule once all constraints have been propagated.
This is precisely the type of problem a real-time optimisation engine must solve in last-mile logistics.

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

“A locally optimal insertion can produce a significant overall degradation of the schedule once all temporal and operational constraints are taken into account.”

This distinction between local optimisation and overall schedule stability lies at the heart of modern dynamic insertion problems.

For a broader overview of route optimisation mechanisms in last-mile logistics, you can also read our complete article on route optimisation.

In this article, we will cover:

• Why dynamic insertions are far more complex than they appear
• The limitations of marginal cost when evaluating routes
• How time windows create strong interdependencies
• Why a feasible route can quickly become highly fragile
• The impact of operational constraints on insertions
• How the optimisation engine locally reorganises the schedule
• Why not all insertions deserve the same level of exploration

The insertion problem is far broader than it may initially appear

Within an already built multi-day schedule, a new task τ does not have a single possible insertion point.

The optimisation engine may potentially need to explore a decision space of the following form:
(day d) × (route rᵢ ∈ R_d) × (position p within rᵢ)

In other words:

• several candidate days,
• several routes per day,
• several possible positions within each route.

And every candidate insertion affects distance-related costs, propagated schedules, waiting times, temporal slack, the feasibility of operational constraints, as well as the future ability to reorganise the schedule.

The problem quickly becomes combinatorial.

In real-world systems, the challenge is therefore not simply to find “an available slot”, but to evaluate the overall quality of every candidate insertion.

Why marginal cost is not enough

Most insertion approaches naturally begin by measuring the marginal cost introduced into the route:
Δc = c(vₚ₋₁, τ) + c(τ, vₚ) − c(vₚ₋₁, vₚ)

This metric remains essential. It makes it possible to evaluate the additional geographical cost created by inserting a new task τ between two consecutive vertices in a route.
However, in highly constrained routes, this criterion quickly becomes insufficient.

Let us take a simple example.
Two insertions generate exactly the same marginal cost:

• the same increase in mileage,
• the same additional travel time.

And yet, the first preserves substantial temporal slack across the remainder of the route, while the second concentrates several critical jobs within an already highly congested time window between 2 pm and 4 pm.

Geographically, both insertions appear equivalent. Temporally, however, they are completely different.
The second insertion makes the route far more sensitive:

• to traffic,
• to delays,
• to service time overruns,
• or to last-minute emergencies.

In other words, local cost does not necessarily reflect the overall stability of the solution.

Time windows create strong interdependencies

In a VRPTW (Vehicle Routing Problem with Time Windows), each task is linked to the previous ones through a chain of temporal dependencies.
The arrival time at a stop implicitly depends on:

• previous travel times,
• service durations,
• potential waiting times,
• and delays accumulated earlier in the route.

When a new task is inserted, the entire temporal structure must be recalculated.
It is this propagation effect that makes dynamic insertions particularly sensitive.
A delay of just a few minutes in the middle of a route may be enough to:

• eliminate safety margins,
• shift a mandatory break,
• generate additional waiting times,
• or trigger multiple violations later in the day.

At AntsRoute, the optimisation engine notably penalises unnecessary waiting times:
min Σᵢ max(0, eᵢ − tᵢ)

where:

• ei represents the opening of the customer’s time window,
• and ti the estimated arrival time.

These waiting times are often underestimated in simplified approaches, even though they significantly reduce productivity, route density, and the future ability to absorb unexpected disruptions.

A route may be feasible… yet extremely fragile

In many systems, feasibility is treated as a binary condition:

• an insertion is valid,
• or it is not.

In real-world operations, however, the situation is far more nuanced. Some insertions remain technically feasible while still producing an extremely fragile route.
For example, a route may comply with all time windows while leaving virtually no temporal slack at all, remaining technically valid yet becoming incapable of absorbing even the slightest delay.

As Ammar Oulamara points out:

“The challenge is not only to guarantee the immediate feasibility of an insertion. It is also necessary to preserve the operational robustness of the schedule.”

This notion of robustness becomes central in dynamic systems.
A solution that is slightly less optimised in terms of mileage may therefore be preferable if it preserves greater operational flexibility.

Operational constraints further amplify these ripple effects

The challenges increase significantly when the optimisation engine must integrate complex operational constraints:

• specific skills,
• certifications,
• specialised equipment,
• working hour limits,
• vehicle capacities,
• pickup & delivery constraints,
• and assignment rules.

Some resources then become critical.
A poorly positioned insertion may, for example, prematurely saturate an agent with a rare skill set, prevent future reassignment opportunities, or lock certain reorganisation possibilities altogether.

In pickup & delivery problems, the optimisation engine must also guarantee precedence constraints:
t(dτ) − t(pτ) ≤ Δtₘₐₓ

In other words, the maximum delay between a pickup and its delivery must remain compatible with the operational constraints of the system.
These additional dependencies significantly increase the complexity of dynamic insertions.

Why the optimisation engine must locally reorganise the schedule

Faced with these multiple interactions, a simple direct insertion logic is no longer sufficient.
A candidate insertion must often be followed by a local reorganisation phase aimed at restoring an acceptable balance within the schedule.
At AntsRoute, the optimisation engine leverages several local search operators:

• relocate,
• Or-opt,
• 2-opt,
• and cross-exchange.

The objective is not merely to make the insertion feasible.
It is also about:

• reducing propagation effects,
• restoring temporal slack,
• improving route compactness,
• and preserving the overall stability of the system.

As Ammar Oulamara explains:

“An insertion should never be evaluated in isolation. It is also necessary to measure the local improvement potential it subsequently enables.”

This logic is fundamental in modern optimisation engines.

Not all insertions deserve the same level of exploration

One of the main challenges for a real-time optimisation engine is computational cost.
Exhaustively exploring every possible reorganisation would be incompatible with the operational constraints of last-mile logistics.

This is why our engine uses a hierarchy of neighbourhoods.
Clearly unfavourable insertions are quickly eliminated through limited local modifications.
More promising insertions then benefit from deeper exploration:

• inter-route exchanges,
• multi-day reorganisation,
• and advanced local optimisation.

This structure makes it possible to intelligently concentrate computing power on the solutions that truly matter.

Conclusion

In dynamic routing systems, a geographically optimal insertion can produce highly negative effects on the overall quality of the schedule.

A route is not merely a sequence of journeys. It is a constrained operational structure in which temporal slack, operational dependencies, reorganisation capabilities, and operational robustness are constantly evolving.

Optimising dynamic insertions is therefore not merely about minimising additional mileage.
Above all, it is about preserving the overall balance of the system after every schedule modification.