Algorytm planowania tras dostaw dla wielu komiwojażerów

Abstract

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.

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.