PL
 |
EN
Ograniczanie wyników
Czasopisma help
  1. 6 Logistyka
  2. 5 Gospodarka Materiałowa i Logistyka
  3. 5 Material Economy and Logistics Journal
  4. 4 Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
  5. 3 Annals of Computer Science and Information Systems
Więcej...
Autorzy help
  1. 3 Michlowicz E.
  2. 2 Klimek M.
  3. 2 Kucharska E.
  4. 2 Laszczyk Maciej
  5. 2 Myszkowski Paweł B.
Więcej...
Lata help
  1. 1 2023
  2. 1 2020
  3. 3 2019
  4. 2 2018
  5. 1 2017
Więcej...
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 39

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote Optimizing Municipal Waste Collection: a Case Study of a City in Poland
Roman Monika, Waśkiewicz Michał
Systemy Logistyczne Wojsk
|
2023
|
Vol. 58, no. 1
197--218
EN
The main problem of waste management is the increasing amount of municipal waste, and one of the key processes generating high costs is the waste collection process. The aim of the article was to optimize the route of a garbage truck using information technology (IT) software in one of the most populated Polish cities. The article tests the study hypothesis: the use of route optimization software will reduce the route length traveled by the garbage truck of the MZO in Pruszków. The data for the study was made available with the consent of the Municipal Treatment Plant in Pruszków. The received materials included information on, among others, Global Positioning System (GPS) readings of the garbage truck, including route start and end times, route length, average speed, driving time, and time of stops, points selected by the planners to collect waste along the route, information on the amount of waste collected during the implementation of the route, technical data on the moving vehicle and characteristics of the sorting plant were received. The article proposes the optimization of the routes of collection and transportation of municipal waste using the traveling salesman problem (TSP). The minimization of route length was assumed as the optimization criterion. All calculations were made in the Routimo program dedicated to route planning and optimization. As a result of the optimization, the route length was reduced by nearly 32%, and the working time by 9%. Thus, the research hypothesis stated in the article was positively verified.
PL
Głównym problemem gospodarki odpadami jest rosnąca ilość odpadów komunalnych, a jednym z kluczowych procesów generujących wysokie koszty jest proces zbierania odpadów. Celem artykułu była optymalizacja trasy przejazdu śmieciarki z wykorzystaniem oprogramowania informatycznego w jednym z najbardziej zaludnionych miast Polski. W artykule weryfikowano hipotezę badawczą: zastosowanie oprogramowania optymalizującego trasę skróci długość trasy pokonywanej przez śmieciarkę MZO w Pruszkowie. Dane do badań zostały udostępnione za zgodą Miejskiego Zakładu Oczyszczania w Pruszkowie. Otrzymane materiały zawierały informacje m.in. o odczytach Global Positioning System (GPS) śmieciarki, w tym o czasie rozpoczęcia i zakończenia trasy, długości trasy, średniej prędkości, czasie jazdy i czasie postojów, zbiór wybranych przez planistów punktów odbioru odpadów na trasie, informację o ilości odpadów zebranych w trakcie realizacji trasy, dane techniczne poruszającego się pojazdu oraz charakterystykę sortowni. W artykule zaproponowano optymalizację trasy odbioru i transportu odpadów komunalnych z wykorzystaniem problemu komiwojażera (TSP). Jako kryterium optymalizacji przyjęto minimalizację długości trasy. Wszystkie obliczenia wykonano w programie Routimo przeznaczonym do planowania i optymalizacji tras. W wyniku optymalizacji długość trasy uległa skróceniu o blisko 32%, a czas pracy o 9%. Tym samym zweryfikowano pozytywnie postawioną w artykule hipotezę badawczą.
2
Content available remote Stochastic multi-depot vehicle routing problem with pickup and delivery: an ILS approach
Rios Brenner H. O., Xavier Eduardo C., Miyazawa Flávio K., Amorim Pedro
Annals of Computer Science and Information Systems
|
2020
|
Vol. 21
307--315
EN
We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD). In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed. We denote this stochastic version by S-MDVRPPD. One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route. The objective is to find a solution with minimum expected traveling distance. We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions. To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure. The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work. We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances. The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.
3
Content available Metody oraz narzędzia wspierające optymalizację dystrybucji wyrobów o ograniczonej trwałości
Ponikierska Agnieszka
Gospodarka Materiałowa i Logistyka
|
2019
|
nr 4
21--28
PL
Zaprezentowane w artykule rozwiązanie jest dedykowane przedsiębiorstwom dystrybucyjnym, dla których priorytet stanowi szybka i sprawna dostawa towaru o krótkim terminie przydatności, bez utraty czy obniżenia jego jakości. Ta determinująca cecha oferowanych produktów sprawia, że optymalizacja funkcjonowania łańcucha dostaw, a w szczególności procesów dystrybucyjnych, wymaga przede wszystkim skrócenia czasu realizacji dostaw od producenta do finalnego odbiorcy. W rozwiązaniu zastosowano proste, a zarazem skuteczne metody optymalizacyjne w celu podniesienia efektywności tego procesu, oparte na systemie klasy Just in Time, przeładunku kompletacyjnym cross dock i metodzie komiwojażera. Efektem wprowadzonego rozwiązania jest znaczne skrócenie czasu realizacji zamówień, a co za tym idzie — wzrost zadowolenia klientów. Uzyskano także zmniejszenie zapotrzebowania ma powierzchnię magazynową, wyeliminowanie konieczności utrzymywania zapasów, optymalizację tras przewozu, co doprowadziło do znacznego obniżenia kosztów prowadzonej działalności i zwiększenie jej efektywności.
EN
Solution presented in this article is dedicated to distribution companies, that prioritize fast and efficient supply of products with limited shelf life without losing or lowering their quality. This determining feature of offered products, makes shortening of delivery time from producent to customer the key of supply chain optimization. This solution uses simple and effective optimization methods that are able to make the whole process more effective. These methods are based on class system ‘Just in Time’, cross docking and canvasser method. Implementation of presented solution results both in shortening the time of execution of the order and growth of customers satisfaction. Reduction of storage space demand, elimination of necessity to hold reserves and optimization of cargo routes were also the results of presented solution. All these changes lowered expenses of the company and made it more effective.
4
Content available remote Non-dominated sorting tournament genetic algorithm for multi-objective travelling salesman problem
Myszkowski Paweł B., Laszczyk Maciej, Dziadek Kamil
Annals of Computer Science and Information Systems
|
2019
|
Vol. 18
67--76
EN
A Travelling Salesman Problem (TSP) is an NP-hard combinatorial problem that is very important for many real-world applications. In this paper, it is shown, that proposed approach solves multi-objective TSP (mTSP) more effectively than other investigated methods, i.e. Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed methods use rank and crowding distance (well-known from NSGA-II), combining those mechanisms in a novel, unique way: competing and co-evolving in the evolution process. The proposed modifications are investigated and verified by the benchmark mTSP instances, and results are compared to other methods.
5
Content available remote A Specialized evolutionary approach to the bi-objective travelling thief problem
Laszczyk Maciej, Myszkowski Paweł B.
Annals of Computer Science and Information Systems
|
2019
|
Vol. 18
47--56
EN
In the recent years, it has been shown that real world-problems are often comprised of two, interdependent subproblems. Often, solving them independently does not lead to the solution to the entire problem. In this article, a Travelling Thief Problem is considered, which combines a Travelling Salesman Problem with a Knapsack Problem. A Non-Dominated Sorting Genetic Algorithm II (NSGA-II) is investigated, along with its recent modification - a Non-Dominated Tournament Genetic Algorithm (NTGA). Each method is investigated in two configurations. One, with generic representation, and genetic operators. The other, specialized to the given problem, to show how the specialization of genetic operators leads to better results. The impact of the modifications introduced by NTGA is verified. A set of Quality Measures is used to verify the convergence, and diversity of the resulting PF approximations, and efficiency of the method. A set of experiments is carried out. It is shown that both methods work almost the same when generic representation is used. However, NTGA outperforms classical NSGA-II in the specialized results.
6
Content available Równoległa realizacja przykładowego algorytmu genetycznego z wykorzystaniem akceleratorów GPU
Ratuszniak P., Stasiak A., Łańcucki R.
Zeszyty Naukowe Wydziału Elektroniki i Informatyki Politechniki Koszalińskiej
|
2018
|
Nr 13
63--78
PL
W artykule zaprezentowano praktyczną implementację aplikacji rozwiązującej przykładowy algorytm genetyczny z wykorzystaniem akceleratorów GPU. W tym przypadku zdecydowano się na rozwiązanie za pomocą algorytmu genetycznego typowego problemu optymalizacyjnego, jakim jest problem komiwojażera. Dodatkowo w celu wykorzystania mocy karty graficznej w tworzonej aplikacji wykorzystano technologię programowania na karcie graficznej – technologię Nvidia CUDA.
EN
The paper presents a practical implementation of a local desktop application that solves exemplary genetic algorithm with the use of GPU accelerators. In this case decided with the use of genetic algorithm to solve typical optimization problem which is travelling salesman problem. Additionally used Nvidia CUDA programming technology in order to use power of GPU in created application.
7
Content available remote Problem komiwojażera – studium przypadku
Ziółkowski Jarosław, Miziołek Angelika, Ćwik Dariusz
Systemy Logistyczne Wojsk
|
2018
|
Vol. 49, no. 2
236--245
PL
W artykule przedstawiono problem komiwojażera na przykładzie liczbowym. Celem jest znalezienie trasy łączącej wszystkie miasta, która całościowo jest najkrótsza, najszybsza lub najtańsza i ponadto zaczyna się i kończy się w określonym punkcie. Jest to typowe zagadnienie optymalizacyjne, w którym zadane jest n miast, które komiwojażer musi odwiedzić. Jego rozwiązanie polega na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
EN
The paper presents the travelling salesman problem (TSP) on a numerical example. The aim of the paper is to find the shortest, the fastest and the cheapest route, which links all the cities and additionally starts and ends at a particular point. This is the typical optimization problem with n number of cities that the travelling salesman has to visit. The solution of the problem is to find the minimum Hamiltonian cycle in a complete weighted graph.
8
Content available Interfejs do zdalnego sterowania ploterem z funkcją rozpoznawania obrazów
Kamiński M., Morawiec M.
Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej
|
2017
|
Nr 57
37--42
PL
Maszyny numeryczne takie jak obrabiarki CNC, plotery czy drukarki 3D są coraz powszechniejsze w użytku. Na Politechnice Gdańskiej przygotowano pracę magisterską [12], której rezultaty przedstawiono w niniejszym artykule. Ze względu na objętość referatu, przedstawiono jedynie wybrane aspekty budowy plotera, aplikacji na urządzenie mobilne oraz przegląd zastosowanych algorytmów optymalizacji pod kątem szybkości rysowania. Aplikacja funkcjonuje w systemie Android, a komunikuje się z maszyną za pomocą interfejsu bluetooth. Aplikacja oferuje także możliwość optymalizacji tras, zarówno tych rysowanych, jak i nierysowanych, pokonywanych przez ploter. Jest to problem komiwojażera bez powrotu, który rozwiązany może być poprzez algorytmy: zachłanny, genetyczny, wspinaczkowy lub symulowanego wyżarzania.
EN
The topic is to build a CNC machine working as a plotter, and also create an application running on the Android operating system, which processes images, optimizes the code and allows to control the built machine. The examination is an estimation which of the methods used in this thesis is optimal and gives the best results in this type of problem, which is choosing the shortest path of the salesman problem. The purpose of the paper is to obtain the code processed by the numerical machine in the shortest possible time, which will be carried out in a short period of time with the proper accuracy of the work. Another important aspect is the implementation of an intuitive user interface that does not cause problems with support. The optimization methods used produce satisfactory results that are more or less practical depending on the problem. The effect in the form of drawn images is at a high level of accuracy. After many hours of working with the CNC machine using the created application, it can be seen that this is a useful set for both people who want to create their own images as well as for those seeking education in this field. The great advantage is that the design is very easily expandable so that it can acquire new, very useful features for a small amount of extra work in the form of adding new functionality.
9
Content available remote A comparison of ant colony optimization and genetic algorithm for solving the traveling salesman problem
Ochelska-Mierzejewska J.
Journal of Applied Computer Science
|
2016
|
Vol. 24, nr 1
51--66
EN
Every company in today’s world faces the constant challenge of cost reduction. For distribution and transport service providers, cost cutting appears to be the main operational goal. The successful companies seek to develop an optimal routes for their fleets to minimize the costs and guarantee a timely delivery of the goods. With a growing informatization of the industrial world, it is worth considering the use of intelligent systems as a possible way of solving various types of decision problems, which in turn can contribute to the reduction of costs incurred by a company. Such systems enable multidimensional data analysis and to provide information useful in decision making. The paper investigates the use of the genetic algorithm and the ants colony optimization algorithm as a solution to the travelling salesman problem. It has been shown that both methods provide satisfactory results in solving the problem under examination.
10
Content available A note on the Miller-Tucker-Zemlin model for the asymmetric traveling salesman problem
Sawik T.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2016
|
Vol. 64, nr 3
517--520
EN
An enhancement of the Miller-Tucker-Zemlin (MTZ) model for the asymmetric traveling salesman problem is presented by introducing additional constraints to the initial formulation. The constraints account for ordering of boundary nodes as well as all successive nodes in the salesman tour. The enhanced MTZ subtour elimination constraints are computationally compared with the basic MTZ constraints and the version of MTZ lifted by Desrochers and Laporte. The proposed enhancement shows improved performance on a number of asymmetric TSPLIB instances.
11
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.
12
Content available Algorytm mrówkowy jako metoda rozwiązania problemu komiwojażera
Ochelska-Mierzejewska J.
TTS Technika Transportu Szynowego
|
2015
|
R. 22, nr 12
1140--1146, CD
PL
Celem każdej firmy jest obniżenie kosztów. Firmy związane z dystrybucją i transportem próbują opracować trasy swoich pojazdów, aby możliwie zminimalizować koszty i umożliwić dostarczenie ich towarów w wystarczająco krótkim czasie. W pracy przedstawiono rozwiązanie problemu komiwojażera poprzez optymalizację kolonią mrówek, następnie przeanalizowano dobór parametrów wejściowych dla tego algorytmu, aby znaleźć optymalne rozwiązanie tego problemu.
EN
The aim of each company is to lower costs. Companies associated with the distribution and transport are trying to develop a routes of their fleet vehicles to possibly minimize cost and allow their goods to be delivered in a sufficiently short time. The paper presents a solution to the traveling salesman problem by optimizing an ants colony, then the paper presents the analysis of input parameters selection for this algorithm to find the optimal solution to this problem.
13
Wybrane zagadnienia optymalizacji transportu odpadów komunalnych
Pawul M., Kwiecień J., Śliwka M.
Logistyka
|
2015
|
nr 4
9585--9592, CD3
PL
Gospodarowanie odpadami wymaga rozwiązań skutecznych pod względem ochrony środowiska, ale także efektywnych ekonomicznie. Spośród wszystkich etapów gospodarowania odpadami komunalnymi, dużą część kosztów generuje ich transport pomiędzy punktami zbiórki a miejscem ich przetwarzania. Opierając się na danych literaturowych zaprezentowano różne modele i metody stosowane do wyboru najkorzystniejszej trasy przejazdu śmieciarek, w tym problemy trasowania z żądaniami zlokalizowanym w wierzchołkach lub na krawędziach czy łukach grafu.
EN
Waste management requires effective solutions in terms of environmental protection, and also cost-effective. Among all stages of municipal waste management, transport between collection points and the place of processing, generates a large part of the costs. Based on the literature, different models and methods used for selecting the best route of garbage trucks, including node routing problems and arc routing problems, are presented.
14
Metoda rozwiązywania problemu logistycznego typu TSP z wykorzystaniem grafowej bazy danych
Czerepicki A., Połomski B., Wytrykowska A.
Logistyka
|
2015
|
nr 4
140--145
PL
Artykuł przedstawia koncepcję wykorzystania współczesnej grafowej bazy danych do rozwiązania wybranego problemu logistycznego typu TSP. Sformułowano zadanie algorytmiczne „problemu komiwojażera”. Zaproponowano model danych opisujący problem z wykorzystaniem elementów struktury grafowej bazy danych. Zaimplementowano zapytania w języku grafowej bazy danych realizujące wybrane kroki algorytmu rozwiązania problemu. Oszacowano perspektywy zastosowania grafowej bazy danych do rozwiązania wybranego rodzaju problemów logistycznych.
EN
The paper presents the concept of using modern graph database, to solve the logistics problem of TSP type. The algorithmic task of "traveling salesman problem" was formulated. A data model that describes the problem using graph database structures was proposed. The graph-oriented queries performing selected steps of the algorithm to solve the problem are implemented. The perspectives of using graph database to solve the selected kind of logistic problems was estimated.
15
Hybrydowy system heurystyk przeszukiwania lokalnego dla symetrycznego TSP
Szatkiewicz T., Szafraniec F.
Logistyka
|
2015
|
nr 4
5914--5923, CD 2
PL
W artykule dokonano szczegółowej analizy mocnych i słabych stron heurystyk przeszukiwania lokalnego dla problemu komiwojażera. Analiza ta pozwoliła na opracowanie dwóch nowych heurystyk przeszukiwania lokalnego – LLS i CLS, które szczegółowo opisano.
EN
We described twno brand new local search heuristics for travelling salesman problem. We show that the LLS and CLS local search heuristics joint in one hybrid system can solve TSP better than known 2-opt, 3-opt standar heuristics.
16
Content available W poszukiwaniu optymalnej trasy – wybrane algorytmy w zastosowaniu do problemu komiwojażera
Jakubowska A., Piechocka K.
Journal of TransLogistics
|
2015
|
Vol. 1, nr 1
7--24
PL
Ze względu na dążenie do ograniczenia kosztów logistycznych przedsiębiorstw coraz większego znaczenia nabiera zagadnienie optymalizacji tras. Coraz częściej wykorzystuje się w tym celu rozwiązania heurystyczne oparte na sztucznej inteligencji. Uwzględniając duży stopień trudności w tym zakresie, szczególnie istotne jest wykorzystanie wsparcia informatycznego. Niniejsza praca przedstawia problem komiwojażera oraz możliwość jego rozwiązania za pomocą algorytmów heurystycznych. Szerzej zaprezentowano algorytmy mrówkowy oraz genetyczny.
EN
Due to striving for reducing the logistic cost of enterprises, the route optimisation issue becomes more and more important. For this purpose heuristic solutions based on artificial intelligence are often used. Taking into account the high difficulty of optimization problems, it is particularly important to use IT support. This paper presents the Traveling Salesman Problem and the idea of heuristic algorithms used to solve this problem. More detailed were presented Ant Colony Optimization Algorithm and Genetic Algorithm.
17
Content available Rozwiązywanie problemu komiwojażera za pomocą LP/Quadratic Solver z Analytic Solver Platform v12.5
Węgrzyn J.
Gospodarka Materiałowa i Logistyka
|
2014
|
nr 10
11--19
PL
W artykule przedstawiono wyniki rozwiązań przykładów Problemu Komiwojażera (TSP). Uzyskano je za pomocą LP/Quadratic Solver wchodzącego w skład Analytic Solver Platform v12.5. LP/Quadratic Solver zaprojektowany do rozwiązywania problemów LP/MIP pozwala na rozwiązanie TSP w postaci modelu programowania całkowitoliczbowego. Rozwiązania uzyskano w oparciu: o wprowadzony do Excela 2010 model problemu przydziału z warunkami ograniczającymi Millera, Tuckera i Zemlina eliminującymi podcykle. Przedstawiono czasy rozwiązań symetrycznych i asymetrycznych przykładów TSP z TSPLIB o małych rozmiarach, ograniczonych przez maksymalną liczbę zmiennych całkowitoliczbowych w LP/Quadratic Solver.
EN
The solutions of results of Traveling Salesperson Problem (TSP) samples are presented in this article. Their were received using LP/Quadratic Solver included in Analytic Solver Platform V12.5. LP/Quadratic Solver designed for solutions of LP/MIP problems allow to solve TSP as integer programming model. Solutions were received based on Assignment Problem with Miller, Tucker, Zemlin subtour eliminating constraints model introduced to Excel 2010. Solved times of symmetric and asymmetric TSP samples from TSPLIB with small size of problems, limited by max integer variables of LP/Quadratic Solver are presented.
18
Content available Problem komiwojażera na przykładzie przedsiębiorstwa mleczarskiego
Roman M.
Gospodarka Materiałowa i Logistyka
|
2014
|
nr 11
38--43
PL
Celem artykułu było opracowanie projektu obsługi transportowej dla Okręgowej Spółdzielni Mleczarskiej z wykorzystaniem zagadnienia wielu komiwojażerów. W artykule obliczono przybliżone całkowite koszty realizacji przewozu i porównano je z obecnie ponoszonymi kosztami z tytułu outsourcingu procesów dystrybucji. Do rozwiązania zadania optymalizacyjnego komiwojażera wykorzystano program komputerowy.
EN
The purpose of the article was to develop transport service for the Okręgowa Spółdzielnia Mleczarska using multiple traveling salesmen problems. In the paper calculated the approximate total costs of the transport and compared with current costs incurred in respect of the distribution process outsourcing. To solve the optimization task traveling salesman used a computer program.
19
Content available Aplikacja wyszukiwania i wizualizacji trasy dla przewoźników samochodowych
Ratuszniak P., Gątnicki Ł.
Zeszyty Naukowe Wydziału Elektroniki i Informatyki Politechniki Koszalińskiej
|
2013
|
Nr 5
115--125
PL
W artykule zaprezentowano praktyczną implementację algorytmu genetycznego do rozwiązywania problemu optymalizacji trasy analogicznego do problemu komiwojażera. Algorytm został zaimplementowany w autorskiej aplikacji do wyznaczania trasy przejazdu dla rzeczywistych danych geograficznych polskich miejscowości pobieranych z serwisu Google Maps. Prezentowana aplikacja generuje wskazówki dojazdu i umozliwia export wyznaczonej trasy do programu Automapa, co stanowi jego doskonałe uzupełnienie.
EN
The paper presents a practical implementation of a genetic algorithm to solve the problem of route optimization analogous to the traveling salesman problem. The algorithm has been implemented in the author's application for route calculation for the real Polish geographic data retrieved from Google Maps service. Presented application generates travel directions in the text and graphic form and allows to export the computed route to the Automapa program, which is his perfect complement.
20
Content available Zastosowanie problemu komiwojażera z profitami i oknami czasowymi do wyznaczania tras atrakcyjnych turystycznie okolic Białegostoku
Karbowska-Chilińska J., Zabielski P.
Symulacja w Badaniach i Rozwoju
|
2013
|
Vol. 4, nr 2
81--89
PL
Problem komiwojażera z profitami i oknami czasowymi jest dogodnym modelem dla problemu optymalnego planowania tras atrakcyjnych turystycznie. W pracy przedstawiono rozwiązanie tej odmiany problemu komiwojażera za pomocą algorytmu genetycznego GAPR. W miejsce krzyżowania zaproponowano wymianę obiektów między losowo wybranymi trasami. Rozwiązanie przetestowano na rzeczywistej sieci obiektów turystycznych okolicy Białegostoku. W wyniku testów otrzymano trasy o porównywalnej atrakcyjności jak w algorytmie genetycznym GA z krzyżowaniem (różnica jest na korzyść GAPR około 0.5%) i czasem generowania trasy nie przekraczającym 1.5 sekundy. Algorytm może być zastosowany w planerach tras turystycznych.
EN
Orienteering problem with time windows (OPTW) is a good model for the tour planning problem. In this article a genetic algorithm with path relinking (GAPR) is used for solving OPTW. The path relinking (PR) process is applied instead of a crossover. The solution has been tested on a real network of tourist points of interests in Bialystok region. Routes which are the test results are comparable with the routes generated by the previous GA with crossover (the GAPR exceeds profit result about 0.5% relative to GA, the execution time of GAPR does not exceed 1.5 s). The algorithm can be used in trip planners.
first rewind previous Strona / 2 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ć.