Minimising the total travel distance to pick orders on a unidirectional picking line
Date
2012-03
Authors
De Villiers, Anton Pierre
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Order picking is the most important activity in distribution centres. It involves the process of
retrieving products from storage in response to a speci c customer request. The order picking
system in a distribution centre used by Pep Stores Ltd. (Pep), located in Durban, South Africa,
is considered. The order picking system in Pep utilises picking lines. The system requires that
the pickers move in a clockwise direction around the picking line. The planning of picking
lines may be divided into three tiers of decisions. The rst tier determines which Stock Keeping
Units (SKUs) should be allocated to which picking line and is known as the SKU to Picking Line
Assignment Problem (SPLAP). The second tier, the SKU Location Problem (SLP), considers
the positioning of the various SKUs in a picking line. The nal tier considers the sequencing of
the orders for pickers within a picking line and is referred to as the Order Sequencing Problem
(OSP). Collectively, these three tiers aim to achieve the objective of picking all the SKUs
for all the orders in the shortest possible time. The decisions associated with each tier are
made sequentially during the planning of a picking line. Each problem therefore relies on the
information generated by its predecessing tier(s).
Initially the OSP is addressed. A number of heuristic and metaheuristic approaches are presented,
together with an exact formulation to solve this tier. The size of the problem is reduced
by using a relaxation of the problem that may be solved exactly. A number of greedy tour
construction heuristics, a scope and ranking algorithm, methods based on awarding starting
locations with respect to preference ratios and a modi ed assignment approach was used to
solve the OSP. Furthermore, a tabu search, simulated annealing, genetic algorithm and a generalised
extremal optimisation approach are used to solve the OSP. The solution quality and
computational times of all the approaches are compared for the data provided by Pep, with the
generalised extremal optimisation approach delivering the best solution quality.
Two methods from the literature was used to model the SLP, whereafter an ant colony system
was used to maximise the number of orders in common between adjacent SKUs. A number of
agglomerative clustering algorithms were used from which dendrograms could be constructed.
Two novel heuristic clustering algorithms were considered. The rst heuristic calculates a distance
between two clusters as the set of orders that have to collect all the SKUs in both clusters,
whereas the second method is based upon the frequency of SKUs within a cluster. Little or no
improvement was achieved in most cases.
The SPLAP was introduced by means of a number of possibilities of how to formulate objectives.
A possible exact formulation is presented, followed by a nearest neighbour search, which was
initially used to construct new picking lines based on all data sets. A di erent approach was
then taken by means of a tabu search where the waves of two or three picking lines were altered.
Signi cant savings may be incurred for large data sets.
AFRIKAANSE OPSOMMING: Die opmaak van bestellings is die belangrikste aktiwiteit in 'n distribusiesentrum. Dit behels dat geskikte hoeveelhede produkte uit stoorplekke opgespoor en herpak moet word om aan kleinhandeltakke gestuur te word. Die bedrywighede binne een van Pep Stores Ltd. (Pep) se distribusiesentrums in Durban, Suid-Afrika, word beskou. Die sisteem vereis dat die werkers in 'n kloksgewyse rigting om 'n uitsoeklyn beweeg. Die beplanning van die uitsoeklyne kan verdeel word in drie besluite/probleme. Die eerste besluit is watter voorraadeenhede (VEs) toegewys moet word aan watter uitsoeklyn. Die tweede besluit is in watter vakkies in die uitsoeklyn die VEs geplaas moet word, en word die VE-plasings probleem (VLP) genoem. Die nale besluit is in watter volgorde bestellings opgemaak moet word in 'n uitsoeklyn, en staan bekend as die volgorde-van-bestellings-probleem (VBP). Die doel van al drie hierdie probleme is om al die bestellings in 'n uitsoeklyn in die kortste moontlike tyd af te handel. Die besluite wat verband hou met elke vlak van besluit word opeenvolgend gedoen tydens die beplanning van 'n uitsoeklyn. Die oplossing van elke subprobleem berus op die inligting van die voorafgaande probleme. Aanvanlik word die VBP beskou. 'n Aantal heuristiese en metaheuristiese benaderings word aangebied saam met 'n eksakte formulering om die derde vlak op te los. Die grootte van die probleem is verminder deur die gebruik van 'n verslapping van 'n eksakte formulering. 'n Aantal toerkonstruksie heuristieke, 'n omvang en rangorde algoritme, metodes wat gebaseer is op die toekenning van beginpunte met betrekking tot voorkeurverhoudings en 'n veralgemeende toewysingsprobleem is gebruik om die VBP op te los. 'n Tabu-soektog, gesimuleerde tempering, genetiese algoritme en 'n veralgemeende-ekstreme-optimering-benadering word ook gebruik om die VBP op te los. Die oplossingsgehalte en berekeningstye van al die benaderings word vergelyk vir werklike data wat verskaf is deur Pep. Die veralgemeende-ekstreme-optimering-benadering lewer die beste oplossingsgehalte. Twee metodes uit die literatuur is gebruik om die VLP te modelleer, waarna 'n mier kolonie stelsel gebruik word om die aantal bestellings wat aangrensende VEs in gemeen het te maksimeer. 'n Aantal groeperingsalgoritmes word gebruik wat dendrogramme kan lewer. Twee heuristiese groeperingsalgoritmes word oorweeg. Die eerste heuristiek bereken die afstand tussen twee groepe as die aantal bestellings wat al die VEs in beide groepe moet versamel, terwyl die tweede metode gebaseer is op die frekwensie van VEs binne 'n groep. Min of geen verbeterings is in die meeste gevalle gevind. Die eerste besluit word bekend gestel na aanleiding van 'n aantal moontlike maniere om die doelwitte te formuleer. 'n Moontlike eksakte formulering word aangebied. 'n Alternatiewe benadering is geneem deur middel van 'n tabu-soektog waar die golwe van twee of drie uitsoeklyne gewysig word. Beduidende besparings word gerealiseer vir groot datastelle.
AFRIKAANSE OPSOMMING: Die opmaak van bestellings is die belangrikste aktiwiteit in 'n distribusiesentrum. Dit behels dat geskikte hoeveelhede produkte uit stoorplekke opgespoor en herpak moet word om aan kleinhandeltakke gestuur te word. Die bedrywighede binne een van Pep Stores Ltd. (Pep) se distribusiesentrums in Durban, Suid-Afrika, word beskou. Die sisteem vereis dat die werkers in 'n kloksgewyse rigting om 'n uitsoeklyn beweeg. Die beplanning van die uitsoeklyne kan verdeel word in drie besluite/probleme. Die eerste besluit is watter voorraadeenhede (VEs) toegewys moet word aan watter uitsoeklyn. Die tweede besluit is in watter vakkies in die uitsoeklyn die VEs geplaas moet word, en word die VE-plasings probleem (VLP) genoem. Die nale besluit is in watter volgorde bestellings opgemaak moet word in 'n uitsoeklyn, en staan bekend as die volgorde-van-bestellings-probleem (VBP). Die doel van al drie hierdie probleme is om al die bestellings in 'n uitsoeklyn in die kortste moontlike tyd af te handel. Die besluite wat verband hou met elke vlak van besluit word opeenvolgend gedoen tydens die beplanning van 'n uitsoeklyn. Die oplossing van elke subprobleem berus op die inligting van die voorafgaande probleme. Aanvanlik word die VBP beskou. 'n Aantal heuristiese en metaheuristiese benaderings word aangebied saam met 'n eksakte formulering om die derde vlak op te los. Die grootte van die probleem is verminder deur die gebruik van 'n verslapping van 'n eksakte formulering. 'n Aantal toerkonstruksie heuristieke, 'n omvang en rangorde algoritme, metodes wat gebaseer is op die toekenning van beginpunte met betrekking tot voorkeurverhoudings en 'n veralgemeende toewysingsprobleem is gebruik om die VBP op te los. 'n Tabu-soektog, gesimuleerde tempering, genetiese algoritme en 'n veralgemeende-ekstreme-optimering-benadering word ook gebruik om die VBP op te los. Die oplossingsgehalte en berekeningstye van al die benaderings word vergelyk vir werklike data wat verskaf is deur Pep. Die veralgemeende-ekstreme-optimering-benadering lewer die beste oplossingsgehalte. Twee metodes uit die literatuur is gebruik om die VLP te modelleer, waarna 'n mier kolonie stelsel gebruik word om die aantal bestellings wat aangrensende VEs in gemeen het te maksimeer. 'n Aantal groeperingsalgoritmes word gebruik wat dendrogramme kan lewer. Twee heuristiese groeperingsalgoritmes word oorweeg. Die eerste heuristiek bereken die afstand tussen twee groepe as die aantal bestellings wat al die VEs in beide groepe moet versamel, terwyl die tweede metode gebaseer is op die frekwensie van VEs binne 'n groep. Min of geen verbeterings is in die meeste gevalle gevind. Die eerste besluit word bekend gestel na aanleiding van 'n aantal moontlike maniere om die doelwitte te formuleer. 'n Moontlike eksakte formulering word aangebied. 'n Alternatiewe benadering is geneem deur middel van 'n tabu-soektog waar die golwe van twee of drie uitsoeklyne gewysig word. Beduidende besparings word gerealiseer vir groot datastelle.
Description
Thesis (MSc)--Stellenbosch University, 2012.
Keywords
Travel distance, Order picking systems, Dissertations -- Operations research, Theses -- Operations research, Dissertations -- Logistics, Theses -- Logistics