EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fair and Efficient Algorithms for Sequenced Group Trip Planning Query Problem

Napendra Solanki, Shweta Jain, Suman Banerjee, Yayathi Pavan Kumar S

ACM Journal on Autonomous Transportation Systems · 31.03.2027 · 4 (1) · 1-29

DOI: 10.1145/3820905 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Journal on Autonomous Transportation Systems, online erschienen am 04.11.2026. Verfasst von Napendra Solanki und 3 weiteren Autor:innen. Die Arbeit nennt 70 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This article 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 tradeoff 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 (2b-1) for minimum-envy path, b for minimax-distance path, and (2b-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 with existing approaches. Excluding the one-time shortest-path preprocessing step, the algorithms compute fair routes in 𝒪( 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.

Zitieren

APA

Solanki, N., Jain, S., Banerjee, S., & S, Y. P. K. (2027). Fair and Efficient Algorithms for Sequenced Group Trip Planning Query Problem. ACM Journal on Autonomous Transportation Systems, 4(1), 1-29. https://doi.org/10.1145/3820905

Vancouver

Solanki N, Jain S, Banerjee S, S YPK. Fair and Efficient Algorithms for Sequenced Group Trip Planning Query Problem. ACM Journal on Autonomous Transportation Systems. 2027;4(1):1-29. doi:10.1145/3820905

BibTeX
@article{Solanki2027,
  author = {Solanki, Napendra and Jain, Shweta and Banerjee, Suman and S, Yayathi Pavan Kumar},
  title = {Fair and Efficient Algorithms for Sequenced Group Trip Planning Query Problem},
  journal = {ACM Journal on Autonomous Transportation Systems},
  year = {2027},
  volume = {4},
  number = {1},
  pages = {1--29},
  doi = {10.1145/3820905}
}
Kostenlos starten →