PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 5

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  komiwojażer
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Zastosowanie algorytmów sztucznej inteligencji do rozwiązania problemu komiwojażera
Ficoń K., Krasnodębski A.
Gospodarka Materiałowa i Logistyka
|
2018
|
nr 12
286--307, CD
PL
W pracy omówiono heurystyczne metody rozwiązania problemu komiwojażera za pomocą algorytmów sztucznej inteligencji. Oprócz niemal klasycznych algorytmów opartych na sztucznych sieciach neuronowych i algorytmach genetycznych (ewolucyjnych) zostały przeanalizowane nowoczesne algorytmy korzystające z tzw. inteligencji roju (stada). W tej grupie zostały przeanalizowane algorytmy kolonii pszczół i stada ptaków. Szerzej zostały przedyskutowane algorytmy mrówkowe, bardzo ściśle związane z suboptymalizacją tras komunikacyjnych.
EN
The paper discusses the heuristic methods of solving the traveling salesman problem using artificial intelligence algorithms. In addition to almost classic algorithms based on artificial neural networks and genetic (evolutionary) algorithms, modern algorithms using the so-called swarm intelligence (herd). In this group, the algorithms for colonies of bees and flocks of birds have been analyzed. The formic algorithms, very closely related to the suboptimization of communication routes, have been discussed in more detail.
2
Content available Algorytm mrówkowy w problemie komiwojażera
Rutczyńska-Wdowiak K., Jabłoński N.
Autobusy : technika, eksploatacja, systemy transportowe
|
2016
|
R. 17, nr 6
1523--1526
PL
W artykule omówiony został algorytm mrówkowy wykorzystany do rozwiązania zagadnienia komiwojażera. Zaimplementowana aplikacja zapewnia wygenerowanie najkrótszej trasy przejazdu, w możliwie krótkim czasie oraz pozwala na analizowanie pracy algorytmu mrówkowego i dobór optymalnych wartości jego parametrów kontrolnych.
EN
In this article discussed ant algorithm was used to solve the traveling salesman problem. Implemented application provides to generate the shortest route in the shortest possible time and allows to analyze work of algorithm and selection of the optimal values of his control parameters.
3
Content available remote Dualizm logistyczno-kombinatoryczny zadania komiwojażera
Ficoń Krzysztof
Systemy Logistyczne Wojsk
|
2015
|
Vol. 42, no. 1
45--64
PL
W pracy został przedstawiony dualny charakter problemu komiwojażera (TPS –Travelling Salesman Problem), który może być jednocześnie rozpatrywany jako utylitarne zadanie transportowe według kryteriów logistycznych oraz jako złożony problem kombinatoryczny optymalizacji dyskretnej. W aspekcie optymalizacyjnym zadanie TSP należy do problemów NP-zupełnych, dla których w ogólności nie istnieją efektywne metody rozwiązań. Ze względu na bardzo szeroki zakres logistycznych aplikacji zadania TSP, dokonano prezentacji najbardziej popularnych metod jego rozwiązania. Szczególną uwagę zwrócono na nowoczesne podejście oparte na metodach sztucznej inteligencji i algorytmach mrówkowych. Klasyczny problem TSP jest szczególnym przypadkiem bardzo ważnego we współczesnej logistyce wielowymiarowego problemu marszrutacji rzutującego m.in. na globalne koszty działalności transportowej i logistycznej.
EN
At the work described dual character of the vehicle routing stayed (TPS – Travelling Salesman Problem) which can simultaneously be considered as the utilitarian transport task according to logistic criteria and as a combinatorial many-sided problem of discreet optimization. In the operational research aspect the TSP task is included in problems NP-complete, which in general effective methods of solutions don’t exist for. On account of very wide range of logistic applications of the TSP task they made the pre-sentation the most of popular methods of untying him. They paid special attention to the modern attempt based on methods of the artificial intelligence and ant algorithms. The classic TSP problem is a special case very much important in the contemporary logistics of the multidimensional problem route projecting among others onto total costs of transport and logistic activity.
4
Content available An improved genetic algorithm for solving the Selective Travelling Salesman Problem on a road network
Piwońska A.
Zeszyty Naukowe Politechniki Białostockiej. Informatyka
|
2011
|
Z. 7
59-70
EN
The Selective Travelling Salesman Problem (STSP) is a modified version of the Travelling Salesman Problem (TSP) where it is not necessary to visit all vertices. Instead of it, with each vertex a number meaning a profit is associated. The problem is to find a cycle which maximizes collected profit but does not exceed a given cost constraint. A direct application of the STSP, e.g. in Intelligent Transportation Systems, is finding an optimal tour in road networks. However, while the classic STSP is defined on a complete graph, a road network is in general not complete and often has a rather sparse edge set. This paper presents the STSP defined on a road network (R-STSP). Since the R-STSP is NP-hard, the improved genetic algorithm (IGA) is proposed which is the enlarged version of our previous GA. The main aim of this paper is to investigate the role of the deletion mutation in the performance of the IGA.
PL
Selektywny problem komiwojażera (STSP) jest zmodyfikowaną wersją problemu komiwojażera (TSP), w której nie jest konieczne odwiedzenie wszystkich wierzchołków. Zamiast tego, z każdym wierzchołkiem związana jest liczba oznaczająca zysk. Problem polega na znalezieniu cyklu w grafie, który maksymalizuje zysk, ale którego koszt nie przekracza zadanego ograniczenia. Bezpośrednim zastosowaniem problemu STSP, np. w Inteligentnych Systemach Transportowych, jest odnajdywanie optymalnej trasy w sieci drogowej. Jednakże, podczas gdy klasyczny problem STSP jest zdefiniowany na grafie zupełnym, sieć drogowa zwykle nie jest grafem pełnym i często ma rzadki zbiór krawędzi. Artykuł przedstawia problem STSP zdefinowany w sieci drogowej (R-STSP). Ponieważ R-STSP jest NP-trudny, zaproponowano ulepszony algorytm genetyczny (IGA), który jest rozszerzoną wersją poprzedniego algorytmu genetycznego. Głównym celem artykułu jest zbadanie roli mutacji usuwającej w w jakości wyników IGA.
5
Content available Genetic algorithm finds routes in travelling salesman problem with profits
Piwońska A.
Zeszyty Naukowe Politechniki Białostockiej. Informatyka
|
2010
|
Z. 5
51-65
EN
Travelling salesman problem with profits is a version of a classic travelling salesman problem where it is not necessary to visit all vertices. Instead of it, with each vertex a number meaning a profit is associated. The problem is to find a cycle in a graph which maximizes collected profit but does not exceed a given cost constraint. This problem is NP-hard. Additional assumptions to this problem were proposed in the paper.We assumed that a graph may not be a complete graph. Moreover, repeated visiting of a given vertex is allowed, however with an assumption that a profit is realized only during first visiting. With these additional assumptions, the problem is more real-life and could have applications in logistics and shipping. To solve the problem, a genetic algorithm with special operators was proposed. The algorithm was tested on networks of cities in some voivodeships of Poland, obtaining very good results.
PL
Problem komiwojażera z zyskami (ang. TSP with profits) jest pewną wersją klasycznego problemu komiwojażera, w której nie jest konieczne odwiedzenie wszystkich wierzchołków grafu. Zamiast tego, z każdym wierzchołkiem związana jest pewna liczba oznaczająca zysk. Problem polega na znalezieniu cyklu w grafie, który maksymalizuje zysk, ale którego koszt nie przekracza zadanego ograniczenia. Problem ten jest problemem NPtrudnym. Do tak postawionego problemu, w pracy zaproponowano dodatkowe założenia. Przyjęto mianowicie, że graf nie musi być pełny. Ponadto dopuszczona jest możliwość powrotów, czyli ponownego odwiedzenia danego wierzchołka, przy założeniu jednak, iż zysk realizowany jest tylko podczas pierwszego odwiedzenia. Przy tych dodatkowych założeniach problem jest bardziej realny i może mieć konkretne zastosowania w logistyce i spedycji. Do rozwiązania problemu zaproponowano algorytm genetyczny, uzyskując bardzo dobre wyniki.
first rewind previous Strona / 1 next fast forward last
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ć.