1
Problem marszrutyzacji
Problem marszrutyzacji
pojazdów
pojazdów
(
(
Vehicle
Vehicle
Routing
Routing
)
)
Wprowadzenie w problematykę
Wprowadzenie w problematykę
komputerowego wspomagania
komputerowego wspomagania
marszrutyzacji pojazdów z
marszrutyzacji pojazdów z
wykorzystaniem systemu
wykorzystaniem systemu
TransCAD
TransCAD
Klasyczny problem marszrutyzacji
Klasyczny problem marszrutyzacji
pojazdów
pojazdów
Zakładamy istnienie
Zakładamy istnienie
zbioru klientów
zbioru klientów
, których
, których
należy obsłużyć z wykorzystaniem
należy obsłużyć z wykorzystaniem
posiadanych
posiadanych
pojazdów
pojazdów
zlokalizowanych w określonych
zlokalizowanych w określonych
miejscach (bazach, hurtowniach itp.)
miejscach (bazach, hurtowniach itp.)
Celem
Celem
prowadzonej optymalizacji jest
prowadzonej optymalizacji jest
określenie tras przejazdów
określenie tras przejazdów
dla poszczególnych
dla poszczególnych
pojazdów takich aby:
pojazdów takich aby:
•
•
obsłużyć wszystkich
obsłużyć wszystkich
klientów
klientów
•
•
nie przekroczyć
nie przekroczyć
dopuszczalnej
dopuszczalnej
ładowności
ładowności
pojazdów
pojazdów
•
•
zoptymalizować
zoptymalizować
wybrane
wybrane
kryterium
kryterium
(przejechany
(przejechany
dystans, czasy przejazdów, zrównoważenie obciążenia,
dystans, czasy przejazdów, zrównoważenie obciążenia,
średni czas obsługi)
średni czas obsługi)
2
Problem marszrutyzacji pojazdów
Problem marszrutyzacji pojazdów
-
-
ograniczenia
ograniczenia
Istnieje wiele wariantów problemu stąd różne są
Istnieje wiele wariantów problemu stąd różne są
ograniczenia nakładane na proces optymalizacji.
ograniczenia nakładane na proces optymalizacji.
Do typowych ograniczeń można zaliczyć:
Do typowych ograniczeń można zaliczyć:
•
•
Ilość pojazdów
Ilość pojazdów
dostępnych w poszczególnych
dostępnych w poszczególnych
lokalizacjach
lokalizacjach
•
•
Pojemność
Pojemność
pojazdów (wyrażona masą i objętością
pojazdów (wyrażona masą i objętością
ładunków)
ładunków)
•
•
Ograniczenia czasowe
Ograniczenia czasowe
lub
lub
odległościowe
odległościowe
na trasę
na trasę
pojazdu
pojazdu
•
•
Alokacja określonych klientów do określonych pojazdów
Alokacja określonych klientów do określonych pojazdów
(preselekcja klientów do baz, hurtowni itp.)
(preselekcja klientów do baz, hurtowni itp.)
Problem marszrutyzacji pojazdów
Problem marszrutyzacji pojazdów
–
–
rozwinięcia problemu
rozwinięcia problemu
W zastosowaniach praktycznych wykorzystuje się
W zastosowaniach praktycznych wykorzystuje się
najczęściej warianty problemu marszrutyzacji pojazdów
najczęściej warianty problemu marszrutyzacji pojazdów
rozbudowane o:
rozbudowane o:
•
•
Okna czasowe
Okna czasowe
–
–
pozwalają uwzględniać wymagania klientów
pozwalają uwzględniać wymagania klientów
(oczekiwane ramy czasowe kiedy obsługa ma nastąpić) oraz
(oczekiwane ramy czasowe kiedy obsługa ma nastąpić) oraz
dostępność środków transportowych
dostępność środków transportowych
•
•
Dodatkowy,
Dodatkowy,
stały czas obsługi
stały czas obsługi
charakterystyczny dla
charakterystyczny dla
poszczególnych klientów (niezależny od czasu dojazdu)
poszczególnych klientów (niezależny od czasu dojazdu)
•
•
Zmienny czas obsługi
Zmienny czas obsługi
klientów (w ogólności zależny od ilości
klientów (w ogólności zależny od ilości
dowiezionego/wywożonego towaru)
dowiezionego/wywożonego towaru)
•
•
Mieszane tryby dostawy i odbioru
Mieszane tryby dostawy i odbioru
(towaru, opakowań
(towaru, opakowań
zwrotnych itp.)
zwrotnych itp.)
•
•
Otwarte pętle
Otwarte pętle
transportowe (pojazdy nie muszą powracać do
transportowe (pojazdy nie muszą powracać do
baz)
baz)
3
Etapy rozwiązywania problemu
Etapy rozwiązywania problemu
Przygotowanie danych
Przygotowanie danych
wyściowych
wyściowych
(informacje o
(informacje o
lokalizacji klientów i baz transportowych wraz z niezbędnymi
lokalizacji klientów i baz transportowych wraz z niezbędnymi
dla danego typu optymalizacji danymi np. o oknach
dla danego typu optymalizacji danymi np. o oknach
czasowych)
czasowych)
Przygotowanie macierzy kosztów
Przygotowanie macierzy kosztów
definiującej odległości i
definiującej odległości i
czasy przejazdów pomiędzy wszystkimi punktami wyjściowymi
czasy przejazdów pomiędzy wszystkimi punktami wyjściowymi
(bazy, hurtownie
(bazy, hurtownie
–
–
w systemie nazywane
w systemie nazywane
Depots
Depots
) a
) a
wszystkimi punktami odbioru (klienci
wszystkimi punktami odbioru (klienci
–
–
w systemie
w systemie
Stops
Stops
)
)
Przygotowanie macierzy pojazdów
Przygotowanie macierzy pojazdów
definiującej ilość i
definiującej ilość i
rodzaj (pojemność) pojazdów dostępnych w określonych
rodzaj (pojemność) pojazdów dostępnych w określonych
lokalizacjach
lokalizacjach
Uruchomienie procedury
Uruchomienie procedury
optymalizacji problemu
optymalizacji problemu
marszrutyzacji pojazdów i zdefiniowanie jej parametrów
marszrutyzacji pojazdów i zdefiniowanie jej parametrów
(wybór wariantu, ograniczeń, określenie zbiorów danych)
(wybór wariantu, ograniczeń, określenie zbiorów danych)
Prezentacja
Prezentacja
graficzna i tabelaryczna oraz edycja uzyskanych
graficzna i tabelaryczna oraz edycja uzyskanych
wyników
wyników
Dane wyjściowe do optymalizacji
Dane wyjściowe do optymalizacji
Dane wykorzystywane w procedurze marszrutyzacji
Dane wykorzystywane w procedurze marszrutyzacji
pojazdów z wykorzystaniem okien czasowych muszą
pojazdów z wykorzystaniem okien czasowych muszą
zawierać następujące pola informacyjne (nazwa pola jest
zawierać następujące pola informacyjne (nazwa pola jest
w zasadzie dowolna
w zasadzie dowolna
):
):
•
•
Dla miejsc nadania (
Dla miejsc nadania (
Depots
Depots
-
-
hurtownie, bazy)
hurtownie, bazy)
Nazwa pola
Typ
Znaczenie
Id
integer
Unikalny identyfkator puntku nadania
Name
string
Nazwa opisowa wykorzystywana w raportach
Open Time
integer
Najwcześniejsza pora dostępności obiektu
(w formacie wojskowym czyli 17:30 to 1730)
Close Time
integer
Najpóźniejsza pora dostępności obiektu
Node id
integer
Identyfikator najbliższego dla danego obiektu węzła sieci drogowej
4
Dane wyjściowe do optymalizacji
Dane wyjściowe do optymalizacji
•
•
Dla miejsc odbioru (
Dla miejsc odbioru (
Stops
Stops
-
-
klienci)
klienci)
Nazwy poszczególnych pól informacyjnych mogą być
Nazwy poszczególnych pól informacyjnych mogą być
dowolne
dowolne
–
–
stosowanie nazw standardowych ułatwia pracę
stosowanie nazw standardowych ułatwia pracę
z systemem poprzez automatyczny wybór stosownych pól
z systemem poprzez automatyczny wybór stosownych pól
informacyjnych w poszczególnych okienkach
informacyjnych w poszczególnych okienkach
konfiguracyjnych
konfiguracyjnych
Nazwa pola
Typ
Znaczenie
Id
integer
Unikalny identyfkator puntku odbioru (klienta)
Name
string
Nazwa opisowa wykorzystywana w raportach
Open Time
integer
Najwcześniejsza pora dostępności obiektu
(w formacie wojskowym czyli 17:30 to 1730)
Close Time
integer
Najpóźniejsza pora dostępności obiektu
Delivery demand
integer
Żądana wielkość dostawy
Pickup demand
integer
Żądana wielkość wywozu (np. opakowań zwrotnych)
Fixed time
numeric Stały czas obsługi u klienta (niezależny od ilości towaru)
Unit time
numeric Zmienny czas obsługi zależny od ilości przywiezionego towaru
Depot Assigned
integer
Preselekcja punktu obsługującego danego klienta (Id punktu nadania)
Node id
integer
Identyfikator najbliższego dla danego obiektu węzła sieci drogowej
Tworzenie macierzy odległości
Tworzenie macierzy odległości
i czasów przejazdów
i czasów przejazdów
Macierze odległości i czasów przejazdu pomiędzy
Macierze odległości i czasów przejazdu pomiędzy
wszystkimi punktami nadania (
wszystkimi punktami nadania (
Depots
Depots
) a
) a
klientami (
klientami (
Stops
Stops
) estymować można dwiema
) estymować można dwiema
metodami:
metodami:
•
•
Na podstawie
Na podstawie
odległości liniowych
odległości liniowych
-
-
zakłada się brak
zakłada się brak
informacji o sieci drogowej
informacji o sieci drogowej
–
–
do obliczenia odległości i
do obliczenia odległości i
czasów przejazdu wykorzystuje się zależności
czasów przejazdu wykorzystuje się zależności
geometryczne położenia punktów na mapie
geometryczne położenia punktów na mapie
•
•
Na postawie
Na postawie
sieci drogowej
sieci drogowej
–
–
wykorzystanie
wykorzystanie
informacji o układzie dróg, ich kierunkowości i
informacji o układzie dróg, ich kierunkowości i
dostępności dla danej chwili planowania
dostępności dla danej chwili planowania
–
–
pozwala na
pozwala na
uwzględnienie prędkości operacyjnych na
uwzględnienie prędkości operacyjnych na
poszczególnych fragmentach dróg (niezależność
poszczególnych fragmentach dróg (niezależność
kryterium odległości i czasu)
kryterium odległości i czasu)
5
Tworzenie macierzy pojazdów
Tworzenie macierzy pojazdów
Macierz pojazdów
Macierz pojazdów
musi zawierać następujące pola
musi zawierać następujące pola
informacyjne
informacyjne
:
:
Nazwa pola
Typ
Znaczenie
Depot Id
integer
Unikalny identyfkator puntku nadania (bazy) z którym pojazd jest związany
Type
string
Unikalna nazwa typu pojazdu
Capacity
real
Pojemność (wyrażona w jednostkach niemianowanych)
Number of Vehicle integer
Ilość pojazdów danego typu dostępna w danej bazie
Cost
real
Koszt eksploatacji pojazdu
Może być dana w postaci dowolnej bazy danych (np.
Może być dana w postaci dowolnej bazy danych (np.
arkusza kalkulacyjnego) zawierającej niezbędne pola
arkusza kalkulacyjnego) zawierającej niezbędne pola
informacyjne
informacyjne
Może zostać utworzona poprzez dostępny w systemie
Może zostać utworzona poprzez dostępny w systemie
edytor macierzy pojazdów (metoda mało wygodna dla
edytor macierzy pojazdów (metoda mało wygodna dla
dużych problemów optymalizacyjnych)
dużych problemów optymalizacyjnych)
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Niech będzie dany problem marszrutyzacji pojazdów z
Niech będzie dany problem marszrutyzacji pojazdów z
ograniczeniami czasowymi (oknami czasowymi)
ograniczeniami czasowymi (oknami czasowymi)
zapisany w postaci arkusza kalkulacyjnego postaci:
zapisany w postaci arkusza kalkulacyjnego postaci:
Id
Nazwa
Adres
Czas_od Czas_do
Ile Dostawca Czas_post Czas_jedn
1
Hurtownia 1
Kościuszki 77
900
1900
100
1
25
0
2
Hurtownia 2
Osiedle Orła Białego 1
900
1900
60
1
10
0
3
Hurtownia 3
Bukowska 285
800
1800
50
1
5
0
4
Hurtownia 4
28 Czerwca 1956r. 132
800
1800
70
1
10
0
5
Hurtownia 5
Głogowska 179
800
1800
90
1
20
0
6
Sklep 1
Grunwaldzka 60
900
1000
20
0
15
0,1
7
Sklep 2
23 lutego 28
800
1000
50
0
15
0,1
8
Sklep 3
Główna 58
800
1000
40
0
5
0,2
9
Sklep 4
Starołęcka 66
900
1000
10
0
10
0,1
10 Sklep 5
28 Czerwca 1956r. 267
800
1000
20
0
10
0,1
11 Sklep 6
Wołyńska 6
800
1000
10
0
10
0,1
12 Sklep 7
Warszawska 93
900
1000
50
0
20
0,2
13 Sklep 8
Strzelecka 49
800
1000
40
0
15
0,1
14 Sklep 9
Czesława 2
800
1000
20
0
15
0,1
15 Sklep 10
Nowotarska 7
800
1000
50
0
5
0,2
16 Sklep 11
Chojnicka 76
800
1000
40
0
10
0,1
17 Sklep 12
Wojciechowskiego 3/5
800
1000
10
0
5
0,2
18 Sklep 13
Sułowska 1
900
1000
10
0
15
0,1
6
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Niech będzie dany problem marszrutyzacji pojazdów z
Niech będzie dany problem marszrutyzacji pojazdów z
ograniczeniami czasowymi (oknami czasowymi)
ograniczeniami czasowymi (oknami czasowymi)
zapisany w postaci arkusza kalkulacyjnego postaci:
zapisany w postaci arkusza kalkulacyjnego postaci:
Tabela dostępnego taboru
Tabela dostępnego taboru
Id hurtowni
Typ
Pojemność
Ilość
Koszt
1
1
50
2
0,12
2
2
50
2
0,12
3
3
50
2
0,12
4
4
50
2
0,12
5
5
50
2
0,12
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Ł
Ł
adujemy mapę Poznania (
adujemy mapę Poznania (
File
File
-
-
>Open
>Open
:
:
Poznań.map
Poznań.map
)
)
i na warstwie ulic wyłączamy wyświetlanie nazw ulic
i na warstwie ulic wyłączamy wyświetlanie nazw ulic
aby zwiększyć przejrzystość mapy.
aby zwiększyć przejrzystość mapy.
7
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Wczytujemy dane z arkusza (skoroszytu)
Wczytujemy dane z arkusza (skoroszytu)
kalkulacyjnego (
kalkulacyjnego (
File
File
-
-
>Open
>Open
) wykorzystując
) wykorzystując
odpowiedni filtr importu (wybieramy filtr „Excel
odpowiedni filtr importu (wybieramy filtr „Excel
Worksheet
Worksheet
[*.
[*.
xls
xls
]
]
” wczytujemy plik
” wczytujemy plik
VRTW.xls
VRTW.xls
i
i
wybieramy
wybieramy
Arkusz1
Arkusz1
jako źródło danych).
jako źródło danych).
Po wczytaniu danych pojawia się okienko zapisu
Po wczytaniu danych pojawia się okienko zapisu
danych w postaci binarnej (wewnętrznej postaci dla
danych w postaci binarnej (wewnętrznej postaci dla
TransCAD’a
TransCAD’a
) podajemy nazwę
) podajemy nazwę
VRTW
VRTW
i zatwierdzamy.
i zatwierdzamy.
TransCAD
TransCAD
przy zrealizowaniu wielu operacji tworzy
przy zrealizowaniu wielu operacji tworzy
pliki z ich wynikami
pliki z ich wynikami
–
–
starajmy się zachowywać spójne
starajmy się zachowywać spójne
nazewnictwo tak tworzonych plików.
nazewnictwo tak tworzonych plików.
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Geokodujemy
Geokodujemy
wczytane dane o
wczytane dane o
dostawcach
dostawcach
i
i
odbiorcach
odbiorcach
wykorzystując metodę
wykorzystując metodę
geokodowania
geokodowania
w
w
oparciu o adres
oparciu o adres
(
(
Tools
Tools
-
-
>
>
Locate
Locate
-
-
>
>
Locate
Locate
by
by
address
address
)
)
8
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Jeśli procedura się powiedzie zobaczymy informację
Jeśli procedura się powiedzie zobaczymy informację
podsumowującą, w której pozycja
podsumowującą, w której pozycja
Records
Records
not
not
Located
Located
będzie
będzie
równa 0
równa 0
. Wartość niezerowa oznacza
. Wartość niezerowa oznacza
problemy z ustaleniem pewnych adresów
problemy z ustaleniem pewnych adresów
–
–
system
system
wyświetli listę tych adresów i trzeba będzie po
wyświetli listę tych adresów i trzeba będzie po
stwierdzeniu przyczyny wykonać
stwierdzeniu przyczyny wykonać
geokodowanie
geokodowanie
ponownie (tylko dla nie zlokalizowanych adresów)
ponownie (tylko dla nie zlokalizowanych adresów)
Z taką sytuacją mamy do czynienia w tym właśnie
Z taką sytuacją mamy do czynienia w tym właśnie
przypadku. System
przypadku. System
nie potrafi określić położenia
nie potrafi określić położenia
dla
dla
2 obiektów
2 obiektów
:
:
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Przypadek drugi nie budzi wątpliwości
Przypadek drugi nie budzi wątpliwości
–
–
adres został
adres został
określony
określony
„zbyt dokładnie”
„zbyt dokładnie”
co spowodowało
co spowodowało
niemożność jego interpretacji. Poprawna postać to
niemożność jego interpretacji. Poprawna postać to
Wojciechowskiego
Wojciechowskiego
3
3
W pierwszym przypadku trudno jest określić przyczynę
W pierwszym przypadku trudno jest określić przyczynę
błędu. Należy zatem
błędu. Należy zatem
dokładnie przyjrzeć
dokładnie przyjrzeć
się
się
lokalizacji przy
lokalizacji przy
ulicy Czesława
ulicy Czesława
.
.
9
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Odszukanie przedmiotowej lokalizacji realizujemy
Odszukanie przedmiotowej lokalizacji realizujemy
poprzez
poprzez
zaznaczenie
zaznaczenie
na mapie
na mapie
wszystkich
wszystkich
segmentów ulic
segmentów ulic
o nazwie „
o nazwie „
Czesława
Czesława
”
”
Przechodzimy na warstwę „
Przechodzimy na warstwę „
Poznań
Poznań
” mapy Poznania a
” mapy Poznania a
następnie uruchamiamy narzędzie selekcji obiektów z
następnie uruchamiamy narzędzie selekcji obiektów z
menu
menu
Selection
Selection
-
-
>
>
Select
Select
by
by
Condition
Condition
. Jako
. Jako
warunek realizujący opisaną metodę lokalizacji ulicy
warunek realizujący opisaną metodę lokalizacji ulicy
podajemy:
podajemy:
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
W wyniku realizacji funkcji selekcji powstaje
W wyniku realizacji funkcji selekcji powstaje
podzbiór
podzbiór
obiektów o nazwie „Czesława”
obiektów o nazwie „Czesława”
składający się z
składający się z
4
4
segmentów
segmentów
ulicy Czesława.
ulicy Czesława.
Aby poprawić widoczność obiektów wybieramy funkcję
Aby poprawić widoczność obiektów wybieramy funkcję
Settings
Settings
z
z
menu
menu
Selection
Selection
i zmieniamy ustawienia
i zmieniamy ustawienia
stylu wyświetlania elementów zbioru „Czesława”:
stylu wyświetlania elementów zbioru „Czesława”:
10
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Następnie włączamy
Następnie włączamy
wyświetlanie etykiet ulic
wyświetlanie etykiet ulic
(
(
Labels
Labels
) z wykorzystaniem mechanizmu
) z wykorzystaniem mechanizmu
Multiple
Multiple
Fields
Fields
(wyświetlenie kilku pól informacyjnych) dla pól
(wyświetlenie kilku pól informacyjnych) dla pól
definiujących
definiujących
przebieg numeracji po prawej i
przebieg numeracji po prawej i
lewej
lewej
stronie każdego segmentu ulicy:
stronie każdego segmentu ulicy:
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Po wykonaniu powiększenia interesującego nas rejonu
Po wykonaniu powiększenia interesującego nas rejonu
miasta widać wyraźnie przyczynę problemów ze
miasta widać wyraźnie przyczynę problemów ze
znalezieniem adresu
znalezieniem adresu
Czesława 2
Czesława 2
:
:
11
Przykład wykorzystania systemu TransCAD
Przykład wykorzystania systemu TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Faktyczna numeracja posesji przebiega (dla
Faktyczna numeracja posesji przebiega (dla
pierwszego segmentu ulicy) od numeru 1 do 5 w
pierwszego segmentu ulicy) od numeru 1 do 5 w
sposób ciągły, czyli po jednej stronie ulicy znajdują się
sposób ciągły, czyli po jednej stronie ulicy znajdują się
również numery parzyste, o czym system nie wie
również numery parzyste, o czym system nie wie
Aby zasygnalizować taką sytuację potrzebne jest
Aby zasygnalizować taką sytuację potrzebne jest
dodatkowe pole w strukturze mapy
dodatkowe pole w strukturze mapy
, którego na
, którego na
mapie Poznania nie ma
mapie Poznania nie ma
–
–
pole
pole
Parity
Parity
Sposobem na eliminację napotkanego problemu jest
Sposobem na eliminację napotkanego problemu jest
zmiana adresu w danych wejściowych
zmiana adresu w danych wejściowych
(dane w
(dane w
systemie
systemie
TransCAD
TransCAD
można edytować tak jak edytuje
można edytować tak jak edytuje
się dane w arkuszu kalkulacyjnym) na sąsiedni
się dane w arkuszu kalkulacyjnym) na sąsiedni
nieparzysty
nieparzysty
(1 lub 3) i ponowne wykonanie
(1 lub 3) i ponowne wykonanie
operacji
operacji
geokodowania
geokodowania
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Kolejnym krokiem jest
Kolejnym krokiem jest
powiązanie wszystkich
powiązanie wszystkich
obiektów
obiektów
z najbliższymi
z najbliższymi
węzłami sieci drogowej
węzłami sieci drogowej
.
.
W tym celu należy
W tym celu należy
zmodyfikować tabelę
zmodyfikować tabelę
(
(
dodać
dodać
nową kolumnę
nową kolumnę
, w której zapamiętany zostanie
, w której zapamiętany zostanie
identyfikator najbliższego węzła sieci drogowej)
identyfikator najbliższego węzła sieci drogowej)
Pierwszym krokiem jest wyświetlenie w postaci
Pierwszym krokiem jest wyświetlenie w postaci
tabelarycznej danych (
tabelarycznej danych (
Datawiew
Datawiew
)
)
zgeokodowanej
zgeokodowanej
warstwy
warstwy
Dostawcy i Odbiorcy
Dostawcy i Odbiorcy
a następnie
a następnie
uruchomienie
uruchomienie
edytora
edytora
struktrury
struktrury
tabeli
tabeli
(
(
Modify
Modify
Table
Table
) i
) i
dodanie nowego pola
dodanie nowego pola
o nazwie
o nazwie
node_id
node_id
(operacje te były już omawiane i są praktycznie
(operacje te były już omawiane i są praktycznie
identycznie realizowane przy wszystkich problemach
identycznie realizowane przy wszystkich problemach
rozwiązywanych w systemie
rozwiązywanych w systemie
TransCAD
TransCAD
)
)
12
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Następnie wykonujemy operację automatycznego
Następnie wykonujemy operację automatycznego
zapisania w nowo utworzonej (i zaznaczonej) kolumnie
zapisania w nowo utworzonej (i zaznaczonej) kolumnie
informacji o
informacji o
najbliżej położonych węzłach
najbliżej położonych węzłach
sieci
sieci
drogowej (
drogowej (
Edit
Edit
-
-
>Fill
>Fill
-
-
>Tag
>Tag
)
)
13
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Kolejnym etapem jest selekcja danych przeznaczonych
Kolejnym etapem jest selekcja danych przeznaczonych
do dalszych obliczeń (
do dalszych obliczeń (
podział na podzbiory
podział na podzbiory
:
:
Dostawcy
Dostawcy
i
i
Odbiorcy
Odbiorcy
). Podział na grupy definiuje w
). Podział na grupy definiuje w
naszych danych kolumna
naszych danych kolumna
Dostawca
Dostawca
wartość
wartość
1
1
w tym
w tym
polu oznacza dostawcę wartość
polu oznacza dostawcę wartość
0
0
odbiorcę
odbiorcę
. Podziału
. Podziału
danych na podzbiory dokonujemy poprzez menu
danych na podzbiory dokonujemy poprzez menu
Selection
Selection
-
-
>
>
Select
Select
by
by
condition
condition
.
.
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Dokonujemy
Dokonujemy
modyfikacji wyświetlania
modyfikacji wyświetlania
utworzonych
utworzonych
grup (
grup (
Selection
Selection
-
-
>
>
Settings
Settings
) zmieniając kolorystykę i
) zmieniając kolorystykę i
dodając identyfikatory w postaci nazw dostawców i
dodając identyfikatory w postaci nazw dostawców i
klientów (dla zwiększenia czytelności):
klientów (dla zwiększenia czytelności):
14
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Rozwiązywanie problemu marszrutyzacji pojazdów dla
Rozwiązywanie problemu marszrutyzacji pojazdów dla
przygotowanych danych rozpoczynamy poprzez
przygotowanych danych rozpoczynamy poprzez
wywołanie polecenia
wywołanie polecenia
Vehicle
Vehicle
Routing
Routing
dostępnego z
dostępnego z
menu
menu
Routing
Routing
/
/
Logistics
Logistics
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Po uruchomieniu polecenia na pierwszej zakładce
Po uruchomieniu polecenia na pierwszej zakładce
konfiguracyjnej należy wybrać przede wszystkim
konfiguracyjnej należy wybrać przede wszystkim
podtyp zadania
podtyp zadania
, które będzie rozwiązywane (w
, które będzie rozwiązywane (w
naszym przykładzie
naszym przykładzie
Dostawa
Dostawa
–
–
Delivery
Delivery
)
)
Możliwe jest na tym etapie zdefiniowanie szeregu
Możliwe jest na tym etapie zdefiniowanie szeregu
ograniczeń na tworzone rozwiązanie (część ograniczeń
ograniczeń na tworzone rozwiązanie (część ograniczeń
zależy od podtypu zadania
zależy od podtypu zadania
–
–
jest aktywna tylko dla
jest aktywna tylko dla
przypadku transportu mieszanego
przypadku transportu mieszanego
–
–
Mixed
Mixed
Pickup
Pickup
and
and
Delivery
Delivery
)
)
15
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Na kolejnej zakładce ustalamy parametry
Na kolejnej zakładce ustalamy parametry
punktów
punktów
nadania
nadania
(punkty początkowe
(punkty początkowe
porocesu
porocesu
transportowego
transportowego
-
-
Depot
Depot
)
)
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Podobnie należy uczynić w przypadku
Podobnie należy uczynić w przypadku
punktów
punktów
docelowych
docelowych
(klienci
(klienci
–
–
Stops
Stops
) pamiętając o
) pamiętając o
dodatkowych parametrach, które muszą być określone
dodatkowych parametrach, które muszą być określone
16
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Na zakładce
Na zakładce
Matrix
Matrix
generujemy macierz kosztów
generujemy macierz kosztów
wybierając jako
wybierając jako
kryterium optymalizacji
kryterium optymalizacji
pole
pole
Time
Time
(wybór kryterium pomiędzy czasem a odległością):
(wybór kryterium pomiędzy czasem a odległością):
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
W efekcie uzyskamy macierz czasów przejazdów
W efekcie uzyskamy macierz czasów przejazdów
pomiędzy wszystkimi punktami występującymi w
pomiędzy wszystkimi punktami występującymi w
rozważanym problemie. Po zamianie sposobu
rozważanym problemie. Po zamianie sposobu
wyświetlania etykiet kolumn i wierszy otrzymamy:
wyświetlania etykiet kolumn i wierszy otrzymamy:
17
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Ostatnim etapem konfiguracji zadania jest
Ostatnim etapem konfiguracji zadania jest
zdefiniowanie macierzy określającej dostępne w
zdefiniowanie macierzy określającej dostępne w
poszczególnych lokalizacjach pojazdy
poszczególnych lokalizacjach pojazdy
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Uruchomienie procedury optymalizacyjnej następuje
Uruchomienie procedury optymalizacyjnej następuje
po określeniu parametrów i
po określeniu parametrów i
kliknięciu
kliknięciu
przycisku
przycisku
GO
GO
.
.
Wyniki pośrednie procesu optymalizacji zostaną
Wyniki pośrednie procesu optymalizacji zostaną
zapisane w standardowej postaci w domyślnych
zapisane w standardowej postaci w domyślnych
katalogach systemu. Ponieważ może dojść do konfliktu
katalogach systemu. Ponieważ może dojść do konfliktu
z już istniejącymi plikami
z już istniejącymi plikami
–
–
pojawia się okienko
pojawia się okienko
pozwalające na zarządzanie plikami (zmianę
pozwalające na zarządzanie plikami (zmianę
katalogów, nazw lub zezwolenie na nadpisanie):
katalogów, nazw lub zezwolenie na nadpisanie):
18
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Pierwszym efektem realizacji procedury
Pierwszym efektem realizacji procedury
optymalizacyjnej jest
optymalizacyjnej jest
wyświetlenie
wyświetlenie
Itinerera
Itinerera
opisującego szczegółowo, w sposób tekstowy,
opisującego szczegółowo, w sposób tekstowy,
poszczególne trasy przejazdów pojazdów:
poszczególne trasy przejazdów pojazdów:
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Zakończenie procedury optymalizacyjnej jest
Zakończenie procedury optymalizacyjnej jest
sygnalizowane pojawieniem się okienka
sygnalizowane pojawieniem się okienka
podsumowującego proces obliczeniowy o postaci:
podsumowującego proces obliczeniowy o postaci:
19
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
System, choć znalazł rozwiązanie problemu, zgłosił
System, choć znalazł rozwiązanie problemu, zgłosił
dwa ostrzeżenia
dwa ostrzeżenia
-
-
Warnings
Warnings
Analiza ostrzeżeń pozwala na właściwą interpretację
Analiza ostrzeżeń pozwala na właściwą interpretację
uzyskanych wyników (ponowne policzenie problemu
uzyskanych wyników (ponowne policzenie problemu
dla zmienionych warunków lub odrzucenie uwag jako
dla zmienionych warunków lub odrzucenie uwag jako
nieistotnych). W przypadku omawianego zadania
nieistotnych). W przypadku omawianego zadania
system zgłosił problemy w postaci:
system zgłosił problemy w postaci:
•
•
3
3
stop(s
stop(s
)
)
assigned
assigned
to
to
second
second
nearest
nearest
depot
depot
.
.
•
•
1
1
stop(s
stop(s
)
)
assigned
assigned
to
to
second
second
nearest
nearest
depot
depot
.
.
Komunikat ten oznacza, iż kilku klientów zostało
Komunikat ten oznacza, iż kilku klientów zostało
obsłużonych przez hurtownie dalsze niż by to wynikało
obsłużonych przez hurtownie dalsze niż by to wynikało
z ich wzajemnego położenia. Istnieje zatem możliwość
z ich wzajemnego położenia. Istnieje zatem możliwość
polepszenia rozwiązania jeśli zmieni się alokację
polepszenia rozwiązania jeśli zmieni się alokację
środków transportowych do innych niż wyjściowe
środków transportowych do innych niż wyjściowe
lokalizacji hurtowni.
lokalizacji hurtowni.
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Postać graficzną rozwiązania uzyskamy uruchamiając
Postać graficzną rozwiązania uzyskamy uruchamiając
narzędzie wizualizacji wyników:
narzędzie wizualizacji wyników:
20
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
Informacje wyświetlone na mapie możemy poddać
Informacje wyświetlone na mapie możemy poddać
szczegółowej analizie oraz edycji z wykorzystaniem
szczegółowej analizie oraz edycji z wykorzystaniem
edytora tras przejazdów
edytora tras przejazdów
–
–
uruchamianego poprzez
uruchamianego poprzez
wybranie polecenia
wybranie polecenia
Editing
Editing
Routes
Routes
:
:
21
Przykład wykorzystania systemu
Przykład wykorzystania systemu
TransCAD
TransCAD
do rozwiązania problemu marszrutyzacji
do rozwiązania problemu marszrutyzacji
W efekcie mamy możliwość dostępu do wszystkich
W efekcie mamy możliwość dostępu do wszystkich
danych związanych z każdą z planowanych tras
danych związanych z każdą z planowanych tras
(również
(również
możliwość ręcznej modyfikacji
możliwość ręcznej modyfikacji
uzyskanego rozwiązania
uzyskanego rozwiązania
–
–
usuwania i dodawania
usuwania i dodawania
klientów do nowych lub już istniejących tras)
klientów do nowych lub już istniejących tras)