How to minimize group trip cost with multimodal journeys?
Group Trip Planning Query Problem with Multimodal Journey
February 6, 2025
https://arxiv.org/pdf/2502.03144This paper introduces the Group Trip Planning Query Problem with Multimodal Journey (GTP-MTM), which aims to optimize group travel plans in a city with various points of interest (POIs) and transportation options. Given a city road network with categorized POIs, agent start and end locations, and transport details (cost, time, etc.), the GTP-MTM finds the optimal set of POIs to visit (one per category) and the best travel plan (sequence of routes and transport modes) minimizing total group travel cost. A dynamic programming algorithm is proposed and evaluated on real-world datasets.
Key points for LLM-based multi-agent systems:
- Complex Planning Problem: GTP-MTM is a complex planning problem, involving multiple agents with individual goals (reaching destination and visiting POIs) within a shared context (group travel plan, transportation network). LLMs could be used for modeling individual agent preferences and constraints or even for generating negotiation strategies between agents.
- Multi-Agent Coordination: The algorithm inherently addresses multi-agent coordination by optimizing a shared objective (group cost). LLMs could be explored for decentralized coordination mechanisms, where agents communicate and negotiate their individual plans using natural language.
- Dynamic Environment: The inclusion of multiple transport modalities and associated costs implicitly introduces a dynamic environment. LLMs could contribute by handling real-time updates in transport availability and costs, enabling adaptive planning during the trip.
- Multimodal Optimization: The problem formulation itself requires optimization across multiple modalities (transport types). LLMs, combined with numerical optimization techniques, could explore strategies that incorporate more nuanced preferences, such as comfort and convenience, in addition to cost and time.