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.

Reference no: EM131522763

Questions Cloud

Discuss at least one significant advantage ias approach : [Differences between U.S. GAAP and International Accounting Standards-statement of cash flows] Roche provides cash flow statements based on International.
To research and describe a new technology : Purpose: To research and describe a new technology and hypothesis where it may be used in the future
Explain the natural greenhouse effect : Explain the natural greenhouse effect and why it is important to our planet. How many degrees would earth be different without the Greehouse effect?
Discuss usefulness of data provided for financial analysis : [Differences between U.S. (MAP and Swedish GAAP-statement of cash flows] Holmen's consolidated cash flow statements are based on Swedish accounting standards.
What is salesman best plan if he wants to minimize time : What's salesman best plan, if he wants to minimize time? 2. What's his best plan if he wants to minimize cost?
Identifying components of a biblical worldview : Defining the term worldview; and identifying components of a biblical/Christian worldview.
Explain the differences of MIS systems and KMS systems : Explain the differences and focus of MIS systems and KMS systems. Research online, present a specific company that most benefits from each type of system
The opportunity to apply ethical theories : The purpose of this discussion is to give you the opportunity to apply ethical theories and perspectives to modern issues of the workplace.
Discuss the primary advantages of GUI : Describe two (2) linux desktop environments and explain how they generally function

Reviews

Write a Review

 

Engineering Mathematics Questions & Answers

  Prime number theorem

Dirichlet series

  Proof of bolzano-weierstrass to prove the intermediate value

Every convergent sequence contains either an increasing, or a decreasing subsequence.

  Antisymmetric relations

How many relations on A are both symmetric and antisymmetric?

  Distributed random variables

Daily Airlines fies from Amsterdam to London every day. The price of a ticket for this extremely popular flight route is $75. The aircraft has a passenger capacity of 150.

  Prepare a system of equations

How much money will Dave and Jane raise for charity

  Managing ashland multicomm services

This question is asking you to compare the likelihood of your getting 4 or more subscribers in a sample of 50 when the probability of a subscription has risen from 0.02 to 0.06.]  Talk about the comparison of probabilities in your explanation.

  Skew-symmetric matrices

Skew-symmetric matrices

  Type of taxes and rates in spokane wa

Describe the different type of taxes and their rates in Spokane WA.

  Stratified random sample

Suppose that in the four player game, the person who rolls the smallest number pays $5.00 to the person who rolls the largest number. Calculate each player's expected gain after one round.

  Find the probability density function

Find the probability density function.

  Develop a new linear programming for an aggregate production

Linear programming applied to Aggregate Production Planning of Flat Screen Monitor

  Discrete-time model for an economy

Discrete-time model for an economy

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd