Solving vehicle routing problems and algorithm implementation on GPU
| Thesis title: | Využití grafických procesorů v úlohách celočíselného programování |
|---|---|
| Author: | Hájek, Jan |
| Thesis type: | Diplomová práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Černý, Michal |
| Thesis language: | Česky |
| Abstract: | Š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. |
| Keywords: | grafická výpočetní jednotka; větvení a mezí; obchodní cestující |
| Thesis title: | Solving vehicle routing problems and algorithm implementation on GPU |
|---|---|
| Author: | Hájek, Jan |
| Thesis type: | Diploma thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Černý, Michal |
| Thesis language: | Česky |
| Abstract: | 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: | graphics processing unit; branch and bound; travelling salesman problem |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 23. 3. 2010 |
|---|---|
| Date of submission: | 5. 1. 2011 |
| Date of defense: | 25. 1. 2012 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/27160/podrobnosti |