Accelerating supply chains with Ant Colony Optimization across a range of hardware solutions

Area of Science:

• Computational Intelligence
• Operations Research
• Artificial Intelligence

Background:

• Ant Colony Optimization (ACO) is widely used for optimization.
• Existing research on ACO scaling and parallelism primarily focuses on Traveling Salesman Problems (TSPs).
• Real-world problems often require additional metadata during solution construction, which may not be captured by standard TSP benchmarks.

Purpose of the Study:

• To investigate the performance differences between ACO on benchmark problems and complex real-world applications.
• To analyze the scaling dynamics of ACO with parallel architectures.
• To evaluate the suitability of different hardware solutions for ACO.

Main Methods:

• Implemented and compared two parallel ACO architectures: Independent Ant Colonies (IAC) and Parallel Ants (PA).
• Assessed algorithm performance on both standard benchmarks and simulated real-world supply chain routing problems.
• Measured speed performance across a 16-core CPU, a 68-core Xeon Phi, and up to 4 GeForce GPUs.
• Utilized state-of-the-art ACO vectorization techniques like SS-Roulette with C++ and CUDA.

Main Results:

• The Parallel Ants (PA) architecture achieved higher solution quality with fewer iterations as parallel instances increased.
• GPU performance was found to be suboptimal for complex real-world routing due to significant metadata access requirements.
• The study demonstrated performance discrepancies between benchmark results and real-world application outcomes.

Conclusions:

• Standard benchmarks are insufficient for drawing generalized conclusions about ACO performance on complex, real-world problems.
• The effectiveness of parallel ACO architectures varies depending on the problem's complexity and metadata requirements.
• Hardware suitability for ACO is context-dependent, with GPUs being less effective for large-scale, metadata-intensive routing tasks.