Los Movimientos, Part II: Solving Large Pickup-and-Delivery Problems with Adaptive Large Neighborhood Search
Los Movimientos, Part II: Solving Large Pickup-and-Delivery Problems with Adaptive Large Neighborhood Search
Los Movimientos 系列之二：利用自适应大邻域搜索（ALNS）解决大规模取送货问题
Building an ALNS heuristic in Python for vehicle routing, time windows, capacity constraints, and mandatory driver breaks. 使用 Python 构建 ALNS 启发式算法，以解决车辆路径规划、时间窗、容量限制及强制司机休息等问题。
Luis Fernando Pérez Armas | Jul 29, 2026 | 28 min read Luis Fernando Pérez Armas | 2026年7月29日 | 28分钟阅读
In the first article of this series, I introduced Los Movimientos, 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. 在本系列的第一篇文章中，我介绍了“Los Movimientos”，这是我在石油和天然气行业工作时曾面临的路径规划问题。该业务涉及两个相关但可分离的运输问题：我们需要用皮卡车运送人员，同时用重型卡车运送工具和设备。由于人员和重型设备显然不能乘坐同一辆车，这两个问题可以独立规划。
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. 在第一部分中，我仅关注了人员运输。这是一个典型的取送货问题（Pickup-and-Delivery Problem）。有时皮卡车需要从运营基地接人并送往钻井平台；有时需要从一个平台接人并转移到另一个平台；还有些时候需要从平台接人送回基地。因此，每一次移动都有起点、终点、乘客数量和时间窗。挑战在于决定哪辆车负责哪个请求、访问地点的顺序，以及如何满足车辆容量、先取后送关系、工作时间和安全限制。手动解决这个问题极其困难。
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. 在第一部分中，我们基于 Pisinger 等人 2026 年的公式 [1]，将 Los Movimientos 的一个小规模版本建模为混合整数线性规划（MILP），并使用 Pyomo（数学规划建模框架）和 HiGHS（开源免费求解器）精确求解。在第二篇文章中，我们将转向更大、更复杂的 Los Movimientos 实例，并使用自适应大邻域搜索（ALNS）来解决它。这是一种强大的元启发式算法，专为那些规模过大或精确求解速度过慢的路径规划问题而设计。
Why Not Keep Solving It with a MILP?
为什么不继续使用 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. 在第一部分中，混合整数线性规划模型运行得非常完美。我们将请求、车辆容量、行驶时间和时间窗输入 Pyomo，HiGHS 便返回了一组可证明的最优路径。那么，为什么不继续使用这种方法呢？答案是可扩展性。路径规划问题的复杂度增长极快。每增加一个请求，就意味着增加一个取货点和一个送货点，模型必须决定由哪辆车负责、取货点在路径中的位置，以及随后送货点的位置。
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. 这并不意味着 MILP 是一种糟糕的方法。对于中小型实例，精确优化仍然极具价值，特别是它能检测不可行性并提供最优性证明。它还为我们评估启发式算法提供了基准。Gurobi 或 CPLEX 等商业求解器可以解决比许多开源替代方案更大的实例，但它们无法消除问题的组合本质。
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. 随着请求和车辆数量的增加，即使是最强大的精确方法，最终也可能需要超出运营承受范围的时间。这在物流和电子商务领域尤为重要，因为随着新订单的到来、车辆不可用或客户需求的变化，路线可能需要重新计算。此时，我们改变了问题：不再纠结于是否能证明某条路线是“最优的”，而是询问在有限时间内能否找到一个非常好的、完全可行的路线。这就是启发式算法的用武之地。对于 Los Movimientos，我们将使用自适应大邻域搜索（ALNS），它通过反复移除现有解的一部分并以不同方式重建来工作。其理念很简单：破坏部分路径，修复它，并不断重复该过程，直到出现更好的结果。
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… 自适应大邻域搜索背后的基本思想出奇地简单：从一个可行解开始，部分破坏它，以不同的方式修复它，并多次重复该过程。与传统的局部搜索方法不同……