https://eight-wonders.fly.dev/
Eight Wonders is a flight path optimizer which finds the shortest path between a series of airports.
Have you ever wanted to fly around the world to visit your bucket list destinations? We'll help you create an itinerary that minimizes time spent on the plane. You can start an itinerary from scratch or customize one of our favorites such as Michelin Star Dining or Festivals!. Select up to 8 airports, and we'll automatically sort them in the optimal flight order. You can also make notes on the experiences you want to have at each place. Bon voyage!
The idea is that you can visit the Seven Wonders of the World, and whichever you consider to be the Eighth Wonder!
🗺️ Generate a Link to Great Circle Mapper
Eight Wonders is an project I built halfway through the Launch School Core Curriculum, to make something fun using what I've learned. The material covered up to this point includes fundamental Ruby syntax, OOP, closures, regex, testing, deployment, networking, databases, HTML & CSS, and problem solving.
- Ruby application written with the Rack-based Sinatra framework
- ERB view templates
- Puma web server
- PostgreSQL database
- Tests written in Minitest
- Vanilla HTML, CSS, and JS
- Github Action for continuous deployment to fly.io
This is an example of the Traveling Salesman Problem (TSP), which asks:
"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
To solve this, we find the lowest-cost Hamiltonian cycle for an undirected symmetric graph. Of three algorithms considered, the dynamic programming solution was selected to provide an exact solution with acceptable computation time for n ≤ 8.
| Algorithm | Description | Accuracy | Time Complexity |
|---|---|---|---|
| Sort by longitude | Normalize airport longitudes to positive numbers, and sort in ascending order. Some inaccuracy when airports are close together. | Approximate | O(n log(n)) |
| Naive approach | Compute travel distances for all possible routes, and select the shortest. | Exact | O(n!) |
| Dynamic programming (Held-Karp) | Iteratively find the shortest travel path from the starting location to cities that are 1 through n-1 nodes away, storing results in a DP table for reference in subsequent iterations. Add the "return home" segment to all paths in the final table, and select the shortest. Code adapted from rameziophobia. |
Exact | O(2^n n^2) |
Distances between locations around the world are calculated using the haversine formula.