The multiobjective traveling salesman–repairman problem with profits: design and implementation of a variable neighborhood descent algorithm for a real scenario

Abstract

This paper introduces a problem that can be seen as a combination of the traveling salesman problem with profits and the traveling repairman problem with profits, coined as the multi-objective traveling salesman–repairman problem with profits (Mo-TSRPP). The objective of the Mo-TSRPP is to simultaneously optimize three objectives: the total cost, total latency, and total profit. Indirectly, the number of nodes visited is also considered although not as an objective itself since it is determined by the size of every efficient solution in the Pareto front. The Mo-TSRPP emerges as a real-world problem in which a freelancer, which repairs appliances, wants to plan the daily route. Moreover, the daily plan does not require to visit all customers. To solve the problem, first, a greedy randomized adaptive procedure is designed to generate a set of high-quality nondominated solutions and then, a variable neighborhood descent algorithm is applied for further improving the initial set. This procedure allows us to attain a good approximation of the Pareto front. To prove the performance of the proposal a comparison is done against three well-known evolutionary algorithms: NSGA-II, SPEA-2, and MOEA/D. Finally, a realistic problem is shown and solved to illustrate the potential of the algorithm.