Solving Large Pickup and Delivery Problems with Adaptive Large Neighborhood Search

In the first article of this series, I introduced Los Movimientos, the routing problem I used to face in my previous job in the oil and gas industry.

The operation involved two related but separable transportation problems. We had to move personnel using pickup trucks, and we also had to move tools and equipment using heavy trucks. Since people and heavy equipment obviously did not travel in the same vehicles, the two problems could be planned independently.

In Part I, I focused only on personnel transportation.

This was a pickup-and-delivery problem. Sometimes a pickup truck had to collect people at the operational base and take them to a drilling rig. Sometimes it had to pick up personnel at one rig and transfer them to another. In other cases, it had to collect people from a rig and bring them back to the base.

Each movement therefore had an origin, a destination, a number of passengers, and a time window. The challenge was to decide which truck should serve each request, in what order the locations should be visited, and how to respect vehicle capacities, pickup-before-delivery relationships, operating hours, and safety restrictions.

It was an extremely difficult problem to solve manually.

Although my experience comes from oilfield operations, this is also a typical pickup-and-delivery and last-mile logistics challenge. Retailers, transportation companies, food-delivery platforms, and e-commerce businesses face similar decisions every day.

As the way we purchase and consume becomes increasingly digital, these problems will only become more relevant. More online orders mean more stops, tighter delivery commitments, larger fleets, and greater pressure to use transportation resources efficiently.

And no, autonomous trucks will not make the problem disappear.

Even if nobody is physically driving the vehicle, we will still need to decide which truck serves each request, in what order it visits the locations, and how to minimize distance, delays, and operating costs. The driver may change, but the routing problem remains.

In Part I, we solved a small version of Los Movimientos, formulated as a MILP (Mixed Integer Linear Program), based on the formulation of Pisinger et al. [1], and solved it exactly using Pyomo (a mathematical programming modeling framework) and HiGHS (an open-source, free-to-use solver). In this second article, we move to a larger and more complicated instance of Los Movimientos and tackle it using Adaptive Large Neighborhood Search (ALNS), a powerful metaheuristic designed for routing problems that become too large or too slow to solve exactly.

Why Not Keep Solving It with a MILP?

In Part I, the mixed-integer linear programming model worked beautifully. We gave Pyomo the requests, vehicle capacities, travel times, and time windows, and HiGHS returned a provably optimal set of routes. So why not simply continue using the same approach? The answer is scalability.

Routing problems grow extremely quickly. Every additional request introduces both a pickup and a delivery, and the model must decide which vehicle will serve them, where the pickup should appear in the route, and where the delivery should be placed afterwards. At the same time, every route must respect capacity limits, pickup-before-delivery precedence, service time windows, operating hours, vehicle compatibility, and, in our larger instance, mandatory driver breaks. Adding a few requests therefore creates many new assignments and sequencing possibilities, producing the combinatorial explosion that makes routing problems so difficult.

An exact solver may find a very good feasible solution relatively quickly, but proving that no better solution exists can take much longer. For a company planning tomorrow morning’s routes, that distinction matters. A mathematically proven optimum delivered three days later may be less useful than an excellent feasible solution produced in five minutes. This does not make MILP a bad approach. Exact optimization remains extremely valuable for small and medium-sized instances, particularly because it can detect infeasibility and provide a certificate of optimality. It also gives us a benchmark against which we can evaluate a heuristic.

Commercial solvers such as Gurobi or CPLEX can solve larger instances than many open-source alternatives, but they cannot eliminate the combinatorial nature of the problem. As the number of requests and vehicles increases, even the strongest exact methods may eventually require more time than the operation can afford. This is especially relevant in logistics and e-commerce, where routes may need to be recalculated as new orders arrive, vehicles become unavailable, or customer requirements change.

At that point, we change the question. Instead of asking whether we can prove that a route is the best possible one, we ask whether we can find a very good, fully feasible route within the time available. That is where heuristics become useful. For Los Movimientos, we will use Adaptive Large Neighborhood Search, or ALNS, which repeatedly removes part of an existing solution and reconstructs it in a different way. Its philosophy is simple: destroy part of the route, repair it, and keep repeating the process until something better appears.

How Adaptive Large Neighborhood Search Works

The basic idea behind Adaptive Large Neighborhood Search is surprisingly simple: start with a feasible solution, partially destroy it, repair it in a different way, and repeat the process many times. Unlike traditional local-search methods that make very small changes — such as moving one request from one truck to another — ALNS can remove and reorganize a substantial part of the solution in a single iteration. This allows the search to escape routes that look locally good but prevent larger improvements.

Suppose we already have a complete plan for Los Movimientos. Each pickup and delivery has been assigned to a truck, and every truck has an ordered route. During one ALNS iteration, the algorithm first chooses a destroy operator and removes several complete transportation requests. Removing a request means deleting both its pickup and delivery from the route. These requests are temporarily placed back into the request bank, leaving several holes in the current solution.

The implementation developed here uses three destroy operators. Random removal simply selects requests randomly, introducing diversity into the search. Worst removal targets requests that appear particularly expensive in their current positions, since moving them elsewhere may reduce distance or duration. Related removal removes requests with similar origins, destinations, time windows, or passenger quantities. The idea is that removing a whole cluster of related requests gives the algorithm an opportunity to reorganize that part of the plan more intelligently. These strategies explore the solution from different perspectives: one introduces randomness, one attacks inefficient assignments, and one restructures groups of similar movements.

Once part of the solution has been destroyed, a repair operator attempts to reinsert the removed requests. Every candidate insertion must place the pickup before the delivery and must preserve capacity limits, time windows, operating hours, and mandatory driver breaks. The first repair operator uses greedy insertion, repeatedly choosing the request and position that produce the smallest immediate increase in cost. This is fast and intuitive, but it can be shortsighted because the easiest request to insert now may block another request later.

The second repair operator uses regret-2 insertion. For each unassigned request, it compares its best and second-best insertion possibilities. If the best position is much better than the second-best one, the algorithm experiences high “regret” from postponing that request and inserts it first. In plain terms, the rule says: place this request now because we may lose its only good opportunity if we wait. The original ALNS framework combines several insertion strategies because different operators may perform better on different problem instances.

After repairing the routes, the algorithm must decide whether to accept the new solution. An obvious rule would be to accept it only when it improves the objective. The problem with that rule is that the search can become trapped in a local optimum. To avoid this, ALNS uses a simulated-annealing acceptance mechanism. Better solutions are always accepted, but slightly worse solutions may also be accepted, particularly near the beginning of the search. This temporary willingness to move backwards can help the algorithm reach a much better region later. As the search progresses, the probability of accepting worse solutions gradually decreases.

The final ingredient is what makes the method adaptive. Destroy and repair operators are not selected equally throughout the search. Each operator receives a weight based on its recent performance. Operators that frequently produce new best solutions or useful accepted moves receive higher weights and are chosen more often through a roulette-wheel mechanism. Poorly performing operators remain available, since they may still become useful later, but they are selected less frequently. The algorithm therefore learns which combinations of destroy and repair strategies are most effective for the particular instance it is solving.

The complete process can be summarized as follows:

Start with a solution, destroy part of it, repair it, decide whether to accept the new version, reward the operators according to their performance, and repeat.

ALNS does not examine every possible routing plan, and it does not provide a mathematical proof that its best solution is globally optimal. Instead, it searches the solution space intelligently, making large changes when necessary and gradually learning which search strategies work best.

A Larger Instance and a New Safety Constraint

For this second article, we use a larger version of Los Movimientos. The new instance contains six pickup trucks, twenty-four transportation requests, forty-eight pickup and delivery nodes, one operational base, and nine drilling rigs. The same operational logic still applies: some groups must travel from the base to a rig, others must be transferred between rigs, and others must return from a rig to the base. Each truck can carry at most three passengers, every request has its own time windows, and all routes must be completed within the operating hours of the day. This larger instance also introduces mandatory driver breaks as an additional safety constraint, reflecting real-world regulatory requirements that the MILP formulation in Part I did not need to handle. ALNS is well suited to incorporate these constraints directly into the feasibility checks performed during each repair step, making it a practical choice when problem complexity grows beyond what exact methods can handle in reasonable time.