In the first article of this series, I introduced Los Movimientos, the routing problem I faced in my previous role in the oil and gas industry.
The operation involved two related but separable transportation problems: moving personnel using pickup trucks, and moving tools and equipment using heavy trucks. Since people and heavy equipment traveled in separate vehicles, the two problems could be planned independently.
In Part I, I focused solely on personnel transportation. This was a classic pickup-and-delivery problem. A pickup truck might collect workers from the operational base and take them to a drilling rig, transfer personnel from one rig to another, or return workers from a rig to the base. Each movement had an origin, a destination, a number of passengers, and a time window. The challenge was to assign trucks to requests, sequence the visits, and respect vehicle capacities, pickup-before-delivery constraints, operating hours, and safety restrictions. Solving this manually was extremely difficult.
While my experience comes from oilfield operations, this problem mirrors typical pickup-and-delivery and last-mile logistics challenges faced by retailers, transportation companies, food-delivery platforms, and e-commerce businesses. As digital purchasing and consumption grow, these problems become more pressing: more online orders mean more stops, tighter delivery windows, larger fleets, and greater pressure to use transportation resources efficiently.
And no, autonomous trucks will not make the problem disappear. Even without a driver, we must still decide which truck serves each request, the optimal visit order, 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 instance of Los Movimientos using a Mixed Integer Linear Program (MILP), based on the formulation by Pisinger et al. (2026) [1]. We solved it exactly using Pyomo (a mathematical programming framework) and HiGHS (an open-source solver). In this second article, we tackle a larger, more complex instance using Adaptive Large Neighborhood Search (ALNS), a powerful metaheuristic designed for routing problems that become too large or too slow for exact methods.
Why Not Keep Solving with a MILP?
In Part I, the MILP model worked beautifully: we provided requests, vehicle capacities, travel times, and time windows, and HiGHS returned provably optimal routes. So why not continue with the same approach? The answer is scalability.
Routing problems grow extremely quickly. Each new request introduces both a pickup and a delivery, forcing the model to assign them to a vehicle, decide where the pickup fits in the route, and where the delivery follows—all while respecting capacity limits, precedence, service times, operating hours, vehicle compatibility, and, in our larger instance, mandatory driver breaks. Adding just a few requests creates many new assignment and sequencing possibilities, producing the combinatorial explosion that makes routing so difficult.
An exact solver may find a 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 is less useful than an excellent feasible solution produced in five minutes. This does not make MILP a bad approach. Exact optimization remains invaluable for small and medium instances, particularly for detecting infeasibility or providing optimality certificates. It also gives us a benchmark for evaluating other methods.