Fair and Efficient Algorithms for Sequenced Group Trip Planning Query Problem

This paper studies the Fair Sequenced Group Trip Planning Query Problem (Fair-SGTP) , a variant of the Group Trip Planning Problem that arises in autonomous and intelligent transportation systems supporting shared group-based mobility services. Fair-SGTP focuses on selecting optimal sequences of Points-of-Interest in a road network to minimize total travel distance while ensuring fairness among group members, which is an increasingly important requirement in autonomous ride-sharing, tourist routing, and collaborative mobility planning. Despite the NP-hard nature of classical GTP queries, we present polynomial-time algorithms for Fair-SGTP under multiple fairness constraints. Drawing inspiration from fair resource allocation problems, we investigate three fairness notions: minimum-envy path, minimax-distance path, and ϵ-proportional path, and adapt them to the group trip planning context. We introduce the Price of Fairness (PoF) to quantify the trade-off between efficiency and fairness in autonomous route planning. Our theoretical analysis shows that while the PoF can be unbounded for general solutions, it is bounded for Pareto-optimal solutions by (2 b − 1) for minimum-envy path, b for minimax-distance path, and (2 b − 1) for ϵ-proportional path with b agents, and these bounds are provably tight. We evaluate the proposed algorithms using real-world urban road network datasets, demonstrating superior performance compared to existing approaches. Excluding the one-time shortest-path preprocessing step, the algorithms compute fair routes in \(O(bn^4 + (kn)^3) \) time with k being the number of categories, and experimental results indicate that the PoF remains below 2 across all tested city networks and fairness criteria. These results highlight the practicality of Fair-SGTP for deployment in autonomous transportation systems requiring equitable and efficient group decision-making.