Group-wise Itinerary Planning: Solving the "Travel Buddy" Problem in Temporary Social Networks

TL;DR

Attending a conference in a new city and want to share a rental car with like-minded people without the logistical headache? This paper introduces a framework that automatically groups users in a Temporary Social Network (TSN) based on their interests and schedules, then recommends an itinerary that maximizes group satisfaction while avoiding crowded tourist traps.

Background & Motivation

Temporary Social Networks (TSNs) are fleeting communities formed around events like academic conferences or concerts. While users often want to travel together to save costs (e.g., car rentals and fuel), organizing such trips is a nightmare due to:

1. Heterogeneous Preferences: Everyone likes different things (museums vs. parks).
2. Strict Time Budgets: Everyone has different "free blocks" between sessions.
3. Physical Constraints: Car capacities are limited, and POIs (Points of Interest) can become overcrowded, ruining the experience.

Prior works often ignored group size limits or POI crowdedness. This paper bridges those gaps.

Methodology: The Three-Step Framework

The authors break down the complexity into three distinct phases:

1. Offline City Model Training

Instead of starting from scratch for every user, the system analyzes historical data using a Gaussian Mixture Model (GMM) to identify "Interest Patterns" in a city (e.g., the "History Buff" pattern or the "Nature Lover" pattern). This reduces the search space for the next steps.

2. Greedy Car Group Allocation

This is where the "Social" meets the "Spatial." The system calculates a combined similarity score:

• Time Similarity: Using Jaccard Similarity to find overlapping free time.
• Interest Similarity: Using Cosine Similarity between user preference vectors.

A greedy algorithm then fills cars (e.g., 4-5 people) ensuring high Occupancy Rate (OR) and minimal waiting time for members.

3. Crowdedness-Aware Recommendation

Once a group is formed, the system generates a route. The "Profit" of visiting a POI is calculated by: $p{r}_g(v,t)=\frac{(\rho \cdot Pop(v)+(1-\rho )\cdot I_g(c){)}^{\gamma }}{Crd(v,t)}$ Essentially, it rewards popular places that match group interests but penalizes them heavily if they are currently crowded ($Crd(v,t)$).

Experiments & Results

The framework was tested on Flickr datasets from Toronto, Edinburgh, and Osaka.

• Grouping Efficiency: Car utilization reached nearly 97% in some cities, with user time utilization (percentage of time spent traveling rather than waiting) consistently above 93%.
• Itinerary Quality: The authors compared a Backtracking approach (which finds the absolute best route) with a Greedy approach. While Backtracking becomes exponentially slow as the number of POIs grows, the Greedy method achieved ~90% of the optimal score in a fraction of the time.

Table 1: Comparing the proposed system against state-of-the-art methods across multiple constraints.

Critical Insight: Why Does This Work?

The brilliance of this approach lies in its parallelism. By first clustering users into broad "Pattern Groups" (Step 1), the server can process group allocations (Step 2) in parallel for each pattern, significantly reducing latency—a crucial requirement for mobile social applications where users expect near-instant responses.

Limitations & Future Outlook

While the framework is robust, it assumes a static "start point" (the hotel). In a more dynamic TSN, users might want to join a group from different locations. Furthermore, the crowdedness model is based on historical averages; integrating real-time sensor data or social media feeds would make the "Crowdedness-Aware" feature even more powerful.

Conclusion

This paper provides a complete end-to-end pipeline for group-based mobile computing. By balancing individual user satisfaction with collective group constraints, it moves us closer to a "smarter" and more social way of exploring new cities.