💻 computer science

A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

This study demonstrates that an Ant Colony Optimisation approach incorporating flexible capacity constraints significantly outperforms a geographic clustering baseline in a real-world Colombian inbound logistics network, achieving substantial reductions in fleet size, travel distance, and operating costs while maximizing vehicle utilization.

Original authors: Joseph Javier Sánchez Acuña

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joseph Javier Sánchez Acuña

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a delivery company in Colombia. You have a central warehouse in a town called Guadalajara de Buga, and you need to pick up packages from 30 different locations scattered all over the country—from coastal ports to mountain towns. You have a fleet of 10 identical trucks, and each truck is officially rated to carry 150 packages.

However, your company has a smart rule: if the math works out perfectly, a truck can carry a little extra—up to 5% more (about 157 packages)—without breaking the law or the truck. This is your "flexible capacity."

The problem is that your current system for planning routes, called "Rout Now," is a bit rigid. It works like a teacher assigning students to groups based on who sits closest to each other in the classroom (using a straight-line map). Once the groups are formed, it sends a truck to pick them up. Because it groups people by "straight lines" rather than "actual roads," it often ends up with some trucks half-empty and others overloaded, forcing you to use all 10 trucks even when you might only need 8.

The New Solution: The "Ant Colony" Approach

The author, Joseph Javier Sánchez Acuña, tested a new, smarter way to plan these routes using a computer program inspired by how ants find food. This is called Ant Colony Optimisation (ACO).

Here is how the paper explains the difference using simple concepts:

1. The "Straight Line" vs. The "Real Road"

The Old Way (Rout Now): Imagine trying to plan a road trip by drawing straight lines on a piece of paper. You might think two towns are close because they are next to each other on the map. But in reality, to get between them, you might have to drive over a huge mountain or take a long detour. The old system ignores the actual roads and just groups stops by their location on a flat map.
The New Way (Ants): The new system looks at the actual road network (using a digital map called OpenStreetMap). It knows that sometimes the "closest" town on a map is actually the hardest to reach by road.

2. The "Packing" Analogy

The Old Way: The old system tries to fill the trucks by grabbing the nearest neighbors first. It's like trying to pack a suitcase by throwing in the closest items without looking at the shape of the bag. You end up with gaps and wasted space, so you need to open a second suitcase (a second truck) even though you have room in the first one.
The New Way: The ant algorithm is like a master packer. It doesn't just grab the nearest item; it looks at the whole suitcase. It asks, "If I put this heavy box here, can I still fit that lighter box there?" It uses the "flexible capacity" (the extra 5% room) very carefully. It builds the route one stop at a time, checking constantly if the truck is getting too full. If a truck is almost full but has just enough room for one more stop, the ant takes it. If not, it closes that truck and starts a new one.

3. The Results: Packing More Efficiently

The author ran this new system against the old one using real data from 10 different busy days. Here is what happened, especially on the busiest day (Scenario S-3):

Fewer Trucks: The old system used all 10 trucks. The new ant system only needed 8 trucks. That's a 20% reduction in the fleet needed.
Less Driving: The trucks drove 20% less distance (saving about 2,232 kilometers).
Money Saved: Because they drove less and used fewer trucks, the fuel cost dropped by 16%.
Fuller Trucks: The old system left trucks running at about 79% capacity (lots of empty space). The new system filled them up to 99.5%, meaning almost every inch of the truck was used.

4. Why It Worked (The "Secret Sauce")

The paper argues that the magic wasn't just that the new system was "smarter" in a general sense. The magic was that it was allowed to use the flexible capacity (the 5% extra room) in a coordinated way.

The old system couldn't do this because it locked the trucks into specific geographic groups before it even started planning the route. It was like trying to rearrange furniture in a room after you've already painted the walls; the groups were fixed. The ant system, however, built the route and the group at the same time. It could say, "This truck is full, but if I squeeze in this one extra stop and use the 5% extra space, I can save an entire truck."

The Bottom Line

The study proves that for a logistics company in a place with tricky roads (like Colombia's mountains), using a bio-inspired computer program (Ant Colony Optimisation) that respects real road distances and uses flexible loading rules is significantly better than the old method of grouping by straight-line distance.

The author concludes that this isn't just a lucky guess; the results were tested 20 times for each scenario and proved statistically significant. The new method saves money, saves fuel, and reduces the number of trucks needed, all by packing the "suitcases" (trucks) more intelligently.

Technical Summary: A Metaheuristic Solution for the Capacitated Vehicle Routing Problem

1. Problem Definition and Context
The study addresses a real-world Capacitated Vehicle Routing Problem (CVRP) arising from an inbound raw-material collection operation in Colombia. The logistics network consists of a central depot in Guadalajara de Buga (Valle del Cauca) serving thirty distribution centers located across diverse Colombian regions (coasts, Andean highlands, and industrial zones). The operation faces variable demand cycles (643 to 1,192 packages per cycle) and utilizes a homogeneous fleet of ten Foton FRR Cummins trucks.

A critical operational constraint is the flexible capacity policy: while the nominal vehicle capacity is $Q = 150$ packages, corporate policy authorizes a controlled 5% overload, establishing an effective planning capacity of $Q_{eff} = 157.5$ packages. The routing must be performed over non-Euclidean road networks derived from OpenStreetMap (via OSMnx), where topological complexities (mountain corridors, one-way streets) create significant asymmetry between Euclidean distances and actual travel costs.

The incumbent planning system, "Rout Now," employs a "cluster-first, route-second" architecture: it partitions nodes into 10 geographic clusters using k-means (based on flat coordinates) and then sequences each cluster independently using Simulated Annealing (SA). This approach results in heterogeneous fleet utilization (35%–90%) and systematically deploys all 10 vehicles, even when theoretical lower bounds suggest 6–8 vehicles would suffice.

2. Methodology
The research proposes and evaluates an Ant Colony Optimisation (ACO) metaheuristic designed to operate on the complete graph of active nodes without prior geographic partitioning.

Mathematical Formulation: The problem is modeled as a Mixed-Integer Linear Programme (MILP) using the Miller–Tucker–Zemlin (MTZ) formulation for subtour elimination. The capacity constraint is explicitly relaxed to $Q_{eff} = 157.5$ to model the overload policy within the optimization logic.
ACO Architecture:
- Construction: Ants construct multi-vehicle routes iteratively. A key differentiator is the dynamic masking mechanism: the set of feasible next nodes ( $F_k$ ) is filtered in real-time to ensure the accumulated load does not exceed $Q_{eff}$ . This allows the algorithm to "pack" nodes efficiently, exploiting the 5% margin only when necessary to avoid opening a new route.
- Transition Probability: The probability of selecting a node depends on pheromone trails ( $\tau$ ) and heuristic visibility ( $\eta = 1/C_{ij}$ ). Given the high variance in Colombian road costs (47% standard deviation relative to the mean), the heuristic weight ( $\beta = 2.0$ ) was calibrated to dominate the pheromone weight ( $\alpha = 1.0$ ), prioritizing immediate cost efficiency.
- Update Mechanism: Standard evaporation and deposit rules apply, reinforcing arcs that contribute to low-cost, high-consolidation solutions.
Experimental Design:
- Scenarios: Ten distinct operational scenarios (S-1 to S-10) representing a full month of planning cycles were extracted from real company data.
- Repetition: Each scenario was executed 20 times independently with different random seeds to isolate stochastic variance.
- Baseline Comparison: The ACO results were compared against the "Rout Now" baseline (k-means + SA) using identical OSMnx distance matrices to ensure internal validity.
- Statistical Validation: The non-parametric Wilcoxon signed-rank test was applied to the mean total distances of the 20 runs per scenario to test for statistical significance.

3. Key Results
The ACO approach demonstrated systematic and statistically significant improvements over the baseline across all ten scenarios:

Fleet Reduction: In the highest-demand scenario (S-3; 1,192 packages), the ACO reduced the active fleet from 10 vehicles (baseline) to 8 vehicles, matching the theoretical lower bound ( $\lceil 1192/157.5 \rceil = 8$ ). Across all scenarios, the active fleet was reduced by approximately 20%.
Distance and Cost:
- Total Distance: Reduced by an average of 20.05% (ranging from 19.97% to 20.25%). In S-3, distance dropped from 11,023 km to 8,790.5 km.
- Fuel Cost: Estimated savings of 16.05% in the critical scenario (approx. 941,340 COP per cycle).
- Operating Time: Reduced by 20.02%.
Capacity Utilization: The ACO achieved near-perfect consolidation, raising average capacity utilization from ~79.47% (baseline) to 99.50% in S-3. Routes in the ACO solution operated between 96% and 101% of nominal capacity, with specific routes exploiting the 5% overload margin to prevent the need for a ninth vehicle.
Statistical Significance: The Wilcoxon signed-rank test yielded a statistic of $W=0$ (all differences favored ACO) with a p-value $< 0.01$ , rejecting the null hypothesis of median equality and confirming the robustness of the improvements.

4. Significance and Contributions
The paper claims three primary scientific contributions:

Empirical Evaluation of Flexible Constraints: It documents how explicitly modeling a flexible capacity constraint ( $Q_{eff}$ ) within a constructive metaheuristic allows for coordinated load consolidation that is structurally impossible for pre-partitioning architectures. The study demonstrates that the 5% tolerance is not merely a safety buffer but a strategic lever for fleet reduction when managed dynamically.
Robustness in Real-World Topology: The work provides evidence that bio-inspired metaheuristics (specifically ACO) outperform classical "cluster-first, route-second" heuristics in complex, non-Euclidean road networks. The study highlights that geographic pre-partitioning (k-means) fails to account for road network asymmetries, whereas ACO operates on the true cost space.
Causal Mechanism Identification: The paper identifies the "dynamic masking" of infeasible nodes during route construction as the causal mechanism for success. This allows the algorithm to perform an "efficient packing" of demand, organically exploiting the overload margin to minimize the number of routes, a capability absent in the baseline's fixed geographic clusters.

5. Limitations and Future Work
The authors note that the study is limited to a specific industrial context without time windows (VRPTW) or driver hour constraints. Future research directions proposed include:

Extending the model to VRPTW to incorporate reception schedules.
Addressing demand uncertainty via Stochastic VRP (SVRP).
Developing multi-objective formulations (e.g., minimizing CO₂ emissions) using evolutionary algorithms.
Integrating the ACO core as a microservice for controlled A/B testing within existing logistics systems.