Análise Experimental de Solvers MILP para o Problema Multi-objetivo do Caixeiro Viajante com Bônus e Passageiros

Sistemas de transporte compartilhado são uma alternativa potencial para melhorar a mobilidade urbana, mas envolvem inerentemente funções objetivo conflitantes. O Problema do Caixeiro Viajante Multi-objetivo com Bônus e Passageiros (MoTSPPP), um problema NP-difícil, combina roteamento, transporte de passageiros e coleta de bônus sob três funções objetivo: custo, tempo e bônus. Embora exista uma formulação MILP para o problema, faltam estudos comparativos sobre o desempenho de solvers em sua resolução exata. Este trabalho avalia o Gurobi, IBM CPLEX e SCIP em uma formulação de programação linear inteira mista (MILP) para o MoTSPPP. Os experimentos envolvem 84 instâncias com até 200 vértices, e as métricas consideram tempo de processamento, quantidade de soluções Pareto-ótimas e hipervolume. Os resultados mostram que apenas instâncias pequenas são resolvidas no limite de tempo, evidenciando a dificuldade do problema. O Gurobi apresentou melhor desempenho, com mais soluções e fronteiras de Pareto mais completas, seguido pelo CPLEX e SCIP.