1 Zagadnienia transportowe Katedra Ekonomiki i Funkcjonowania Przedsiębiorstw Transportowych

2 Transport to: działalność polegająca na celowym przemieszczaniu ładunków oraz osób przy użyciu odpowiednich przedmiotów pracy, zwanych środkami transportowymi, pokonujących drogę między nadawcą a odbiorcą operacji transportowej

3 Transport umożliwia, realizację procesu produkcji, dostarczając surowce, materiały, półfabrykaty i części zamienne na stanowiska produkcyjne oraz zaistnienie samego procesu technologicznego. Jest on czynnikiem niezbędnym w sferze wymiany, dostarczając gotowe produkty do konsumenta, odpowiada za fizyczną dystrybucję dóbr materialnych i usług

4 Zagadnienia transportowe Jest to zbiór zagadnień badań operacyjnych związanych z transportem. Wymagają one użycia specyficznych metod będących połączeniem programowania liniowego, dynamicznego i sieciowego. Do zagadnień transportowych należą: problem Hitchcocka (klasyczne zagadnienie transportowe), problem przydziału, problem najkrótszej trasy, problem maksymalnego przepływu, problem najmniejszego drzewa rozpinającego i problem komiwojażera.

5 Grafy Graf jest to zbiór punktów (wierzchołków) połączonych krawędziami (łukami).

6 Grafy zorientowane Grafy, w których łuki pomiędzy wierzchołkami są skierowane, a ich kolejność określona nazywa się grafami zorientowanymi.

7 Grafy ważone Graf ważony to taki, w którym każdej krawędzi przypisana jest określona wartość, która oznaczać może na przykład odległość.

8 Pętla Pętla jest to krawędź mająca swój początek i koniec w tym samym wierzchołku.

9 Trasa Trasą w grafie nazywa się ciąg krawędzi AB, BC,… prowadzący od wierzchołka początkowego do wierzchołka końcowego w którym każde dwie kolejne krawędzie są sąsiednie lub identyczne. Przykładowa trasa: AC, CE, EE, ED, DC, CB. W tym wypadku wierzchołkiem początkowym jest A, a wierzchołkiem końcowym B.

10 Droga Jeśli wszystkie krawędzie i wierzchołki do niej należące są różne, trasę nazywa się drogą. Trasa, w której wszystkie krawędzie są różne, a wierzchołek początkowy jest równy wierzchołkowi końcowemu nazywa się cyklem. Przykładowa droga: AC, CB, BD, DE; Przykładowy cykl: AC, CE, ED, DA

11 Sieci Grafy zorientowane, w których nie występują pętle ani cykle nazywa się sieciami.

12 Klasyczne zagadnienie transportowe Problem najtańszego przewozu jednorodnego dobra pomiędzy punktami nadania (dostawcy), a punktami odbioru (odbiorcy). Wymagane informacje: koszt przewozu jednostki dobra pomiędzy i-tym dostawcą, a j-tym odbiorcą; wielkość podaży dostawców; wielkość podaży odbiorców Jeżeli suma wielkości podaży odbiorców i dostawców są równe problem nazywa się zamkniętym zagadnieniem transportowym

13 Klasyczne zagadnienie transportowe W klasycznym zagadnieniu transportowym istnieje zawsze co najmniej jedno rozwiązanie optymalne!

14 Problem maksymalnego przepływu Odnalezienie łącznej wartości ścieżek w grafie pozwalającej na wygenerowanie największego przepływu, Stosowany w: sieciach transportowych, informatyce, programowaniu produkcji, przydziale personelu.

15 Problem komiwojażera

16 Rozwiązanie optymalne - trasa, dla której łączny czas / koszt / odległość są najmniejsze; Ilość rozwiązań dopuszczalnych – ilość możliwości uszeregowania wszystkich punktów odbioru – ilość permutacji n-elementowych

17 Permutacje n-elementowe P n = n! 2 punkty odbioru = 2! = 2 możliwości, 5 punktów odbioru = 5! = 120 możliwości 100 punktów odbioru = 100! = 9,3 * 10 157

18 Metody i techniki heurystyczne „to ogół sposobów i reguł postępowania służących podejmowaniu najwłaściwszych decyzji w skomplikowanych sytuacjach, wymagających analizy dostępnych informacji, a także przewidzenia zjawisk przyszłych; oparte na twórczym myśleniu i kombinacjach logicznych” M. Jełowicki, W. Kieżuń, Z. Leoński, B. Ostapczuk „Teoria Organizacji i Zarządzania”

19 Motywy stosowania heurystyk Oszczędność czasu; Oszczędność kosztów; Niemożność znalezienia rozwiązania optymalnego.

20 Heurystyki w problemie komiwojażera Nearest Neighbour Heuristic Cheapest Insertion Heuristic Two-way Exchange Improvement Heuristic Branch and Bound Method