MOTSPPP: multi-objective traveling salesman problem with profits and passengers.

Abstract

Ridesharing systems have emerged as a potential solution to urban mobility challenges, promoting collaborative vehicle usage and route optimization. These systems require efficient routing algorithms to balance conflicting objective functions such as travel cost, travel time, and driver bonuses. Previous studies have modeled such systems using the Traveling Salesman Problem with Profits (TSPP), where the driver shares the vehicle with passengers and minimizes travel cost. The Bi-objective Traveling Salesman Problem (BiTSP) has also been investigated in prior work, but it ignores passenger collection and bonuses. Consequently, the literature lacks a multi-objective formulation that captures the real-world trade-offs among these objective functions. This work introduces the Multi-objective Traveling Salesman Problem with Profits and Passengers (MoTSPPP), an NP-hard optimization problem that minimizes travel cost and time, and maximizes bonus collection. A mathematical formulation and an NP-hardness proof are provided. Eight algorithms are investigated: an exact solver, three naive heuristics, and four state-of-the-arte volutionary metaheuristics (NSGA-II, MOEA/D, IBEA and SPEA2). A comprehensive experimental study is conducted on 252 instances, comprising symmetric and asymmetric graphs with varying edge-weight correlations. Supported by statistical tests, the performance evaluation considers processing time, solution quality, and solution diversity. Results demonstrate that the MoTSPPP is computationally more challenging than the TSPP and BiTSP, and that metaheuristic approaches yield significantly better results than naive heuristics.