Group Trip Planning Query Problem with Multimodal Journey

Dildar Ali, Suman Banerjee, Yamuna Prasad · 2025

Read Group Trip Planning Query Problem with Multimodal Journey by Dildar Ali, Suman Banerjee, Yamuna Prasad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-03144.txt.

Introduction

Dildar Ali, Suman Banerjee, and Yamuna Prasad extend a group trip planning problem to cover travel modes, in a 2025 paper. In the classic problem, a group must pick one sight per category. Each member starts and ends at their own points. The goal is the lowest total group travel cost. Past work ignored how the group travels. This version adds modes like bus or car, each with its own cost. The algorithm must now choose sights and modes together.

The team proposes an efficient solution method. They analyze its time and memory needs. Tests on real-life datasets compare it with baseline methods. The recommended sights and modes cost much less in time and money. The authors claim the model is more practical for real planning tools. Friend groups and tour apps both face this joint choice. Future work could add live traffic or budget caps per member.

Catalog record

CREATORDildar Ali, Suman Banerjee, Yamuna Prasad
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-03144

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Group Trip Planning Query Problem with Multimodal Journey Dildar Ali, Suman Banerjee, Yamuna Prasad Abstract In Group Trip Planning (GTP) Query Problem , we are given a city road network where a number of PoInt of Interest (PoI) has been marked with their respective categories (e.g., Cafeteria, Park, Movie Theater, etc.). A group of agents want to visit one PoI from every category from their respective starting location and once finished, they want to reach their respective destinations. This problem asks which PoI from every category should be chosen so that the aggregated travel cost of the group is minimized. This problem has been studied extensively in the last decade, and several solution approaches have been proposed. However, to the best of our knowledge, none of the existing studies have considered the different modalities of the journey, which makes the problem more practical. To bridge this gap, we introduce and study the GTP Query Problem with Multimodal Journey in this paper. Along with the other inputs of the GTP Query Problem, we are also given the different modalities of the journey that are available and their respective cost. Now, the problem is not only to select the PoIs from respective categories but also to select the modality of the journey. For this problem, we have proposed an efficient solution approach, which has been analyzed to understand their time and space requirements. A large number of experiments have been conducted using real-life datasets, and the results have been reported. From the results, we observe that the PoIs and modality of journey recommended by the proposed solution approach lead to much less time and cost than the baseline methods. 1 Introduction In recent times, due to the advancement of wireless internet and GPS-enabled hand-holding mobile devices, capturing the location of a moving object has become easier. This leads to the generation of a large number of datasets and such datasets lead to a different domain called Spatial Databases and Spatial Data Mining [ 13 , 10 ] . One well-studied problem in the domain of spatial databases is the Group Trip Planning Query Problem [ 10 , 8 , 1 , 15 ] . In this problem, we are given a road network of a city where the vertex set is constituted by the set of PoIs and the edge set is the road fragments connecting the PoIs. Also, the PoIs are classified into different categories, such as cafeterias, parks, movie theaters, restaurants, etc. A group of friends (referred to as agents in this paper) want to travel from their respective starting location to a destination location in the city, and during their journey, they want to visit one PoI from every category so that the aggregated travel cost by the group is minimized. This problem has been studied extensively in the last decade, and these can be broadly categorized into passenger-focused and transport manager-focused studies. The passenger-focused studies aim to optimize travel efficiency and experience by minimizing factors like travel time, cost, and number of transfers while considering comfort and convenience. Potthoff and Sauer [ 11 , 12 ] introduced the McTB approach, which optimizes three key criteria: arrival time, the number of public transit trips, and unrestricted transfer modes. Building on this, their HydRA algorithm [ 11 ] enhances query execution efficiency, supporting faster computations in multimodal networks. Delling et al. [ 6 , 4 ] developed efficient algorithms for multimodal routing and delays, incorporating transfer penalties and mode preferences. Further, RAPTOR, proposed by Delling et al. [ 5 ] , focuses on minimizing transfer times and ensuring scalability in large public transportation networks. The transport manager-focused studies address system-wide efficiency, emphasizing operational optimization. Ceder [ 3 ] outlined methods for public transit scheduling and operations essential for integrating multiple transport modes. Li et al. [ 10 ] was the first to study the trip planning query problem on metric graphs and proposed several approximate solutions. Subsequently, this problem has been extended to include a group of travelers instead of a single traveler by Hashem et al. [ 8 ] . Later, Ahmadi et al. [ 1 ] proposed a mixed search (both breadth and depth) strategy and used the progressive group neighbor exploration technique. Lee and Park [ 9 ] studied the trip planning problem to identify a typical meeting point such that the ride-sharing mechanism becomes effective. Additionally, several variants of the GTP Query Problem have been studied, such as incorporating PoI utility values [ 2 ] and fairness criteria [ 14 ] . To the best of our knowledge, the GTP Query Problem has not been studied considering the presence of multiple transport mediums. This paper bridges this gap by studying the GTP Query Problem with multiple transport mediums. In particular, we make the following contributions in this paper: • We introduce and study a practical variant of the GTP Query Problem considering the presence of multiple transport mediums. To the best of our knowledge, this is the first study in this direction. • To address this problem, we introduce an optimal journey planning algorithm and analyze it to understand its time and space requirements. • A large number of experiments have been carried out to establish the effectiveness and efficiency of the proposed solution approach. The rest of this paper has been organized as follows. The background concepts and formal problem description have been described in Section 2 . The proposed solution approach has been stated in Section 3 . Section 4 contains the experiment evaluation of the proposed solution approach. Finally, Section 5 concludes our study and gives future research directions. 2 Background and Problem Definition 2.1 Road Network In this study, we model a city road network using an undirected, weighted graph \mathcal{G}(\mathcal{V},\mathcal{E},W) , where the vertex set \mathcal{V}=\{v_{1},v_{2},\ldots,v_{n}\} contains the set of PoIs in the city. The edge set \mathcal{E} of \mathcal{G} is constituted by the road segments joining the PoIs. Here, W is the edge weight function that maps each edge to the corresponding travel cost between the two PoIs joined by the corresponding road segment, i.e., W:\mathcal{E}\longrightarrow\mathbb{R}^{+} . For any edge (v_{i}v_{j}) , its weight is denoted by W(v_{i}v_{j}) . As per our problem context, ‘vertex’ and ‘PoI’ have been used interchangeably. Similarly, ‘road segment ’ and ‘edge’ have been used interchangeably. For any vertex v_{i}\in\mathcal{V} , the neighbor of v_{i} is denoted by N(v_{i}) and defined as the other PoIs that are directly linked with v_{i} , i.e., N(v_{i})=\{v_{j}:(v_{i}v_{j})\in\mathcal{E}\} . The cardinality of N(v_{i}) is called the degree of v_{i} . A sequence of vertices P=<v_{i},v_{i+1},\ldots,v_{j}> is said to be a path in \mathcal{G} if (v_{k}v_{k+1})\in\mathcal{E} for all i\leq k\leq j-1 . For any path P in \mathcal{G} , let \mathcal{V}(P) and \mathcal{E}(P) denote the set of vertices and edges that constitute the path. The weight of the path P is defined as the sum of the edge weights of the edges that constitute the path, i.e., W(P)=\underset{(v_{p}v_{q})\in\mathcal{E}(P)}{\sum}\ W(v_{p}v_{q}) . For any two vertices v_{i} and v_{j} , the shortest path distance from v_{i} to v_{j} is denoted by dist(v_{i}v_{j}) . As \mathcal{G} is undirected, dist(v_{i}v_{j})=dist(v_{j}v_{i}) . 2.2 Group Trip Planning Query Problem For any positive integer k , [k]

Read the complete text