An Efficient Evolutionary Metaheuristic for the Traveling Repairman (Minimum Latency) Problem

Authors

Boldizsár Tüű-Szabó^{1, *,} , Péter Földesi², László T. Kóczy^{1, 3}

¹Department of Information Technology, Szechenyi Istvan University, Gyor, Hungary

²Department of Logistics, Szechenyi Istvan University, Gyor, Hungary

³Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, Budapest, Hungary

^*Corresponding author. Email. tuu.szabo.boldizsar@sze.hu

DOI

10.2991/ijcis.d.200529.001How to use a DOI?

Keywords

Metaheuristics; Traveling repairman problem; Minimum latency problem; Discrete optimization; Memetic algorithm

Abstract

In this paper we revisit the memetic evolutionary family of metaheuristics, called Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA), whose members combine Furuhashi's Bacterial Evolutionary Algorithm and various discrete local search techniques. These algorithms have proven to be efficient approaches for the solution of NP-hard discrete optimization problems such as the Traveling Salesman Problem (TSP) with Time Windows.

This paper presents our results in solving the Traveling Repairman Problem (also called Minimum Latency Problem) with a DBMEA variant. The results are compared with state-of-the-art heuristics found in the literature. The DBMEA in most cases turned out to be faster than all other methods, and for the bigger benchmark instances it was also found to have better solutions than the former best-known results. Based on these test results we claim to have found the best approach and thus we suggest the use of the DBMEA for the Traveling Repairman Problem, especially for large instances.

Copyright

© 2020 The Authors. Published by Atlantis Press SARL.

Open Access

This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

TY  - JOUR
AU  - Boldizsár Tüű-Szabó
AU  - Péter Földesi
AU  - László T. Kóczy
PY  - 2020
DA  - 2020/06/16
TI  - An Efficient Evolutionary Metaheuristic for the Traveling Repairman (Minimum Latency) Problem
JO  - International Journal of Computational Intelligence Systems
SP  - 781
EP  - 793
VL  - 13
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.200529.001
DO  - 10.2991/ijcis.d.200529.001
ID  - Tüű-Szabó2020
ER  -