|
Numer |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Ładowność środka transportu: 13 palet |
|
Numer |
Nazwa miasta |
Radom |
Grójec |
Kozienice |
Pionki |
Puławy |
Ostrowiec Świętokrzyski |
Skarżysko-Kamienna |
Rawa Mazowiecka |
Piotrków Trybunalski |
Tomaszów Mazowiecki |
Kielce |
|
|
0 |
Radom |
0 |
55 |
35 |
23 |
60 |
61 |
39 |
77 |
101 |
82 |
72 |
zapotrzebowanie |
|
1 |
Grójec |
0 |
0 |
67 |
75 |
111 |
115 |
90 |
43 |
99 |
74 |
124 |
4 |
15 |
2 |
Kozienice |
0 |
23 |
0 |
16 |
35 |
90 |
74 |
110 |
136 |
120 |
107 |
6 |
6 |
3 |
Pionki |
0 |
3 |
42 |
0 |
40 |
81 |
63 |
116 |
126 |
106 |
96 |
3 |
24 |
4 |
Puławy |
0 |
4 |
60 |
43 |
0 |
93 |
99 |
137 |
161 |
143 |
132 |
11 |
14 |
5 |
Ostrowiec Świętokrzyski |
0 |
1 |
6 |
3 |
26 |
0 |
46 |
137 |
137 |
142 |
57 |
10 |
10 |
6 |
Skarżysko-Kamienna |
0 |
4 |
0 |
0 |
0 |
54 |
0 |
96 |
93 |
89 |
33 |
5 |
13 |
7 |
Rawa Mazowiecka |
0 |
83 |
0 |
0 |
0 |
0 |
14 |
0 |
55 |
30 |
115 |
8 |
8 |
8 |
Piotrków Trybunalski |
0 |
57 |
0 |
0 |
0 |
25 |
47 |
123 |
0 |
26 |
90 |
4 |
15 |
9 |
Tomaszów Mazowiecki |
0 |
63 |
0 |
0 |
0 |
1 |
32 |
129 |
157 |
0 |
92 |
10 |
10 |
10 |
Kielce |
0 |
3 |
0 |
0 |
0 |
76 |
78 |
34 |
83 |
62 |
0 |
8 |
8 |
Zadanie:
Dokonać minimalizacji liczby tras między Radomiem i okolicznymi miastami (i tym samym środków transportu).
Tabela 1
Założenia:
Z bazy (Radom) regularnie przewożone są ładunki do punktów odbioru. Znany jest środek transportu, którym dysponuje przewoźnik (tutaj jest to samochód z 1 kierowcą, o ładowności 13 europalet, poruszający się z prędkością średnią 65 km/h) oraz wielkość przewozu (zapotrzebowanie - w europaletach, ostatnia kolumna tab. 1). Znane są czasy przejazdu pomiędzy poszczególnymi miastami ( Tabela 1 na białym tle, na szarym tle poniżej głównej przekątnej zysk czasu wynikający z łączenia tras). Czas pracy kierowcy wynosi 180 minut.
Rozwiązanie:
Tabela 2. Potencjalne połączenia tras w kolejności od największego zysku czasowego do najmniejszego.
d98 |
d97 |
d87 |
d71,d108 |
d106 |
d105 |
d91 |
d109 |
|||
157 |
129 |
123 |
83 |
78 |
76 |
263 |
62 |
|||
d42 |
d81 |
d65 |
d86 |
d43 |
d32 |
d107 |
d96 |
|||
60 |
57 |
54 |
47 |
43 |
42 |
34 |
32 |
|||
d54 |
d85 |
d21 |
d76 |
d52 |
d41,d61 |
d101,d31,d53 |
d95,d51 |
|||
26 |
25 |
23 |
14 |
6 |
4 |
3 |
1 |
|||
W chwili obecnej mamy do obsłużenia następujące trasy: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
Proces łączenia:
1) Rozpatrujemy trasę d98.
Łączne zapotrzebowanie: 10 + 4 = 14 - niespełnione,
czas jazdy (trasa 0-9-8-0): 82 + 26 + 101 = 209 - przekroczony,
2) Rozpatrujemy trasę d97.
Łączne zapotrzebowanie: 10 + 8 = 18 - niespełnione,
czas jazdy (trasa 0-9-7-0): 82 + 30 + 77 = 189 - przekroczony,
3) Rozpatrujemy trasę d87.
Łączne zapotrzebowanie: 8 + 4 = 12 - spełnione,
czas jazdy (trasa 0-8-7-0): 101 + 55 + 77 = 233 - przekroczony,
Tras d98,d97,d87 nie można łączyć, usuwamy je z tabeli 2 otrzymując tabelę 2a.
Tabela 2a.
d71,d108 |
d106 |
d105 |
d91 |
d109 |
d42 |
d81 |
d65 |
d86 |
d43 |
d32 |
d107 |
|
83 |
78 |
76 |
263 |
62 |
60 |
57 |
54 |
47 |
43 |
42 |
34 |
|
d96 |
d54 |
d85 |
d21 |
d76 |
d52 |
d41,d61 |
d101,d31,d53 |
d95,d51 |
||||
32 |
26 |
25 |
23 |
14 |
6 |
4 |
3 |
1 |
||||
W chwili obecnej mamy do obsłużenia następujące trasy: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
4) Rozpatrujemy trasę d71.
Łączne zapotrzebowanie: 8 + 4 = 12 - spełnione,
czas jazdy (trasa 0-7-1-0): 77 + 43 + 55 = 175 - spełnione,
Trasę łączymy usuwając jednocześnie ze zbioru tras trasy 7 i 1 otrzymując zbiór tras: 2, 3, 4, 5, 6, 8, 9, 10, (7,1).
W tabeli 2a sprawdzamy wszystkie (niewykreślone) drogi zawierające 7 lub 1. Jednak w tym przypadku „wolna” ładowność wynosi 1 paletę, a zapotrzebowanie dla każdej z pozostałych tras jest większe niż 1, stąd wynika, że trasy (7,1) nie można połączyć z żadną z nich.
Usuwamy z tabeli 2a wszystkie trasy w których występuje 7 lub 1 otrzymując tabelę 2b.
Tabela 2b.
d108 |
d106 |
d105 |
d109 |
d42 |
d65 |
d86 |
d43 |
|
83 |
78 |
76 |
62 |
60 |
54 |
47 |
43 |
|
d32 |
d96 |
d54 |
d85 |
d52 |
d53 |
d95 |
||
42 |
32 |
26 |
25 |
6 |
3 |
1 |
||
W chwili obecnej mamy do obsłużenia następujące trasy: 2, 3, 4, 5, 6, 8, 9, 10, (7,1).
5) Rozpatrujemy trasę d108.
Łączne zapotrzebowanie: 8 + 4 = 12 - spełnione,
czas jazdy (trasa 0-10-8-0): 72 + 90 + 101 = 263 - przekroczony,
Trasy d108 nie można łączyć, usuwamy ją z tabeli 2b otrzymując tabelę 2c
Tabela 2c.
d106 |
d105 |
d109 |
d42 |
d65 |
d86 |
d43 |
d32 |
d96 |
d54 |
d85 |
d52 |
d53 |
d95 |
78 |
76 |
62 |
60 |
54 |
47 |
43 |
42 |
32 |
26 |
25 |
6 |
3 |
1 |
W chwili obecnej mamy do obsłużenia następujące trasy: 2, 3, 4, 5, 6, 8, 9, 10, (7,1).
6) Rozpatrujemy trasę d106.
Łączne zapotrzebowanie: 8 + 5 = 12 - spełnione,
czas jazdy (trasa 0-10-6-0): 72 + 33 + 39 = 144 - spełnione,
Trasę łączymy usuwając jednocześnie ze zbioru tras trasy 10 i 6 otrzymując zbiór tras: 2,3, 4, 5, 8, 9, (7,1), (10,6).
W tab. 2c sprawdzamy wszystkie (niewykreślone) drogi zawierające 10 lub 6. Jednak w tym przypadku „wolna” ładowność wynosi 1 palety, a zapotrzebowanie dla każdej z pozostałych tras jest większe niż 1, stąd wynika, że trasy (10,6) nie można połączyć z żadną z nich.
Usuwamy z tabeli 2c wszystkie trasy w których występuje 10 lub 6 otrzymując tabelę 2d.
Tab. 2d.
d42 |
d43 |
d32 |
d54 |
d85 |
d52 |
d53 |
d95 |
60 |
43 |
42 |
26 |
25 |
6 |
3 |
1 |
W chwili obecnej mamy do obsłużenia następujące trasy: 2, 3, 4, 5, 8, 9, (7,1), (10,6).
7) Rozpatrujemy trasę d42.
Łączne zapotrzebowanie: 11 + 6 = 17 - niespełnione,
czas jazdy (trasa 0-4-2-0): 60 + 35 + 35 = 130 - spełnione,
8) Rozpatrujemy trasę d43.
Łączne zapotrzebowanie: 11 + 3 = 14 - niespełnione,
czas jazdy (trasa 0-4-3-0): 60 + 40 + 23 = 123 - spełnione,
Tras d42,d43 nie można łączyć, usuwam ją z tab. 2d otrzymując tab. 2e.
Tab. 2e
d32 |
d54 |
d85 |
d52 |
d53 |
d95 |
42 |
26 |
25 |
6 |
3 |
1 |
W chwili obecnej mamy do obsłużenia następujące trasy: 2, 3,4, 5, 8, 9, (7,1), (10,6).
9) Rozpatrujemy trasę d32.
Łączne zapotrzebowanie: 3 + 6 = 14 - spełnione,
czas jazdy (trasa 0-3-2-0): 23 + 16 + 35 = 74 - spełnione,
Trasę łączymy usuwając jednocześnie ze zbioru tras trasy 3 i 2 otrzymując zbiór tras:
4, 5, 8, 9, (7,1), (10,6), (3,2).
Sprawdzam, czy do trasy (3,2) można dołączyć inną trasę. W tab. 2e sprawdzam wszystkie (niewykreślone) drogi zawierające 3 lub 2.
- sprawdzam trasę d52. (0-3-2-5-0)
Łączne zapotrzebowanie: 9 + 10 = 19 - niespełnione,
czas jazdy (trasa 0-5-2-0): 23 + 16 + 90 + 61 = 190 - przekroczone,
- sprawdzam trasę d53. (0-5-3-2-0)
Łączne zapotrzebowanie: 9 + 10 = 19 - przekroczone,
czas jazdy (trasa 0-5-3-0): 61 + 81 + 16 + 35 = 193 - przekroczone,
Trasy d32 nie można łączyć z trasą d52, ani z trasą d53, ponieważ łączne zapotrzebowanie oraz czas jazdy zostały przekroczone w obydwu przypadkach.
Trasy (3,2) nie można już połączyć z żadną inną trasą. Usuwamy z tabeli 2e wszystkie trasy zawierające trasę 3 lub 2 otrzymując tabelę 2f.
Tabela 2f,
d54 |
d85 |
d95 |
26 |
25 |
1 |
W chwili obecnej mamy do obsłużenia następujące trasy: 4, 5, 8, 9, (7,1), (10,6), (3,2).
10) Rozpatrujemy trasę d54.
Łączne zapotrzebowanie: 10 + 11 = 21 - niespełnione,
czas jazdy (trasa 0-5-4-0): 61 + 93 + 60 = 214 - przekroczone,
11) Rozpatrujemy trasę d85.
Łączne zapotrzebowanie: 4 + 10 = 14 - niespełnione,
czas jazdy (trasa 0-8-5-0): 101 + 137 + 61 = 299 - przekroczone,
12) Rozpatrujemy trasę d95.
Łączne zapotrzebowanie: 10 + 10 = 20 - niespełnione,
czas jazdy (trasa 0-9-5-0): 82 + 142 + 61 = 285 - przekroczone,
Ponieważ nie ma już tras do rozpatrywania, proces łączenia został zakończony. Ostateczne wyniki zawiera tabela 3.
Tabela 3.
trasa |
|
|
|
|
|
|
|
(7,1) |
(10,6) |
(3,2) |
czas jazdy |
|
|
|
|
|
|
|
175 |
144 |
74 |
liczba kursów |
|
|
|
|
|
|
|
1 |
1 |
1 |