Fairness Driven Efficient Algorithms for Sequenced Group Trip Planning Query Problem

Abstract

The Group Trip Planning Query Problem (GTP) is a well-researched spatial database problem. Given a city road network with Point-of-Interests (PoIs) representing vertices divided into different categories, GTP aims to suggest one PoI from each category to minimize the group's total distance traveled. This paper focuses on sequenced GTP with pre-determined category visit order, studied under the constraints of fairness, and referred to as sequenced Fair Group Trip Planning Query Problem (Fair-GTP). While GTP aims to minimize the group's total travel time, Fair-GTP seeks to minimize the maximum time difference between any two agents in the group. Although solving group trip planning queries is NP-hard, we present polynomial time algorithms for finding optimal paths for both sequenced GTP and Fair-GTP. Our second significant result provides a bound on the price of fairness (PoF) representing the ratio of optimal path cost in sequenced Fair-GTP to optimal path cost in sequenced GTP. We show that while the PoF can go arbitrarily bad for general sequenced Fair-GTP solutions, restricting to Pareto-optimal solutions bounds the PoF by (2b - 1), where b denotes the number of agents traveling in the group. We further show that this bound is tight. Finally, we present the performance analysis of our algorithms on real-world datasets, demonstrating that our solution approach recommends PoIs within reasonable computational time, and in practice, PoF is below 2. © 2023 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.