Los Movimientos, Part II: Solving Large Pickup-and-Delivery Problems with Adaptive Large Neighborhood Search | Towards Data Science

In the first article of this series, I , the routing problem that 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. 2026 [1], and we solved the formulation exactly using Pyomo (a mathematical programming modeling framework) and HiGHS (an open-source free to use solver). In this second article, we will 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, that we are going to develop in this notebook, 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. Our 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 English, 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 forever. 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 will 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 between 6:00 a.m. and 8:00 p.m.

We will also introduce an additional constraint inspired directly by the safety rules we followed in the field. A driver may drive continuously for at most two hours. If a direct journey takes longer than 120 minutes, the driver must stop immediately after reaching that limit, rest for 15 minutes, and then continue. This process is repeated as many times as the duration of the journey requires. For example, a 259-minute trip consists of 120 minutes of driving, a 15-minute break, another 120 minutes of driving, a second 15-minute break, and the final 19 minutes of the journey.

Once the vehicle reaches a rig, the operational base, or another service location, it must remain stopped for at least 15 minutes. That stop resets the accumulated driving fatigue before the next journey begins. This gives us a practical rule that is simple enough to evaluate efficiently inside ALNS, while still capturing an important safety requirement.

This is not a cosmetic addition. Driving is one of the most serious hazards in oil and gas operations. OSHA [4] identifies highway vehicle crashes as the leading cause of fatalities among oil and gas extraction workers, accounting for roughly four out of every ten occupational deaths in the industry. NIOSH [5] also identifies fatigued driving as a major crash risk because workers frequently combine long journeys to remote well sites with long and irregular shifts.

The larger instance intentionally includes several direct arcs longer than two hours, so the mandatory rest rule will actually become active in the routes. The longest direct journey takes 259 minutes and therefore requires two roadside breaks. This allows us to test not only whether ALNS can find good pickup-and-delivery routes, but also whether it can produce schedules that remain feasible once realistic safety requirements are included.

The complete instance, including the vehicles, requests, locations, time windows, distances, travel times, and passenger quantities, is available as a JSON file in the project repository:

Download the larger Los Movimientos instance from GitHub

Solving Los Movimientos with ALNS

For this implementation, we will use the open-source alns Python library [3], developed by Niels Wouda and Leon Lan [2]. The package provides a flexible implementation of Adaptive Large Neighborhood Search and is designed to be reused across different combinatorial optimization problems. Its accompanying software paper, ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic, was published in the Journal of Open Source Software in 2023.

Using the library makes our lives considerably easier because we do not need to program the entire ALNS engine from scratch. It already manages the iterative search process, selects destroy and repair operators, applies an acceptance criterion, updates operator-selection weights, checks the stopping condition, and stores the best solution and search statistics.

However, the library does not know anything about the structure and requirements of our problem “Los Movimientos”. We still need to teach it what a solution looks like and what makes a route feasible. In particular, we must implement the vehicle routes, the request bank, the objective function, the initial solution, and the destroy and repair operators. We must also create the route evaluator that checks passenger capacity, pickup-before-delivery precedence, time windows, the evening deadline, minimum stop durations, and mandatory driver breaks. These problem-specific components are precisely what the library expects users to provide.

In other words, the package gives us the ALNS machinery. Our job is to give that machinery an understanding of the routing problem we want it to solve.

So, we begin by installing the alns package [3], importing the required libraries, and downloading the larger JSON instance directly from GitHub.

!pip -q install alns==7.0.0

import math
from functools import lru_cache

import matplotlib.pyplot as plt
import numpy as np
import requests

from alns import ALNS
from alns.accept import SimulatedAnnealing
from alns.select import RouletteWheel
from alns.stop import MaxIterations

JSON_URL = (
    "https://raw.githubusercontent.com/ceche1212/los_movimientos/"
    "refs/heads/main/data/los_movimientos_large_rest_instance.json"
)

response = requests.get(JSON_URL, timeout=30)
response.raise_for_status()
instance = response.json()

print("Instance loaded successfully")
print(f"Name: {instance['instance_name']}")
print(f"Vehicles: {len(instance['vehicles'])}")
print(f"Requests: {len(instance['requests'])}")
print(f"Service nodes: {2 * len(instance['requests'])}")

Next, we convert the nested JSON structure into dictionaries that can be accessed efficiently during the search. This includes the pickup and delivery nodes, passenger quantities, time windows, vehicle capacities, and travel matrices.

vehicles = [v["id"] for v in instance["vehicles"]]
request_ids = [r["id"] for r in instance["requests"]]

vehicle_record = {v["id"]: v for v in instance["vehicles"]}
request_record = {r["id"]: r for r in instance["requests"]}

pickup_node = {
    r: request_record[r]["pickup"]["node_id"]
    for r in request_ids
}

delivery_node = {
    r: request_record[r]["delivery"]["node_id"]
    for r in request_ids
}

passengers = {
    r: request_record[r]["passengers"]
    for r in request_ids
}

compatible_vehicles = {
    r: request_record[r].get("compatible_vehicles", vehicles.copy())
    for r in request_ids
}

node_location, earliest, latest = {}, {}, {}
service_time, load_change = {}, {}
node_type, node_request = {}, {}

for r in request_ids:
    request = request_record[r]

    for data, kind, sign in (
        (request["pickup"], "pickup", 1),
        (request["delivery"], "delivery", -1),
    ):
        node = data["node_id"]

        node_location[node] = data["location"]
        earliest[node], latest[node] = data["time_window"]
        service_time[node] = data["service_time"]
        load_change[node] = sign * request["passengers"]
        node_type[node] = kind
        node_request[node] = r

capacity = {
    k: vehicle_record[k]["capacity_passengers"]
    for k in vehicles
}

start_time = {
    k: vehicle_record[k]["start_time"]
    for k in vehicles
}

end_time = {
    k: vehicle_record[k]["end_time"]
    for k in vehicles
}

start_location = {
    k: vehicle_record[k]["start_location"]
    for k in vehicles
}

end_location = {
    k: vehicle_record[k]["end_location"]
    for k in vehicles
}

travel_time = instance["travel_time_minutes"]
distance = instance["distance_km"]
coordinates = instance["locations"]


def minutes_to_clock(minutes):
    minutes = int(round(minutes))
    return f"{minutes // 60:02d}:{minutes % 60:02d}"


longest_leg = max(
    value
    for row in travel_time.values()
    for value in row.values()
)

print(f"Longest direct driving leg: {longest_leg} minutes")

Before evaluating any route, we define the safety rule, objective weights, and ALNS search parameters. The helper functions calculate how many roadside breaks a journey requires, its effective duration, and the exact timing of each break.

MAX_CONTINUOUS_DRIVING = 120
BREAK_DURATION = MIN_STOP_DURATION = 15

DISTANCE_WEIGHT = 1.0
DURATION_WEIGHT = 0.05
UNSERVED_PENALTY = 10_000.0

INFEASIBLE_COST = 1e12
DESTRUCTION_RATE = 0.30


def required_breaks(driving_minutes):
    if driving_minutes <= 0:
        return 0

    return max(
        0,
        math.ceil(driving_minutes / MAX_CONTINUOUS_DRIVING) - 1
    )


def effective_travel_time(driving_minutes):
    return (
        driving_minutes
        + BREAK_DURATION * required_breaks(driving_minutes)
    )


def break_intervals(departure_time, driving_minutes):
    return [
        (
            departure_time
            + n * MAX_CONTINUOUS_DRIVING
            + (n - 1) * BREAK_DURATION,
            departure_time
            + n * MAX_CONTINUOUS_DRIVING
            + n * BREAK_DURATION
        )
        for n in range(1, required_breaks(driving_minutes) + 1)
    ]


for driving in [120, 121, 240, 241, 370]:
    print(
        f"{driving:>3} minutes → "
        f"{required_breaks(driving)} break(s) → "
        f"{effective_travel_time(driving)} effective minutes"
    )

ALNS will test thousands of possible routes, so we need a function that quickly determines whether a route is feasible. It simulates the entire itinerary while checking time windows, pickup-before-delivery precedence, passenger capacity, mandatory breaks, minimum stop durations, and the final operating deadline.

@lru_cache(maxsize=None)
def evaluate_route(vehicle_id, route_tuple):
    route = list(route_tuple)

    current_time = start_time[vehicle_id]
    current_load = 0
    total_distance = total_driving = total_breaks = 0

    previous_location = start_location[vehicle_id]
    active_requests, completed_requests = set(), set()
    events = []

    index = 0

    while index < len(route):
        location = node_location[route[index]]
        leg_departure = current_time
        driving = travel_time[previous_location][location]
        breaks = required_breaks(driving)
        arrival = leg_departure + effective_travel_time(driving)

        total_distance += distance[previous_location][location]
        total_driving += driving
        total_breaks += breaks

        stop_events = []

        while (
            index < len(route)
            and node_location[route[index]] == location
        ):
            node = route[index]
            request_id = node_request[node]

            if vehicle_id not in compatible_vehicles[request_id]:
                return None

            previous_end = (
                arrival
                if not stop_events
                else stop_events[-1]["service_end"]
            )

            service_start = max(previous_end, earliest[node])

            if service_start > latest[node]:
                return None

            if node_type[node] == "pickup":
                if (
                    request_id in active_requests
                    or request_id in completed_requests
                ):
                    return None

                active_requests.add(request_id)

            else:
                if request_id not in active_requests:
                    return None

                active_requests.remove(request_id)
                completed_requests.add(request_id)

            current_load += load_change[node]

            if not 0 <= current_load <= capacity[vehicle_id]:
                return None

            service_end = service_start + service_time[node]

            stop_events.append({
                "node": node,
                "location": location,
                "arrival": arrival,
                "service_start": service_start,
                "service_end": service_end,
                "load": current_load,
                "leg_departure": leg_departure,
                "driving_before": driving if not stop_events else 0,
                "breaks_before": breaks if not stop_events else 0
            })

            index += 1

        departure = max(
            stop_events[-1]["service_end"],
            arrival + MIN_STOP_DURATION
        )

        for event in stop_events:
            event["stop_departure"] = departure

        events.extend(stop_events)
        current_time = departure
        previous_location = location

    end_leg_departure = current_time
    driving = travel_time[
        previous_location
    ][
        end_location[vehicle_id]
    ]

    breaks = required_breaks(driving)
    finish_time = (
        end_leg_departure
        + effective_travel_time(driving)
    )

    total_distance += distance[
        previous_location
    ][
        end_location[vehicle_id]
    ]

    total_driving += driving
    total_breaks += breaks

    if (
        finish_time > end_time[vehicle_id]
        or current_load != 0
        or active_requests
    ):
        return None

    duration = finish_time - start_time[vehicle_id]

    return {
        "distance": total_distance,
        "duration": duration,
        "driving_time": total_driving,
        "finish_time": finish_time,
        "breaks": total_breaks,
        "cost": (
            DISTANCE_WEIGHT * total_distance
            + DURATION_WEIGHT * duration
        ),
        "events": events,
        "end_leg_departure": end_leg_departure,
        "end_leg_driving": driving,
        "end_leg_breaks": breaks
    }

The function returns None whenever a route violates an operational rule. Otherwise, it returns its distance, duration, cost, break count, finishing time, and detailed schedule. The cache avoids recalculating routes that ALNS has already evaluated. The ALNS library needs a state object describing the current solution. In our case, a state contains one ordered route for each truck and a request bank holding any requests that are still unassigned.

class MovementsState:

    def __init__(self, routes, unassigned=None):
        self.routes = {
            k: list(routes.get(k, []))
            for k in vehicles
        }
        self.unassigned = list(unassigned or [])

    def copy(self):
        return MovementsState(
            self.routes,
            self.unassigned
        )

    def objective(self):
        served = [
            node_request[node]
            for route in self.routes.values()
            for node in route
            if node_type[node] == "pickup"
        ]

        expected = set(request_ids) - set(self.unassigned)

        if (
            len(served) != len(set(served))
            or set(served) != expected
        ):
            return INFEASIBLE_COST

        total = UNSERVED_PENALTY * len(self.unassigned)

        for k, route in self.routes.items():
            evaluation = evaluate_route(k, tuple(route))

            if evaluation is None:
                return INFEASIBLE_COST

            total += evaluation["cost"]

        return total

    @property
    def cost(self):
        return self.objective()

    def served_requests(self):
        visited = {
            node
            for route in self.routes.values()
            for node in route
        }

        return [
            r
            for r in request_ids
            if pickup_node[r] in visited
        ]

    def vehicle_of(self, request_id):
        pickup = pickup_node[request_id]

        return next(
            (
                k
                for k, route in self.routes.items()
                if pickup in route
            ),
            None
        )

The class evaluates the total routing cost, applies a large penalty to unassigned requests, rejects inconsistent or infeasible states, and provides helper methods for identifying which requests are served and which truck currently handles each one.

Preparing the destroy operators

Before defining the removal strategies, we create three shared helpers. The first removes both nodes of a request, the second tests every feasible pickup-and-delivery insertion, and the third determines how many requests should be removed in each ALNS iteration.

def remove_request(state, request_id):
    k = state.vehicle_of(request_id)

    if k is not None:
        state.routes[k] = [
            node for node in state.routes[k]
            if node_request[node] != request_id
        ]

    if request_id not in state.unassigned:
        state.unassigned.append(request_id)


def insertion_options(state, request_id):
    pickup = pickup_node[request_id]
    delivery = delivery_node[request_id]
    options = []

    for k in compatible_vehicles[request_id]:
        route = state.routes[k]
        base = evaluate_route(k, tuple(route))

        if base is None:
            continue

        for pickup_pos in range(len(route) + 1):
            with_pickup = (
                route[:pickup_pos]
                + [pickup]
                + route[pickup_pos:]
            )

            for delivery_pos in range(
                pickup_pos + 1,
                len(with_pickup) + 1
            ):
                candidate = (
                    with_pickup[:delivery_pos]
                    + [delivery]
                    + with_pickup[delivery_pos:]
                )

                evaluation = evaluate_route(k, tuple(candidate))

                if evaluation is not None:
                    options.append((
                        evaluation["cost"] - base["cost"],
                        k,
                        candidate
                    ))

    return sorted(options, key=lambda option: option[0])


def number_to_remove(state):
    served = len(state.served_requests())

    return min(
        served,
        max(1, math.ceil(DESTRUCTION_RATE * served))
    )

These functions ensure that complete requests are removed together, candidate insertions always place the pickup before the delivery, and each destroy operator removes the same proportion of the current solution.

Random and worst removal

The first destroy operator removes requests randomly to introduce diversity. The second targets requests whose removal produces the largest reduction in route cost.

def random_removal(current, rng):
    destroyed = current.copy()
    served = destroyed.served_requests()
    q = number_to_remove(destroyed)

    if q:
        for request_id in rng.choice(
            served,
            size=q,
            replace=False
        ):
            remove_request(destroyed, str(request_id))

    return destroyed


def removal_saving(state, request_id):
    k = state.vehicle_of(request_id)

    if k is None:
        return -math.inf

    current = evaluate_route(k, tuple(state.routes[k]))

    reduced_route = [
        node for node in state.routes[k]
        if node_request[node] != request_id
    ]

    reduced = evaluate_route(k, tuple(reduced_route))

    return current["cost"] - reduced["cost"]


def worst_removal(current, rng):
    destroyed = current.copy()

    for _ in range(number_to_remove(destroyed)):
        served = destroyed.served_requests()

        if not served:
            break

        request_id = max(
            served,
            key=lambda r: (
                removal_saving(destroyed, r)
                + 1e-6 * rng.random()
            )
        )

        remove_request(destroyed, request_id)

    return destroyed

Random removal helps the search explore unfamiliar regions, while worst removal focuses on requests that appear particularly expensive in their current positions.

Related-request removal

The final destroy operator removes groups of similar requests. Similarity is measured using the proximity of their pickup and delivery locations, their time windows, and their passenger quantities.

MAX_DISTANCE = max(
    value
    for row in distance.values()
    for value in row.values()
)

HORIZON = (
    instance["planning_horizon"]["end"]
    - instance["planning_horizon"]["start"]
)

MAX_PASSENGERS = max(passengers.values())


def relatedness(first, second):
    p1, p2 = pickup_node[first], pickup_node[second]
    d1, d2 = delivery_node[first], delivery_node[second]

    spatial = (
        distance[node_location[p1]][node_location[p2]]
        + distance[node_location[d1]][node_location[d2]]
    ) / (2 * MAX_DISTANCE)

    temporal = (
        abs(earliest[p1] - earliest[p2])
        + abs(earliest[d1] - earliest[d2])
    ) / (2 * HORIZON)

    demand = (
        abs(passengers[first] - passengers[second])
        / MAX_PASSENGERS
    )

    return spatial + temporal + demand


def related_removal(current, rng):
    destroyed = current.copy()
    served = destroyed.served_requests()
    q = number_to_remove(destroyed)

    if not served:
        return destroyed

    seed = str(rng.choice(served))

    candidates = sorted(
        (r for r in served if r != seed),
        key=lambda r: relatedness(seed, r) + 0.05 * rng.random()
    )

    for request_id in [seed] + candidates[:q - 1]:
        remove_request(destroyed, request_id)

    return destroyed

Related removal creates a larger opening around one part of the solution, giving the repair operator an opportunity to reorganize several similar transportation requests together.

Repairing the partially destroyed solution

After removing several requests, ALNS must place them back into the routes. We use two repair strategies: greedy insertion and regret-2 insertion.

def greedy_repair(destroyed, rng):
    repaired = destroyed.copy()

    while repaired.unassigned:
        candidates = []

        for request_id in repaired.unassigned:
            options = insertion_options(repaired, request_id)

            if options:
                delta, k, route = options[0]
                candidates.append(
                    (delta, rng.random(), request_id, k, route)
                )

        if not candidates:
            break

        _, _, request_id, k, route = min(
            candidates,
            key=lambda item: (item[0], item[1])
        )

        repaired.routes[k] = route
        repaired.unassigned.remove(request_id)

    return repaired


def regret_2_repair(destroyed, rng):
    repaired = destroyed.copy()

    while repaired.unassigned:
        choices = []

        for request_id in repaired.unassigned:
            options = insertion_options(repaired, request_id)

            if not options:
                continue

            regret = (
                options[1][0] - options[0][0]
                if len(options) > 1
                else 1e6
            )

            delta, k, route = options[0]

            choices.append(
                (
                    regret,
                    -delta,
                    rng.random(),
                    request_id,
                    k,
                    route
                )
            )

        if not choices:
            break

        _, _, _, request_id, k, route = max(
            choices,
            key=lambda item: (item[0], item[1], item[2])
        )

        repaired.routes[k] = route
        repaired.unassigned.remove(request_id)

    return repaired

The greedy operator repeatedly chooses the feasible insertion with the smallest immediate cost increase. Regret-2 instead prioritizes requests whose best insertion is much better than their second-best option, reducing the risk of leaving difficult requests until the end.

Building the initial solution

ALNS needs a feasible starting point before it can begin destroying and repairing routes. We start with empty vehicle routes, place every request in the request bank, and use the greedy repair operator to construct the initial solution. A fixed random seed makes the experiment reproducible.

SEED = 42
initial_rng = np.random.default_rng(SEED)

empty_state = MovementsState(
    routes={k: [] for k in vehicles},
    unassigned=request_ids
)

initial_solution = greedy_repair(empty_state, initial_rng)

print(f"Initial objective: {initial_solution.objective():.2f}")
print("Initially unserved requests:", initial_solution.unassigned)

The greedy operator inserts requests one at a time using their least expensive feasible positions. This gives ALNS a complete starting solution that it can subsequently improve. For our particular large instance of Los Movimientos, this intial greedy heuristic is able to find a solution with an Initial objective: 11859.65 but with an unserved request ‘R12’, lets see if ALNS is able to improve upon this solution.

Configuring and running ALNS

We now register the destroy and repair operators, configure their adaptive selection, define the simulated-annealing acceptance rule, and run the search for 5,000 iterations.

ITERATIONS = 5_000

alns = ALNS(np.random.default_rng(SEED))

alns.add_destroy_operator(random_removal, name="Random removal")
alns.add_destroy_operator(worst_removal, name="Worst removal")
alns.add_destroy_operator(related_removal, name="Related removal")

alns.add_repair_operator(greedy_repair, name="Greedy insertion")
alns.add_repair_operator(regret_2_repair, name="Regret-2 insertion")

selection = RouletteWheel(
    scores=[25, 5, 1, 0],
    decay=0.8,
    num_destroy=len(alns.destroy_operators),
    num_repair=len(alns.repair_operators)
)

acceptance = SimulatedAnnealing.autofit(
    init_obj=initial_solution.objective(),
    worse=0.05,
    accept_prob=0.50,
    num_iters=ITERATIONS
)

result = alns.iterate(
    initial_solution,
    selection,
    acceptance,
    MaxIterations(ITERATIONS)
)

best_solution = result.best_state

The roulette wheel increasingly favors operators that produce useful solutions. Simulated annealing occasionally accepts worse solutions, particularly early in the search, helping ALNS escape local optima. Finally, we evaluate the best routes found and report their main operational results.

evaluations = {
    k: evaluate_route(k, tuple(best_solution.routes[k]))
    for k in vehicles
}

total_distance = sum(e["distance"] for e in evaluations.values())
total_duration = sum(e["duration"] for e in evaluations.values())
total_driving = sum(e["driving_time"] for e in evaluations.values())
total_breaks = sum(e["breaks"] for e in evaluations.values())

print("ALNS search completed")
print(f"\nInitial objective: {initial_solution.objective():.2f}")
print(f"Best objective: {best_solution.objective():.2f}")
print(f"Total distance: {total_distance:.1f} km")
print(f"Total vehicle duration: {total_duration:.0f} minutes")
print(f"Total driving time: {total_driving:.0f} minutes")
print(f"Mandatory roadside breaks: {total_breaks}")
print(f"Unserved requests: {len(best_solution.unassigned)}")

if best_solution.unassigned:
    print("Requests in the request bank:", best_solution.unassigned)
else:
    print("All transportation requests were served.")

After few seconds, ALNS produced the following outputs.

ALNS search completed

Initial objective: 11859.65
Best objective: 1738.75
Total distance: 1580.4 km
Total vehicle duration: 3167 minutes
Total driving time: 2502 minutes
Mandatory roadside breaks: 6
Unserved requests: 0
All transportation requests were served.

This output shows just how much ALNS improved the initial solution. It reduced the objective value by almost a factor of ten and, more importantly, produced a plan that serves every transportation request while respecting vehicle capacities, time windows, mandatory rest periods, and all other operational constraints. Honestly, results like this still amaze me. Seeing a computer reorganize such a complex puzzle in seconds feels almost like magic, even when we understand the mathematics and algorithms working behind the scenes. Moreover, the figure below show us the progress of ALNS across the iterations, we can see that it was able to drastically reduce the objective value on the first iterations, and then the rest of the time was spent refining this solution.

At this point, we already have the best solution found by ALNS. The next step is to display each route in a format that a dispatcher or driver could actually read, including the sequence of stops, the service times, the passenger changes, and any mandatory roadside breaks.

for k in vehicles:
    route = best_solution.routes[k]
    evaluation = evaluate_route(k, tuple(route))

    print(f"\n{'=' * 82}")
    print(
        f"{k} | {evaluation['distance']:.1f} km | "
        f"Finish: {minutes_to_clock(evaluation['finish_time'])}"
    )
    print(f"{'=' * 82}")
    print(f"{minutes_to_clock(start_time[k])} | {start_location[k]:<18} | Start")

    for event in evaluation["events"]:
        if event["breaks_before"] > 0:
            for b0, b1 in break_intervals(
                event["leg_departure"],
                event["driving_before"]
            ):
                print(
                    f"{minutes_to_clock(b0)}–{minutes_to_clock(b1)}"
                    f" | {'Roadside':<18} | Mandatory rest"
                )

        node = event["node"]
        print(
            f"{minutes_to_clock(event['service_start'])}"
            f" | {event['location']:<18}"
            f" | {node_type[node].title():<8}"
            f" | Request {node_request[node]:<3}"
            f" | Change: {load_change[node]:+d}"
            f" | Onboard: {event['load']}"
        )

    if evaluation["end_leg_breaks"] > 0:
        for b0, b1 in break_intervals(
            evaluation["end_leg_departure"],
            evaluation["end_leg_driving"]
        ):
            print(
                f"{minutes_to_clock(b0)}–{minutes_to_clock(b1)}"
                f" | {'Roadside':<18} | Mandatory rest"
            )

    print(
        f"{minutes_to_clock(evaluation['finish_time'])}"
        f" | {end_location[k]:<18} | End"
    )

This output gives a route sheet for each vehicle, showing when the truck starts, where it goes, which request it serves at each stop, how the passenger load changes, and where the mandatory driving breaks take place.

==================================================================================
PU_1 | 272.4 km | Finish: 15:04
==================================================================================
06:00 | BASE               | Start
06:00 | BASE               | Pickup   | Request R04 | Change: +2 | Onboard: 2
06:10 | BASE               | Pickup   | Request R02 | Change: +1 | Onboard: 3
07:30 | RIG_B              | Delivery | Request R02 | Change: -1 | Onboard: 2
09:11 | RIG_F              | Delivery | Request R04 | Change: -2 | Onboard: 0
09:21 | RIG_F              | Pickup   | Request R10 | Change: +2 | Onboard: 2
10:47 | RIG_G              | Pickup   | Request R16 | Change: +1 | Onboard: 3
10:57 | RIG_G              | Delivery | Request R10 | Change: -2 | Onboard: 1
12:33 | RIG_D              | Delivery | Request R16 | Change: -1 | Onboard: 0
12:43 | RIG_D              | Pickup   | Request R22 | Change: +2 | Onboard: 2
14:49 | BASE               | Delivery | Request R22 | Change: -2 | Onboard: 0
15:04 | BASE               | End

==================================================================================
PU_2 | 204.5 km | Finish: 12:52
==================================================================================
06:00 | BASE               | Start
06:49 | RIG_A              | Pickup   | Request R07 | Change: +2 | Onboard: 2
08:16 | RIG_D              | Delivery | Request R07 | Change: -2 | Onboard: 0
08:26 | RIG_D              | Pickup   | Request R13 | Change: +1 | Onboard: 1
09:31 | RIG_F              | Delivery | Request R13 | Change: -1 | Onboard: 0
09:41 | RIG_F              | Pickup   | Request R19 | Change: +1 | Onboard: 1
11:51–12:06 | Roadside           | Mandatory rest
12:37 | BASE               | Delivery | Request R19 | Change: -1 | Onboard: 0
12:52 | BASE               | End

==================================================================================
PU_3 | 126.9 km | Finish: 11:16
==================================================================================
06:00 | BASE               | Start
06:20 | BASE               | Pickup   | Request R03 | Change: +3 | Onboard: 3
07:38 | RIG_C              | Delivery | Request R03 | Change: -3 | Onboard: 0
07:48 | RIG_C              | Pickup   | Request R09 | Change: +2 | Onboard: 2
08:39 | RIG_A              | Pickup   | Request R15 | Change: +1 | Onboard: 3
08:49 | RIG_A              | Delivery | Request R09 | Change: -2 | Onboard: 1
09:31 | RIG_B              | Delivery | Request R15 | Change: -1 | Onboard: 0
09:41 | RIG_B              | Pickup   | Request R21 | Change: +1 | Onboard: 1
11:01 | BASE               | Delivery | Request R21 | Change: -1 | Onboard: 0
11:16 | BASE               | End

==================================================================================
PU_4 | 360.4 km | Finish: 17:51
==================================================================================
06:00 | BASE               | Start
06:15 | BASE               | Pickup   | Request R05 | Change: +1 | Onboard: 1
06:25 | BASE               | Pickup   | Request R06 | Change: +2 | Onboard: 3
08:35–08:50 | Roadside           | Mandatory rest
10:02 | RIG_H              | Delivery | Request R05 | Change: -1 | Onboard: 2
10:12 | RIG_H              | Pickup   | Request R11 | Change: +1 | Onboard: 3
12:05 | RIG_I              | Delivery | Request R11 | Change: -1 | Onboard: 2
12:15 | RIG_I              | Delivery | Request R06 | Change: -2 | Onboard: 0
12:25 | RIG_I              | Pickup   | Request R17 | Change: +2 | Onboard: 2
13:44 | RIG_G              | Pickup   | Request R23 | Change: +1 | Onboard: 3
13:54 | RIG_G              | Delivery | Request R17 | Change: -2 | Onboard: 1
16:04–16:19 | Roadside           | Mandatory rest
17:36 | BASE               | Delivery | Request R23 | Change: -1 | Onboard: 0
17:51 | BASE               | End

==================================================================================
PU_5 | 267.7 km | Finish: 14:26
==================================================================================
06:00 | BASE               | Start
07:10 | RIG_B              | Pickup   | Request R08 | Change: +2 | Onboard: 2
08:53 | RIG_E              | Delivery | Request R08 | Change: -2 | Onboard: 0
09:03 | RIG_E              | Pickup   | Request R14 | Change: +2 | Onboard: 2
10:24 | RIG_H              | Delivery | Request R14 | Change: -2 | Onboard: 0
10:34 | RIG_H              | Pickup   | Request R20 | Change: +2 | Onboard: 2
12:44–12:59 | Roadside           | Mandatory rest
14:11 | BASE               | Delivery | Request R20 | Change: -2 | Onboard: 0
14:26 | BASE               | End

==================================================================================
PU_6 | 348.5 km | Finish: 17:18
==================================================================================
06:00 | BASE               | Start
06:00 | BASE               | Pickup   | Request R01 | Change: +2 | Onboard: 2
07:04 | RIG_A              | Delivery | Request R01 | Change: -2 | Onboard: 0
09:19–09:34 | Roadside           | Mandatory rest
11:09 | RIG_I              | Pickup   | Request R12 | Change: +2 | Onboard: 2
13:24–13:39 | Roadside           | Mandatory rest
14:09 | RIG_E              | Pickup   | Request R18 | Change: +1 | Onboard: 3
14:19 | RIG_E              | Delivery | Request R12 | Change: -2 | Onboard: 1
15:35 | RIG_C              | Delivery | Request R18 | Change: -1 | Onboard: 0
15:45 | RIG_C              | Pickup   | Request R24 | Change: +2 | Onboard: 2
17:03 | BASE               | Delivery | Request R24 | Change: -2 | Onboard: 0
17:18 | BASE               | End

To visualize the solution more clearly, we now plot the six vehicle routes using a 3-row by 2-column layout. Each subplot shows one truck, its travel direction, and the order in which the locations are visited.

vehicle_ids = list(best_solution.routes)

all_x = [loc["x_km"] for loc in coordinates.values()]
all_y = [loc["y_km"] for loc in coordinates.values()]

fig, axes = plt.subplots(
    3, 2,
    figsize=(16, 18),
    sharex=True,
    sharey=True
)

axes = axes.flatten()

for ax, k in zip(axes, vehicle_ids):
    route = best_solution.routes[k]
    evaluation = evaluate_route(k, tuple(route))

    for loc in coordinates.values():
        ax.scatter(
            loc["x_km"],
            loc["y_km"],
            s=100,
            zorder=3
        )

        ax.text(
            loc["x_km"] + 0.8,
            loc["y_km"] + 0.8,
            loc["name"],
            fontsize=9
        )

    physical_locations = (
        [start_location[k]]
        + [node_location[node] for node in route]
        + [end_location[k]]
    )

    x_values = [
        coordinates[loc]["x_km"]
        for loc in physical_locations
    ]

    y_values = [
        coordinates[loc]["y_km"]
        for loc in physical_locations
    ]

    ax.plot(
        x_values,
        y_values,
        marker="o",
        linewidth=2,
        zorder=2
    )

    for x0, y0, x1, y1 in zip(
        x_values[:-1],
        y_values[:-1],
        x_values[1:],
        y_values[1:]
    ):
        if (x0, y0) != (x1, y1):
            ax.annotate(
                "",
                xy=(x1, y1),
                xytext=(x0, y0),
                arrowprops={
                    "arrowstyle": "->",
                    "alpha": 0.5,
                    "linewidth": 1.5
                }
            )

    ax.set_title(
        f"{k}\n"
        f"{evaluation['distance']:.1f} km | "
        f"Finish: {minutes_to_clock(evaluation['finish_time'])}"
    )

    ax.set_xlabel("x coordinate (km)")
    ax.set_xlim(min(all_x) - 5, max(all_x) + 5)
    ax.set_ylim(min(all_y) - 5, max(all_y) + 5)
    ax.set_aspect("equal", adjustable="box")
    ax.grid(True, alpha=0.3)

for ax in axes[len(vehicle_ids):]:
    ax.axis("off")

for ax in axes[::2]:
    ax.set_ylabel("y coordinate (km)")

plt.tight_layout()
plt.show()

This figure gives one map per vehicle. The arrows show the travel direction.

Conclusions

And there we have it: Los Movimientos solved with Adaptive Large Neighborhood Search.

The central lesson of this article is not that heuristics are better than exact optimization. They serve different purposes. A MILP solved to optimality gives us the best possible solution and a mathematical certificate proving it. A heuristic such as ALNS gives up that guarantee, but can produce excellent, fully feasible solutions much faster when the problem becomes too large for exact optimization. In real operations, a very good route available now may be considerably more valuable than a proven optimum obtained after the plan is already obsolete.

ALNS is also much more general than the routing application explored here. The same destroy-and-repair logic can be adapted to inventory decisions, sequencing and scheduling, maintenance planning, and staff allocation. Maintenance scheduling is particularly important in oil and gas operations and will be the subject of one of my future articles. I will also return to another problem from my time in the industry: crew pairing, where workers must be assigned to compatible crews, rotations, and operating schedules. The alns library was designed precisely as a reusable framework for difficult combinatorial optimization problems, leaving us to define the problem-specific solution representation and operators [2, 3].

I sincerely hope you found this article useful and entertaining. Feel free to leave a comment, show your appreciation with a clap 👏, and follow the latest work from Sávila Education or connect with me on LinkedIn.

All the code and data used in this article are available in the Los Movimientos GitHub repository.

Thank you for reading, and stay tuned. We still have maintenance schedules, crew pairing, and many other operational nightmares left to solve.

References

[1] Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472.

[2] Wouda, N. A., & Lan, L. (2023). ALNS: A Python implementation of the adaptive large neighbourhood search metaheuristic. Journal of Open Source Software, 8(81), 5028. https://doi.org/10.21105/joss.05028

[3] Wouda, N. A., & Lan, L. (2024). alns (Version 7.0.0) [Python package]. Python Package Index. https://pypi.org/project/alns/

[4] Occupational Safety and Health Administration. (n.d.). Oil and gas extraction: Hazards. U.S. Department of Labor. https://www.osha.gov/oil-and-gas-extraction/hazards

[5] National Institute for Occupational Safety and Health. (2018). Oil and gas employers: How to prevent fatigued driving at work (DHHS [NIOSH] Publication No. 2018-125). Centers for Disease Control and Prevention. https://doi.org/10.26616/NIOSHPUB2018125