Baza wiedzy: Politechnika Warszawska

Ustawienia i Twoje konto

Powrót

Zastosowanie populacyjnych metaheurystyk uwzgledniajacych rozkład danych problemu do rozwiazywania problemu dynamicznej marszrutyzacji

Michał Okulewicz

Abstract

This thesis presents the possibility of using continuous metaheuristic algorithms for solving Dynamic Vehicle Routing Problem (DVRP). DVRP belongs to a group of transportation problems, which most famous representative is a Traveling Salesman Problem (TSP). The goal of the DVRP is to find an assignment of requests to vehicles, and a route for each of the vehicles, which minimize the total route length. Dynamic nature of the DVRP comes from the fact that some of the requests become known only during the optimization process. DVRP differs from the Stochastic Vehicle Routing Problem (SVRP), in which the approximate location and volume of the requests are known. Literature methods to solving DVRP process it as a sequence of dependent static Vehicle Routing Problem (VRP) instances. Although, continuous problem encoding has been utilized for the VRP, no such approach has been proposed for the DVRP. This thesis introduces such an algorithm, denoted ContDVRP, which by utilizing a continuous search space allows for a direct application of population based metaheuristics, like Particle Swarm Optimization (PSO) or Differential Evolution (DE). The initial encoding has been introduced independently from research on the VRP, while the final version integrates the author’s approach with the methods of Ai and Kachitvichyanukul. Effectiveness of the algorithm is tested on a set of 21 benchmark instances, converted from a static VRP instances by Kilby et al. and Montemanni et al. ContDVRP has obtained the largest number of significantly better average results than other algorithms presented in the literature. Best average result is achieved on two types of experiments: the one using a limit of fitness function evaluations, and the one using time limit to stop the optimization process. Besides experimental proof of abilities of continuous DVRP encoding its properties are thoroughly analyzed. The thesis presents ContDVRP as both the example of a dynamic optimization algorithm and a method of solving vehicle routing problems. Thesis experimentally proves that the choice of the encoding is a more crucial factor than the choice of the optimization algorithm in terms of achieving a certain solution quality on a given instance. This thesis extends knowledge about the features on the continuous encodings and their computation time to quality ratio. Additionally: (1) it introduces solving capacitated clustering problem as an alternative method to greedy construction of initial candidate solutions, (2) points out the most important optimization techniques in terms of results quality, (3) extends experimental knowledge on impact of parallel processing on computation time and quality of the achieved results. Final chapters of this thesis are dedicated to the analysis of the DVRP dynamics and its features which allowed for a success of the approach of solving DVRP as a sequence of static instances (without explicit accounting for the growth of the problem during the process). The thesis states, and experimentally proves, that it is possible to improve the quality of solution by estimating the expected sum of requests’ volume. The optimization process accounting for the expected growth of the number of requests shows a greater stability of the candidate solutions’ sequences. That stability has been measured by the number of requests reassignments and changes in the number of needed vehicles.
Identyfikator pozycji
WUT0182120d51af41b2bb7e45cb47ac9558
Rodzaj dyplomu
Praca doktorska
Autor
Tytuł w języku polskim
Zastosowanie populacyjnych metaheurystyk uwzgledniajacych rozkład danych problemu do rozwiazywania problemu dynamicznej marszrutyzacji
Język
(pl) polski
Jednostka dyplomująca
Wydział Matematyki i Nauk Informacyjnych (WMiNI)
Dyscyplina nauki
informatyka / dziedzina nauk technicznych / obszar nauk technicznych
Status pracy
Obroniona
Data nadania stopnia
23-02-2017
Promotor
Recenzenci zewnętrzni
Krzysztof Krawiec Krzysztof Krawiec Afiliacja zewnętrzna autora: Politechnika Poznańska
Leszek Rutkowski Leszek Rutkowski Afiliacja zewnętrzna autora: Politechnika Częstochowska
Wyróżnienie
tak
Paginacja
142
Słowa kluczowe w języku polskim
xxx
Streszczenie w języku polskim
Rozprawa dotyczy mozliwosci zastosowania metaheurystycznych algorytmów optymalizacji ciagłej do rozwiazania problemu dynamicznej marszrutyzacji. Problem dynamicznej marszrutyzacji nalezy do grupy problemów transportowych, w której najbardziej znanym problemem jest problem komiwojazera. Celem problemu dynamicznej marszrutyzacji jest znalezienie takiego podziału zbioru zamówien pomiedzy pojazdy oraz kolejnosci realizacji zamówien przez te pojazdy, które zminimalizuja sumaryczna trase pojazdów. Dynamizm tego problemu polega na tym, ze nowe zamówienia pojawiaja sie w trakcie procesu optymalizacji. W przeciwienstwie do stochastyczego problemu marszrutyzacji nie sa znane ani ich przyblizona lokalizacja ani rozmiar. Opisywane w literaturze podejscia optymalizujace problem dynamicznej marszrutyzacji traktuja go jako ciag zaleznych od siebie statycznych instancji problemu. W obszarze dynamicznej marszrutyzacji były stosowane wyłacznie algorytmy wykorzystujace dyskretne przestrzenie rozwiazan, jednak w literaturze poswieconej statycznym wariantom problemu znajdowały sie propozycje ciagłych reprezentacji takich problemów. Zaproponowany w tej rozprawie algorytm, nazwany ContDVRP, wykorzystuje kodowanie ciagłe, nie wymagajace modyfikacji algorytmów optymalizacyjnych takich jak Optymalizacja Rojem Czastek czy Ewolucja Róznicowa. Poczatkowy wariant kodowania był wprowadzony niezaleznie od innych prac w obszarze marszrutyzacji, zas w finalnej wersji wykorzystuje połaczenie propozycji autora rozprawy z wariantami kodowan z prac Ai i Kachitvichyanukula. Skutecznosc proponowanego algorytmu jest weryfikowana eksperymentalnie na zestawie standardowo wykorzystywanych 21 instancji testowych, spopularyzowanych pracami Kilby’ego i Montemanniego. ContDVRP osiaga najwiecej najlepszych srednich wyników sposród podejsc prezentowanych w literaturze. Sumaryczna poprawa srednich wyników jest osiagana w obu rodzajach eksperymentów: zarówno tych zatrzymujacych proces optymalizacji po zadanej liczbie ewaluacji funkcji jakosci, jak i tych wykorzystujacych limit czasowy jako kryterium stopu. Oprócz eksperymentalnego potwierdzenia zasadnosci wykorzystania ciagłego kodowania, jest ono równiez w rozprawie szczegółowo analizowane. Rozprawa prezentuje algorytm ContDVRP zarówno w kontekscie badan nad optymalizacja problemów dynamicznych metodami metaheurystycznymi, jak i badan nad algorytmami optymalizujacymi problemy marszrutyzacji. Rozprawa wykazuje eksperymentalnie, ze sposób kodowania problemu ma wiekszy wpływ na jakosc wyniku uzyskiwanego przez poszczególne algorytmy, niz sam wybór algorytmu wykorzystanego do optymalizacji. Rozprawa poszerza wiedze na temat mozliwych do zastosowania ciagłych kodowan i wynikajacego z nich stosunku szybkosci działania algorytmu do jakosci uzyskiwanych wyników. Ponadto: 1) wprowadza alternatywny do standardowo stosowanego algorytmu zachłannego sposób inicjalizacji rozwiazan poprzez poszukiwanie skupisk zamówien, 2) wskazuje najistotniejsze z punktu widzenia jakosci finalnego wyniku techniki optymalizacji wspomagajace przetwarzanie problemów dynamicznych, 3) poszerza eksperymentalna wiedze na temat wpływu zrównoleglenia procesu optymalizacji nie tylko na czas, ale i jakosc osiaganych rozwiazan. Ostatnie rozdziały rozprawy sa poswiecone analizie dynamizmu problemu oraz wskazaniu przyczyn sukcesu podejsc polegajacych na optymalizacji ciagu instancji statycznych, bez uwzgledniania mozliwej zmiennosci problemu. W tym zakresie rozprawa stawia teze, ze mozliwa jest dalsza poprawa działania algorytmu ContDVRP w oparciu o estymacje spodziewanej wielkosci sumy zamówien na podstawie dostepnych danych problemu. Eksperymenty udowodniły słusznosc tej tezy, a analiza ciagu kolejnych proponowanych wyników wykazała poprawe ich stabilnosci wzgledem bazowych eksperymentów. Wieksza stabilnosc czastkowych wyników dotyczyła mniejszej zmiennosci przypisan zamówien do pojazdów i liczby wykorzystywanych w rozwiazaniu pojazdów.
Plik pracy
  • Plik: 1
    Okulewicz.pdf
Poproś o plik WCAG

Jednolity identyfikator zasobu
https://repo.pw.edu.pl/info/phd/WUT0182120d51af41b2bb7e45cb47ac9558/
URN
urn:pw-repo:WUT0182120d51af41b2bb7e45cb47ac9558

Potwierdzenie
Czy jesteś pewien?
Zgłoszenie uwag dotyczących tej strony
Schowek