Автор работы: Пользователь скрыл имя, 13 Мая 2013 в 09:38, курсовая работа
На цьому етапі ми перебираємо усі вузли на роль початого вузла, з якого починається маршрут, і визначаємо довжину кожного маршруту. Потім обираємо найоптимальніший (найменший) маршрут та знаходимо для нього показник ефективності. Для кожної програми ми обираємо свій начальний вузол, з якого починається найоптимальніший маршрут.
1 ФОРМУВАННЯ ВХІДНИХ ДАНИХ 4
1.1. Генерація загальних обсягів замовлень для трьох можливих програм загальних вантажних перевезень F1, F2, F3 4
1.2. Генерація замовлень вантажу в кожному з вузлів (чіткі значення) 4
2 ФОРМУВАННЯ СИМЕТРИЧНОЇ МАТРИЦІ ВІДСТАНЕЙ МІЖ ЗАДАНИМИ ВУЗЛАМИ. 7
3 ФОРМУВАННЯ ПОСЛІДОВНОСТІ ОБХОДУ (ЗАДАЧА TSP – TRAVELING SALESMAN PROBLEM АБО ЗАДАЧА КОМІВОЯЖЕРА) НА ОСНОВІ SAVING-АЛГОРИТМУ 10
3.1 Формування saving-таблиці відстаней 10
3.2 Графічна візуалізація гамільтонового циклу сформованого за saving-алгоритмом 13
4 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ SAVING-АЛГОРИТМУ 14
5 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ МОДИФІКОВАННОГО SAVING-АЛГОРИТМУ 19
5.1 Програма F1 20
5.2 Програма F2 21
5.3 Програма F3 22
6 Формування послідовності обходу вузлів (задача tsp-комівояжера) на основі sweeping-алгоритму 24
6.1 Графічна візуалізація відповідного Гамільтонового циклу. 24
7 ФОРМУВАННЯ МАРШРУТІВ ТРАНСПОРТНИХ ЗАСОБІВ НА ОСНОВІ SWEEPING-АЛГОРИТМУ 25
7.1 Програма F1 26
7.2 Програма F2 27
Продовження таблиці 5. Симетрична матриця відстаней між заданими вузлами
№ вузла |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
3 |
46,0651 |
9 |
12,0415 |
16,2788 |
41,1096 |
54,6443 |
39,4081 |
32,3882 |
19,7230 |
14,1421 |
19,4164 |
20,0249 |
35,7351 |
4 |
27,0185 |
25,6320 |
12,0415 |
37,6430 |
17,2626 |
37,4432 |
32,0156 |
37,2155 |
38,0131 |
38,0525 |
33,8378 |
4,1231 |
14,8660 |
5 |
8,0622 |
37,5765 |
32,5576 |
58,4123 |
28,8617 |
12,5299 |
13,0384 |
29,8328 |
44,7213 |
53,2259 |
58,1377 |
29,5296 |
14 |
6 |
30,6757 |
12,1655 |
10 |
32,5576 |
32,2024 |
38,5875 |
23,7065 |
22,1359 |
22,8035 |
27,5136 |
34 |
14,4222 |
22 |
7 |
28,6356 |
32,2024 |
18,0277 |
41,4366 |
12,1655 |
39,3954 |
37,4833 |
44,1021 |
44,7772 |
43,5660 |
35,8468 |
9,8488 |
16,7630 |
8 |
22,1359 |
35,1710 |
22,0227 |
47,2969 |
7,6157 |
32,8937 |
33,8378 |
43,1856 |
47,1699 |
48,0416 |
42,4852 |
14,0356 |
11 |
9 |
50,2095 |
23,5372 |
16,5529 |
17,2626 |
37,6430 |
60,2079 |
49,3963 |
46 |
34,4383 |
24,8394 |
10,2956 |
19,8494 |
38,2883 |
10 |
47,4130 |
35,5105 |
23,0867 |
32,5729 |
28,4253 |
58,1377 |
53,1507 |
54,8178 |
47,8016 |
40,2243 |
23,0867 |
20,0249 |
35,3411 |
11 |
41,5932 |
44,6878 |
30,4138 |
46,8721 |
18,3847 |
52,1727 |
53,1507 |
59,5399 |
57,4891 |
52,8015 |
38,0131 |
23,6008 |
31 |
12 |
38,1837 |
20,5182 |
7,2801 |
26,4764 |
27,1661 |
48,2700 |
39,0512 |
39,0512 |
33,2415 |
29,1204 |
22,2036 |
7,8102 |
26,2488 |
13 |
11 |
41,0121 |
30,3644 |
57,0087 |
13 |
21,3775 |
28,4253 |
42,1900 |
51,4781 |
55,5787 |
53,5350 |
23,7065 |
7,0710 |
14 |
33 |
46,0651 |
31,7804 |
53,0094 |
9 |
43,1856 |
47,5394 |
56,8506 |
58,6685 |
56,7538 |
45,5411 |
23,7065 |
24,0416 |
15 |
0 |
42,7200 |
35,2278 |
61,9112 |
24 |
10,7703 |
21,0950 |
37,6430 |
51,1566 |
58,1893 |
60,2079 |
30,4138 |
12,2065 |
16 |
42,7200 |
0 |
14,4222 |
23,3238 |
42,7200 |
50,0899 |
32,5269 |
23,5372 |
12,8062 |
15,6524 |
28,2842 |
22,3606 |
34,0587 |
17 |
35,2278 |
14,4222 |
0 |
26,8328 |
29,2745 |
44,5982 |
32,8937 |
31,7804 |
27,2029 |
26,0192 |
25,6124 |
8,2462 |
24,1660 |
18 |
61,9112 |
23,3238 |
26,8328 |
0 |
53,6003 |
70,8025 |
55,4436 |
46,2385 |
28,0713 |
13,1529 |
11,3137 |
33,5261 |
50,9901 |
19 |
24 |
42,7200 |
29,2745 |
53,6003 |
0 |
34,2344 |
39,3573 |
50,2095 |
54,7813 |
55,2268 |
47,7598 |
21,0950 |
15,6524 |
20 |
10,7703 |
50,0899 |
44,5982 |
70,8025 |
34,2344 |
0 |
22,0227 |
40,0124 |
56,7538 |
65,7419 |
70,0071 |
40,6078 |
22,8254 |
21 |
21,0950 |
32,5269 |
32,8937 |
55,4436 |
39,3573 |
22,0227 |
0 |
18 |
36,2491 |
47,6340 |
57,7061 |
33,1360 |
23,7065 |
22 |
37,6430 |
23,5372 |
31,7804 |
46,2385 |
50,2095 |
40,0124 |
18 |
0 |
21,2132 |
35,5105 |
51,7880 |
36,2491 |
35,8050 |
23 |
51,1566 |
12,8062 |
27,2029 |
28,0713 |
54,7813 |
56,7538 |
36,2491 |
21,2132 |
0 |
15,5241 |
36,4965 |
34,9857 |
44,4072 |
24 |
58,1893 |
15,6524 |
26,0192 |
13,1529 |
55,2268 |
65,7419 |
47,6340 |
35,5105 |
15,5241 |
0 |
23,2594 |
34,1320 |
48,8364 |
25 |
60,2079 |
28,2842 |
25,6124 |
11,3137 |
47,7598 |
70,0071 |
57,7061 |
51,7880 |
36,4965 |
23,2594 |
0 |
30 |
48,4148 |
26 |
30,4138 |
22,3606 |
8,2462 |
33,5261 |
21,0950 |
40,6078 |
33,1360 |
36,2491 |
34,9857 |
34,1320 |
30 |
0 |
18,4390 |
27 |
12,2065 |
34,0587 |
24,1660 |
50,9901 |
15,6524 |
22,8254 |
23,7065 |
35,8050 |
44,4072 |
48,8364 |
48,4148 |
18,4390 |
0 |
На рис. 1 зображено графічну візуалізацію простору вузлів з їх відповідною нумерацією.
Рис. 1. Графічна візуалізація простору вузлів з їх відповідною нумерацією
Формування послідовності обходу вузлів (задача TSP = Traveling Salesman Problem або задача комівояжера) відбувається за допомогою saving-алгоритму, в основу якого покладено формування saving-таблиці відстаней
Пари
вузлів в saving-таблиці відстаней
В таблиці 6 наведена сформована saving-таблиця відстаней
№ |
Вузли |
Sij |
№ |
Вузли |
Sij |
№ |
Вузли |
Sij | |||||
1 |
16 |
23 |
56,8134 |
20 |
16 |
21 |
38,1989 |
39 |
8 |
12 |
30,0331 | ||
2 |
16 |
22 |
54,8687 |
21 |
14 |
21 |
37,9949 |
40 |
6 |
12 |
29,7218 | ||
3 |
13 |
18 |
53,2022 |
22 |
11 |
18 |
37,9530 |
41 |
1 |
7 |
28,3817 | ||
4 |
3 |
18 |
49,2396 |
23 |
14 |
22 |
36,9001 |
42 |
11 |
12 |
28,3639 | ||
5 |
21 |
22 |
48,9966 |
24 |
8 |
23 |
36,1547 |
43 |
8 |
16 |
28,3125 | ||
6 |
7 |
23 |
46,5468 |
25 |
9 |
17 |
34,1794 |
44 |
21 |
23 |
28,1297 | ||
7 |
9 |
12 |
46,3275 |
26 |
7 |
8 |
33,9484 |
45 |
5 |
12 |
28,0526 | ||
8 |
3 |
13 |
44,1407 |
27 |
1 |
23 |
33,4719 |
46 |
20 |
22 |
28,0393 | ||
9 |
22 |
23 |
43,1182 |
28 |
13 |
19 |
33,4026 |
47 |
5 |
9 |
27,4855 | ||
10 |
12 |
17 |
42,2123 |
29 |
11 |
17 |
32,9704 |
48 |
18 |
20 |
27,1709 | ||
11 |
18 |
19 |
42,0415 |
30 |
7 |
22 |
31,8974 |
49 |
3 |
25 |
27,1555 | ||
12 |
7 |
16 |
41,2237 |
31 |
11 |
25 |
31,6455 |
50 |
13 |
17 |
26,6123 | ||
13 |
20 |
21 |
40,5853 |
32 |
6 |
17 |
31,6050 |
51 |
14 |
20 |
26,2931 | ||
14 |
8 |
9 |
40,1215 |
33 |
1 |
21 |
31,3085 |
52 |
6 |
11 |
26,1659 | ||
15 |
19 |
20 |
39,7085 |
34 |
13 |
25 |
31,1519 |
53 |
17 |
18 |
25,9445 | ||
16 |
3 |
19 |
39,2563 |
35 |
3 |
11 |
31,0081 |
54 |
3 |
20 |
25,5809 | ||
17 |
11 |
13 |
38,7640 |
36 |
14 |
16 |
30,9782 |
55 |
5 |
17 |
25,3860 | ||
18 |
1 |
22 |
38,6408 |
37 |
18 |
25 |
30,0996 |
56 |
6 |
9 |
24,9661 | ||
19 |
1 |
16 |
38,2536 |
38 |
1 |
14 |
30,0634 |
57 |
9 |
23 |
24,3831 | ||
№ |
Вузли |
Sij |
№ |
Вузли |
Sij |
№ |
Вузли |
Sij | |||||
58 |
14 |
23 |
24,3738 |
100 |
7 |
12 |
15,3482 |
142 |
10 |
21 |
10,2262 | ||
59 |
17 |
25 |
23,9124 |
101 |
15 |
22 |
15,1791 |
143 |
12 |
24 |
10,1791 | ||
60 |
7 |
10 |
23,6423 |
102 |
3 |
12 |
15,1465 |
144 |
2 |
11 |
9,9090 | ||
61 |
7 |
9 |
23,1414 |
103 |
7 |
15 |
15,1102 |
145 |
8 |
14 |
9,9059 | ||
62 |
10 |
23 |
23,1210 |
104 |
4 |
22 |
14,8420 |
146 |
7 |
24 |
9,8342 | ||
63 |
5 |
6 |
22,8825 |
105 |
9 |
13 |
14,7644 |
147 |
12 |
16 |
9,6790 | ||
64 |
19 |
21 |
22,4303 |
106 |
9 |
25 |
14,3103 |
148 |
8 |
21 |
9,5830 | ||
65 |
8 |
10 |
22,2717 |
107 |
14 |
19 |
14,1843 |
149 |
9 |
22 |
9,4893 | ||
66 |
12 |
13 |
22,0058 |
108 |
2 |
5 |
14,1421 |
150 |
7 |
17 |
9,3672 | ||
67 |
11 |
19 |
21,4304 |
109 |
2 |
12 |
14,0653 |
151 |
1 |
9 |
9,3555 | ||
68 |
12 |
18 |
21,3868 |
110 |
2 |
9 |
13,8651 |
152 |
23 |
24 |
9,3243 | ||
69 |
5 |
8 |
21,2742 |
111 |
9 |
18 |
13,7515 |
153 |
6 |
19 |
9,2682 | ||
70 |
8 |
17 |
20,9841 |
112 |
5 |
25 |
13,5346 |
154 |
3 |
9 |
9,1548 | ||
71 |
6 |
25 |
20,9669 |
113 |
2 |
17 |
13,2178 |
155 |
2 |
24 |
9,0307 | ||
72 |
9 |
11 |
20,9099 |
114 |
14 |
15 |
13,0565 |
156 |
17 |
23 |
8,8911 | ||
73 |
6 |
13 |
20,8784 |
115 |
2 |
6 |
12,8825 |
157 |
3 |
5 |
8,7283 | ||
74 |
7 |
21 |
20,5472 |
116 |
10 |
15 |
12,8652 |
158 |
4 |
23 |
8,4611 | ||
75 |
10 |
16 |
20,4922 |
117 |
4 |
19 |
12,8077 |
159 |
17 |
24 |
8,3971 | ||
76 |
13 |
20 |
19,9737 |
118 |
19 |
22 |
12,7967 |
160 |
2 |
25 |
8,3605 | ||
77 |
12 |
25 |
19,9167 |
119 |
5 |
13 |
12,7094 |
161 |
10 |
17 |
8,3263 | ||
78 |
19 |
25 |
19,7436 |
120 |
1 |
4 |
12,5876 |
162 |
3 |
4 |
8,1427 | ||
79 |
6 |
18 |
19,6872 |
121 |
15 |
21 |
12,2440 |
163 |
7 |
20 |
8,0147 | ||
80 |
3 |
17 |
19,5477 |
122 |
10 |
12 |
12,2273 |
164 |
6 |
24 |
7,8585 | ||
81 |
7 |
14 |
19,4801 |
123 |
5 |
7 |
12,1110 |
165 |
5 |
16 |
7,5910 | ||
82 |
16 |
20 |
19,0608 |
124 |
8 |
24 |
12,0578 |
166 |
12 |
19 |
7,5581 | ||
83 |
8 |
22 |
18,9117 |
125 |
20 |
23 |
11,8673 |
167 |
1 |
19 |
7,5334 | ||
84 |
4 |
21 |
17,8007 |
126 |
3 |
21 |
11,6634 |
168 |
2 |
10 |
7,4922 | ||
85 |
1 |
20 |
17,6724 |
127 |
9 |
24 |
11,6367 |
169 |
16 |
24 |
7,4422 | ||
86 |
4 |
20 |
17,4974 |
128 |
4 |
16 |
11,5474 |
170 |
13 |
21 |
7,4310 | ||
87 |
5 |
11 |
17,4938 |
129 |
5 |
23 |
11,5368 |
171 |
4 |
18 |
7,4015 | ||
88 |
1 |
8 |
17,3273 |
130 |
5 |
18 |
11,5163 |
172 |
4 |
15 |
7,2818 | ||
89 |
9 |
16 |
17,1681 |
131 |
2 |
8 |
11,4840 |
173 |
2 |
13 |
7,2555 | ||
90 |
9 |
10 |
16,8247 |
132 |
18 |
21 |
11,4004 |
174 |
6 |
7 |
7,2098 | ||
91 |
1 |
10 |
16,4984 |
133 |
17 |
19 |
11,3468 |
175 |
2 |
7 |
7,0711 | ||
92 |
4 |
14 |
16,4705 |
134 |
5 |
10 |
11,1919 |
176 |
6 |
10 |
7,0138 | ||
93 |
15 |
16 |
16,1150 |
135 |
10 |
14 |
10,9812 |
177 |
4 |
7 |
6,8589 | ||
94 |
10 |
22 |
16,0987 |
136 |
8 |
15 |
10,9755 |
178 |
3 |
14 |
6,8399 | ||
95 |
6 |
8 |
16,0044 |
137 |
11 |
20 |
10,7848 |
179 |
8 |
25 |
6,8143 | ||
96 |
3 |
6 |
15,8114 |
138 |
20 |
25 |
10,7643 |
180 |
9 |
15 |
6,8032 | ||
97 |
15 |
23 |
15,6913 |
139 |
8 |
11 |
10,5479 |
181 |
16 |
19 |
6,7366 | ||
98 |
1 |
15 |
15,6675 |
140 |
5 |
24 |
10,3760 |
182 |
15 |
20 |
6,6956 | ||
99 |
12 |
23 |
15,5032 |
141 |
10 |
24 |
10,3556 |
183 |
6 |
23 |
6,5676 | ||
№ |
Вузли |
Sij |
№ |
Вузли |
Sij |
№ |
Вузли |
Sij | |||||
184 |
2 |
23 |
6,4748 |
226 |
3 |
8 |
2,6161 |
268 |
2 |
21 |
0,4426 | ||
185 |
2 |
18 |
6,3973 |
227 |
21 |
24 |
2,4818 |
269 |
11 |
16 |
0,4378 | ||
186 |
14 |
18 |
6,0961 |
228 |
11 |
21 |
2,4676 |
270 |
4 |
6 |
0,4342 | ||
187 |
15 |
24 |
5,8988 |
229 |
15 |
19 |
2,4632 |
271 |
4 |
17 |
0,4265 | ||
188 |
8 |
13 |
5,7899 |
230 |
4 |
8 |
2,4629 |
272 |
4 |
9 |
0,3611 | ||
189 |
4 |
13 |
5,7468 |
231 |
1 |
3 |
2,4450 |
273 |
10 |
19 |
0,3265 | ||
190 |
1 |
24 |
5,7047 |
232 |
2 |
19 |
2,3501 |
274 |
2 |
20 |
0,2693 | ||
191 |
2 |
3 |
5,1452 |
233 |
11 |
23 |
2,2675 |
275 |
11 |
15 |
0,2588 | ||
192 |
22 |
24 |
5,0867 |
234 |
18 |
24 |
2,2444 |
276 |
20 |
24 |
0,2474 | ||
193 |
11 |
24 |
4,9373 |
235 |
15 |
17 |
2,1971 |
277 |
19 |
24 |
0,2414 | ||
194 |
3 |
22 |
4,9101 |
236 |
2 |
22 |
2,1546 |
278 |
13 |
23 |
0,2365 | ||
195 |
1 |
12 |
4,7297 |
237 |
13 |
22 |
2,1497 |
279 |
15 |
18 |
0,2336 | ||
196 |
16 |
17 |
4,6946 |
238 |
10 |
25 |
1,9897 |
280 |
3 |
10 |
0,1913 | ||
197 |
8 |
18 |
4,6318 |
239 |
1 |
17 |
1,9467 |
281 |
13 |
16 |
0,1772 | ||
198 |
1 |
5 |
4,3611 |
240 |
6 |
15 |
1,8509 |
282 |
7 |
18 |
0,1624 | ||
199 |
2 |
16 |
4,3135 |
241 |
1 |
18 |
1,7721 |
283 |
8 |
19 |
0,1440 | ||
200 |
4 |
10 |
4,1853 |
242 |
8 |
20 |
1,5959 |
284 |
11 |
22 |
0,1183 | ||
201 |
12 |
22 |
4,1851 |
243 |
3 |
24 |
1,5531 |
285 |
14 |
17 |
0,1059 | ||
202 |
5 |
15 |
4,1766 |
244 |
14 |
25 |
1,5132 |
286 |
3 |
23 |
0,1038 | ||
203 |
18 |
22 |
4,1637 |
245 |
7 |
19 |
1,4992 |
287 |
1 |
25 |
0,0672 | ||
204 |
12 |
15 |
4,0846 |
246 |
3 |
16 |
1,4732 |
288 |
6 |
14 |
0,0569 | ||
205 |
5 |
19 |
3,9535 |
247 |
7 |
25 |
1,4680 |
289 |
15 |
25 |
0,0517 | ||
206 |
13 |
14 |
3,8994 |
248 |
1 |
6 |
1,4583 |
290 |
16 |
25 |
0,0508 | ||
207 |
9 |
14 |
3,8834 |
249 |
12 |
20 |
1,3660 |
291 |
13 |
15 |
0,0374 | ||
208 |
24 |
25 |
3,7992 |
250 |
5 |
14 |
1,3561 |
292 |
9 |
20 |
0,0287 | ||
209 |
5 |
22 |
3,7122 |
251 |
17 |
22 |
1,3187 |
293 |
6 |
21 |
0,0262 | ||
210 |
17 |
20 |
3,6137 |
252 |
12 |
14 |
1,1542 |
294 |
4 |
5 |
0,0164 | ||
211 |
10 |
20 |
3,4456 |
253 |
10 |
13 |
1,1022 |
295 |
17 |
21 |
0,0127 | ||
212 |
6 |
16 |
3,4000 |
254 |
23 |
25 |
0,9822 |
296 |
2 |
4 |
0,0118 | ||
213 |
4 |
25 |
3,3750 |
255 |
11 |
14 |
0,9653 |
297 |
4 |
12 |
0,0089 | ||
214 |
9 |
19 |
3,2987 |
256 |
6 |
22 |
0,9058 |
298 |
1 |
11 |
0,0060 | ||
215 |
10 |
11 |
3,2594 |
257 |
4 |
24 |
0,8801 |
299 |
18 |
23 |
0,0040 | ||
216 |
14 |
24 |
3,1386 |
258 |
2 |
14 |
0,8555 |
300 |
3 |
7 |
0,0004 | ||
217 |
21 |
25 |
3,1330 |
259 |
16 |
18 |
0,8525 |
||||||
218 |
2 |
15 |
3,0917 |
260 |
1 |
13 |
0,7847 |
||||||
219 |
9 |
21 |
3,0503 |
261 |
5 |
21 |
0,7496 |
||||||
220 |
6 |
20 |
3,0396 |
262 |
7 |
13 |
0,5942 |
||||||
221 |
7 |
11 |
2,8953 |
263 |
10 |
18 |
0,5825 |
||||||
222 |
13 |
24 |
2,8719 |
264 |
12 |
21 |
0,5190 |
||||||
223 |
19 |
23 |
2,8301 |
265 |
3 |
15 |
0,5046 |
||||||
224 |
4 |
11 |
2,7633 |
266 |
22 |
25 |
0,4551 |
||||||
225 |
1 |
2 |
2,7180 |
267 |
5 |
20 |
0,4538 |
||||||
На рис. 2 зображений відповідний Гамільтонів цикл
Рис. 2 Гамільтонів цикл
На даному етапі відбувається формування маршрутів транспортних засобів з вантажомісткістю Dmax на основі saving-алгоритму наступним чином. Потрібно визначити загальну кількість маршрутів R, що відповідає необхідній кількості транспортних засобів, довжину кожного маршруту Lr, r=1,...,R, кількість перевезеного вантажу та залишкову кількості вантажу DDr=Dmax- на кожному з маршрутів, сумарну довжину всіх маршрутів LS=r , та при повній реалізації кожної з програм F1, F2, F3 а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:
4.1. Програма F1
В табл. 7 занесена інформація про маршрути транспортних перевезень для програми F1.
Таблиця 7. Маршрути транспортних перевезень для програми F1.
R |
Номери вузлів, що входять в маршрут |
Lr |
||
|
1 |
0-23-16-22-21-20-0 |
124,8594 |
1,9545 |
0,0455 |
2 |
0-19-18-13-0 |
87,2907 |
1,9901 |
0,0099 |
3 |
0-3-11-17-12-9-0 |
103,3379 |
1,6507 |
0,3493 |
4 |
0-8-7-1-14-4-15-0 |
95,7463 |
1,8259 |
0,1741 |
5 |
0-10-5-6-0 |
49,9988 |
1,7238 |
0,2762 |
6 |
0-25-2-24-0 |
41,2274 |
0,7877 |
1,2123 |
502,4605 |
Показник ефективності: E1 = 0,9773.
Рис. 3. Маршрути транспортних перевезень для програми F1.
4.2. Програма F2
В табл. 8. занесена інформація про маршрути транспортних перевезень для програми F2.
Таблиця 8. Маршрути транспортних перевезень для програми .
R |
Номери вузлів, що входять в маршрут |
Lr |
||
|
1 |
0-23-16-22-21-20-19-0 |
139,7403 |
1,8531 |
0,1469 |
2 |
0-18-13-3-11-17-0 |
108,5645 |
1,6070 |
0,3930 |
3 |
0-12-9-8-7-1-14-4-15-0 |
123,2126 |
1,7903 |
0,2097 |
4 |
0-10-5-6-25-2-24-0 |
70,2593 |
1,7770 |
0,2230 |
441,7767 |
Показник ефективності: E2 = 0,9266.
Рис. 4. Маршрути транспортних перевезень для програми F2.
4.3. Програма F3
В табл. 9. занесена інформація про маршрути транспортних перевезень для програми F3.
Таблиця 9. Маршрути транспортних перевезень для програми F3.
R |
Номери вузлів, що входять в маршрут |
Lr |
||
|
1 |
0-23-16-22-21-0 |
104,6171 |
1,7638 |
0,2362 |
2 |
0-20-19-18-0 |
107,2061 |
1,5796 |
0,4204 |
3 |
0-13-3-11-17-0 |
88,2275 |
1,6968 |
0,3032 |
4 |
0-12-9-8-7-1-0 |
103,6317 |
1,9054 |
0,0946 |
5 |
0-14-4-15-10-5-0 |
78,0376 |
1,8482 |
0,1518 |
6 |
0-6-25-2-24-0 |
51,8833 |
1,4425 |
0,5575 |
533,6033 |
Показник ефективності: E3 = 0,8819.
Рис. 5. Маршрути транспортних перевезень для програми F3.
Рис. 6 Залежність
Даний алгоритм при визначенні першого вузла на маршруті починає з найвищої пари вузлів, які ще не включені в маршрути, а першим вузлом в такій парі виступає вузол, який в saving-таблиці відстаней зустрічається першим. Алгоритм виконується наступним чином. Визначається загальна кількість маршрутів R, що відповідає необхідній кількості транспортних засобів, довжини кожного маршруту Lr, r=1,…R, кількість перевезеного вантажу та залишкова кількість вантажу DDr=Dmax- на кожному з маршрутів, сумарна довжина всіх маршрутів LS=r , та при повній реалізації кожної з програм F1, F2, F3, а також показник ефективності завантаження транспортних засобів E при реалізації кожної програми, що визначається за формулою:
В табл. 10 занесена інформація про маршрути транспортних перевезень для програми F1.
Таблиця10. Маршрути транспортних перевезень для програми F1.
R |
Номери вузлів, що входять в маршрут |
Lr |
||
|
1 |
0-23-16-22-21-20-0 |
124,8594 |
1,9545 |
0,0455 |
2 |
0-13-18-3-0 |
75,5032 |
1,3660 |
0,6340 |
3 |
0-9-12-17-11-0 |
84,3459 |
1,6100 |
0,3900 |
4 |
0-8-7-1-14-4-0 |
86,9036 |
1,3945 |
0,6055 |
5 |
0-5-6-25-0 |
48,3687 |
1,7763 |
0,2237 |
6 |
0-15-10-24-2-19-0 |
86,5860 |
1,8314 |
0,1686 |
506,5669 |
Показник ефективності: E1 = 0,9773.
Рис. 7. Маршрути транспортних перевезень для програми F1.