Ant Colony Optimization

Implementation of Ant Colony Optimization algorithms and analysis suite for the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP). The computation layer is built in Rust, while the experimental and analytical layer is handled in Python.

Greedy Algorithm	Classic Ant System
Rank-Based Ant System	MAX-MIN Ant System

Computation Layer

The computation layer requires the Rust toolchain (compiler version 1.88.0 or newer). Compiling the project in release mode (cargo build --release) generates four distinct solver executables: greedy, as, mmas and asrank.

All algorithms log their execution metrics—including feasibility status, execution time in milliseconds, convergence history, and found routes—to an aggregated CSV file to enable automated Python analysis.

Algorithms

• Greedy (Nearest Neighbor) The baseline reference algorithm.

  • It iteratively constructs routes by selecting the closest feasible, unvisited customer.
  • It serves as a benchmark and is used to calculate the initial pheromone level ($\tau_0$) for the advanced ACO variants.

• Classic Ant System The traditional Ant System proposed by M. Dorigo.

  • A colony of $M$ ants iteratively constructs routes based on a probabilistic rule that considers both pheromone trails and heuristic information.
  • All ants deposit pheromones based on the quality of their generated solutions.

• MAX-MIN Ant System An advanced modification by T. Stützle and H. H. Hoos designed to prevent premature stagnation.

  • Only the iteration-best ant is allowed to update the pheromone trail.
  • Pheromone levels are strictly bounded within a dynamic $[\tau_{min}, \tau_{max}]$ range to prevent absolute stagnation.
  • Pheromone trails are initialized to $\tau_{max}$ to force early exploration.

• Rank-Based Ant System A hybrid approach proposed by Bullnheimer, Hartl, and Strauss.

  • After each iteration, ants are sorted by their route quality.
  • Only the top $w - 1$ ants, alongside the global-best ant, are permitted to update the pheromone trails.

Usage & CLI Arguments

All the executables share a unified Command Line Interface (CLI) powered by clap. Use --help for more information on available parameters, options and flags.

Input File Format (.cvrp)

The compute core does not operate directly on raw CVRPLIB files. It requires a streamlined, custom .cvrp format (you can use convert_cvrp.py to convert .vrp file to .cvrp format).

The file must follow this exact sequential order, separated by newlines (empty lines and lines starting with # are ignored):

[dimension (total number of nodes)]
[adjacency matrix: NxN space-separated natural numbers]

[customer demands: N space-separated natural numbers, where the depot is 0]
[number of vehicles (K)] [vehicle capacity (C)] [max distance limit (S_max)]

In the example below: 5 nodes, followed by the 5×5 distance matrix, 5 demand values, a fleet of 2 vehicles, a vehicle capacity of 1000, and a max route distance of 150:

# Dimension (Depot + 4 customers)
5

# Adjacency Matrix (5x5)
0 10 20 30 40
10 0 15 25 35
20 15 0 10 20
30 25 10 0 15
40 35 20 15 0

# Demands (Depot demand is 0)
0 100 200 300 400

# Constraints: K, C, S_max
2 1000 150

Analytical Layer

The analytical layer utilizes pandas, numpy, and matplotlib to evaluate the performance, convergence dynamics, and stability of the algorithms across multiple CVRPLIB instances.