Multifactorial Evolutionary Algorithm for Simultaneous Solution of TSP and TRP

Abstract

We study two problems called the Traveling Repairman Problem (TRP) and Traveling Salesman Problem (TSP). The TRP wants to minimize the total time for all customers that have to wait before being served, while the TSP aims to minimize the total time to visit all customers. In this sense, the TRP takes a customer-oriented view, whereas the TSP is server-oriented. In the literature, there exist numerous algorithms that are developed for two problems. However, these algorithms are designed to solve each problem independently. Recently, Multifactorial Evolutionary Algorithm (MFEA) has been a variant of Evolutionary Algorithm (EA) aiming to solve multiple optimization tasks simultaneously. The MFEA framework has yet to be fully exploited, but the realm has recently attracted much interest from the research community. This paper proposed a new approach using the MFEA framework to solve these two problems simultaneously. The MFEA has two tasks simultaneously: the first is solving the TRP problem, and the second is solving the TSP. Experiment results show the efficiency of the proposed MFEA: 1. for small instances, the algorithm reaches the optimal solutions of both problems; 2. for large instances, our solutions are better than those of the previous MFEA algorithms.