EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Solving optimization problems simultaneously: the variants of the traveling salesman problem with time windows using multifactorial evolutionary algorithm

Ha-Bang Ban, Dang-Hai Pham

PeerJ Computer Science · 10.01.2023 · 9 · e1192

DOI: 10.7717/peerj-cs.1192 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PeerJ Computer Science, online erschienen am 10.01.2023. Verfasst von Ha-Bang Ban und 1 weiteren Autor:innen. Beteiligte Einrichtung: Computer Science Department, School of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, Vietnam. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Hanoi University of Science and Technology.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We studied two problems called the Traveling Repairman Problem (TRPTW) and Traveling Salesman Problem (TSPTW) with time windows. The TRPTW wants to minimize the sum of travel durations between a depot and customer locations, while the TSPTW aims to minimize the total time to visit all customers. In these two problems, the deliveries are made during a specific time window given by the customers. The difference between the TRPTW and TSPTW is that the TRPTW takes a customer-oriented view, whereas the TSPTW is server-oriented. Existing algorithms have been developed for solving two problems independently in the literature. However, the literature does not have an algorithm that simultaneously solves two problems. Multifactorial Evolutionary Algorithm (MFEA) is a variant of the Evolutionary Algorithm (EA), aiming to solve multiple factorial tasks simultaneously. The main advantage of the approach is to allow transferrable knowledge between tasks. Therefore, it can improve the solution quality for multitasks. This article presents an efficient algorithm that combines the MFEA framework and Randomized Variable Neighborhood Search (RVNS) to solve two problems simultaneously. The proposed algorithm has transferrable knowledge between tasks from the MFEA and the ability to exploit good solution space from RVNS. The proposed algorithm is compared directly to the state-of-the-art MFEA on numerous datasets. Experimental results show the proposed algorithm outperforms the state-of-the-art MFEA in many cases. In addition, it finds several new best-known solutions.

Schlagwörter

Stichwörter der Autor:innen

AlgorithmCombinatorial optimizationMFEAMetaheuristicTRPTWTSPTW

Autor:innen und Institutionen

  • Computer Science Department, School of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, Vietnam.

Förderung

  • Hanoi University of Science and Technology

Zitieren

APA

Ban, H. B., & Pham, D. H. (2023). Solving optimization problems simultaneously: the variants of the traveling salesman problem with time windows using multifactorial evolutionary algorithm. PeerJ Computer Science, 9, e1192. https://doi.org/10.7717/peerj-cs.1192

Vancouver

Ban HB, Pham DH. Solving optimization problems simultaneously: the variants of the traveling salesman problem with time windows using multifactorial evolutionary algorithm. PeerJ Computer Science. 2023;9:e1192. doi:10.7717/peerj-cs.1192

BibTeX
@article{Ban2023,
  author = {Ban, Ha-Bang and Pham, Dang-Hai},
  title = {Solving optimization problems simultaneously: the variants of the traveling salesman problem with time windows using multifactorial evolutionary algorithm},
  journal = {PeerJ Computer Science},
  year = {2023},
  volume = {9},
  pages = {e1192},
  doi = {10.7717/peerj-cs.1192}
}
Kostenlos starten →