Zastosowanie algorytmu symulowanego wyżarzania do rozwiązania problemu dostaw z oknami czasowymi
- Marcin Woch, Piotr ŁEBKOWSKI
- Kategoria: Pozostałe zagadnienia
W artykule przedstawiono metodę znalezienia najlepszych rozwiązań problemu dostawy z oknami czasowymi. Zaproponowany algorytm jest implementacją sekwencyjnego symulowanego wyżarzania. Zastosowano nową postać funkcji przejścia, dzięki czemu bardzo szybko otrzymuje się rozwiązania bliskie optymalnym.
1. WPROWADZENIE
Transport dóbr materialnych jest bardzo ważnym elementem działalności człowieka.
Prawidłowe zarządzanie siecią dystrybucyjną oraz parkiem pojazdów pozwala na znaczne obniżenie kosztów dostaw.
Obecnie na rynku systemów ERP można zaobserwować zwiększone zapotrzebowanie na aplikacje wspomagające planowanie tras [6]. Jest to związane z faktem, że nawet niewielka oszczędność na pojedynczych wysyłkach pozwala na znaczne redukcje kosztów w dłuższym okresie. Prawidłowe zarządzanie wysyłką pozwala na lepsze spełnianie potrzeb klientów, co sprzyja poprawie wizerunku firmy.
2. PROBLEM DOSTAW Z OKNAMI CZASOWYMI
Problem dostaw (Vehicle Routing Problem - VRP) jest rozwinięciem problemu komiwojażera. W problemie dostaw pomiędzy zbiorem klientów poruszają się pojazdy o określonej ładowności. Każdy z klientów ma określone zapotrzebowanie na towar, zaś kolejność ich odwiedzania nie ma znaczenia. Każda trasa zaczyna się oraz kończy w tym samym miejscu, w centralnym magazynie. Rozwiązanie problemu dostaw oznacza znalezienie najkrótszej łącznej długości tras wszystkich pojazdów, przy czym ładowność każdego z nich nie może zostać przekroczona.
W problemie dostaw z oknami czasowymi (VRPTW - Vehicle Routing Problem with Time
Windows), oprócz założeń przyjętych w klasycznym problemie dostaw VRP, każdy klient ma zdefiniowany najwcześniejszy możliwy czas rozpoczęcia ei obsługi dostawy oraz najpóźniejszy możliwy czas rozpoczęcia fi. Wartości te wyznaczają tzw. okno czasowe klienta. Każdy klient posiada określony czas trwania obsługi si, czyli okres, w jakim u klienta przebywa pojazd.
Problem dostaw został formalnie opisany przez Salomona [8, 9] w 1987 roku. Przygotował on zbiór zagadnień, które są używane do testowania algorytmów oraz do porównywania wyników badań z aktualnie istniejącymi najlepszymi rozwiązaniami. W niniejszym artykule (...)
Transport dóbr materialnych jest bardzo ważnym elementem działalności człowieka.
Prawidłowe zarządzanie siecią dystrybucyjną oraz parkiem pojazdów pozwala na znaczne obniżenie kosztów dostaw.
Obecnie na rynku systemów ERP można zaobserwować zwiększone zapotrzebowanie na aplikacje wspomagające planowanie tras [6]. Jest to związane z faktem, że nawet niewielka oszczędność na pojedynczych wysyłkach pozwala na znaczne redukcje kosztów w dłuższym okresie. Prawidłowe zarządzanie wysyłką pozwala na lepsze spełnianie potrzeb klientów, co sprzyja poprawie wizerunku firmy.
2. PROBLEM DOSTAW Z OKNAMI CZASOWYMI
Problem dostaw (Vehicle Routing Problem - VRP) jest rozwinięciem problemu komiwojażera. W problemie dostaw pomiędzy zbiorem klientów poruszają się pojazdy o określonej ładowności. Każdy z klientów ma określone zapotrzebowanie na towar, zaś kolejność ich odwiedzania nie ma znaczenia. Każda trasa zaczyna się oraz kończy w tym samym miejscu, w centralnym magazynie. Rozwiązanie problemu dostaw oznacza znalezienie najkrótszej łącznej długości tras wszystkich pojazdów, przy czym ładowność każdego z nich nie może zostać przekroczona.
W problemie dostaw z oknami czasowymi (VRPTW - Vehicle Routing Problem with Time
Windows), oprócz założeń przyjętych w klasycznym problemie dostaw VRP, każdy klient ma zdefiniowany najwcześniejszy możliwy czas rozpoczęcia ei obsługi dostawy oraz najpóźniejszy możliwy czas rozpoczęcia fi. Wartości te wyznaczają tzw. okno czasowe klienta. Każdy klient posiada określony czas trwania obsługi si, czyli okres, w jakim u klienta przebywa pojazd.
Problem dostaw został formalnie opisany przez Salomona [8, 9] w 1987 roku. Przygotował on zbiór zagadnień, które są używane do testowania algorytmów oraz do porównywania wyników badań z aktualnie istniejącymi najlepszymi rozwiązaniami. W niniejszym artykule (...)
Artykuł zawiera 19335 znaków.
Źródło: Czasopismo Logistyka