MoTSPPP: Multi-objective Traveling Salesman Problem with Profits and Passengers
Resumo
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.
Referências
Awerbuch, B., Azar, Y., Blum, A., and Vempala, S. (1995). Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pages 277–283.
Balas, E. (1989). The prize collecting traveling salesman problem. Networks, 19(6):621–636.
Cai, J., Zhu, Q., Lin, Q., Ma, L., Li, J., and Ming, Z. (2023). A survey of dynamic pickup and delivery problems. Neurocomputing, page 126631.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197.
Dell’Amico, M., Maffioli, F., and Värbrand, P. (1995). On prize-collecting tours and the asymmetric travelling salesman problem. International Transactions in Operational Research, 2(3):297–308.
Feillet, D., Dejax, P., and Gendreau, M. (2005). Traveling salesman problems with profits. Transportation Science, 39(2):188–205.
Friedman, M. (1937). The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32(200):675–701.
Gunawan, A., Lau, H. C., and Vansteenwegen, P. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2):315–332.
Li, W., Özcan, E., John, R., Drake, J. H., Neumann, A., and Wagner, M. (2017). A modified indicator-based evolutionary algorithm (mIBEA). In IEEE Congress on Evolutionary Computation (CEC), pages 1047–1054. IEEE.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.
Marques, T. S., Cezario, S. F., Goldbarg, E. F. G., Goldbarg, M. C., and Maia, S. M. D. M. (2019). Quota traveling salesman with passengers and collection time. In 2019 8th Brazilian Conference on Intelligent Systems (BRACIS), pages 299–304. IEEE.
Nemenyi, P. B. (1963). Distribution-Free Multiple Comparisons. Princeton University.
Silva, B. C., Fernandes, I. F., Goldbarg, M. C., and Goldbarg, E. F. (2020). Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms. Computers & Operations Research, 120:104950.
Silva, J. B., Brito, T. A., Rios, R. A., Rios, T. N., and Fernandes, I. F. (2025). Multi-objective traveling salesman problem with profits and passengers: Exact, heuristic and evolutionary approaches. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 419–422.
Tsiligirides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9):797–809.
Yue, C., Song, J., Liu, M., Bi, Y., Guo, W., Lin, H., and Liang, J. (2026). An evolutionary algorithm for multimodal multi-objective traveling salesman problems. Expert Systems with Applications, 297:129540.
Zhang, Q. and Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712–731.
Zitzler, E., Laumanns, M., and Thiele, L. (2001). SPEA2: Improving the strength pareto evolutionary algorithm. TIK Report, 103.
