Multi-Candidate Carpooling Routing Problem and Its Approximation Algorithms

Motivated by the carpooling services, we investigate a new and more challenging scenario for carpooling and model it as the Multi-candidate Carpooling Routing Problem (MCRP). The MCRP can be regarded as a new variant of TSP called Generalized Precedence-Constaint Asymmetric Subset Traveling Salesman Path Problem (GPAS-TSPP) and we construct complexity hierarchies for the related problems. We propose a 4-approximation algorithm for its special case Carpooling Routing Problem (CRP), followed by a ( \(5+\epsilon \) )-approximation algorithm for MCRP on the planar graph. We also design an exact algorithm based on dynamic programming to solve the general MCRP, serving as a benchmark. To the best of our knowledge, we are the first to explore the complexity hierarchy of carpooling problems in the TSP family and give constant-approximation algorithms for these new practical variants.