### What is salesman best plan if he wants to minimize time

Assignment Help Engineering Mathematics
##### Reference no: EM131522763

Module Case- SCHEDULING: THE TRAVELING SALESMAN PROBLEM

CASE ASSIGNMENT

Part I

Here is a table of road miles (via most direct routes) and flight time among five cities.
Green cells (above diagonal): Highway miles
Blue cells (below diagonal): Flight time (hrs:mins)

A traveler wants to visit all these cities by car, beginning and ending in Dallas. Find the round trip with the fewest miles. To simplify your work, please use the one-letter codes instead of city names; for example, A=Dallas. Use the "by-hand" scheme described on the module Home page.

1. How many non-redundant routes are there, total? Use the formula.
2. List them.
3. Which is the shortest route?

Help for 2, above.
Here's a partial solution. →

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. Five stops is near the upper practical limit for hand solutions. Anything larger requires a computer app.

Help for 3, above.
You may use the Excel app →
TSP Route Calculator.xlsx

Part II

For all of its complexity, given more than four or five cities, the TSP may still be unable to deal with the real world. Consider the "too simple" problem of three cities, mentioned on the Module 3 Home page. A is an airline hub, such as Atlanta; B and C are satellite cities. 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. Here's the relevant information.

 Via Air: Flying Time (hrs:mins) Airfare A→B 1:30 \$500 B→A 1:30 \$420 A→C 0:50 \$380 C→A 0:50 \$300 C→B (via A) 2:30 (incl. layover at A) \$400 B→C (via A) 3:50 (incl. layover at B) \$590 Via rental car Driving time Mileage + drop-off fee B→C 3:45 \$120 C→B 3:45 \$100

A salesman wants to visit all three cities on one day, starting and finishing in A.

1. What's his best plan, if he wants to minimize time?
2. What's his best plan if he wants to minimize cost?

Part III

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. But in addition to that, it's sometimes difficult to decide which data to use when setting up the problem.

1. Go to any online travel site. Fill in the following table for daily, weekday (M-F) one-way flights between New York and Los Angeles. Include data for at least two different airlines, two different classes of service (Coach/Tourist and Business/First), and two different departure times.

WEEKDAY FLIGHTS FROM JFK TO LAX (One way non-refundable)

 Airline Class Depart (EDT) Arrive (PDT) Time Enrt (HH:MM) Intermediate stops (if any) Price (undiscounted) 1 2 3 4 5 6 7 8

1. Assume you're planning a business trip. What business-related factors would you consider, when choosing one of the flights listed above? Feel free to make up hypothetical factors affecting an imaginary business. (Have fun!)

ASSIGNMENT EXPECTATIONS

1. There are no page limits. Write what you need to write, neither more nor less. Make each sentence count! (Having said that; it's unlikely that one page would be enough, and very likely that eight pages would be too much.)

2. Ensure that your answer reflects your detailed understanding of the theory and techniques taught in this module.

3. References and citations are required. This requirement can be satisfied by citing the module Home page.

4. Follow the instructions in the Writing Style Guide.

### Write a Review

#### Find the total time for both to complete their advising

Mary and Marcia Brown are two sisters currently attending university together. Each requires advising in five subjects: history, English, mathematics, science.

#### Compare the interest earned by p dollars

A 12-cylinder heavy-duty diesel engine will have a guaranteed residual value of \$1,000 in 5 years. Today (year 0) the equivalent worth of this engine.

#### Does she win the claim or not

A Pentecostal nurse claims she was constructively discharged after refusing to assist in medical procedures she considered to be abortions because of her.

#### Why would you be willing to pay this extra interest

The longer a loan schedule lasts, the more interest you will pay. To illustrate, a \$20,000-car-loan at 9% APR (compounded monthly) for three years.

#### Determine the mode for each given series

Given the following series of numbers, determine the mode for each series. Series A: 50, 45, 55, 55, 45, 50, 55, 45, 55 and Series B: 89, 87, 88, 83, 86, 82, 84.

#### How many unique paths would there be

Given a grid of size m * n, lets assume you are starting at (1,1) and your goal is to reach (m,n). At any instance, if you are on (x,y).

#### Make a plot of the solutions

Consider the unconstrained NLP max x1x2 - 5(x1 - 3)4 - 4(x2 - 5)3. Start at the point x(0) = (3,7) and compute 3 iterations of the gradient search to find points x(1), x(2), and x(3). Then make a plot of the 4 solutions (x(0) through x(3)) and show h..

#### What is the total annual equivalent expense for operating

A small company heats its building and spends \$8,000 per year on natural gas for this purpose. Cost increases of natural gas are expected to be 10% per year.

#### Product mix that maximizes weekly profit

There are 2500 labor hours and 4,000 square feet of lumber available each week. Determine the product mix that maximizes weekly profit.

#### Differentiate between the nominal and real exchange rates

Describe the difference between the nominal and real exchange rates. What does rising inflation do to that country's real exchange rate?

#### Best mix of large and small globes

Your company works 1 shift, 40 hours per week, 40 hours for the kiln and 40 hours for the spray paint equipment. Plot the constraints. Show the feasible region. What is the best mix of large and small globes to make the most profit?

#### How much will blooper receive each month

Football coach Ira Blooper has just been fired as head coach at a large university. His buyout amount is \$7.5 million, and Blooper will be repaid.