Original title: Využití grafických procesorů v úlohách celočíselného programování
Translated title: Solving vehicle routing problems and algorithm implementation on GPU
Authors: Hájek, Jan ; Fábry, Jan (advisor) ; Černý, Michal (referee)
Document type: Master’s theses
Year: 2010
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
Široká podskupina okružních úloh z teorie grafů je častým problémem, který řeší přepravní firmy, letecké společnosti, hi-tech firmy pro plánování výroby plošných spojů nebo společnosti z úplně jiného hospodářského odvětví. Během dřívějších nejrůznějších výzkumů těchto úloh bylo provedeno mnoho analýz a představeno mnoho způsobů řešení, jejichž nástin je uveden v této práci. Některé z nich podávají lepší či horší výsledky v delším či kratším výpočetním čase. Přestože se výkon procesorů a současných technologií nadále zvyšuje, je s některými algoritmy obtížné se dopočítat výsledku v rozumném čase. Proto se práce zabývá otázkou, zda je možné nalézt vhodný algoritmus, který by bylo možné aplikovat na jiné a rychlejší struktury výpočetních jednotek tak, aby se zajistilo mnohonásobné zvýšení výpočetní rychlosti než doposud. Pro tento výzkum byl vytvořen a implementován testovací algoritmus metody větvení a mezí s maticovou redukcí sazeb, který byl podroben počítačovým experimentálním testům, jejichž důsledky jsou zde uvedeny. A very wide-ranging subgroup of vehicle routing problems from the graph theory is a common and frequent problem handled daily by transport companies, airline businesses, hi-tech companies with planning drilling of printed circuits boards or other companies from different industries. During numerous previous researches of these problems a lot of analyses were made and many solutions proposed -- of which an outline is in this paper. Some of them giving better or worse results in longer or shorter computing time. In spite of the fact that the processors and new technologies performance is increasing, with some algorithms we cannon compute the result in a reasonable time. That is why this paper is asking a question, if there can be found a fitting algorithm which could be applied on different and faster processing unit structures so it could be ensured a multiple computing speed increase so far. The analysis was carried out using computer experiments on a new build and implemented branch and bound algorithm with a matrix rate reduction.
Keywords: branch and bound; graphics processing unit; travelling salesman problem; grafická výpočetní jednotka; obchodní cestující; větvení a mezí

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/29559

Permalink: http://www.nusl.cz/ntk/nusl-81881


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Master’s theses