Finding the minimum cost of an airline route using the traveling salesman problem
We present an application of the Traveling Salesman Problem (TSP) using Integer Linear Programming (ILP) via Branch-and-Bound and Heuristics via Nearest Neighbor and 2-Opt. We apply these methods to find the minimum cost of visiting 48 states in the United States of America (U.S.A.) where we have to...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Animo Repository
2014
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/etd_bachelors/17997 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Language: | English |
| Summary: | We present an application of the Traveling Salesman Problem (TSP) using Integer Linear Programming (ILP) via Branch-and-Bound and Heuristics via Nearest Neighbor and 2-Opt. We apply these methods to find the minimum cost of visiting 48 states in the United States of America (U.S.A.) where we have to visit each states exactly once and return to its original destination. We compare the different results and see how each algorithm appraise the accuracy of the calculations. |
|---|