Numericals on Travelling Salesman Assignment Model


0

(Travelling Salesman)

1.         A salesman has to visit five different cities. The distance (in km) between the cities is given below. Find the sequence of the visit to these cities so that the distance he travels is minimum without visiting city more than once.

    To  

Cities

From

1

2

3

4

5

1

70

60

80

40

2

70

80

50

60

3

60

80

90

70

4

80

50

90

70

5

40

60

70

80

            (Ans. :  1 ® 5 ®  2 ® 4 ® 3 ®1 or 3 ® 4 ® 2 ® 5 ®1 are feasible routes which             give the same (300 kms) distance traveled. The salesman can take either     of these two routes.)

 

2.         A bread distribution Van of Santosh Bakery has to supply bread at different outlets. A, B and C in the morning. It collects the bread from Bakery and distributes to outlets A, B and C only once in the mornings. The van has to visit outlets A, B and C only once in the mornings. The van has to visit outlets once only and all the outlets have to be supplied with morning fresh bread. The distances of the outlets A, B and C from the Bakery is given in the following table. The van starts from Bakery and has to come back to the Bakery after visiting each outlet only once. Which route should be selected by the Van so that the total distance traveled by it is minimized. What is the total distance traveled by the Van ?

Find the alternate route, if any.

   

From

To

Bakery

Outlet A

Outlet B

Outlet C

Bakery

4

7

3

Outlet A

4

6

3

Outlet B

7

6

7

Outlet C

3

3

7

            (Ans. :    BK ®  B ® A ® C ® BK

It has total distance of 7 + 6 + 3 + 3 = 19

There is also an alternate route

BK ® C ® A ® B ® BK

With a total distance 3 + 3 + 6 + 7 = 19.

These two routes are optimal.


Like it? Share with your friends!

0
MT UVA BMS

MT UVA- University, Vocational and Affiliated Education for BMS

216 Comments


Warning: Undefined array key "html5" in /home/bmsnewco/public_html/wp-content/plugins/facebook-comments-plugin/class-frontend.php on line 140

Facebook comments:

This Website Is For Sale. Email us an offer we cannot refuse on [email protected] :)

X
Choose A Format
Personality quiz
Series of questions that intends to reveal something about the personality
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Poll
Voting to make decisions or determine opinions
Story
Formatted Text with Embeds and Visuals
List
The Classic Internet Listicles
Countdown
The Classic Internet Countdowns
Open List
Submit your own item and vote up for the best submission
Ranked List
Upvote or downvote to decide the best list item
Meme
Upload your own images to make custom memes
Video
Youtube and Vimeo Embeds
Audio
Soundcloud or Mixcloud Embeds
Image
Photo or GIF
Gif
GIF format