Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A comparative study between a genetic algorithm and a simulated annealing algorithm for solving the order batching problem
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförande studie mellan en genetisk algoritm och simulated annealing för att lösa order batching problemet (Swedish)
Abstract [en]

Optimizing warehouse automation requires finding efficient routes for pickingup items. Dividing the orders into batches is a realistic requirement for warehouses to have. This problem, known as the order batching problem, is an NP-hard problem. This thesis implements and compares two meta-heuristics to the order batching problem, simulated annealing (SA) and a genetic algorithm(GA). SA was found to perform equal to or better than GA on all occasions in terms of minimizing traveling distance. The algorithms were tested on 6 different warehouses with various layouts. The algorithms performed similarly on the smallest problem size, but in the largest problem size SA managed to find 17.1 % shorter solutions than GA. SA tended to find shorter solutions in a smaller amount of time as well.

Abstract [sv]

Optimering av automatiserade varuhuslager kräver att effektiva rutter hittas för att hämta upp varor. Att dela upp ordrarna i grupper är ett realistiskt krav som lager kan ha. Detta problem, som kallas för order batching-problemet, är ett NP-svårt problem. Detta kandidatarbete jämför två implementationer av meta-heuristiker till order batching-problemet, simulated annealing (SA) och genetic algorithm (GA).

SA visade sig vara lika bra eller bättre än GA vid alla tillfällen då målet är att minimera den totala färdsträckan. Algoritmen testades på 6 olika varuhus som hade olika designer. Algoritmerna kom fram till liknande lösningar för de minsta varuhusen, men i det största varuhuset lyckades SA hitta en lösning som var 17.1 % bättre än GA. SA tenderade även att hitta kortare lösningar givet mindre tid.

Place, publisher, year, edition, pages
2019.
Series
TRITA-EECS-EX ; 2019:313
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-254929OAI: oai:DiVA.org:kth-254929DiVA, id: diva2:1336286
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2019-07-29 Created: 2019-07-09 Last updated: 2019-07-29Bibliographically approved

Open Access in DiVA

fulltext(858 kB)22 downloads
File information
File name FULLTEXT01.pdfFile size 858 kBChecksum SHA-512
105969a560146f0dc9101af5457c97a9c6b2d03e91dbdacd8412398b8c44d12df2fc80a4aa5ff39119564f91e48017c5cb4ee74b099050fc0415b8e06ba94ec7
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 22 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

urn-nbn

Altmetric score

urn-nbn
Total: 100 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf