Algorytm planowania tras dostaw dla wielu komiwojażerów

• Autorzy: Dutkiewicz L. , Kucharska E.

Warianty tytułu

EN

Route planning algorithm for multiple traveling salesman

• Języki publikacji: PL

Abstrakty

PL

Celem artykułu jest przedstawienie opracowanego algorytmu heurystyeznego dla NP-trudnego problemu planowania tras dostaw do firm wielooddziałowych. Rozważany problem jest modyfikacją znanego problemu wielu komiwojażerów, w którym dodatkowo występują ograniczenia czasowe udostępniania miast. W pracy przedstawiono model algebraiczno-logiczny problemu. Następnie zaproponowano algorytm oparty na metodzie zadań zastępczych wykorzystującej ogólny schemat modelu algebraiczno-logicznego. Szczegółowo opisano istotne dla algorytmu elementy: cele pośrednie, sposób wyliczania wartości priorytetów dla celów pośrednich, wyznaczanie elementów zbioru celów pośrednich wybranych do realizacji. Przedstawiono rezultaty przeprowadzonego eksperymentu.

EN

The aim of the article is presenting a heuristic algorithm for NP-hard problem of planning delivery routes to multi-branch firms. This problem is a modification of well-known multiple TSP problem with additional constrains related to need of visiting some cities to make other ones available. The algebraic-logical model of the given problem is presented in the article. The proposed algorithm is based on the optimization task substituting method which uses general scheme of an algebraic-logical model. Characteristic elements of the algorithm are described: transitional goals, its priorities and way of choosing in each state a number of the goals to be accomplished. Results of experiment are also presented.

Słowa kluczowe

PL

model algebraiczno-logiczny; dyskretny proces decyzyjny; metoda zadań zastępczych; algorytmy heurystyczne

EN

algebraic-logical model; discrete decision process; optimization task substituting method; heuristic algorithms

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2010
• Tom: T. 14, z. 3/2
• Strony: 853--865
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Dutkiewicz L.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

autor

Kucharska E.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Bubnicki Z., Wstęp do systemów ekspertowych. PWN, Warszawa, 1990.
• [2] Dudek-Dyduch E., Formalizacja i analiza problematyki dyskretnych procesów produkcyjnych. Zesz. Nauk. AGH, s. Automatyka, z. 54, Kraków, 1990.
• [3] Dudek-Dyduch E., Learning based algorithm in scheduling. Journal of Intelligent Manufacturing (JIM), vol. 11, No. 2, Kluwer Academic Publishers, 2000, 135-143.
• [4] Dudek-Dyduch E., Dutkiewicz L., Metoda zadań zastępczych do rozwiązywania NP-trudnych problemów szeregowania. Zeszyty Naukowe/Politechnika Śląska; nr 1726, Automatyka, Wydawnictwo PŚ, Gliwice 2006, 57-66.
• [5] Dudek-Dyduch E., Dyduch T., Learning algorithms for scheduling using knowledge based model. Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence; 4029, Springer-Verlag, Berlin, 2006, 1091-1100.
• [6] Dutkiewicz L., Kucharska E., Kraszewska M., Szeregowanie prac przygotowawczych w kopalni algorytmy symulacyjne. Gospodarka Surowcami Mineralnymi, t. 24, z. 3/3, Kraków, 2008, 79-93.
• [7] www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLrB95/.