The Traveling Salesman Problem
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View The Traveling Salesman Problem as PDF for free.
More details
- Words: 665
- Pages: 16
The Traveling Salesman Problem
There are “m” places (nodes) to be visited, each place only once Starting from any place all the places must be visited only once but in any order. The cost of travel or the distance between pairs of places or time required are usually given. The objective is to minimize the total cost, or distance or time
A company executive has to visit five offices each only once starting from any office but has to return to the office from where he started. The distances between the offices are given in the Table. Determine the sequence that results in the lowest
Offic e3
Offic e2
Offic e1
Offic e4 Offic e5
Time of travel between offices Office 1 Office 2 Office 3 Office 4 Office 5 Office 1
-
25
50
50
30
Office 2
25
-
40
40
45
Office 3
50
40
-
35
65
Office 4
50
40
35
-
80
Office 5
30
45
65
80
-
Solving as an assignment problem we get ∞
25 50 50 30
25
∞
50 40
40 40 45
∞
35 65
∞
80
30 45 65 80
∞
50 40 35
∞
0 25 25 5
0
∞
15 15 20
35 5
∞
0 30
15 5
0
∞
45
∞
0 25 25 0
0 15 35 50
∞
0
∞
15 15 15
35 5
∞
0 25
15 5
0
∞
40
0 15 35 50
∞
25
25 50 50 30 -
50 40
40 40 45 -
50 40 35
35 65
- 80
30 45 65 80
Solving as an assignment problem we get
-
25
25 50 50 30 -
50 40
40 40 45 -
50 40 35
35 65
- 80
30 45 65 80
-
25
25 50 50 30 -
50 40
1
5
30
2
1
25
35 65
3
4
35
80
4
3
35
-
5
2
45
40 40 45 -
50 40 35
-
30 45 65 80
Not feasible
Total
170
15 2 1 3 4 3
Feasible 2 1 5 3 4 2 = 195
In a machine shop the set up times are dependent on the job presently on the job and the one coming up next. The set up cost based on this time is given for four jobs in the Table. Obtain the sequence of jobs to minimize the total set up cost. A B C D A B C D
4 7 3
4 6 3
7 6 7
3 3 7 -
A A
∞
B 4
C 7
D 3
B
4
∞
6
3
C
7
6
∞
7
D
3
3
7
∞
Solving as an assignment problem
A A
∞
B 1
C 4
D 0
B
1
∞
3
0
C
1
0
∞
1
D
0
0
4
∞
A A
∞
B 1
C 1
D 0
B
1
∞
0
0
C
1
0
∞
1
D
0
0
1
∞
A
B
C
D 0
0
0
A B C D
0 0
0
A
B
C
D 0
0
0 X
A B C D
0 0
0 X
A
B
C
D 0
0
0 X
A B C D
0 0
0 X
A D A – Not feasible
A
D
B
C
A
Minimum total set up cost =3+3+6+7= 19
A B C D
A
A 4 7 3
B 4 6 3
C
C 7 6 7
B
D 3 3 7 -
D
A B C D
C D B A
Total
A
Minimum total set up cost = 19
7 3 6 3 19
A
A
-
B 16
C 18
D 13
E 20
B C D E
21
-
16
27
14
12
14
-
15
21
11
18
19
-
21
16
14
17
12
-
There are “m” places (nodes) to be visited, each place only once Starting from any place all the places must be visited only once but in any order. The cost of travel or the distance between pairs of places or time required are usually given. The objective is to minimize the total cost, or distance or time
A company executive has to visit five offices each only once starting from any office but has to return to the office from where he started. The distances between the offices are given in the Table. Determine the sequence that results in the lowest
Offic e3
Offic e2
Offic e1
Offic e4 Offic e5
Time of travel between offices Office 1 Office 2 Office 3 Office 4 Office 5 Office 1
-
25
50
50
30
Office 2
25
-
40
40
45
Office 3
50
40
-
35
65
Office 4
50
40
35
-
80
Office 5
30
45
65
80
-
Solving as an assignment problem we get ∞
25 50 50 30
25
∞
50 40
40 40 45
∞
35 65
∞
80
30 45 65 80
∞
50 40 35
∞
0 25 25 5
0
∞
15 15 20
35 5
∞
0 30
15 5
0
∞
45
∞
0 25 25 0
0 15 35 50
∞
0
∞
15 15 15
35 5
∞
0 25
15 5
0
∞
40
0 15 35 50
∞
25
25 50 50 30 -
50 40
40 40 45 -
50 40 35
35 65
- 80
30 45 65 80
Solving as an assignment problem we get
-
25
25 50 50 30 -
50 40
40 40 45 -
50 40 35
35 65
- 80
30 45 65 80
-
25
25 50 50 30 -
50 40
1
5
30
2
1
25
35 65
3
4
35
80
4
3
35
-
5
2
45
40 40 45 -
50 40 35
-
30 45 65 80
Not feasible
Total
170
15 2 1 3 4 3
Feasible 2 1 5 3 4 2 = 195
In a machine shop the set up times are dependent on the job presently on the job and the one coming up next. The set up cost based on this time is given for four jobs in the Table. Obtain the sequence of jobs to minimize the total set up cost. A B C D A B C D
4 7 3
4 6 3
7 6 7
3 3 7 -
A A
∞
B 4
C 7
D 3
B
4
∞
6
3
C
7
6
∞
7
D
3
3
7
∞
Solving as an assignment problem
A A
∞
B 1
C 4
D 0
B
1
∞
3
0
C
1
0
∞
1
D
0
0
4
∞
A A
∞
B 1
C 1
D 0
B
1
∞
0
0
C
1
0
∞
1
D
0
0
1
∞
A
B
C
D 0
0
0
A B C D
0 0
0
A
B
C
D 0
0
0 X
A B C D
0 0
0 X
A
B
C
D 0
0
0 X
A B C D
0 0
0 X
A D A – Not feasible
A
D
B
C
A
Minimum total set up cost =3+3+6+7= 19
A B C D
A
A 4 7 3
B 4 6 3
C
C 7 6 7
B
D 3 3 7 -
D
A B C D
C D B A
Total
A
Minimum total set up cost = 19
7 3 6 3 19
A
A
-
B 16
C 18
D 13
E 20
B C D E
21
-
16
27
14
12
14
-
15
21
11
18
19
-
21
16
14
17
12
-
Related Documents
The Traveling Salesman Problem
June 2020 0
Salesman
April 2020 3
Traveling
November 2019 21
Traveling Nitrogen
April 2020 9
Salesman Cover
November 2019 16
Traveling Brochure
June 2020 11More Documents from "Amy Adams"