Ćwiczenie nr 4 |
Problem marszrutyzacji pojazdów w systemie TransCAD. |
CEL ĆWICZENIA |
Podstawowym celem ćwiczenia jest przybliżenie problematyki rozwiązywania problemów marszrutyzacji pojazdów z wykorzystaniem nowoczesnych systemów informacji geograficznej (GIS) na przykładzie programu TransCAD. W procesie poszukiwania rozwiązania problemu uwzględniane są dodatkowe ograniczenia na pojemności pojazdów oraz okna czasowe (dostępność) zarówno dla dostawców jak i odbiorców.
WSTĘP TEORETYCZNY |
Ogólny schemat postępowania przy rozwiązywaniu dowolnego problemu z wykorzystaniem narzędzi opartych o technologię GIS został przedstawiony w ramach ćwiczenia nr 3.
Niech będzie dany problem marszrutyzacji pojazdów z ograniczeniami czasowymi (oknami czasowymi) zapisany w postaci arkusza kalkulacyjnego postaci:
W powyższym arkuszu kolumny Czas_od oraz Czas_do wyznaczają okna czasowe w których należy obsłużyć poszczególnych odbiorców. Kolumna Ile określa ilość towaru jaką należy do danego odbiorcy dostarczyć (w zakresie dostawców dane tej kolumny są ignorowane - mogą zawierać dowolne wartości, np. „0”). Kolumna Czas_post określa stałą wielkość czasu przez jaką obsługiwany jest pojazd u danego dostawcy (bez względu na ilość dowiezionego towaru). Kolumna Czas_jedn określa czas obsługi jednostki towarowej (czas postoju pojazdu wydłuża się o wielkość będącą iloczynem wartości z tej kolumny i ilości towaru dowiezionego danym pojazdem)
W celu jego rozwiązania posługujemy się poznanym wcześniej schematem postępowania:
Ładujemy mapę obszaru Poznania (File->OpenWorkspace: C:\log\Poznań.wrk) i na warstwie ulic wyłączamy wyświetlanie etykiet nazw ulic aby zwiększyć przejrzystość mapy.
Wczytujemy dane z arkusza (skoroszytu) kalkulacyjnego (File->Open) wykorzystując odpowiedni filtr importu (wybieramy filtr „Excel Worksheet [*.xls]” wczytujemy plik „VRTW.xls” [UWAGA: przy realizacji ćwiczenia (opis dalej) wskazujemy własny arkusz kalkulacyjny !] i wybieramy Arkusz1 jako źródło danych). Po wczytaniu danych pojawia się okienko zapisu danych w postaci binarnej (wewnętrznej postaci dla TransCAD'a) podajemy nazwę VRTW i zatwierdzamy. TransCAD przy zrealizowaniu wielu operacji tworzy pliki z ich wynikami - starajmy się zachowywać spójne nazewnictwo tak tworzonych plików (czyli nazwę arkusza z danymi wyjściowymi wszędzie tam gdzie TransCAD nie proponuje swojej nazwy plikowej).
Geokodujemy wczytane dane o dostawcach i odbiorcach wykorzystując metodę geokodowania w oparciu o adres (Tools-> Locate -> Locate by address)
Uwaga! Na pierwszej zakładce pole Rekord ID może być nieaktywne. Nie powinno się zmieniać wartości tego pola.
Jeśli procedura się powiedzie zobaczymy informację podsumowującą, w której pozycja Records not Located będzie równa 0. Wartość niezerowa oznacza problemy z ustaleniem pewnych adresów - system wyświetli listę tych adresów i trzeba będzie po stwierdzeniu przyczyny wykonać geokodowanie ponownie (tylko dla nie zlokalizowanych adresów)
Z taką sytuacją mamy do czynienia w tym właśnie przypadku. System nie potrafi określić położenia dla 2 obiektów:
Przypadek drugi nie budzi wątpliwości - adres został określony „zbyt dokładnie” co spowodowało niemożność jego interpretacji. Poprawna postać to „Wojciechowskiego 3”.
W przypadku nieznalezienia adresu proponowane są następujące kroki:
usunięcie słów „ul.” „ulica” z nazw adresów,
dodanie słowa „Osiedle” (np. zamiast „os.”) w przypadku nazw osiedli,
zmiana numeru domu,
zmiana adresu na inny, ale znajdujący się w pobliżu (np. „Podgórna” -> „Marcinkowskiego”).
W kolejnym etapie pracy wiążemy wszystkie obiekty z najbliższymi węzłami sieci drogowej. W tym celu należy zmodyfikować tabelę (dodać nową kolumnę, w której zapamiętany zostanie identyfikator najbliższego węzła sieci drogowej) W tym celu wyświetlamy dane (New Dataview) zgeokodowanej warstwy Dostawcy i Odbiorcy a następnie uruchamiamy edytor struktrury tabeli i dodajemy nowe pole o nazwie node_id (nazwa jest nieprzypadkowa - takiej nazwy oczekuje w wielu okienkach dialogowych system TransCAD - jeśli je znajdzie w naszych danych okienka te zostaną automatycznie uzupełnione, jeśli dane nazwiemy inaczej będziemy za każdym razem musieli je wskazywać)
Następnie wykonujemy operację automatycznego wpisania do nowo utworzonej (i zaznaczonej) kolumny informacji o najbliżej położonych węzłach sieci drogowej (Edit->Fill->Tag)
Kolejny etap rozwiązywania problemu to podział danych przeznaczonych do dalszych obliczeń (podział na zbiory: Dostawcy i Odbiorcy). Podział danych na grupy definiuje w naszych danych kolumna Dostawca: wartość 1 w tym polu oznacza dostawcę wartość 0 odbiorcę. Podziału danych na podzbiory dokonujemy poprzez menu Selection-> Select by condition:
Następnie dokonujemy modyfikacji wyświetlania utworzonych grup (Selection-> Settings) zmieniając kolorystykę i dodając identyfikatory w postaci nazw dostawców i klientów:
Rozwiązywanie problemu marszrutyzacji pojazdów dla przygotowanych danych rozpoczynamy poprzez wywołanie polecenia Vehicle routing dostępnego z menu Routing/Logistics:
Po uruchomieniu polecenia na pierwszej zakładce konfiguracyjnej należy wybrać przede wszystkim podtyp zadania, które będzie rozwiązywane (w naszym przykładzie Dostawa - Delivery) Możliwe jest na tym etapie zdefiniowanie szeregu ograniczeń na tworzone rozwiązanie (część ograniczeń zależy od podtypu zadania - jest aktywna tylko dla przypadku transportu mieszanego - Mixed Pickup and Delivery)
Na kolejnej zakładce ustalamy parametry punktów nadania (punkty początkowe porocesu transportowego - Depot) zgodnie z poniższym rysunkiem:
Podobnie należy uczynić w przypadku punktów docelowych (klienci/odbiorcy - Stops) pamiętając o dodatkowych wielkościach, które dla tych obiektów muszą być określone (zapotrzebowanie - Delivery Demand; oraz opcjonalnie: stały czas obsługi u danego klienta-Fixed Time; zmienny czas obsługi - Unit Time; predefiniowany Depot (dostawca) do obsługi danego klienta - Assigned Depot)
Na kolejnej zakładce definiujemy macierz kosztów wybierając jako kryterium optymalizacji pole Time (wybór kryterium pomiędzy czasem a odległością):
W efekcie uzyskamy macierz czasów przejazdów pomiędzy wszystkimi punktami występującymi w rozważanym problemie. Wygląd macierzy poprawiamy wykorzystując narzędzie zamiany etykiet kolumn i wierszy z identyfikatorów numerów węzłów sieci drogowej (node_id) na nazwy własne poszczególnych obiektów (Nazwa):
Ostatecznie macierz wyglądać będzie jak na rysunku poniżej:
Ostatnim etapem konfiguracji zadania jest zdefiniowanie macierzy określającej dostępne w poszczególnych lokalizacjach pojazdy (ich liczność, ładowność).
Dane mogą zostać wczytane z systemów zewnętrznych lub mogą zostać stworzone w ramach edytora macierzy pojazdów (o dość ograniczonej użyteczności). Przy rozwiązywaniu niniejszego zadania wykorzystano drugą metodę - utworzenia danych „od zera”:
Uruchomienie procedury optymalizacyjnej następuje po skonfigurowaniu parametrów i kliknięciu przycisku OK. Wyniki pośrednie procesu optymalizacji zostaną zapisane w standardowej postaci w domyślnych katalogach systemu. Ponieważ może dojść do konfliktu z już istniejącymi plikami - pojawia się okienko pozwalające na zarządzanie plikami (zmianę katalogów, nazw lub zezwolenie na nadpisanie - Overwrite, Overwrite All):
Pierwszym efektem realizacji procedury optymalizacyjnej jest wyświetlenie Itinerera opisującego szczegółowo, choć w sposób tekstowy, poszczególne trasy przejazdów pojazdów:
Zakończenie procedury optymalizacyjnej jest sygnalizowane pojawieniem się okienka podsumowującego postaci:
W tym przypadku widać, iż system, choć znalazł rozwiązanie problemu, zgłosił dwa zastrzeżenia (ostrzeżenia - Warnings) do uzyskanych wyników. Analiza ostrzeżeń pozwala na właściwą interpretację uzyskanych wyników (uznanie i ponowne policzenie problemu dla zmienionych warunków lub odrzucenie uwag jako nieistotnych). W przypadku tego zadania system zgłosił problemy w postaci komunikatu:
3 stop(s) assigned to second nearest depot.
1 stop(s) assigned to second nearest depot.
Komunikat oznacza, iż co prawda obsłużono wszystkich klientów, ale kilku z nich zostało obsłużonych poprzez pojazdy z dalszych niż by to wynikało z lokalizacji odbiorców punktów startowych (baz, hurtowni). Istnieje zatem możliwość polepszenia rozwiązania jeśli zmieni się alokację środków transportowych do innych niż wyjściowe lokalizacji.
Postać graficzną rozwiązania uzyskamy uruchamiając narzędzie wizualizacji wyników:
Postać graficzną rozwiązania uzyskamy uruchamiając narzędzie wizualizacji wyników (nie jest wymagana żadna konfiguracja bo wszystkie parametry są „odziedziczone” po procedurze optymalizacji problemu marszrutyzacji pojazdów:
Informacje wyświetlone na mapie możemy poddać szczegółowej analizie z wykorzystaniem edytora tras przejazdów - uruchamianego poprzez wybranie polecenia Editing Routes w oknie procedury optymalizacyjnej Vehilce Routing with Time Windows:
W efekcie mamy możliwość dostępu do wszystkich danych związanych z każdą z planowanych tras (również możliwość ręcznej modyfikacji uzyskanego rozwiązania - usuwania klientów z określonych tras, dodawania ich do nowych lub już istniejących tras)
UŻYWANE POMOCE DYDAKTYCZNE |
Lp. |
OPIS |
OZNACZENIE STANOWISKA |
1. |
Opis metody rozwiązania problemu transportowego dla zbioru danych wyjściowych (VRTW.xls) |
|
2. |
System pomocy on-line programu TransCAD |
|
3. |
Arkusz kalkulacyjny z definicją własnego problemu optymalizacyjnego |
|
PRZEBIEG ĆWICZENIA |
Wykorzystując dotychczas zdobytą wiedzę na temat możliwości rozwiązywania problemów marszrutyzacji pojazdów z wykorzystaniem okien czasowych zdefiniować własny problem do rozwiązania w systemie TransCAD :
Przemyśleć koncepcję pseudo-rzeczywistego problemu, który będzie można rozwiązać za pomocą metody Vehicle Routing systemu TransCAD (zwrócić szczególną uwagę na zagadnienie obsługi z wykorzystaniem okien czasowych - wybrać problem, który z natury rzeczy wymaga takiego podejścia - unikać sztucznego „dopasowywania” problemu do wymogów metody),
Zdefiniować ogólną klasę problemów, do których należy przedstawiona propozycja i wskazać praktyczne obszary zastosowań,
Przygotować zestaw danych opisujących punkty źródłowe (origin) i docelowe (destination) procesu transportowego. Dane nie muszą być rzeczywiste, ale lokalizacja obiektów na terenie Poznania powinna odzwierciedlać w miarę wiernie modelowaną sytuację - rozległość i wzajemne rozmieszczenie obiektów powinno odpowiadać proponowanej klasie problemu. Format danych powinien być zgodny z wymaganiami poznanej metody,
Przygotować zestaw danych opisujących flotę pojazdów w formacie zgodnym z wymaganiami metody (dane te mogą mieć postać elektroniczną - do wczytania bezpośrednio przy rozwiązywaniu problemu - jak i również „analogową” - do wprowadzenia ręcznego przy rozwiązywaniu problemu),
Całość przygotowanych zagadnień zapisać w postaci skoroszytu Excel gdzie na pierwszym arkuszu znajdą się dane podstawowe o punktach nadania i odbioru (w formacie gotowym do wykorzystania w systemie TransCAD) na drugim dane o pojazdach i ich lokalizacji (arkusz pozostanie wypełniony jedynie opisem jeśli przewidziano ręczne wprowadzanie danych w trakcie rozwiązywania problemu). Arkusz trzeci przeznaczony będzie na definicję i opis problemu oraz identyfikację autora/autorów projektu zadania,
Arkusz należy dołączyć do sprawozdania gdyż stanowić on będzie jeden ze składników oceny ćwiczenia (obok uzyskanych wyników i ich omówienia).
Rozwiązać problem zgodnie z przedstawionym w części teoretycznej schematem postępowania.
Dokonać analizy uzyskanych wyników.
Zapisać uzyskane wyniki lub dokonać zrzutów ekranowych uzyskanych wyników. Zrzut ekranowy wykonujemy poprzez naciśnięcie klawisza PrintScrn lub Alt-PrintScrn (kopiuje tylko aktywne okienko zamiast całego ekranu) a następnie wklejamy zapamiętaną zawartość do np. edytora tekstów Word w celu późniejszego zamieszczenia w sprawozdaniu końcowym.
SPRAWOZDANIE |
Sprawozdanie z ćwiczeń każdy student wykonuje samodzielnie.
Powinno ono zawierać
omówienie własnego problemu (wraz z postacią arkusza kalkulacyjnego zawierającego arkusze: „dostawcy i odbiory” oraz „pojazdy”)
otrzymane wyniki: zrzut ekranu przedstawiający mapę z naniesionymi na nią trasami (w postaci pliku *.png lub *.jpg), plik tekstowy z przebiegiem tras, plik z ostrzeżeniami - warnings (ale tylko w przypadku jeśli podczas uruchomienia procedury optymalizacyjnej jakieś ostrzeżenia miały miejsce)
dyskusję uzyskanych wyników.
Nie powinno zawierać opisu przebiegu ćwiczenia (procesu dochodzenia do rozwiązania), chyba że jest to istotne dla potrzeb omówienia wyników końcowych (ze względu na pojawienie się błędów czy komunikatów ostrzegawczych).
LITERATURA |
Materiały wykładowe
System pomocy on-line programu TransCAD
POLITECHNIKA POZNAŃSKA |
KIERUNEK: Transport |
|
SEMESTR VII |
|
LABORATORIUM - KOMPUTEROWE WSPOMAGANIE PROCESÓW LOGISTYCZNYCH |
||
|
|
9
opracowanie ćwiczenia - dr inż. Waldemar Walerjańczyk