Login
HomePublicationsJournal Paper

An Analytical Hierarchy Process-Based Approach to Solve the Multi-Objective Multiple Traveling Salesman Problem
Ref: CISTER-TR-180901       Publication Date: Sep 2018

An Analytical Hierarchy Process-Based Approach to Solve the Multi-Objective Multiple Traveling Salesman Problem

Ref: CISTER-TR-180901       Publication Date: Sep 2018

Abstract:
We consider the problem of assigning a team of autonomous robots to target locations in the context of a disaster management scenario while optimizing several objectives. This problem can be cast as a multiple traveling salesman problem, where several robots must visit designated locations. This paper provides an analytical hierarchy process (AHP)-based approach to this problem, while minimizing three objectives: the total traveled distance, the maximum tour, and the deviation rate. The AHP-based approach involves three phases. In the first phase, we use the AHP process to define a specific weight for each objective. The second phase consists in allocating the available targets, wherein we define and use three approaches: market-based, robot and task mean allocation-based, and balanced-based. Finally, the third phase involves the improvement in the solutions generated in the second phase. To validate the efficiency of the AHP-based approach, we used MATLAB to conduct an extensive comparative simulation study with other algorithms reported in the literature. The performance comparison of the three approaches shows a gap between the market-based approach and the other two approaches of up to 30%. Further, the results show that the AHP-based approach provides a better balance between the objectives, as compared to other state-of-the-art approaches. In particular, we observed an improvement in the total traveled distance when using the AHP-based approach in comparison with the distance traveled when using a clustering-based approach.

Authors:
Sahar Trigui
,
Omar Cheikhrouhou
,
Anis Koubâa
,
Anis Zarrad
,
Habib Youssef


Published in Intelligent Service Robotics, Springer, Volume 11, Issue 4, pp 355-369.

DOI:https://doi.org/10.1007/s11370-018-0259-8.
ISSN: 1861-2784.



Record Date: 3, Sep, 2018