[Back]

A. Sramko:
"Enhancing a genetic algorithm by a complete solution archive based on a trie data structure";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2009; final examination: 2009-02.

Within this thesis a real-world problem related to a warehouse for spare parts is
considered. Regarding several constraints typically stated by spare parts suppliers the
time needed to collect articles should be minimized. Based on continuously arriving
orders by customers prede ned delivery times and capacity constraints have to be
met. To accomplish this task e cient pickup tours need to be determined which is
the main issue covered by this work which comes to an end with experimental results
of a concrete implementation of the proposed approach.
The algorithm presented embeds a speci cally developed dynamic program for computing
optimal walks through the warehouse into a general variable neighborhood
search (VNS) scheme. Several stages are used for rst splitting up all orders, then
creating tours out of the results and nally assigning them to available workers. The
VNS uses a variant of the variable neighborhood descent (VND) as local improvement
procedure. While the neighborhood structures de ned are intended to produce
candidate solutions, a dynamic program specially designed to compute optimal order
picking tours is used to evaluate them. For this purpose properties speci c to warehouses
are exploited such to compute optimal routes within polynomial time. The
nal assignment of workers to tours is realized by another VNS. The task is then to
nd an allocation such that the last article to be picked up will be collected as early
as possible.
Evaluations of experimental results of a concrete implementation indicate that the
presented approach provides valuable pickup plans and computation times can be
kept low. Moreover the performed test runs have been compared to a reference solution
which was computed based on an approach found in relevant literature. A
detailed analysis of the obtained results showed that the application of the proposed
approach to real-world instances is promising whereas the savings with respect to
working time can be kept high. Overall an e cient as well as e ective approach is
introduced to solve this real-world problem.

http://publik.tuwien.ac.at/files/PubDat_175430.pdf