This repository is the implementation in C++ for the paper An Effective Memetic Algorithm for the Close-Enough Traveling Salesman Problem by Zhenyu Lei, Jin-Kao Hao.
We propose an effective memetic algorithm to solve the Close-Enough Traveling Salesman Problem (CETSP) which is a variant of the well-known Traveling Salesman Problem (TSP). Experimental results on the well-known benchmark instances show that the algorithm is highly competitive with the state-of-the-art methods. We also demonstrate the usefulness of the algorithm on a real laser welding robot path planning problem.
In this repository, we have:
cmake/
folder contains the cmake configuration for gurobi solver.datasets/
folder is for the benchmark instances and real-world instances used in the paper.solutions/
folder provides the solutions for benchmark instances and real-world instancesinclude/
andsrc/
folders contain the source code of the algorithm.CMakelists.txt
is the cmake configuration file.
We conducted experiments on the well-known benchmark instances proposed by Dr. Mennell. The instances are available at link.
And we also tested our algorithm on real-world instances provided by Prof. Béla Vizvári, one of authors of Nedjatia et al.. We provide the instances in the folder datasets/
.
It is necessary to install LKH-2.0 solver which is used to optimize the visiting sequence of solutions, and Gurobi 10.0 solver which is used to obtain the optimal visiting positions for a given visiting sequence.
Please configure Gurobi solver path in the CMakeLists.txt
, and other necessary directories and parameters in include/Defs.hpp
file.
And then compile the code by the following commands:
mkdir build
cd build
cmake ..
make
Then you can run directly the executable binary with default parameters set in include/Defs.hpp
by the following command:
./MA-CETSP
In addition, you can run the code with your own parameters by the following command:
./MA-CETSP -i <instance> -s <seed> -r <max iteration> -p <population size> -b <fitness beta> -d <distance threshold> -n <neighbor size>
If it is helpful for your research, please cite our paper:
@article{lei2024effective,
title={An effective memetic algorithm for the close-enough traveling salesman problem},
author={Lei, Zhenyu and Hao, Jin-Kao},
journal={Applied Soft Computing},
pages={111266},
year={2024},
publisher={Elsevier}
}