GORTS: genetic algorithm based on one-by-one revision of two sides for dynamic travelling salesman problems

Xiaolong Xu, Hao Yuan, PETER MATTHEW, JEFFREY RAY, Ovidiu Bagdasar, MARCELLO TROVATI

Research output: Contribution to journalArticle

Abstract

The dynamic travelling salesman problem (DTSP) is a natural extension of the standard travelling salesman problem, and it has attracted significant interest in recent years due to is practical applications. In this article, we propose an efficient solution for DTSP, based on a genetic algorithm (GA), and on the one-by-one revision of two sides (GORTS). More specifically, GORTS combines the global search ability of GA with the fast convergence feature of the method of one-by-one revision of two sides, in order to find the optimal solution in a short time. An experimental platform was designed to evaluate the performance of GORTS with TSPLIB. The experimental results show that the efficiency of GORTS compares favourably against other popular heuristic algorithms for DTSP. In particular, a prototype logistics system based on GORTS for a supermarket with an online map was designed and implemented. It was shown that this can provide optimised goods distribution routes for delivery staff, while considering real-time traffic information.
Original languageEnglish
Pages (from-to)1
Number of pages14
JournalSoft Computing
Early online date21 Sep 2019
DOIs
Publication statusE-pub ahead of print - 21 Sep 2019

Fingerprint

Traveling salesman problem
Travelling salesman problems
Genetic algorithms
Genetic Algorithm
Distribution of goods
Global Search
Heuristic algorithms
Natural Extension
Efficient Solution
Heuristic algorithm
Logistics
Optimal Solution
Traffic
Prototype
Real-time
Evaluate
Experimental Results

Keywords

  • DTSP
  • Path optimisation
  • One-by-one revision of two slides
  • Genetic algorithm

Cite this

@article{b87fecb4692c4596b47f524e1512cc51,
title = "GORTS: genetic algorithm based on one-by-one revision of two sides for dynamic travelling salesman problems",
abstract = "The dynamic travelling salesman problem (DTSP) is a natural extension of the standard travelling salesman problem, and it has attracted significant interest in recent years due to is practical applications. In this article, we propose an efficient solution for DTSP, based on a genetic algorithm (GA), and on the one-by-one revision of two sides (GORTS). More specifically, GORTS combines the global search ability of GA with the fast convergence feature of the method of one-by-one revision of two sides, in order to find the optimal solution in a short time. An experimental platform was designed to evaluate the performance of GORTS with TSPLIB. The experimental results show that the efficiency of GORTS compares favourably against other popular heuristic algorithms for DTSP. In particular, a prototype logistics system based on GORTS for a supermarket with an online map was designed and implemented. It was shown that this can provide optimised goods distribution routes for delivery staff, while considering real-time traffic information.",
keywords = "DTSP, Path optimisation, One-by-one revision of two slides, Genetic algorithm",
author = "Xiaolong Xu and Hao Yuan and PETER MATTHEW and JEFFREY RAY and Ovidiu Bagdasar and MARCELLO TROVATI",
year = "2019",
month = "9",
day = "21",
doi = "https://doi.org/10.1007/s00500-019-04335-2",
language = "English",
pages = "1",
journal = "Soft Computing",
issn = "1432-7643",
publisher = "Springer Verlag",

}

GORTS: genetic algorithm based on one-by-one revision of two sides for dynamic travelling salesman problems. / Xu, Xiaolong; Yuan, Hao; MATTHEW, PETER; RAY, JEFFREY; Bagdasar, Ovidiu; TROVATI, MARCELLO.

In: Soft Computing, 21.09.2019, p. 1.

Research output: Contribution to journalArticle

TY - JOUR

T1 - GORTS: genetic algorithm based on one-by-one revision of two sides for dynamic travelling salesman problems

AU - Xu, Xiaolong

AU - Yuan, Hao

AU - MATTHEW, PETER

AU - RAY, JEFFREY

AU - Bagdasar, Ovidiu

AU - TROVATI, MARCELLO

PY - 2019/9/21

Y1 - 2019/9/21

N2 - The dynamic travelling salesman problem (DTSP) is a natural extension of the standard travelling salesman problem, and it has attracted significant interest in recent years due to is practical applications. In this article, we propose an efficient solution for DTSP, based on a genetic algorithm (GA), and on the one-by-one revision of two sides (GORTS). More specifically, GORTS combines the global search ability of GA with the fast convergence feature of the method of one-by-one revision of two sides, in order to find the optimal solution in a short time. An experimental platform was designed to evaluate the performance of GORTS with TSPLIB. The experimental results show that the efficiency of GORTS compares favourably against other popular heuristic algorithms for DTSP. In particular, a prototype logistics system based on GORTS for a supermarket with an online map was designed and implemented. It was shown that this can provide optimised goods distribution routes for delivery staff, while considering real-time traffic information.

AB - The dynamic travelling salesman problem (DTSP) is a natural extension of the standard travelling salesman problem, and it has attracted significant interest in recent years due to is practical applications. In this article, we propose an efficient solution for DTSP, based on a genetic algorithm (GA), and on the one-by-one revision of two sides (GORTS). More specifically, GORTS combines the global search ability of GA with the fast convergence feature of the method of one-by-one revision of two sides, in order to find the optimal solution in a short time. An experimental platform was designed to evaluate the performance of GORTS with TSPLIB. The experimental results show that the efficiency of GORTS compares favourably against other popular heuristic algorithms for DTSP. In particular, a prototype logistics system based on GORTS for a supermarket with an online map was designed and implemented. It was shown that this can provide optimised goods distribution routes for delivery staff, while considering real-time traffic information.

KW - DTSP

KW - Path optimisation

KW - One-by-one revision of two slides

KW - Genetic algorithm

U2 - https://doi.org/10.1007/s00500-019-04335-2

DO - https://doi.org/10.1007/s00500-019-04335-2

M3 - Article

SP - 1

JO - Soft Computing

JF - Soft Computing

SN - 1432-7643

ER -