MoTSPPP: Multi-objective Traveling Salesman Problem with Profits and Passengers - Silva, Juvenal Bruno Andrade da; Fernandes, Islame Felipe da Costa (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2026: Anais do XXXIX Concurso de Teses e DissertaçõesDO - 10.5753/ctd.2026.19545, 2026)
Ridesharing systems have emerged as a promising solution to urban mobility challenges, requiring routing algorithms that handle conflicting objectives such as travel cost, travel time, and driver bonuses. Previous studies addressed this context through extensions of the Traveling Salesman Problem, notably the Traveling Salesman Problem with Profits (TSPP) and the Bi-objective Traveling Salesman Problem (BiTSP), which consider subsets of these objectives. However, the literature lacks a multi-objective formulation that simultaneously optimizes cost, time, and bonuses in ridesharing systems. This work proposes the Multi-objective Traveling Salesman Problem with Profits and Passengers (MoTSPPP), an NP-hard optimization problem that minimizes travel cost and time while maximizing bonus collection. Eight algorithms are investigated, including an exact method based on a mathematical formulation, three naive heuristics, and four state-of-the-art evolutionary metaheuristics (NSGA-II, MOEA/D, IBEA, and SPEA2). An experimental study on 252 symmetric and asymmetric instances with varying edge-weight correlations evaluates processing time, solution quality, and diversity using statistical analysis. Results indicate that MoTSPPP is computationally more challenging than TSPP and BiTSP, and that metaheuristics significantly outperform naive heuristics.