Multi-City Optimized Flight Planner

Position: Backend Engineer, Frontend Engineer, Product Lead
Type: Personal project
Duration: Sep 2025 - Present
Stack: Backend — Python · FastAPI · Uvicorn Frontend — React
Skills: API design, caching, optimization, constraint modeling, BFS search, UX/UI design

Summary

Objective

Construct flexible, cost-minimized itineraries given travel windows, stay durations, and required or optional destinations. Treat the itinerary as a constraint-optimization task so the system finds the most cost-efficient multi-city plan that fits the schedule and is the lowest-cost option.

Why This Project?

We want to travel and gain as many new experiences as possible on tight budgets and narrow windows. Current tools assume fixed destinations or single routes, which breaks down when the goal is flexible exploration across multiple cities. This project fixes that by letting you specify time windows; must vs. optional cities; and min/max stay days so the system searches and builds a plan that actually fits your constraints.

Algorithms

• Greedy baseline: Rejected due to local-minima behavior; produced suboptimal downstream legs that we not always feasible given user travel time constraint.
• Top-K nearest neighbors + Beam Search (current): Chooses the cheapest K legs (sorted by price) and breaks ties by earliest arrival time.
  • K: number of cheapest candidate legs to consider at each step (per alias-expanded O/D).
  • BEAM: beam width (keeps BEAM best partial sequences per layer).

Endpoints

• POST /optimize_beam — current optimizer (Top-K + Beam).
• POST /optimize_v0 — greedy (no longer used).
• GET /city-groups — given a city name, returns airport codes (handles aliases / metro areas).
• GET /airport-codes — API data is based on city; parse data and get the airport codes that match the city.

Cache

• Caches the past 24 hours of timeline data per backend session (TTL 24h). 24 hour is currently a placeholder; it will be replaced with dynamic TTL that matches external API.
• Optimization: Skip airports with no connections after 3 consecutive no‑connection days (~30% speedup).
• Attaches basic diagnostics alongside prices in cached payloads.

Reachability Gate

• No offline preprocessing, so the reachability is computed in real time.
• Breadth-first search over a connection map supports both direct and multi-leg routes.
• BFS explores airport pairs layer-by-layer to determine connectivity, enabling reliable detection of transfer paths.

Key Features

• Heuristic optimization: Graph-based solver that generates feasible, low-cost itineraries under user constraints.
• Structured API: JSON inputs for windows, stay durations, and must/optional city sets; ranked plans with simple diagnostics.
• Interactive frontend: React UI to create, submit, and visualize candidate itineraries; tie-breakers surfaced (earliest arrival).

Next Steps

• Implement optimization preference in the future (e.g., price vs. time vs. stops).
• We need to figure out a smarter way to reduce the API call; we don’t want to rely on this API in the future (do web scraping to Google Flights).
• Want the airline website to be integrated so that you can click on it and buy the tickets on the official airline website or Expedia.
• Add a feature that lets users choose between two locations, and the system selects the optimal one.
• Harden error handling, caching, and performance for larger searches and heavier usage.