In Group Trip Planning (GTP) Query Problem, we are given a city road network where a number of Point of Interest (PoI) have been marked with their respective categories (e.g., Cafeteria, Park, Movie Theater, etc.). A group of agents wants 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 its 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Group Trip Planning Query Problem with Multimodal Journey

  • Dildar Ali,
  • Suman Banerjee,
  • Yamuna Prasad

摘要

In Group Trip Planning (GTP) Query Problem, we are given a city road network where a number of Point of Interest (PoI) have been marked with their respective categories (e.g., Cafeteria, Park, Movie Theater, etc.). A group of agents wants 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 its 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.