PL
 |
EN
Ograniczanie wyników
Czasopisma help
  1. 3 Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
  2. 3 Gospodarka Materiałowa i Logistyka
  3. 3 Material Economy and Logistics Journal
  4. 2 Control and Cybernetics
  5. 2 Prace Naukowe Politechniki Warszawskiej. Elektronika
Więcej...
Autorzy help
  1. 2 Klimek M.
  2. 1 Affenzeller M.
  3. 1 Białogłowski M.
  4. 1 Boryczka U.
  5. 1 Chmiel W.
Więcej...
Lata help
  1. 3 2023
  2. 1 2019
  3. 2 2018
  4. 1 2016
  5. 1 2015
Więcej...
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 26

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  traveling salesman problem
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 Traveling salesman problem parallelization by solving clustered subproblems
Romanuke Vadim
Foundations of Computing and Decision Sciences
|
2023
|
Vol. 48, No. 4
453--481
EN
A method of parallelizing the process of solving the traveling salesman problem is suggested, where the solver is a heuristic algorithm. The traveling salesman problem parallelization is fulfilled by clustering the nodes into a given number of groups. Every group (cluster) is an open-loop subproblem that can be solved independently of other subproblems. Then the solutions of the respective subproblems are aggregated into a closed loop route being an approximate solution to the initial traveling salesman problem. The clusters should be enumerated such that then the connection of two “neighboring” subproblems (with successive numbers) be as short as possible. For this, the destination nodes of the open-loop subproblems are selected farthest from the depot and closest to the starting node for the subsequent subproblem. The initial set of nodes can be clustered manually by covering them with a finite regular-polygon mesh having the required number of cells. The efficiency of the parallelization is increased by solving all the subproblems in parallel, but the problem should be at least of 1000 nodes or so. Then, having no more than a few hundred nodes in a cluster, the genetic algorithm is especially efficient by executing all the routine calculations during every iteration whose duration becomes shorter.
3
Content available Application of genetic algorithms to the traveling salesman problem
Sikora Tomasz, Gryglewicz-Kacerka Wanda
Applied Computer Science
|
2023
|
Vol. 19, no 2
55--62
EN
The purpose of this paper was to investigate in practice the possibility of using evolutionary algorithms to solve the traveling salesman problem on a real example. The goal was achieved by developing an original implementation of the evolutionary algorithm in Python, and by preparing an example of the traveling salesman problem in the form of a directed graph representing Polish voivodship cities. As part of the work an application in Python was written. It provides a user interface which allows to set selected parameters of the evolutionary algorithm and solve the prepared problem. The results are presented in both text and graphical form. The correctness of the evolutionary algorithm's operation and the implementation was confirmed by performed tests. A large number of tested solutions (2500) and the analysis of the obtained results allowed for a conclusion that an optimal (relatively suboptimal) solution was found.
4
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.
5
Content available Dynamics of Stochastic vs. Greedy Heuristics in Traveling Salesman Problem
Białogłowski M., Staniaszek M., Laskowski W., Grudniak M.
Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
|
2018
|
nr 19
7--24
EN
We studied the relative performance of stochastic heuristics in order to establish the relations between the fundamental elements of their mechanisms. The insights on their dynamics, abstracted from the implementation details, may contribute to the development of an efficient framework for design of new probabilistic methods. For that, we applied four general optimization heuristics with varying number of hyperparameters to traveling salesman problem. A problem-specific greedy approach (Nearest Neighbor) served as a reference for the results of: Monte Carlo, Simulated Annealing, Genetic Algorithm, and Particle Swarm Optimization. The more robust heuristics – with higher configuration potential, i.e. with more hyperparameters – outperformed the smart ones, being surpassed only by the method specifically designed for the task.
6
Content available Traveling salesman problem in the function of freight transport optimization
Prokudin G., Chupaylenko O., Dudnik O., Dudnik A., Pylypenko Y.
Journal of Sustainable Development of Transport and Logistics
|
2018
|
Vol. 3, No. 1
29--36
EN
The use of modern information technology means in solving the traveling salesman problem to optimize the routing of freight transportation in international traffic is motivated in this article. The process of solving the traveling salesman problem is automated by modern information technology means, in particular the Delphi Software and the function "Search Solution" in the Microsoft Office Excel table processor. The existing requirements and restrictions on the specificity and dimension of the problem are considered as well.
7
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.
8
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.
9
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.
10
Analiza wydajności przetwarzania danych w chmurze obliczeniowej Windows Azure
Frączek J., Zając Ł.
Studia Informatica
|
2013
|
Vol. 34, nr 2A
97--112
PL
W artykule przedstawiono wyniki badań wydajnościowych dla rozwiązania problemu komiwojażera z wykorzystaniem zrównoleglonej wersji algorytmu genetycznego w środowisku wielordzeniowego serwera lokalnego oraz chmury obliczeniowej Windows Azure. Przeprowadzona analiza wyników umożliwia również dobranie odpowiedniej do określonych zastosowań konfiguracji serwerów w chmurze.
EN
The paper presents the results of performance tests for solving the traveling salesman problem with the use of a parallel version of a genetic algorithm on a local multi-core server, and in the Windows Azure cloud. The analysis of the obtained results allows the selection of a suitable configuration of the servers in the cloud.
11
Content available remote A measure of emergence of a logistic group interaction
Novikov V., Korsuk Y, Shipulina L
LogForum
|
2012
|
Vol. 8, no. 2
109--122
EN
Background: The nature of the relations between group members is a very important part of the integrity of the logistics process. The identification of rating among the participants is certainly the most necessary condition for the quality of the logistics process. It can distinguished four types of emergence rating: direct participation rating, direct impact rating, participation rating and impact rating. The aim of this paper was to create the method to determine the mutual relationships among various elements of logistic group. Methods: The technique is based on the processing of the matrix of pairwise interactions obtained on the basis of a questionnaire survey of all members of the group and expressed as a score on the selected scale of assessments. The computation algorithm is based in particular on the traveling salesman problem using an original method of optimization and is implemented in Visual Studio C #. Results: 16 types of leaderships were distinguished and described by the use of statistical methods. Conclusions: The developed method of calculating the measure of emergence can be used not only for a group of students, but also for the definition of the rate of emergence in any collective system.
PL
Wstęp: Istota zależności pomiędzy członkami grupy jest ważnym elementem spójności procesu logistycznego. Identyfikacja oceny poszczególnych uczestników jest bez wątpienia najważniejszym warunkiem zapewnienia jakości procesu logistycznego. Można wyróżnić cztery rodzaje ocen relacji: bezpośredniego uczestnictwa, bezpośredniego wpływu, uczestnictwa oraz wpływu. Celem pracy było opracowanie metody ustalania wzajemnych zależności pomiędzy poszczególnymi elementami grupy logistycznej. Metody: Zastosowan a metoda jest oparta na macierzy wzajemnych interakcji, jakie zostały otrzymane w wyniku badania ankietowego, obejmującego wszystkich członków grupy i przedstawionego wartościowo na podstawie przyjętej skali pomiarowej. Algorytm wyliczeniowy został w głównej mierze oparty na problemie przedstawiciela handlowego w podróży służbowej jak oryginalna metoda optymalizacji przy użyciu Visual Studio C #. Wyniki: Zostało zidentyfikowanych i opisanych 16 typów przywódczych poprzez zastosowanie odpowiednich metod statystycznych. Wnioski: Uzyskana metoda oceny może być stosowana nie tylko w przypadku grupy studentów ale również w każdym innym złożonym systemie.
12
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.
13
Algorytm ewolucyjny dla problemu komiwojażera z wieloma centrami dystrybucyjnymi
Michlowicz E.
Logistyka
|
2009
|
nr 4
CD-CD
PL
Problem rozdziału zadań przewozowych w typowym zadaniu transportowym jest mało przydatny dla średnich firm transportowych obsługujących wiele centrów dystrybucji. Z kolei problem komiwojażera dotyczy tylko wybranych firm. Połączenie obydwu tych zagadnień może przynieść wiele korzyści. W artykule zaproponowano rozwiązanie problemu przy zastosowaniu algorytmu ewolucyjnego. Przedstawiono formalizację zadania transportowego oraz formułę minimalnej macierzy wykorzystanej do budowy algorytmu genetycznego. Problem komiwojażera został rozważony dla każdego z wybranych centrów dystrybucji towarów.
EN
The problem of allocation tasks in a typical transport issue is not useful for medium-sized transport companies operating multiple distribution centers. The bagman problem affects only the selected companies. The combination of both of these issues can bring many benefits. This paper proposes a solution to the problem using the evolutionary algorithm.
14
Content available Strategia przetwarzania wiedzy w wielopopulacyjnym algorytmie ewolucyjnym
Kadłuczka P., Chmiel W., Piwowarczyk J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
325-331
PL
Artykuł prezentuje koncepcję wielopopulacyjnego, samoadaptacyjnego algorytmu ewolucyjnego, wykorzystującego technologię inteligentnych agentów. Algorytm ten zastosowano dla zagadnienia komiwojażera, należącego do klasy problemów permutacyjnych NP-trudnych. Współbieżna realizacja wielu algorytmów ewolucyjnych pozwala na ich komunikację, mającą na celu udostępnienie informacji dotyczącej dotychczasowego przebiegu obliczeń, uzyskanych rozwiązań oraz oceny aktualnie wykorzystywanych elementów konstrukcyjnych algorytmu. Zróżnicowana strategia przetwarzania i stosowania wiedzy prowadzi do zróżnicowanej efektywności algorytmów i całego systemu.
EN
The paper presents intelligent agent approach to multi-population evolutionary algorithm with self-adaptation. The algorithm was used to solve traveling salesman problem that belongs to the NP-hard permutational problem class, one of the most popular optimization discrete problem. Concurrent system realization allows to exchange data, like solutions, results and parameter estimations between algorithms. The possibility to improve the algorithm and system efficiency is based on the strategy and knowledge processing diversification.
15
Content available Model algebraiczno-logiczny problemu planowania tras dostaw dla m komiwojażerów
Dutkiewicz L., Kucharska E.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2008
|
T. 12, z. 3
933-943
PL
W artykule zaprezentowano ideę modelu algebraiczno-logicznego na przykładzie problemu planowania tras dostaw do firm wielooddziałowych, będącego modyfikacją powszechnie znanego problemu m komiwojażerów. Model algebraiczno-logiczny odpowiada pewnej formalnej postaci wieloetapowego procesu decyzyjnego połączonego z symulacją procesu dyskretnego. Przedstawiona została postać stanu systemu, zbiory stanów docelowych oraz stanów niedopuszczalnych. Dla danego stanu zostały też wyodrębnione pewne zbiory elementów systemu o wspólnych cechach, przydatne do definiowania pozostałych składników modelu. Określona została postać decyzji, zbiór decyzji możliwych do podjęcia w poszczególnych stanach oraz zbiór decyzji dopuszczalnych. Przedstawione zostały elementy składające się na funkcję przejścia, czyli pokazany został sposób wyznaczenia momentu wystąpienia kolejnego stanu oraz podany został szczegółowy wzór na określenie wartości współrzędnych stanu właściwego.
EN
In the article a concept of algebraic-logical model for problem of planning delivery routes to multi-branch companies. This problem is a modification of the well-known m-TSP problem. The algebraic-logical model corresponds to a formal representation of a multistage decision process connected with simulation of a discrete process. There are presented: a state of the system, a set of goal states and a set of not-admissible states. For the current state of the system there are introduced some sets of system elements with analogous features, which are useful in defining other components of the system. There are also specified: a notion of the decision, a set of possible decisions and a set of admissible decisions. Components of the transition function are given: a method of identifying a moment of the next process state and a method of determining values of coordinates of the next state.
16
Content available remote Adaptive Ant Colony Optimization Algorithm Based on Information Entropy: Foundation and Application
Li Y., Li W.
Fundamenta Informaticae
|
2007
|
Vol. 77, nr 3
229-242
EN
In order to solve the premature convergence problem of the basic Ant Colony Optimization algorithm, a promising modification based on the information entropy is proposed. The main idea is to evaluate stability of the current space of represented solutions using information entropy, which is then applied to turning of the algorithm's parameters. The path selection and evolutional strategy are controlled by the information entropy self-adaptively. Simulation study and performance comparison with other Ant Colony Optimization algorithms and other meta-heuristics on Traveling Salesman Problem show that the improved algorithm, with high efficiency and robustness, appears self -adaptive and can converge at the global optimum with a high probability. The work proposes a more general approach to evolutionary-adaptive algorithms related to the population's entropy and has significance in theory and practice for solving the combinatorial optimization problems.
17
Scale free distribution of nodes in Euclidean graphs
Dominik A., Walczak Z., Wojciechowski J., Wojciechowski J.
Prace Naukowe Politechniki Warszawskiej. Elektronika
|
2006
|
z. 156
107-115
EN
In the paper we propose a new model of spatial distribution of nodes in graphs which can be represented in the Euclidean space. Such graphs appear in many areas of computer science, for instance wireless networks design, Traveling Salesman and Vehicle Routing Problems. We show analogies between scale-free and Euclidean graphs. Although the distribution of node's degrees in Euclidean graphs is not scale-free, the spatial distribution of node's follows the power law. We analyze distribution of population density in different continents, propose a model to generate such distributions and provide numerical experiments concerning its quality. Finally, the impact of our model on different NP-complete problems in Euclidean graphs is analyzed.
18
Comparative study : AGO and EC for TSP
Boryczka U., Skinderowicz R., Swistowski D.
Prace Naukowe Politechniki Warszawskiej. Elektronika
|
2006
|
z. 156
69-76
EN
Evolutionary Computing (EC) and Ant Colony Optimization (ACO) apply stochastic searching, parallel investigation as well as autocatalitic process (or stigmergy) to solve optimization problems. This paper concentrates on the Traveling Salesman Problem (TSP) solved by evolutionary and ACO algorithms. We consider the sets of parameters and operators which influence the acting of these algorithms. Two algorithmic structures emphasizing the selection problem are discussed. We describe experiments performed for different instances of TSP problems. The comparison concludes that evolution, which is exploited especially in evolutionary algorithms, can also be observed in the performance of the ACO approach.
19
Content available remote Zadanie rozwózkowe, czyli problem komiwojażera
Sarjusz-Wolski Z.
Gospodarka Materiałowa i Logistyka
|
2006
|
nr 5
31-32
PL
Na początku była gra-łamigłówka, wymyślona w 1859 r. przez sławnego irlandzkiego matematyka, Wiliama Rowana Hamiltona. Składał się na nią dwunastościan, którego każda z 12 ścian była foremnym pięciokątem, a we wszystkich 20 wierzchołkach schodziły się trzy krawędzie. Każdy wierzchołek tej bryły przedstawiał znane duże miasto (Bruksela, Dehli, Frankfurt itd.). Zagadka polegała na znalezieniu takiej trasy podróży, która by zapewniała tylko jednorazową wizytę w każdym mieście. Od niej wzięły swoją nazwę tzw. linie Hamiltona, stanowiące dzisiaj część teorii grafów. Problem komiwojażera ("the traveling salesman problem"), zwany też zadaniem rozwózkowym, przypomina linie Hamiltona, ale jest znacznie utrudniony - trasa (łuki grafu) obejmująca wszystkie punkty (węzły grafu) musi być trasą najkrótszą (ewentualnie generującą minimalne koszty transportu).
20
Content available remote The corridor method: a dynamic programming inspired metaheuristic
Sniedovich M., Viß S.
Control and Cybernetics
|
2006
|
Vol. 35, no 3
551-578
EN
This paper presents a dynamic programming inspired metaheuristic called Corridor Method. It can be classified as a method-based iterated local search in that it deploys method-based neighborhoods. By this we mean that the search for a new candidate solution is carried out by a fully-fledged optimization method and generates a global optimal solution over the neighborhood. The neighborhoods are thus constructed to be suitable domains for the fully-fledged optimization method used. Typically, these neighborhoods are obtained by the imposition of exogenous constraints on the decision space of the target problem and therefore must be compatible with the optimization method used to search these neighborhoods. This is in sharp contrast to traditional metaheuristics where neighborhoods are move-based, that is, they are generated by subjecting the candidate solution to small changes called moves. While conceptually this method-based paradigm applies to any optimization method, in practice it is best suited to support optimization methods such as dynamic programming, where it is easy to control the size of a problem, hence the complexity of algorithms, by means of exogenous constraints. The essential features of the Corridor Method are illustrated by a number of examples, including the traveling salesman problem, where exponentially large neighborhoods are searched by a linear time/space dynamic programming algorithm.
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ć.