Streszczenie: Szybkie i skuteczne planowanie tras dla flot transportowych jest jednym z ważniejszych problemów logistycznych. Odpowiednie przypisanie żądań dostaw/odbioru towaru do właściwych pojazdów skutkuje korzyścią w postaci redukcji bezpośrednich i pośrednich kosztu usług transportowych. Zagadnienie, znane powszechnie jako problem marszrutyzacji (Vehicle Routing Problem - VRP) jest jednym z np-trudnych problemów optymalizacji kombinatorycznej, do rozwiązań którego stosuje się są liczne metody heurystyczne (klasteryzacja, przeszukiwanie lokalne itp.) czy i metaheurystyczne (ewolucyjne, genetyczne, rojowe i inne). Jedną z prostszych i dość popularnych, ze względu na swoją uniwersalność, metod optymalizacji jest tzw. algorytm „zachłanny”, charakteryzujący się dużą szybkością w poszukiwaniu wstępnych rozwiązań problemu marszrutyzacji. W pracy przeprowadzono badania nad implementacją algorytmu zachłannego do rozwiązania rzeczywistego problemu dostaw 569 jednostek towaru do ponad 200 punktów dostaw z użyciem heterogenicznej, tj. zróżnicowanej pod względem ładowności floty w ilości ok. 30 pojazdów. Do standardowych ograniczeń związanych z ładownością nałożono dodatkowe, dotyczące okien czasowych oraz limitu na podjazd. Klasyczny wariant deterministyczny algorytmu zmodyfikowano wprowadzając stochastyczne zaburzenia wartości dystansów między-punktowych. W efekcie algorytm odnajdywał alternatywne rozwiązania, z których znaczna część charakteryzowała się korzystniejszym wynikiem w stosunku do rozwiązania podstawowego. Przeprowadzono badania wpływu poziomu i typu zaburzeń na dystrybucję otrzymanych wyników. Postuluje się, że metoda może posłużyć zarówno do stosunkowo szybkiego znajdowania rozwiązań przybliżonych jak również do generowania populacji startowych dla bardziej zaawansowanych algorytmów ewolucyjnych.
Abstract: Fast and effective route planning for transport fleets is one of the most important logistics problems. Appropriate assignment of delivery/collection requests to the right vehicles results in the benefit of reducing the direct and indirect cost of transport services. The problem, commonly known as the Vehicle Routing Problem (VRP), is one of the NP-hard problems of combinatorial optimization, to which numerous heuristic methods (clustering, local search, etc.) or metaheuristic (evolutionary, genetic, swarm etc.) methods are used. One of the simpler and quite popular, due to its universality, optimization methods is the so-called "greedy" algorithm, characterized by high speed in the search for initial solutions to the VRP problem. In the work, research was carried out on the implementation of a greedy algorithm to solve the real problem of delivering 569 units of goods to over 200 delivery points using a heterogeneous, i.e. diversified in terms of capacity, fleet of about 30 vehicles. In addition to the standard limitations related to the load capacity, additional restrictions regarding time windows and the limit for the driveway have been imposed. The classic deterministic variant of the algorithm was modified by introducing stochastic perturbations of the distances between points. As a result, the algorithm found alternative solutions, where many of which were characterized by a more favourable result compared to the basic solution. Studies on the impact of the level and type of disturbances on the distribution of the obtained results were carried out. It is postulated that the method can be used both to find approximate solutions relatively quickly, as well as to generate starting populations for more advanced evolutionary algorithms.
Pełny tekst