Self-Adaptive Ant System with Hierarchical Clustering for the Thief Orienteering Problem

This repository implements the SAAS-HC algorithm (Self-Adaptive Ant System with Hierarchical Clustering) for the Thief Orienteering problem. The algorithm explanation was presented in the paper "Self-Adaptive Ant System with Hierarchical Clustering for the Thief Orienteering Problem" by Vu Hoang Huynh, The Viet Le, and Ngoc Hoang Luong.

Furthermore, this repository provides the SAAS-HC solution for the ThOP benchmark and the solutions of other algorithms: ILS, BRKGA, ACO, and ACO++. The implementations of these algorithms can be found in this repository. All the solution files were stored in the experiments folder.

Contributor

Vu Hoang Huynh, The Viet Le, and Ngoc Hoang Luong.

Installation

Linux OS

Create Conda environment and install dependencies

conda create -n saas_hc python tqdm tabulate pyaml gxx cmake make mlpack cereal 

Extract ThOP benchmark instances

tar -xzf instances/thop_instances.tar.gz -C instances/

Usage

Activate Conda environment

conda activate saas_hc

Run SAAS-HC experiment

cd src
python run_experiments.py --sol_dir ../experiments/saas_hc

Acknowledgement

Our code is heavily inspired by this repository which is the source code of the paper "Efficiently solving the thief orienteering problem with a max-min ant colony optimization algorithm" by Jonatas B. C. Chagas and Markus Wagner.

Besides that, we used the K-Means library from mlpack and the C implementation of the CMA-ES algorithm from this repository by Nikolaus Hansen.

This research was funded by University of Information Technology - Vietnam National University HoChiMinh City.