Three-Step Metaheuristic for the Multiple Objective Multiple Traveling Salesmen Problem

Youssef Harrath
Additional contact information
Youssef Harrath: Department of Computer Science, University of Bahrain, Zallaq, Bahrain

International Journal of Applied Metaheuristic Computing (IJAMC), 2020, vol. 11, issue 4, 130-148

Abstract: In this article, the multiple objective multiple Traveling Salesman Problem is considered. m salesmen have to visit n cities to perform some tasks each taking a given processing time. Two objectives are considered: balance the working loads of different salesmen and minimize their total traveled distance. To solve this NP-hard problem, a 3-phase metaheuristic was developed. In the first 2 phases, the principle of center of mass and a neighborhood search technique are used to assign the n cities to the m salesmen. In the third phase, a TSP solver was used to generate an optimal tour to every salesman using its assigned cities in phase 2. The metaheuristic was tested using TSP benchmarks of different sizes. The obtained results showed almost optimal load balancing for all tested instances and optimal tours in term of total traveled distances. A conducted comparison study showed that the proposed metaheuristic outperforms a recently published clustering algorithm for the workload objective.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/IJAMC.2020100107 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:11:y:2020:i:4:p:130-148

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().