

Fill in the following table for daily, weekday (M-F) one-way flights between New York and Los Angeles. But in addition to that, it’s sometimes difficult to decide which data to use when setting up the problem. This part of the Case drives home the following point: The TSP may be easy to describe, but it’s hard to solve for other than simple problems. What’s his best plan if he wants to minimize cost?.What’s his best plan, if he wants to minimize time?.Via Air:Ī salesman wants to visit all three cities on one day, starting and finishing in A. There are flights between A and B, and also between A and C but there are no flights between B and C, other than through A. A is an airline hub, such as Atlanta B and C are satellite cities. Consider the “too simple” problem of three cities, mentioned on the Module 3 Home page.

Anything larger requires a computer app.įor all of its complexity, given more than four or five cities, the TSP may still be unable to deal with the real world. Five stops is near the upper practical limit for hand solutions. →The first figure is the flowchart used to find all possible routes, and the second figure is the list of routes and mirror routes used to find the redundancies.We’re giving you this head start because the purpose of the problem is not to waste hours, but rather to introduce you to the complexity of the general TSP. How many non-redundant routes are there, total? Use the formula.Use the “by-hand” scheme described on the module Home page. To simplify your work, please use the one-letter codes instead of city names for example, A=Dallas. Find the round trip with the fewest miles. Green cells (above diagonal): Highway milesīlue cells (below diagonal): Flight time (hrs:mins)Ī traveler wants to visit all these cities by car, beginning and ending in Dallas. Here is a table of road miles (via most direct routes) and flight time among five cities. SCHEDULING: THE TRAVELING SALESMAN PROBLEM
