This paper presents an improved version of the Vantage Point Bees Algorithm (VPBA-II), which is implemented to solve the Travelling Salesman Problem. The Vantage Point Tree has been used to produce initial tour solutions and also as a global search operator of the proposed algorithm to find the minimal Hamiltonian tour of the Travelling Salesman Problem. VPBA-II is tested on 15 different benchmark datasets from TSPLIB, particularly for the high dimensional combinatorial solution spaces, and it outperformed the basic Bees Algorithm. The composition of the local search operators combined with Vantage Point Tours perform better except one dataset and achieved optimum results according to best-known solutions of Travelling Salesman Problem as a best-case scenario. The experiments prove that Vantage Point Tour construction could be used as initialization and global search operator to improve the basic Bees Algorithm performance on the combinatorial domains.

An Improved Vantage Point Bees Algorithm to Solve Combinatorial Optimization Problems from TSPLIB

Caterino, M;
2021

Abstract

This paper presents an improved version of the Vantage Point Bees Algorithm (VPBA-II), which is implemented to solve the Travelling Salesman Problem. The Vantage Point Tree has been used to produce initial tour solutions and also as a global search operator of the proposed algorithm to find the minimal Hamiltonian tour of the Travelling Salesman Problem. VPBA-II is tested on 15 different benchmark datasets from TSPLIB, particularly for the high dimensional combinatorial solution spaces, and it outperformed the basic Bees Algorithm. The composition of the local search operators combined with Vantage Point Tours perform better except one dataset and achieved optimum results according to best-known solutions of Travelling Salesman Problem as a best-case scenario. The experiments prove that Vantage Point Tour construction could be used as initialization and global search operator to improve the basic Bees Algorithm performance on the combinatorial domains.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4808498
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 2
social impact