Jednym z najbardziej znanych problemów kombinatorycznych jest problem komiwojażera. W artykule omówiono jego rozszerzoną wersję – problem wielu komiwojażerów, znany także w literaturze jako zagadnienie układania tras pojazdów. Zagadnienie to, należące do problemów NP-zupełnych, łatwo można sformułować, jednak znalezienie jego optymalnego rozwiązania jest bardzo trudne. Zaprezentowano możliwość wykorzystania algorytmów ewolucyjnych. Są to metody przeznaczone przede wszystkim do rozwiązywania zadań optymalizacji, a wydają się szczególnie użyteczne w przypadku zagadnień o charakterze kombinatorycznym. Przedstawiono sformułowanie problemu układania tras pojazdów oraz znane dotychczas metody jego rozwiązywania. Następnie zaprezentowano algorytm ewolucyjny dla zadania układania tras pojazdów. W części empirycznej pracy zaprezentowano wyniki uzyskane za pomocą algorytmu ewolucyjnego do rozwiązania kilku zadań testowych.
EN
One of the best known combinatorial problems is a Travelling Salesman Problem. In the paper, an extended version is considered, i.e., a multisalesman problem, which is known in the literature as a vehicle routing problem. This NP-hard problem is very easy to define but finding an optimal solution is very hard. In this work, the applicability of evolutionary algorithms is presented. These methods are developed for optimization problems, and particularly, they seem to be very useful when applied to combinatorial problems. In the paper, a vehicle routing problem is defined and the best known heuristic methods are presented. Naxt evolutionary program for solving vehicle routing problem is formulated. Finally, experimental results for some test problems are shown and analyzed.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.