Multi-objective Traveling Salesman Problem with Profits and Passengers: Exact, Heuristic and Evolutionary Approaches

This paper addresses the Multi-objective Traveling Salesman Problem with Profits and Passengers (MoTSPPP), an extension of the Traveling Salesman Problem with Profits, to model ridesharing systems in multi-objective contexts. This problem, which considers three objective functions (minimizing travel cost, minimizing travel time, and maximizing the bonuses collected), has not been studied before. We implement a mathematical formulation to compute Pareto-optimal solutions, two non-evolutionary heuristics, and two evolutionary algorithms (NSGA-II and MOEA/D). Non-evolutionary heuristics solve the salesman route, bonus collection, and passenger assignments sequentially, whereas NSGA-II and MOEA/D combine these three decision levels via genetic operators. Experiments on 84 instances with up to 200 vertices assess the difficulty of optimally solving the problem and the performance of the algorithms.