Change search
ReferencesLink to record
Permanent link

Direct link
Parameter Tuning Experiments of Population-based Algorithms
Mid Sweden University, Faculty of Science, Technology and Media, Department of Information Technology and Media.
2011 (English)Independent thesis Basic level (degree of Bachelor), 30 credits / 45 HE creditsStudent thesis
Abstract [en]

In this study, three different algorithms are implemented to solve thecapacitated vehicle routing problem with and without time windows:ant colony optimization, a genetic algorithm and a genetic algorithmwith self-organizing map. For the capacitated vehicle routing problemthe Augerat et al’s benchmark problems were used and for the capaci-tated vehicle routing problem with time windows the Solomon’sbenchmark problems. All three algorithms were tuned over thirtyinstances per problem with the tuners SPOT and ParamILS. The tuningresults from all instances were combined to the final parameter valuesand tested on a larger set of instances. The test results were used tocompare the algorithms and tuners against each other. The ant colonyoptimization algorithm outperformed the other algorithms on bothproblems when considering all instances. The genetic algorithm withself-organizing map found more best known solutions than any otheralgorithm when using parameters, on the capacitated vehicle routingproblem. The algorithms performed well and several new best knownresults were discovered for the capacitated vehicle routing problem andnew best solutions found by heuristics were discovered for the 100customer Solomon problems. When comparing the tuners they bothworked well and no clear winner emerged.

Place, publisher, year, edition, pages
2011. , 104 p.
Keyword [en]
Artificial Intelligence, Ant Colony Optimization, Genetic Algorithm, Self-Organizing Map, Capacitated Vehicle Routing Problem, Capacitated Vehicle Routing Problem with Time Windows, SPOT, ParamILS.
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:miun:diva-13836OAI: oai:DiVA.org:miun-13836DiVA: diva2:419232
Uppsok
Technology
Supervisors
Examiners
Available from: 2011-06-08 Created: 2011-05-26 Last updated: 2012-07-25Bibliographically approved

Open Access in DiVA

fulltext(4143 kB)336 downloads
File information
File name FULLTEXT01.pdfFile size 4143 kBChecksum SHA-512
9c4f14a8071c9390b96958181546e3399f0c6e85abb819d0ae3428c0a40248820d37c4d34dd65b1b4bd0bc6bd9f671dbd0e5cc22216b8f4f5659e37d5d490f0c
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology and Media
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 336 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 226 hits
ReferencesLink to record
Permanent link

Direct link