QRT-meeting-in-the-middle

Inspiration

Our inspiration came directly from the QRT challenge brief. QRT is a global company with 13 offices, and its teams face a complex problem: how to meet in person while balancing fairness for employees and environmental sustainability. We were particularly motivated by the challenge to go beyond simple flight data and “incorporate alternative transport modes” to find a truly optimal solution.

What It Does

Our tool, Meet in the Middle, ingests a JSON file containing attendees, their home cities, and a meeting’s time window. It then performs a powerful two-phase analysis:

Phase 1 – Scoring:

We scan millions of travel segments—including OAG flight data and our own integrated train data—to rank every potential meeting city. The ranking uses a weighted score that balances total CO₂ emissions against travel fairness, defined as a mix of average travel time and its standard deviation.

Phase 2 – Itinerary Optimization:

We take the top three ranked cities and build a detailed, optimized itinerary for each. For the top-ranked city, we run a span optimization to find the exact combination of flights and trains that minimizes the total event span—the time from the first person’s arrival to the last person’s departure.

The final output is a JSON list of top recommendations, including the chosen host city, total CO₂, detailed travel-time metrics, and a complete travel itinerary.

How We Built It

We developed the solution in Python, using the Polars library as our core data-processing engine.

Data Pipeline: We used Polars’ lazy scan_csv to efficiently process the massive OAG flight schedules. A dynamic file loader reads only data within the requested “availability window,” drastically reducing memory usage.

Train Integration: We extended the dataset by creating our own train_schedules.csv and train_emissions.csv. By mirroring the OAG schema, our algorithm seamlessly treats trains as a low-carbon, first-class travel option—without needing additional logic.

Optimization Algorithm: Our two-phase funnel approach first scores all cities using pre-calculated averages. Then, for the top city, we perform span optimization using itertools.product to find the best combination of travel segments.

Performance: We implemented an aggressive caching system (ROUND_TRIP_CACHE) that memoizes round-trip calculations. This ensures that even complex routes (e.g., Mumbai–Paris) are computed only once, dramatically boosting speed.

Challenges We Faced

Performance Constraints: Brute-forcing this problem was impossible. The biggest challenge was computation time—especially for 1-stop flight calculations, which require self-joins. We solved this through Polars’ lazy execution, pre-filtering, and our round-trip cache. We also added a toggle to disable 1-stop flights for a faster “simple” mode.

Data Integration:

Integrating our custom train data was tricky. We had to perfectly replicate the OAG schema—matching airport codes, ELPTIM formats, and EQUIPMENT_CD_ICAO fields—and create a custom emissions file so CO₂ joins would work for trains.

Fairness Definition:

Fairness is subjective. We defined it as a balance between low average travel time and low standard deviation—minimizing the gap between the shortest and longest journeys.

Accomplishments We’re Proud Of

• Successful pricing and accommodation: Our tool correctly prefers trains over flights for routes like London–Paris, cutting CO₂ emissions and proving the “alternative transport” concept.
• Two-Phase Optimizer: We go beyond finding the best city—we find the best itinerary. Our Phase 2 optimization respects employees’ time by minimizing total time away from home.
• High Performance: Despite handling massive data, our system remains fast. Thanks to lazy loading and caching, we can score hundreds of cities in seconds.

What We Learned

• Polars is a Game-Changer: Its lazy API and high performance make it ideal for large-scale data analysis.
• Schema is King: Matching the train data schema to OAG’s saved us hundreds of lines of code—the algorithm required no structural changes.
• Filter Early, Optimize Late: A multi-phase approach is key. We learned to use quick, approximate scoring (Phase 1) to eliminate 99% of options before applying high-precision optimization (Phase 2).

What’s Next for QRT: Meet in the Middle

• Cost Analysis: Integrate flight and hotel pricing data to introduce a third optimization dimension.
• Interactive UI: Build a dashboard or map that visualizes trade-offs, allowing users to adjust weights for CO₂, travel time, and cost in real time.
• Last-Mile & Accommodation: Add data for last-mile transport and nearby hotels to complete the journey planning experience.