Experimental Analysis of MILP Solvers for the Multi-Objective Problem of the Traveling Salesman with Bonuses and Passengers

Shared transport systems are a potential alternative to improve urban mobility, but inherently involve conflicting objective functions. The Multi-Objective Traveling Salesman Problem with Bonuses and Passengers (MoTSPPP), an NP-hard problem, combines routing, passenger transport, and bonus collection under three objective functions: cost, time, and bonuses. Although there is a MILP formulation for the problem, comparative studies on the performance of solvers at their exact resolution are lacking. This work evaluates Gurobi, IBM CPLEX and SCIP in a mixed integer linear programming (MILP) formulation for MoTSPPP. The experiments involve 84 instances with up to 200 vertices, and the metrics consider processing time, number of Pareto-optimal solutions, and hypervolume. The results show that only small instances are resolved within the time limit, highlighting the difficulty of the problem. Gurobi performed best, with more solutions and more complete Pareto frontiers, followed by CPLEX and SCIP.