Retrieval optimization in a warehouse with multiple input/output-points

Buckow, Jan-Niklas; Goe igk, Ma c; Knus , Sig id
A icle — Published Ve sion
Re ie al op imiza ion in a wa ehouse wi h mul iple inpu /
ou pu -poin s
OR Spec um
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Buckow, Jan-Niklas; Goe igk, Ma c; Knus , Sig id (2024) : Re ie al op imiza ion
in a wa ehouse wi h mul iple inpu /ou pu -poin s, OR Spec um, ISSN 1436-6304, Sp inge , Be lin,
Heidelbe g, Vol. 47, Iss. 1, pp. 1-34,
h ps://doi.o g/10.1007/s00291-024-00775-x
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323269
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Vol.:(0123456789)
OR Spec um (2025) 47:1–34
h ps://doi.o g/10.1007/s00291-024-00775-x
ORIGINAL ARTICLE
Re ie al op imiza ion inawa ehouse wi hmul iple inpu /
ou pu ‑poin s
Jan‑NiklasBuckow1· Ma cGoe igk2· Sig idKnus 1
Recei ed: 22 Decembe 2023 / Accep ed: 31 May 2024 / Published online: 18 June 2024
© The Au ho (s) 2024
Abs ac
Op imizing e ie al eques s in wa ehouses is essen ial o main aining a smoo h
low o p oduc s. Mos s udies on wa ehouse e ie al op imiza ion ha e conside ed
no mo e han wo inpu /ou pu -poin s o p oduc e ie al. In his pape , we s udy
di e en a ian s o a new s acke c ane scheduling p oblem, whe e palle s ha e o
be e ie ed in a wa ehouse wi h mul iple inpu /ou pu -poin s. The goal is o mini-
mize he o al a el ime o he s acke c ane o pe o m all e ie als. The p ob-
lem a ian s we conside equi e de e mining ei he he palle e ie al sequence, he
assignmen o palle s o inpu /ou pu -poin s, o bo h. We p o e NP-ha dness esul s
and iden i y cases ha can be sol ed in s ongly polynomial ime. Addi ionally, we
p opose ans o ma ions o he a eling salesman p oblem, enabling he applica ion
o a as collec ion o exis ing solu ion echniques. Finally, in an ex ensi e compu-
a ional s udy, we compa e di e en p oblem a ian s, assess hei gain o op imiza-
ion, and expe imen ally analyze he impac o a ious ins ance pa ame e s.
Keywo ds Logis ics· Wa ehouse· Re ie al op imiza ion· Mul iple inpu /ou pu -
poin s
* Jan-Niklas Buckow
jabuckow@uni-osnab ueck.de
Ma c Goe igk
[email p o ec ed]
Sig id Knus
[email p o ec ed]
1 Ins i u e o Compu e Science, Osnab ück Uni e si y, Wachsbleiche27, 49090Osnab ück,
Ge many
2 Business Decisions andDa a Science, Uni e si y o Passau, D .-Hans-Kap inge -S aße 30,
94032Passau, Ge many
2
J.-N.Buckow e al.
1 In oduc ion
The s o age and subsequen e ie al o i ems in wa ehouses is c ucial o ensu -
ing a smoo h low o p oduc s in supply chains. To inc ease he e iciency, wa e-
houses o en use au oma ed s o age/ e ie al sys ems (AS/RS), whe e all incom-
ing i ems a e ans e ed on uni o m palle s. In such s o ages, he e a e wo ypes
o eques s: s o age eques s and e ie al eques s. Fo a s o age eques , a palle
is mo ed by an au oma ically con olled s acke c ane om an inpu /ou pu -poin
(I/O-poin ) o a loca ion wi hin he wa ehouse. Mo eo e , o a e ie al eques ,
he s acke c ane e u ns a palle o an I/O-poin . To ob ain mo e de ails on wa e-
houses wi h AS/RS, we e e o he su ey pape s by Boysen and S ephan (2016)
as well as Roodbe gen and Vis (2009).
1.1 Mo i a ion
Ou wo k was ini ially mo i a ed by a p oblem se ing we encoun e ed a an
indus ial company ope a ing a high-bay wa ehouse wi h AS/RS. Ne e heless,
he scope o ou indings eaches beyond his speci ic con ex . The p oblem we
iden i ied and subsequen ly s udied has b oad applicabili y ac oss a ange o se -
ings, e en hose ha do no in ol e wa ehouses, as we will illus a e la e . Fo
cla i y and ease o unde s anding, we will keep using e minology ela ed o
wa ehouses.
A he a o emen ioned indus ial company, we disco e ed a wa ehouse wi h
h ee di e en I/O-poin s and he ollowing s acke c ane scheduling p oblem.
Ini ially and inally, he s acke c ane is loca ed a a speci ic depo I/O-poin .
A gi en se o e ie al eques s has o be p ocessed, whe e each palle o be
e ie ed can be e u ned o an a bi a y I/O-poin . When app oaching an I/O-
poin , he s acke c ane d ops he palle o be e ie ed he e and picks up a palle
o be s o ed. I hen mo es o he nex palle o be e ie ed in he wa ehouse and
swaps i wi h he palle o be s o ed cu en ly loaded on he s acke c ane (i has
an addi ional bu e loca ion o pe o m such swaps).
Each palle o be e ie ed will be e u ned o he s o age a e an employee
has emo ed speci ic pa s om i used in a u he p oduc ion p ocess. Conse-
quen ly, a each I/O-poin , exac ly he palle ha was p e iously e ie ed he e is
a ailable as a s o age eques . This means ha he e ie al eques s a e au oma i-
cally synch onized wi h he numbe o s o age eques s wai ing a he I/O-poin s.
The e o e, o a p ocessing sequence o e ie al eques s and hei assignmen o
I/O-poin s, he s o age eques s esul implici ly and do no ha e o be conside ed
explici ly. Mo eo e , o op imize s o age loca ions based on he e ie al equen-
cies o he palle s, he company egula ly ea anges he assignmen o palle s o
s o age loca ions, o ins ance du ing b eaks o a nigh . The desc ibed p ocess is
called wa ehouse eshu ling (Pazou and Ca lo 2015; Buckow and Knus 2023a,
b), and i ensu es ha high equency e ie al eques s can be pe o med as
wi hou conside ing he selec ion o s o age loca ions o s o age eques s.
3
Re ie al op imiza ion inawa ehouse wi hmul iple…
The goal is o minimize he makespan, i.e., he o al a el ime o he s acke
c ane o pe o m all e ie al eques s o he cu en shi . Howe e , e en i he
a el ime is he key pe o mance measu e in he company’s p oblem se ing,
ou app oaches can also handle o he pe o mance measu es ins ead, such as he
s acke c ane’s ene gy consump ion o i s wea and ea . In he ollowing, we
hence use he mo e gene al e m a el cos s ins ead o a el ime, highligh ing
ha we simply can use ano he pe o mance measu e wi hou a ec ing he co -
ec ness o ou p oposed me hodology.
Fo example, Fig.1 shows a easible s acke c ane ou p ocessing ou pal-
le e ie al eques s in a wa ehouse wi h h ee I/O-poin s ( he le mos I/O-poin
se es as depo whe e he s acke c ane ou s a s and ends). The numbe s indi-
ca e he sequence in which he s acke c ane a e ses he ou .
The indus ial company men ioned ope a es a la ge high-bay acking using a
s acke c ane equipped wi h an addi ional bu e loca ion. This de ice is designed
o swap he palle cu en ly loaded on he s acke c ane wi h a palle a a s o -
age loca ion. We know om he s acke c ane’s manu ac u e ha o he compa-
nies ope a e simila wa ehouses. These i ms a e p edominan ly engaged in sec-
o s such as he me al indus y o he p oduc ion o windows and doo s. Since
hey handle hea y palle s, i is no easible o use he s acke c ane’s inc eased
capaci y o anspo wo palle s a once. The e o e, palle swaps a e he ope a ing
mode o choice in such wa ehouses (Buckow and Knus 2023b, a).
No e ha his se ing can also be used o model o he p oblems. Fo example,
besides he scena io discussed abo e, i also applies o wa ehouses wi h s acke
c anes o capaci y one when only e ie al eques s ha e o be pe o med. This
is possible because he s acke c ane can simply omi picking up a palle when
eaching an I/O-poin , while s ill isi ing palle s and I/O-poin s al e na ely in he
ou . Fu he mo e, he desc ibed p oblem can be used o model speci ic ans-
po a ion p oblems ou side o wa ehouses, such as anspo ing pa ien s o heal h
ca e acili ies. In his scena io, di e en pa ien s a e loca ed in di e en places
and a single ambulance, capable o anspo ing only one pa ien a a ime, mus
anspo each pa ien o one o se e al heal hca e acili ies. The ambulance s a s
and ends i s ou a a gi en acili y, and he goal is o minimize he ime i akes o
comple e he anspo o all pa ien s. This can be modeled by ou p oblem, wi h
he pa ien s co esponding o e ie al eques s and he acili ies co esponding o
I/O-poin s.
Fig. 1 S acke c ane ou
p ocessing ou palle e ie al
eques s. Numbe s indica e he
o de o mo emen s
4
J.-N.Buckow e al.
Ou p oblem can also be in e p e ed as a new a ian o he bipa i e a eling
salesman p oblem (
TSP
). In he bipa i e
TSP
, wo node se s o equal size and a el
cos s be ween he nodes a e gi en, and he goal is o ind a minimum cos ou ha
isi s each node exac ly once, whe e nodes om he wo se s mus be isi ed al e -
na ely. Fo mo e de ails on he bipa i e
TSP
, we e e o Ga cía and Tejel (2017),
Ko ács e al (2018) and F ank e al (1998). In he case o ou p oblem, we also aim
o ind a minimum cos ou ha al e na ely isi s palle s and I/O-poin s. Howe e ,
in con as o he bipa i e
TSP
, I/O-poin s a e allowed o be isi ed any numbe o
imes, while each palle mus be isi ed exac ly once.
Depending on he eal-wo ld scena io o be modeled, each palle may only be
allowed o be e ie ed a a speci ic I/O-poin . This is he case, o example, i he
palle has o be p ocessed on a machine ha is loca ed in a p oduc ion hall which
can only be eached ia a speci ic I/O-poin . Simila ly, each palle may need o be
e ie ed a a speci ic I/O-poin because he e a speci ic uck is loaded. In addi ion,
a sequence may be gi en in which he palle s ha e o be e ie ed. Fo example,
he machines in he p oduc ion p ocess may equi e he palle s in a speci ic o de .
Besides he basic p oblem scena io desc ibed abo e, we hence also s udy he p ob-
lem scena ios ha he palle e ie al sequence and/o he assignmen o palle s o
I/O-poin s is ixed.
1.2 Li e a u e e iew
A lo o li e a u e has ackled s acke c ane scheduling p oblems o op imize s o age
and e ie al eques s in wa ehouses wi h a single I/O-poin (Boysen and S ephan
2016). These p oblems mainly deal wi h inding an app op ia e sequence in which
he s o age and e ie al eques s a e p ocessed by he s acke c ane. The s acke
c ane can he eby be ope a ed in wo di e en ways, namely in a single command
cycle o in a dual command cycle. In a single command cycle, he s acke c ane
pe o ms ei he a single s o age o a single e ie al eques . In a dual command
cycle, he s acke c ane pe o ms a combined s o age and e ie al eques . Fi s , he
s acke c ane picks up a palle o be s o ed a an I/O-poin and b ings i o an emp y
loca ion. A e wa ds, he s acke c ane mo es unloaded o he loca ion o a e ie al
eques and e u ns he palle he e o an I/O-poin .
Some mode n wa ehouses (e.g., he indus ial company men ioned abo e) a e
equipped wi h a s acke c ane classi ied as a win shu le o some imes also called
dual shu le (Kese la and Pe e s 1994; Malmbo g 2000; Melle and Mungwa ana
1997). Because a win shu le has an addi ional bu e , i can pe o m swap mo es
whe e he s acke c ane di ec ly swaps he palle a a s o age loca ion wi h he palle
cu en ly s o ed in i s bu e (Buckow and Knus (2023b, 2023a)). By using swap
mo es when pe o ming dual command cycles, he unloaded a el can be com-
ple ely elimina ed by di ec ly swapping he palle o be s o ed wi h he palle o
be e ie ed. Mo eo e , no e ha he handling e o o he dual command cycles
only depends on he e ie al eques s when using swap mo es, because he palle
e ie al loca ions a e used o s o e he nex palle s. Howe e , ecall ha in he p ob-
lem se ing o he company men ioned abo e, hey a e handling hea y palle s, and i

5
Re ie al op imiza ion inawa ehouse wi hmul iple…
is hence no possible o combine wo s o age and wo e ie al eques s o one com-
mand cycle, e en wi h wo palle posi ions on he s acke c ane.
The e a e ew s udies on he op imiza ion o s o age and e ie al eques s in
wa ehouses wi h mo e han one I/O-poin . None heless, he publica ions on he
s acke c ane scheduling p oblems mos simila o ou s a e summa ized in Table1,
including a b ie desc ip ion o he p oblem cha ac e is ics, hei complexi y and
he solu ion me hods applied. O he complexi y esul s o ela ed p oblems a e p e-
sen ed byBoysen and S ephan (2016). Van den Be g and Gademann (1999) conside
a specialized scena io whe e he inpu and he ou pu poin a e sepa a ed loca ions,
i.e., all s o age eques s s a a he inpu poin , and all e ie al eques s ha e o be
b ough o he ou pu poin . They assume ha he a i al sequence o he s o age
eques s is ixed, and p esen a polynomial- ime algo i hm o sol e hei p oblem
op imally. Bo h Vis and Roodbe gen (2009) as well as Vis and Ca lo (2010) con-
side a con aine s o age wi h mul iple ows each ha ing wo I/O-poin s. On he one
hand, Vis and Roodbe gen (2009) s udy he case wi h a single s acke c ane, and
hey decompose hei p oblem in o single- ow blocks whe e all eques s a e loca ed
on a line. Mo eo e , hey combine a linea assignmen and a dynamic p og amming
app oach o sol e hei p oblem e icien ly. On he o he hand, Vis and Ca lo (2010)
ex end he desc ibed se ing o he case wi h wo coo pe a ing s acke c anes, and
hey de eloped a simula ed annealing heu is ic o hei p oblem.
In he case o wo I/O-poin s and a bi a y posi ions o he eques s, Gha ehgozli
e al (2014b) p esen polynomial- ime algo i hms o minimize he o al a el ime
o he s acke c ane. Man e al (2021) s udy a bi-objec i e s acke c ane schedul-
ing p oblem o op imize s o age and e ie al eques s in a wa ehouse wi h wo I/O-
poin s. They conside he wo objec i es o minimizing he o al a el ime and he
o al a diness. Yu e al (2022) p esen models o he expec ed a el ime in wa e-
houses wi h wo I/O-poin s and a class-based s o age policy, i.e., he s o age is pa -
i ioned in o di e en classes whe e only speci ic palle s a e allowed o be s o ed in
each class. Ne e heless, Yu e al (2022) concen a e on wa ehouse design, and no
algo i hms o scheduling s o age and e ie al eques s a e p esen ed.
Table 1 O e iew o publica ions wi h simila s acke c ane scheduling p oblems
*BB: B anch-and-bound, DP: Dynamic p og amming, ECM:
𝜖
-cons ain me hod, H: Heu is ics, LAP:
Linea assignmen p oblem, PT: Pa ching echniques, SA: Simula ed annealing, TP: T anspo a ion p ob-
lem
Publica ion P oblem cha ac e is ics Complexi y Me hods
∗
Van den Be g and Gademann (1999) Sepa a ed inpu and ou pu poin Polynomial TP
Vis and Roodbe gen (2009) Mul iple ows each ha ing wo I/O-
poin s
Polynomial LAP, DP
Vis and Ca lo (2010) Two I/O-poin s and wo s acke c anes – SA
Gha ehgozli e al (2014b) Two I/O-poin s; a bi a y eques posi-
ions
Polynomial PT
Man e al (2021) Two I/O-poin s; Bi-objec i e p oblem – ECM, H
Gha ehgozli e al (2014a) Mul iple linea ly a anged I/O-poin s NP-ha d PT, BB
6
J.-N.Buckow e al.
Gha ehgozli e al (2014a) conside a ya d c ane scheduling p oblem wi h mul i-
ple I/O-poin s a anged linea ly bo h on he landside and seaside. They p o e ha
hei p oblem is NP-ha d, bu he p oo assumes ha s o age eques s ha e o be
scheduled in addi ion o e ie al eques s. None heless, he complexi y s a us when
only scheduling e ie al eques s in a wa ehouse wi h mul iple I/O-poin s emains
unclea . Gha ehgozli e al (2014a) o mula e hei p oblem as a
TSP
and in oduce a
b anch-and-bound algo i hm ha u ilizes pa ching echniques o sol e i . Howe e ,
he app oach p esen ed by Gha ehgozli e al (2014a) p ima ily exploi s he speci ic
dis ances in con aine ya ds, making i unsui able o ou p oblem se ing. Mo eo-
e , hei algo i hm is no designed o handle he speci ic case ha he e ie al I/O-
poin s a e ixed.
1.3 Con ibu ion
In his pape , we s udy di e en a ian s o a new s acke c ane scheduling p oblem,
which we call he e ie al op imiza ion p oblem (
ROP
). In he
ROP
, we a e gi en a
wa ehouse wi h mul iple I/O-poin s, and a se o e ie al eques s o be p ocessed.
The goal o he
ROP
is o schedule all e ie al eques s wi h minimum o al a el
cos s o he s acke c ane. As al eady desc ibed abo e, he
ROP
has se e al applica-
ions, including he p oblem se ing o he company, which ini ially mo i a ed ou
wo k.
In o de o schedule he e ie al eques s, we ha e o de e mine a sequence in
which he palle s a e e ie ed, and i mus be decided which palle is e ie ed a
which I/O-poin . We also conside di e en p oblem a ian s wi h a ixed palle
e ie al sequence and/o a ixed assignmen o palle s o e ie al I/O-poin s. E en
i he e a e ypically wo-dimensional wa ehouses in p ac ice, ou app oach is mo e
gene al and can handle a bi a y cos s as long as hey a e symme ic and ul ill he
iangle inequali y. In con as o he exis ing li e a u e, we conside an a bi a y
numbe o I/O-poin s, a bi a y posi ions o he eques s, and dual command cycles
in connec ion wi h swap mo es a e used o pai s o age and e ie al asks. Since
swap mo es a e used, only he scheduled e ie al eques s de e mine he handling
e o .
Ou esul s show ha he
ROP
is s ongly NP-ha d as long as he numbe o I/O-
poin s is pa o he inpu and he palle e ie al sequence has o be de e mined.
In con as , i he numbe o I/O-poin s is ixed o he palle e ie al sequence is
al eady gi en, he p oblem becomes polynomially sol able. Mo eo e , we p esen
e icien ans o ma ions o he
ROP
o he
TSP
, which opens a ich a senal o exis -
ing solu ion app oaches in he li e a u e, enabling o e ec i ely sol e he
ROP
. The
compu a ional s udy e eals se e al manage ial implica ions and insigh s, such as
ha he s acke c ane’s o al a el cos s can be educed conside ably by allowing he
palle s o be e ie ed a a bi a y I/O-poin s ins ead o ixing hem.
The emainde o his pape is s uc u ed as ollows. Fi s , in Sec .2, we p o ide
a o mal de ini ion o he
ROP
and in oduce he used no a ions. Sec ion3 is de o ed
o heo e ical p ope ies: we p o e NP-ha dness o wo a ian s o he
ROP
, conside
he case ha he numbe o I/O-poin s is ixed, and in es iga e he gain o lexible
7
Re ie al op imiza ion inawa ehouse wi hmul iple…
e ie al I/O-poin s. Nex , in o de o sol e he
ROP
, we p esen e icien ans o ma-
ions o he
TSP
in Sec .4. In Sec .5, we e eal ex ensi e compu a ional esul s o
di e en p oblem a ian s. Finally, Sec .6 concludes he pape .
2 P oblem de ini ion
The
ROP
can be s a ed as ollows. In a wa ehouse,n palle s
P={p1,…,pn}
ha e o
be e ie ed, and he e a em di e en I/O-poin s
Θ={𝜃1,…,𝜃m}
, whe e
𝜃depo ∈Θ
deno es he depo I/O-poin . Each palle 
p∈P
and each I/O-poin 
𝜃∈Θ
is asso-
cia ed wi h a loca ion
𝓁(p)
and
𝓁(𝜃)
, espec i ely. Fo he esul ing
𝜇=n+m
loca ions
L={𝓁1,…,𝓁𝜇}
, we ha e symme ic a el cos s
c[𝓁i,𝓁j]=c[𝓁j,𝓁i]
,
ul illing he iangle inequali y
c[𝓁i,𝓁j]≤c[𝓁i,𝓁k]+c[𝓁k,𝓁j]
o all loca ions
𝓁i,𝓁j,𝓁k∈L
. To exp ess he a el cos s be ween he loca ions o palle s
p,p�∈P
and I/O-poin s
𝜃,𝜃�∈Θ
, we also use he simple no a ions
c[p,𝜃]
,
c[𝜃,p]
,
c[p,p�]
,
and
c[𝜃,𝜃�]
ins ead o
c[𝓁(p),𝓁(𝜃)]
,
c[𝓁(𝜃),𝓁(p)]
,
c[𝓁(p),𝓁(p�)]
, and
c[𝓁(𝜃),𝓁(𝜃�)]
,
espec i ely.
Le 
Π
deno e he se o pe mu a ions o all palle sP, and
𝜋=(𝜋1,…,𝜋n)∈Π
be a speci ic sequence in which he n palle s a e e ie ed. Mo eo e ,
𝛼=(𝛼(p1),…,𝛼(pn))∈Θ
n
ep esen s an assignmen o he palle s o I/O-
poin s (whe e
𝛼(p)∈Θ
deno es he I/O-poin a which palle 
p∈P
is e ie ed).
The goal o he
ROP
is o ind a palle e ie al sequence
𝜋∈Π
as well as an
assignmen
𝛼∈Θ
n
o he palle s o I/O-poin s such ha he o al a el cos s
TTC ∶Π×Θ
n
→
ℝ+
o he esul ing s acke c ane ou a e minimized, i.e.,
whe e he objec i e unc ion is de ined as
He e, i is assumed ha he s acke c ane ou s a s and ends a he depo I/O-
poin 
𝜃depo
. Fo a solu ion
S∈Π×Θ
n
, we deno e by
𝜋(S)
i s palle sequence,
by
𝛼(S)
he uple
(
𝛼
(p1),…,
𝛼
(pn))
, and by
c(S)=TTC(𝜋(S),𝛼(S))
i s cos s. In he
s acke c ane ou co esponding o a solu ion
S∈Π×Θ
n
, palle s and I/O-poin s
a e isi ed al e na ely. I is su icien o conside only such ou s, as he cos s canno
dec ease by isi ing addi ional loca ions in be ween due o he iangle inequali y. In
pa icula , we can assume ha
𝛼(
𝜋
n)=
𝜃
depo
in an op imal solu ion, as we need o
e u n o he depo I/O-poin a he end o he ou .
Example 1 Conside he ins ance o he
ROP
shown in Fig. 2 wi h
n=3
pal-
le s,
m=2
I/O-poin s,
𝜃depo =𝜃1
, and cos s
c[𝓁i,𝓁j]
as displayed in Fig. 2a. A
min
(𝜋,𝛼)∈Π×Θ
n
TTC(𝜋,𝛼),
TTC(
𝜋
,
𝛼
)=c[
𝜃depo
,
𝜋1
]+c[
𝜋1
,
𝛼
(
𝜋1
)] + c[
𝛼
(
𝜋1
),
𝜋2
]+…
+c[𝜋n,𝛼(𝜋n)] + c[𝛼(𝜋n),𝜃depo ]
=c[𝜃depo ,𝜋1]+c[𝛼(𝜋n),𝜃depo ]+
n
∑
i=2
c[𝛼(𝜋i−1),𝜋i]+
n
∑
i=1
c[𝜋i,𝛼(𝜋i)]
.
8
J.-N.Buckow e al.
easible solu ionS o his ins ance wi h
𝜋(S)=(p1,p2,p3)
,
𝛼(S)=(𝜃1,𝜃1,𝜃2)
, and
o al cos s
c(S)=2+2+2+2+6+1+5=20
is shown in Fig.2b. No e ha in
solu ionS, he s acke c ane addi ionally needs o a e se he a c
(𝜃2,𝜃1)
in o de o
e u n o he depo I/O-poin 
𝜃1
. A be e easible solu ion
S
wi h
𝜋
(S)=(p
2
,p
3
,p
1)
,
𝛼
(S)=(𝜃
1
,𝜃
2
,𝜃
2)
, and
c(S)=13
is displayed in Fig.2c. In solu ion
S
, he las pal-
le 
p1
is al eady e ie ed a he depo I/O-poin 
𝜃1
, elimina ing an addi ional s acke
c ane mo emen .
Since he palle sequence
𝜋
and/o he assignmen 
𝛼
o palle s o I/O-poin s may be
ixed o no , we conside he ollowing ou p oblem a ian s:
(i) bo h
𝜋
and
𝛼
a e ixed,
(ii) he pe mu a ion
𝜋
is ixed, whe eas he assigned I/O-poin s
𝛼(p)∈Θ
o all
palle s
p∈P
ha e o be de e mined,
(iii) he assigned I/O-poin s
𝛼(p)∈Θ
o all palle s
p∈P
a e ixed, whe eas he
pe mu a ion
𝜋
has o be de e mined, o
(i ) bo h he pe mu a ion
𝜋
and he assigned I/O-poin s
𝛼(p)∈Θ
o all pal-
le s
p∈P
ha e o be de e mined.
In case (i), a solu ion is al eady ully de e mined and he e is no oom o op imi-
za ion, as he s acke c ane’s ou is ixed due o he known pe mu a ion
𝜋
and he
known assignmen o he palle s
p∈P
o I/O-poin s
𝛼(p)∈Θ
. Case (ii) is also easy
o sol e, because he palle pe mu a ion
𝜋
is ixed, and he I/O-poin s o be assigned
can be chosen independen ly o each o he , as hey a e always app oached be ween
wo ixed loca ions. The e o e, o all
i=1, …,n−1
, we se he I/O-poin s o
(1)
𝛼(
𝜋
i)=a g min𝜃∈Θ{c[
𝜋
i,
𝜃
]+c[
𝜃
,
𝜋
i+1]},
Fig. 2 Example o he
ROP
15
Re ie al op imiza ion inawa ehouse wi hmul iple…
we p esen wo ans o ma ions o he
ROP
o he
TSP
. Ou compu a ional esul s
in Sec .5 show ha hese ans o ma ions enable o e ec i ely sol e he
ROP
,
ou pe o ming in ui i e nea es neighbo heu is ics.
Fi s , we ans o m
ROPAP
o he me ic
TSP
(i.e., he cos s in he esul ing
TSP
ins ance a e symme ic and he iangle inequali y holds). The key idea is o c e-
a e a node o each palle , and only de e mine a e ie al sequence
𝜋
o he pal-
le s by sol ing he co esponding
TSP
ins ance, while an assignmen 
𝛼
o palle s
o hei e ie al I/O-poin s esul s implici ly. Fo each pai o palle s
pi,pj∈P
,
we deno e by
𝛽(pi,pj)
an I/O-poin 
𝜃∈Θ
ha minimizes he cos o e ie ing
palle 
pi
i palle 
pj
is p ocessed di ec ly a e wa ds, i.e., minimizing he cos
c[pi,𝜃]+c[𝜃,pj]
. We also call
𝛽(pi,pj)
an op imal I/O-poin o be placed be ween
palle s
pi
and
pj
. Based on his, we nex de ine he se o solu ions
whe e an op imal I/O-poin 
𝛽(
𝜋
i,
𝜋
i+1)
is always placed be ween all successi e
palle s
𝜋i
and
𝜋i+1
(
i=1, …,n−1
), and he las palle 
𝜋n
in he palle e ie al
sequence is e ie ed a he depo I/O-poin 
𝜃depo
. Fo 
ROPAP
, no e ha each solu-
ion
S∈Π×Θ
n
can be ans o med in o a solu ion
S�∈SAP
wi h cos s
c(S�)≤c(S)
by eplacing he cu en e ie al I/O-poin s wi h he co esponding op imal I/O-
poin s o be placed be ween all wo pai s o palle s in he gi en palle e ie al
sequence, and e ie ing he las palle a he depo I/O-poin 
𝜃depo
. In o de o
sol e
ROPAP
, i is he e o e su icien o conside only he solu ion se 
SAP
, as i con-
ains in pa icula an op imal solu ion.
A ans o ma ion o 
ROPAP
o he me ic
TSP
is o mula ed in Theo em 6.
Mo eo e , each
TSP
solu ion o he ans o med ins ance co esponds o
an
ROPAP
solu ion
SAP ∈SAP
wi h he same o al cos s. In pa icula , he se o all
co esponding
TSP
solu ions mus con ain a solu ion which is op imal o 
ROPAP
.
Consequen ly, i is su icien o sol e
ROPAP
indi ec ly by using algo i hms o
he
TSP
applied o he ans o med ins ance.
Theo em6 The e is a polynomial- ime ans o ma ion o
ROPAP
o he me ic
TSP
,
and we ha e a bijec ion be ween he se 
SAP
o
ROPAP
solu ions and he se 
STSP
o 
TSP
solu ions. Mo eo e , each
ROPAP
solu ion
SAP ∈SAP
has he same o al
cos s as i s co esponding
TSP
solu ion
STSP ∈STSP
, i.e.,
c(SAP)=c(STSP)
.
P oo We a e gi en an
ROPAP
ins ance wi h n palle s
P={p1,…,pn}
, m I/O-
poin s
Θ={
𝜃
1,…,
𝜃
m}
, a speci ic depo I/O-poin
𝜃depo ∈Θ
, and he co espond-
ing
𝜇=n+m
loca ions
L={𝓁1,…,𝓁𝜇}
wi h me ic a el cos s
c[𝓁i,𝓁j]
o all
𝓁i,𝓁j∈L
. We cons uc a
TSP
ins ance wi h he comple e, undi ec ed g aph
G=(V,E)
ha ing
n�=n+1
nodes and edge cos s
c�[ ,w]
o all
,w∈V
as ollows.
• We ha e he node se 
V={ 0, 1,…, n}
, whe e node
0
co esponds o he
depo I/O-poin
𝜃depo
, and o all
i=1, …,n
, he node
i
co esponds o pal-
le 
pi∈P
.
SAP = {(𝜋,𝛼)∈Π×Θ
n∣𝛼(𝜋i)=𝛽(𝜋i,𝜋i+1) o i=1, …,n−1 and 𝛼(𝜋n)=𝜃depo },

16
J.-N.Buckow e al.
• The edge cos s be ween palle nodes and he depo node emain he same as in
he
ROPAP
ins ance, i.e., o all
i=1, …,n
, we ha e
c�[
0
,
i]=
c
[
𝜃
depo
,p
i].
• The edge cos s be ween wo di e en palle nodes co espond o he cheapes
possible way o place an I/O-poin in be ween, i.e., o all
i,j=1, …,n
wi h
i≠j
, we ha e
The esul ing
TSP
cos s a e symme ic due o he de ini ion abo e. Mo eo e , he
o iginal
ROPAP
cos s ul ill he iangle inequali y, and as discussed nex , his p op-
e y emains also alid o he esul ing
TSP
cos s, i.e.,
c�[ i, j]≤c�[ i, k]+c�[ k, j]
o all di e en
i,j,k=0, …,n
.
• Fo 
i=0
and
j,k=1, …,n
(simila ly he case
j=0
and
i,k=1, …,n
), we ha e
• Fo 
k=0
and
i,j=1, …,n
, we ha e
• Fo 
i,j,k=1, …,n
, we ha e
Nex , we show ha he e is a bijec ion be ween he se 
SAP
o 
ROPAP
solu ions and
he se 
STSP
o 
TSP
solu ions, and ha each
TSP
solu ion has he same o al cos s as
i s co esponding
ROPAP
solu ion. On he one hand, each
ROPAP
solu ion
SAP ∈SAP
can uniquely be desc ibed by i s palle e ie al sequence
𝜋
, as he assignmen o
palle s o I/O-poin s esul s implici ly ( o all
i=1, …,n−1
, palle 
𝜋i
is e ie ed a
I/O-poin 
𝛽(𝜋i,𝜋i+1)
, and he las palle 
𝜋n
is e ie ed a he depo I/O-poin 
𝜃depo
).
On he o he hand, each
TSP
solu ion
STSP ∈STSP
can uniquely be desc ibed by
i s palle node sequence, as he posi ion o he depo node
0
in he ou can be
assumed o be ixed. The e o e, we ha e
|SAP|=|STSP|=n!
, and o each
ROPAP
solu ion
SAP ∈SAP
, we can cons uc a co esponding
TSP
solu ion
STSP ∈STSP
and ice e sa, jus by conside ing he palle e ie al sequence. Mo eo e , we ha e
c(SAP)=c(STSP)
o co esponding solu ions, because in bo h cases, he ou s a s
and ends a a depo I/O-poin o depo node, and he cos s be ween wo palle nodes
c�
[ i, j]=min
𝜃∈Θ
{c[pi,𝜃]+c[𝜃,pj]}
.
c�
[ 0, j]=c[𝜃depo ,pj]
≤c[𝜃depo ,pk]+c[pk,𝛽(pk,pj)] + c[𝛽(pk,pj),pj
]
=c�[
0
,
k
]+c�[
k
,
j
].
c�[
i, j
]=
c
[
pi,𝛽
(
pi,pj
)] +
c
[
𝛽
(
pi,pj
)
,pj
]
≤c[pi,𝜃depo ]+c[𝜃depo ,pj]
=c�[
i
,
0
]+c�[
0
,
j
].
c�
[ i, j]=c[pi,𝛽(pi,pj)] + c[𝛽(pi,pj),pj]
≤c[pi,𝛽(pi,pk)] + c[𝛽(pi,pk),pj]
≤c[pi,𝛽(pi,pk)] + c[𝛽(pi,pk),pk]+c[pk,𝛽(pk,pj)] + c[𝛽(pk,pj),pj
]
=c�[
i
,
k
]+c�[
k
,
j
].
17
Re ie al op imiza ion inawa ehouse wi hmul iple…
i, j∈V⧵{ 0}
also conside he cos o placing an op imal I/O-poin 
𝛽(pi,pj)
be ween he wo co esponding palle s
pi
and
pj
.
The co esponding
TSP
ins ance o an
ROPAP
ins ance can be compu ed in
O(n2
⋅
m)
, as mainly o each pai o wo palle s, an op imal I/O-poin o be placed
be ween hem has o be calcula ed. Con e ing an
ROPAP
solu ion o he co e-
sponding
TSP
solu ion and ice e sa can be done in
O(n)
, since only he palle
e ie al sequence
𝜋
needs o be conside ed (assuming op imal I/O-poin s o be
placed be ween he palle s a e s o ed in he p e ious s ep). We hence conclude ha
he ans o ma ion can be done in polynomial ime.
◻
Example 2 Reconside he
ROPAP
ins ance shown in Fig. 2a wi h
n=3
pal-
le s and
m=2
I/O-poin s. The co esponding
TSP
ins ance is shown in Fig. 5a,
whe e we ha e
𝛽(p1,p2)=𝛽(p2,p1)=𝜃1
,
𝛽(p1,p3)=𝛽(p3,p1)=𝜃2
, and
𝛽(p2,p3)=𝛽(p3,p2)=𝜃2
. Fo he
TSP
solu ion
STSP =( 0, 2, 3, 1)
wi h cos s
c(STSP)=13
, we ob ain he co esponding
ROPAP
solu ion
S
shown in Fig.2c wi h
cos s
c(S)=13
.
Since he ans o ma ion p esen ed in Theo em6 is polynomial, and we ha e a
bijec ion be ween he se 
SAP
o 
ROPAP
solu ions and he se 
STSP
o 
TSP
solu ions,
each app oxima ion algo i hm o he me ic
TSP
also yields he same pe o mance
gua an ee o 
ROPAP
. F om Theo em6, i hence ollows immedia ely Co olla y1.
Co olla y 1 The e is a
3
2
-app oxima ion o 
ROPAP
.
P oo We apply he ans o ma ion om Theo em6 o he gi en
ROPAP
ins ance
and ge he co esponding ins ance o he me ic
TSP
, which in u n is sol ed by
using he algo i hm p esen ed by Ch is o ides (1976). Fo he esul ing
TSP
solu-
ion, we compu e he co esponding
ROPAP
solu ion o he o iginal ins ance. This
p ocedu e yields he same pe o mance gua an ee o 
3
2
o 
ROPAP
as he algo-
i hm p esen ed by Ch is o ides (1976) o he me ic
TSP
, since we ha e a bijec-
ion be ween he se 
SAP
o 
ROPAP
solu ions and he se 
STSP
o 
TSP
solu ions, and
each
ROPAP
solu ion
SAP ∈SAP
has he same o al cos s as i s co esponding
TSP
solu ion
STSP ∈STSP
. Fu he mo e, he p ocedu e can be applied in polynomial ime,
because c ea ing he co esponding me ic
TSP
ins ance can be done in
O(n2
⋅
m)
,
Fig. 5 Example o he cos s
c�[ i, j]
o he esul ing
TSP
ins ances acco ding o he ans o ma ions p e-
sen ed in Theo ems6 and7
18
J.-N.Buckow e al.
and con e ing he esul ing
TSP
solu ion in o an
ROPAP
solu ion can be done in
O(n)
, as shown in he p oo o Theo em6.
◻
In he case o 
ROPP
, only he palle e ie al sequence has o be de e mined, and
we de ine
SP=Π
as he se o all possible solu ions. As s a ed in Theo em7, we
p esen a ans o ma ion o 
ROPP
o he asymme ic
TSP
(
ATSP
) wi h alid ian-
gle inequali y. In addi ion, o each
ATSP
solu ion
SATSP ∈SATSP
o he ans o med
ins ance, we ha e a co esponding
ROPP
solu ion
SP∈SP
wi h he same o al cos s
and ice e sa. The main idea o his ans o ma ion is o c ea e a
TSP
node o
each palle 
p∈P
, and he cos o mo ing om palle p o
p�∈P
conside s he cos
o mo ing o he speci ic I/O-poin 
𝛼(p)
app oached in be ween o e ie e palle p
be o e mo ing o
p′
. No e ha he esul ing cos s a e asymme ic, since he ixed
e ie al I/O-poin s
𝛼(p)
and
𝛼(p�)
may di e .
Unlike in he case o 
ROPAP
, he e does no seem o be an e icien ans o ma-
ion o 
ROPP
o he symme ic
TSP
, since he assigned palle I/O-poin s a e gi en as
inpu . Ne e heless, each possible palle e ie al sequence o he
ROPP
ins ance can
be exp essed as an
ATSP
solu ion o he co esponding ans o med ins ance, and
his solu ion has he same cos s as a solu ion wi h he same sequence o he o iginal
ins ance. I is hus also su icien o sol e
ROPP
indi ec ly by using algo i hms o
he
TSP
applied o he ans o med ins ance.
Theo em7 The e is a polynomial- ime ans o ma ion o
ROPP
o he
ATSP
ul ill-
ing he iangle inequali y, and we ha e a bijec ion be ween he se 
SP
o
ROPP
solu-
ions and he se 
SATSP
o 
ATSP
solu ions. Mo eo e , each
ROPP
solu ion
SP∈SP
has he same o al cos s as i s co esponding
ATSP
solu ion
SATSP ∈SATSP
, i.e.,
c(SP)=c(SATSP )
.
The p oo ollows a simila idea as he p oo o Theo em6 and is p esen ed
inAppendix B.
Example 3 Reconside he
ROPP
ins ance shown in Fig.2a wi h
n=3
palle s,
m=2
I/O-poin s,
𝛼(p1)=𝛼(p2)=𝜃1
, and
𝛼(p3)=𝜃2
. The co esponding
ATSP
ins ance
is shown in Fig. 5b. Fo he
ATSP
solu ion
SATSP =( 0, 1, 2, 3)
wi h cos s
c(SATSP )=20
, we ob ain he co esponding
ROPP
solu ionS shown in Fig.2b wi h
cos s
c(S)=20
.
Again, each app oxima ion algo i hm o he
ATSP
ul illing he iangle inequal-
i y also yields he same pe o mance gua an ee o 
ROPP
, because he ans o ma ion
p esen ed in Theo em7 is polynomial, and we ha e a bijec ion be ween he se 
SP
o 
ROPP
solu ions and he se 
SATSP
o 
ATSP
solu ions whe e co esponding solu-
ions ha e he same o al cos s. Fo he
ATSP
ul illing he iangle inequali y, Asa-
dpou e al (2010) p esen ed an app oxima ion algo i hm wi h an
O(log n∕log log n)
pe o mance gua an ee. We he e o e immedia ely conclude Co olla y2.
19
Re ie al op imiza ion inawa ehouse wi hmul iple…
Co olla y 2 The e is an app oxima ion algo i hm wi h an
O(log n∕log log n)
pe o -
mance gua an ee o 
ROPP
.
5 Compu a ional esul s
This sec ion p esen s ex ensi e compu a ional esul s o he
ROP
. Fi s , in Sec .5.1,
we desc ibe he es ins ances used in ou expe imen s. Op imal esul s de e mined
by a b anch-and-cu sol e o he
ATSP
a e p esen ed in Sec .5.2, whe e we ana-
lyze he e ec o di e en ins ance pa ame e s on he solu ion quali y. In Sec .5.3,
he esul s de e mined by ou di e en heu is ics a e p esen ed. Finally, Sec .5.4
p o ides insigh s on he gain o op imiza ion o di e en 
ROP
a ian s.
We implemen ed all algo i hms inC++, and ou expe imen s we e pe o med on
an In el Co e i9-10920X 3.5GHz machine wi h 64 Bi Ubun u 20.04 LTS and 64GB
RAM. To sol e he
TSP
ins ances esul ing om he ans o ma ions p esen ed in
Sec .4, we implemen ed a b anch-and-cu sol e using CPLEX20.1 and he g aph
lib a y LEMON1.3.1 (Dezső e al 2011). Ou expe imen s wi h he b anch-and-cu
sol e we e mul i- h eaded, allowing o simul aneous use o up o en co es, and we
se a ime limi o one hou o each ins ance. Howe e , o he heu is ics, he expe i-
men s we e single- h eaded, and a e age gaps o he bes lowe bound alues o he
co esponding ins ances a e epo ed. Fo a gi en solu ionS, he pe cen age gap is
calcula ed acco ding o he o mula
100
⋅
c(S)−LB
LB
, whe eLB deno es he bes lowe
bound o he co esponding ins ance ob ained by CPLEX. All ins ances and he aw
da a o all esul s can be ound a h p:// www2. in o ma ik. uos. de/ kombo p / da a/ op/.
5.1 Tes da a
To p ope ly e alua e ou solu ion app oaches, we andomly gene a ed ins ances wi h
a ious pa ame e s based on da a p o ided by he company we collabo a e wi h.
This company ope a es a high-bay wa ehouse using AS/RS whe e a ound
n=100
palle s need o be e ie ed du ing a single shi by using
m=3
di e en I/O-poin s.
Thei s acke c ane can mo e independen ly o each o he in ho izon al and e ical
di ec ions, and hence he a el cos s be ween wo loca ions a e based on he Cheby-
she me ic (i.e., he maximum o he e ical and ho izon al cos s).
To gain deepe insigh s on he
ROP
, we also gene a ed ins ances ha a e mo e
gene al han he company’s speci ic p oblem se ing, allowing o examine he
in luence o some ins ance pa ame e s. Fi s , he numbe o palle s o be e ie ed
o he numbe o I/O-poin s may di e in o he p oblem se ings. Mo eo e , in
wa ehouses wi hou AS/RS, s acke c anes ypically canno mo e independen ly
in ho izon al and e ical di ec ions, and he e o e o he a el cos measu es
apply. Besides he Chebyshe me ic, o he ealis ic a el cos measu es in wa e-
houses include he Euclidean (i.e., he leng h o he di ec connec ion line) and
he Manha an (i.e., he o al ho izon al plus e ical cos s) me ic. Fo example,
in uni -load wa ehouses wi h o kli s and ec ilinea o de ed acks posi ioned on
20
J.-N.Buckow e al.
he g ound, a el cos s can be accu a ely modeled by he Manha an me ic. In
con as , o wa ehouses wi h human picke s and ew i ems s o ed on he g ound,
he Euclidean me ic seems o be a sui able choice as nea ly he di ec connec ion
line be ween wo loca ions can be a e sed.
In p ac ice, he o de ing o I/O-poin s may be linea , o example, i hey a e
loca ed a he bo om o a shel o easy accessibili y. Howe e , we know om he
company we collabo a e wi h ha hey plan o build a new wa ehouse on a hill,
and o accommoda e he di e en g ound le els, he I/O-poin s need o be o de ed
a di e en heigh s ins ead o being loca ed on a line. Addi ionally, he e a e
wa ehouses loca ed abo e p oduc ion o logis ic acili ies whe e he I/O-poin s
may possibly be o de ed a bi a ily on he g ound, such as a ca pe manu ac u e
men ioned by Gha ehgozli e al (2014b). Thus, om a p ac ical pe spec i e, bo h
linea and a bi a y o de ings o he I/O-poin s seem o make sense.
Based on he p e ious discussion, we gene a ed a o al o 160 ins ances wi h
ou pa ame e s. In line wi h he no a ion used abo e, pa ame e n co esponds o
he numbe o palle s o be e ie ed, and pa ame e m desc ibes he numbe o
I/O-poin s in he wa ehouse. The o de ing pa ame e speci ies whe he he loca-
ions co esponding o he I/O-poin s a e chosen andomly o a e o de ed on a
line. The me ic pa ame e desc ibes how he a el cos s be ween wo loca ions
a e calcula ed, whe e we conside he Chebyshe , Manha an and Euclidean me -
ic, espec i ely.
All loca ions a e andomly chosen wi hin a squa e a ea ha ing an edge leng h
o 
1 000
and a e sampled as in ege alues. To ensu e ha he ins ances can be
used no only o 
ROPAP
, bu also o 
ROPA
and
ROPP
, we also andomly sampled
an assignmen 
𝛼
o palle s o I/O-poin s as well as a palle e ie al sequence
𝜋
.
Depending on he p oblem a ian conside ed, he alues o 
𝛼
and
𝜋
may be no
equi ed. In hese cases hey a e simply igno ed.
To in es iga e he in luence o speci ic pa ame e s and o co e a wide ange
o p oblem se ings, we g ouped he ins ances in o h ee se s
In
,
Im
and
ICos s
.
These ins ance se s a e all based on he company’s p oblem se ing, excep ha
ce ain pa ame e s a e a ied. Ins ance se 
In
a ies he numbe o palle s o be
e ie ed
n∈{20, 50, 100, 200, 500, 1 000}
, while assuming
m=3
di e en I/O-
poin s o de ed andomly and a el cos s esul ing om he Chebyshe me ic.
Ins ance se 
Im
a ies he numbe o I/O-poin s
m∈{1, 2, 3, 5, 10, 20}
, while
assuming
n=100
palle s o be e ie ed, a andom o de ing o he I/O-poin s and
a el cos s esul ing om he Chebyshe me ic. Finally, ins ance se 
ICos s
a ies
bo h he o de ing and he me ic pa ame e , conside ing all possible combina-
ions o hese wo pa ame e s while assuming
n=500
and
m=3
(no e ha la ge
ins ances a e needed o ge meaning ul di e ences be ween a ying a el cos s).
Fo each speci ied combina ion o pa ame e s, en andom ins ances we e c ea ed.
5.2 Op imal esul s
In a i s expe imen , we aimed o de e mine op imal solu ions o bo h
ROPP
and
ROPAP
o examine how di e en ins ance pa ame e s a ec he di icul y o

21
Re ie al op imiza ion inawa ehouse wi hmul iple…
sol ing hese p oblems. In p elimina y expe imen s, he ma hema ical model p e-
sen ed inAppendix A u ned ou o be inapp op ia e o sol e
ROPP
and
ROPAP
. In
o de o s ill ob ain op imal solu ions, we hence ans o med he
ROPP
and
ROPAP
ins ances in o hei co esponding
TSP
ins ances acco ding o Theo ems6 and7,
espec i ely. Un o una ely, ha dly any exac sol e s a e eely a ailable o sol e
he esul ing
TSP
ins ances, wi h he Conco de sol e de eloped by Applega e e al
(2006) appa en ly being he only excep ion. Howe e , i is limi ed o handle sym-
me ic
TSP
ins ances. Since only ans o med
ROPAP
ins ances a e gua an eed o
be symme ic, while ans o med
ROPP
ins ances may esul in asymme ic
TSP
ins ances, a gene al
ATSP
sol e is equi ed o sol e all ins ances p ope ly and o
enable a ai compa ison be ween all esul s. To add ess his issue, we implemen ed
ou own b anch-and-cu 
ATSP
sol e using CPLEX o sol e all esul ing
TSP
ins ances.
Ou b anch-and-cu sol e is based on he well-known wo-index o mula ion
o iginally p oposed by Dan zig e al (1954). Fu he de ails can be ound in su -
ey pape s such as he one by Robe i and To h (2012). Mo eo e , we sepa a e sub-
ou elimina ion cons ain s by calcula ing minimum cu s wi h he LEMON lib a y
implemen a ion o he algo i hm p oposed by Hao and O lin (1994). We conduc ed
es s on ou b anch-and-cu sol e o e alua e he impac o a wa m-s a , i.e., ini ial-
izing CPLEX wi h a gi en solu ion de e mined by a heu is ic. In Sec .5.3, we e al-
ua e a ious heu is ics o sol e he esul ing
ATSP
ins ances. The modi ied Ka p-
S eele pa ching heu is ic p esen ed by Glo e e al (2001) p o ed o be he mos
e ec i e on ou ans o med ins ances, and we he e o e use i o he wa m-s a o
ou b anch-and-cu sol e . In all expe imen s wi h ou b anch-and-cu sol e , a ime
limi o one hou pe ins ance was applied.
Table2 p esen s he esul s o he impac o he wa m-s a on ou b anch-and-
cu sol e o all160 ins ances
In∪Im∪ICos s
combined. The i s column indica es
whe he a wa m-s a was applied. The emaining columns show he numbe o ea-
sible solu ions, he numbe o solu ions e i ied as op imal wi hin he ime limi , and
he ac ual a e age compu ing imes in seconds, dis inguished by
ROPP
and
ROPAP
.
As shown in Table2, mo e ins ances we e e i ied as op imally sol ed and he
a e age compu a ion imes we e lowe o 
ROPP
compa ed o
ROPAP
, ega dless
whe he a wa m-s a was used. Al hough
ROPP
may esul in asymme ic
TSP
ins ances in con as o
ROPAP
, hey seem o be easie o sol e. A plausible expla-
na ion is ha in
ROPP
only a palle e ie al sequence
𝜋
has o be de e mined,
whe eas in
ROPAP
addi ionally an assignmen 
𝛼
o he palle s o I/O-poin s has o
Table 2 Impac o he wa m-s a on he b anch-and-cu sol e o ins ances
In
∪
Im
∪
ICos s
ROPP
ROPAP
Wa m-s a #Feas #Op A g. ime [s] #Feas #Op A g. ime [s]
Wi hou 153 153 374.80 130 128 1256.83
Wi h 160 160 2.67 160 139 791.44
22
J.-N.Buckow e al.
be calcula ed. Since he assignmen 
𝛼
is al eady ixed in
ROPP
, a sequence
𝜋
can be
be e de e mined.
No e ha wi hou a wa m-s a , no o all160 ins ances easible solu ions could
be ound o bo h
ROPP
and
ROPAP
as lis ed in Table2. This is due o he insu i-
cien sol ing ime a ailable o sepa a e all sub ou elimina ion cons ain s on hese
ins ances. In con as , when using a wa m-s a , he sol e is gua an eed o ind ea-
sible solu ions o all ins ances because i has al eady been ini ialized wi h one. Fu -
he mo e, he numbe o ins ances e i ied as op imally sol ed is much la ge wi h a
wa m-s a o bo h
ROPP
and
ROPAP
, while he a e age compu a ion imes dec ease
conside ably. E en i he gaps epo ed by CPLEX a e a mos 
2%
on any ins ance
sol ed o easibili y, he compelling posi i e impac o a wa m-s a emphasizes he
alue o conside ing heu is ics o 
ROPP
and
ROPAP
. Due o he high e ec i eness
o a wa m-s a , only esul s wi h a wa m-s a a e shown below.
In Sec .3.1, we p o ed ha bo h
ROPP
and
ROPAP
a e s ongly NP-ha d. Thus,
i can be expec ed ha he ins ance size, measu ed by pa ame e sn andm, s ongly
de e mines he di icul y o sol ing hese p oblems. The e o e, we in es iga ed how
he numbe o palle s o be e ie ed (pa ame e n) and he numbe o I/O-poin s
(pa ame e m) impac he esul s. Tables3 and4 p esen he esul s o ou b anch-
and-cu sol e o ins ances
In
and
Im
, dis inguished by pa ame e sn andm, espec-
i ely. Fo bo h
ROPP
and
ROPAP
and each alue o n o m, he numbe o ins ances
e i ied as op imally sol ed, he maximum pe cen age gap epo ed by CPLEX, and
Table 3 Resul s o he b anch-and-cu sol e o ins ances
In
dis inguished by pa ame e n
ROPP
ROPAP
n#Op Max. gap [%] A g. ime [s] #Op Max. gap [%] A g. ime [s]
20 10 0.0000 0.01 10 0.0000 0.04
50 10 0.0000 0.04 10 0.0000 0.19
100 10 0.0000 0.12 10 0.0000 1.56
200 10 0.0000 0.37 10 0.0000 32.78
500 10 0.0000 3.07 7 0.0044 2351.31
1000 10 0.0000 23.52 2 0.0018 2930.42
Table 4 Resul s o he b anch-and-cu sol e o ins ances
Im
dis inguished by pa ame e m
ROPP
ROPAP
m#Op Max. gap [%] A g. ime [s] #Op Max. gap [%] A g. ime [s]
1 10 0.0000 0.15 10 0.0000 0.16
2 10 0.0000 0.11 10 0.0000 0.67
3 10 0.0000 0.12 10 0.0000 1.56
5 10 0.0000 0.11 10 0.0000 1.90
10 10 0.0000 0.09 10 0.0000 42.43
20 10 0.0000 0.09 8 1.3409 214.90
23
Re ie al op imiza ion inawa ehouse wi hmul iple…
he a e age compu ing imes in seconds a e shown. Recall ha he e a e a o al o
en ins ances o each alue o n o m.
Acco ding o he esul s shown in Table3, all ins ances we e e i ied as op i-
mally sol ed o 
ROPP
, ega dless o he alue o pa ame e n. In con as , in he
case o 
ROPAP
, he ime limi o one hou was insu icien o e i y some ins ances
o alues o 
n≥500
. Howe e , he gap epo ed by CPLEX on any ins ance is a
below
0.01%
, indica ing ha he co esponding solu ions a e a leas nea ly op imal.
Fu he mo e, he a e age compu ing imes inc ease sha ply wi h ising alues o n
o bo h
ROPP
and
ROPAP
. These esul s alida e ha he pa ame e n has a majo
impac on he di icul y o sol ing he p oblem, e en i he gi en ins ances a e well
sol able. Addi ionally, he alues in Table3 con i m ha in p ac ice
ROPAP
is mo e
di icul o sol e han
ROPP
.
As can be seen in Table4, all ins ances we e e i ied as op imally sol ed in he
case o 
ROPP
, independen o he pa ame e m. Mo eo e , o 
ROPP
, he compu -
ing imes a e negligible, being a below one second e en o la ge alues o m. In
con as , o 
ROPAP
, he e is a sha p inc ease in compu ing imes wi h ising alues
o m. Addi ionally, while all solu ions we e e i ied as op imal in he case o 
ROPAP
o 
m≤10
, wo ins ances wi h
m=20
could no be e i ied wi hin he ime limi
o one hou . Howe e , he gaps epo ed by CPLEX a e a mos 
1.5%
. These esul s
show ha he pa ame e m has a la ge in luence on he di icul y o sol ing
ROPAP
,
while i appea s o ha e less impac on
ROPP
. Addi ionally,
ROPAP
seems o be
much mo e di icul o sol e compa ed o
ROPP
.
Nex , we e alua ed he impac o di e en o de ings o he I/O-poin s and a el
cos me ics on he di icul y o sol ing
ROPP
and
ROPAP
. Fo di e en o de ings
and me ics, Table5 shows he numbe o ins ances e i ied as op imally sol ed
and he a e age compu ing imes in seconds o he ins ances
ICos s
, dis inguished
by
ROPP
and
ROPAP
. Ins ances wi h a linea o de ing appea o be easie o sol e
han hose wi h a andom o de ing, pa icula ly o 
ROPAP
. Fo a andom o de -
ing, he me ic has li le in luence on he esul s o bo h
ROPP
and
ROPAP
. How-
e e , i he I/O-poin s a e o de ed linea ly, he e a e s ill ew di e ences in he case
o 
ROPP
, while he me ic has a conside able impac o 
ROPAP
. Wi h
ROPAP
, when
conside ing linea ly o de ed I/O-poin s, ins ances wi h Chebyshe me ic ake he
smalles compu ing imes wi h jus a ew seconds, whe eas ins ances wi h Euclidean
and Manha an me ic ake mo e han one housand seconds on a e age.
Table 5 Resul s o he b anch-
and-cu sol e o ins ances
ICos s
dis inguished by di e en
me ics and o de ings o he
I/O-poin s
ROPP
ROPAP
O de ing Me ic #Op A g. ime [s] #Op A g. ime [s]
Random Chebyshe 10 3.07 7 2351.31
Euclidean 10 3.01 8 1929.82
Manha an 10 3.48 7 2258.06
Linea Chebyshe 10 2.40 10 2.35
Euclidean 10 3.06 9 1328.35
Manha an 10 3.18 8 1568.05
24
J.-N.Buckow e al.
Due o he special s uc u e o ins ances wi h linea ly o de ed I/O-poin s, hese
a e easie o sol e, mainly because he a el cos s be ween palle s and di e en
I/O-poin s a e mo e simila . This is pa icula ly he case o he Chebyshe me ic,
whe e ei he he ho izon al o e ical di ec ion domina es he dis ance, enabling o
each se e al I/O-poin s om a palle wi h he same a el cos s. In con as , wi h
he Euclidean and Manha an me ics and a linea o de ing, he e a e mo e di e -
ences in a el cos s be ween palle s and I/O-poin s, as hese a e ne e comple ely
domina ed by ei he ho izon al o e ical dis ance. Howe e , he esul s gene ally
e eal he insigh ha he
ROP
can be sol ed well ega dless o he cos me ic used
o he gi en o de o I/O-poin s.
5.3 Heu is ics
In a second expe imen , we compa ed some heu is ics o sol e
ROPP
and
ROPAP
.
Despi e he p e iously shown good esul s o ou b anch-and-cu sol e , ecall ha
i s sound pe o mance is la gely ied o he wa m-s a wi h heu is ic solu ions. Fu -
he mo e, he heu is ics we used a e no only easie o implemen han he b anch-
and-cu sol e , bu also equi e much less compu a ional ime.
Fi s , we implemen ed an in ui i e heu is ic ha sol es
ROPP
and
ROPAP
by
g eedily selec ing he nex palle s and I/O-poin s o be isi ed. Fo 
ROPP
, s a ing
a he depo I/O-poin , in each s ep we choose a palle wi h he smalles a el cos
om he cu en I/O-poin un il all palle s ha e been isi ed. When isi ing a palle ,
he nex I/O-poin o be a e sed is implici ly de e mined by he ixed assignmen 
𝛼
in he case o 
ROPP
. In con as , o 
ROPAP
, he only di e ence o he in ui i e heu-
is ic is ha an I/O-poin minimizing he a el cos s om he cu en palle is cho-
sen as nex I/O-poin o be a e sed. No e ha he in ui i e heu is ics o bo h
ROPP
and
ROPAP
can be seen as a special nea es neighbo heu is ic, since in each s ep, a
nea es a ailable loca ion is app oached. In ou expe imen , hese in ui i e heu is ics
se e as simple baseline app oaches ha a wa ehouse planne migh employ. We
also implemen ed h ee
TSP
heu is ics, which can be applied o
ROPP
and
ROPAP
ins ances ans o med acco ding o Theo ems6 and7, espec i ely.
• Nea es neighbo (TSP-NN): S a ing a he node co esponding o he depo
I/O-poin , a nea es un isi ed node is appended o he ou un il all nodes ha e
been isi ed.
• Cheapes inse ion (TSP-CI): The solu ion is ini ialized wi h a ou consis ing
only o he node co esponding o he depo I/O-poin . I e a i ely, an un isi ed
node ha can be inse ed wi h he cheapes inse ion cos s is inse ed a a cheap-
es inse ion posi ion un il all nodes ha e been isi ed.
• Modi ied Ka p-S eele pa ching (TSP-MKSP): A i s , a minimum-cos cycle
co e o all nodes is calcula ed (we sol ed he co esponding ma ching p oblem
by using he ne wo k simplex algo i hm implemen ed in he LEMON lib a y).
A e wa ds, he esul ing cycles a e i e a i ely pa ched un il only a single cycle
emains by e alua ing all possible pa ching op ions and applying one wi h he
smalles cos inc ease (Glo e e al 2001).
31
Re ie al op imiza ion inawa ehouse wi hmul iple…
The o mula ion(A1)-(A8) models he gene al a ian 
ROPAP
whe e bo h he palle
e ie al sequence
𝜋
and he assignmen 
𝛼
o palle s o I/O-poin s ha e o be de e -
mined. In o de o use ha model also o a ian 
ROPP
whe e
𝜋
has o be de e mined
and
𝛼
is al eady ixed, he equa ions(A9) need o be addi ionally inse ed in o he
model. A simila modi ica ion can also be pe o med o a ian 
ROPA
, bu we omi
speci ying i explici ly since he a ian can be sol ed i ially in polynomial ime.
B. P oo o Theo em7
P oo We a e gi en an
ROPP
ins ance wi h n palle s
P={p1,…,pn}
, m I/O-
poin s
Θ={
𝜃
1,…,
𝜃
m}
, a speci ic depo I/O-poin
𝜃depo ∈Θ
, o each palle
p∈P
a speci ic e ie al I/O-poin 
𝛼(p)∈Θ
, and
𝜇=n+m
co esponding loca-
ions
L={𝓁1,…,𝓁𝜇}
wi h me ic a el cos s
c[𝓁i,𝓁j]
o all
𝓁i,𝓁j∈L
. We
cons uc an
ATSP
ins ance wi h he comple e, di ec ed g aph
G=(V,A)
ha -
ing
n�=n+1
nodes and a c cos s
c�[ ,w]
o all
,w∈V
as ollows.
• We ha e he node se 
V={ 0, 1,…, n}
, whe e node
0
co esponds o he
depo I/O-poin
𝜃depo
, and o all
i=1, …,n
, he node
i
co esponds o pal-
le 
pi∈P
.
• The a cs connec ing he depo node wi h he palle nodes ha e he same cos as
in he
ROPP
ins ance, i.e., o all
i=1, …,n
, we ha e
c�[ 0, i]=c[
𝜃
depo ,pi]
.
• The a cs connec ing he palle nodes wi h he depo node ha e he cos co e-
sponding o mo e om he palle ’s speci ic e ie al I/O-poin o he depo I/O-
poin , i.e., o all
i=1, …,n
, we ha e
c�[ i, 0]=c[pi,
𝛼
(pi)] + c[
𝛼
(pi),
𝜃
depo ]
.
• The a c cos s be ween wo di e en palle nodes co espond o he cos s
o e ie ing he i s palle a i s speci ic I/O-poin and mo ing o -
wa d o he second palle , i.e., o all
i,j=1, …,n
wi h
i≠j
, we ha e
c�[ i, j]=c[pi,
𝛼
(pi)] + c[
𝛼
(pi),pj]
.
As discussed nex , he iangle inequali y emains also alid, i.e.,
c′[ i, j]≤c′[ i, k]
+c′[ k, j]
o all di e en
i,j,k=0, …,n
.
• Fo 
j=0
and
i,k=1, …,n
(simila ly he case
k=0
and
i,j=1, …,n
), we ha e
(A7)
xjki ∈{0, 1}j,k=1, …,n;i=1, …,m
(A8)
dk
o
,d
k
om
≥0k=1, …,
n
(A9)
n
∑
k=1
xjki =1j=1, …,n;i=𝛼(j
)

32
J.-N.Buckow e al.
• Fo 
i=0
and
j,k=1, …,n
, we ha e
• Fo 
i,j,k=1, …,n
, we ha e
Nex , we p o e ha he e is a bijec ion be ween he se 
SP
o 
ROPP
solu ions and he
se 
SATSP
o 
ATSP
solu ions, and ha each
ATSP
solu ion has he same o al cos s
as i s co esponding
ROPP
solu ion. On he one hand, each
ROPP
solu ion
SP∈SP
can uniquely be desc ibed by i s palle e ie al sequence
𝜋
, as he assignmen o
palle s o I/O-poin s is ixed. On he o he hand, each
ATSP
solu ion
SATSP ∈SATSP
can uniquely be desc ibed by i s palle node sequence, as he posi ion o he depo
node
0
in he ou can be assumed o be ixed. We hence ha e
|SP|=|SATSP |=n!
,
and o each
ROPP
solu ion
SP∈SP
, we can cons uc a co esponding
ATSP
solu-
ion
SATSP ∈SATSP
and ice e sa, jus by conside ing he palle e ie al sequence.
In addi ion,
c(SP)=c(SATSP )
holds o co esponding solu ions, because in bo h
cases, he ou s a s and ends a he depo I/O-poin o depo node, and he cos s
be ween wo palle nodes
i, j∈V⧵{ 0}
also conside he cos o placing he
e ie al I/O-poin 
𝛼(pi)
be ween he wo co esponding palle s
pi
and
pj
.
The esul ing
ATSP
ins ance co esponding o an
ROPP
ins ance can be compu ed
in
O(n2)
, as mainly o each pai o wo palle s he a el cos s ha e o be calcula ed
and he co esponding e ie al I/O-poin s a e ixed. Con e ing an
ROPP
solu ion o
he co esponding
ATSP
solu ion and ice e sa can be done in
O(n)
, since only he
palle e ie al sequence
𝜋
needs o be conside ed. We hence conclude ha he ans-
o ma ion can be done in polynomial ime.
◻
Acknowledgemen s The au ho s would like o hank he edi o s and wo anonymous e e ees o hei
cons uc i e and help ul commen s.
Funding Open Access unding enabled and o ganized by P ojek DEAL.
Da a a ailabili y All ins ances and esul s can be ound a h p:// www2. in o ma ik. uos. de/ kombo p / da a/
op/.
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License,
which pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long
c�
[ i, 0]=c[pi,𝛼(pi)] + c[𝛼(pi),𝜃depo ]
≤c[pi,𝛼(pi)] + c[𝛼(pi),pk]+c[pk,𝛼(pk)] + c[𝛼(pk),𝜃depo
]
=c
�
[ i, k]+c
�
[ k, 0].
c�
[ 0, j]=c[𝜃depo ,pj]
≤c[𝜃depo ,pk]+c[pk,𝛼(pk)] + c[𝛼(pk),pj
]
=c�[
0
,
k
]+c�[
k
,
j
].
c�[
i, j
]=
c
[
pi,𝛼
(
pi
)] +
c
[
𝛼
(
pi
)
,pj
]
≤c[pi,𝛼(pi)] + c[𝛼(pi),pk]+c[pk,𝛼(pk)] + c[𝛼(pk),pj
]
=c�[
i
,
k
]+c�[
k
,
j
].
33
Re ie al op imiza ion inawa ehouse wi hmul iple…
as you gi e app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e
Commons licence, and indica e i changes we e made. The images o o he hi d pa y ma e ial in his
a icle a e included in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line
o he ma e ial. I ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended
use is no pe mi ed by s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mis-
sion di ec ly om he copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons.o g/
licenses/by/4.0/.
Re e ences
Applega e D, Bixby R, Ch a al V, e al (2006) Conco de TSP sol e . h ps:// www. ma h. uwa e loo. ca/ sp/
conco de. h ml
Asadpou A, Goemans M, Mąd y A, e al (2010) An
O(log
n
∕log log
n
)
-app oxima ion algo i hm o he
asymme ic a eling salesman p oblem. In: P oceedings o he 2010 annual ACM-SIAM sympo-
sium on disc e e algo i hms, pp 379–389, h ps:// doi. o g/ 10. 1137/1. 97816 11973 075. 32
Boysen N, S ephan K (2016) A su ey on single c ane scheduling in au oma ed s o age/ e ie al sys ems.
Eu J Ope Res 254(3):691–704. h ps:// doi. o g/ 10. 1016/j. ejo . 2016. 04. 008
Buckow JN, Knus S (2023a) The wa ehouse eshu ling p oblem wi h swap mo es. T ansp Res Pa E
Logis T ansp Re 169:102994. h ps:// doi. o g/ 10. 1016/j. e. 2022. 102994
Buckow JN, Knus S (2023b) The wa ehouse eshu ling p oblem wi h swap mo es and ime limi . EURO
J T ansp Logis 12:100113. h ps:// doi. o g/ 10. 1016/j. ej l. 2023. 100113
Ch is o ides N (1976) Wo s -case analysis o a new heu is ic o he a elling salesman p oblem. Ca ne-
gie-Mellon Uni e si y Pi sbu gh Managemen Sciences Resea ch G oup, Tech. ep
Dan zig G, Fulke son D, Johnson S (1954) Solu ion o a la ge-scale a eling-salesman p oblem. J Ope
Res Soc Am 2(4):393–410. h ps:// doi. o g/ 10. 1287/ op e.2. 4. 393
Dezső B, Jü ne A, Ko ács P (2011) Lemon - an open sou ce C++ g aph empla e lib a y. Elec on
No es Theo Compu Sci 264(5):23–45. h ps:// doi. o g/ 10. 1016/j. en cs. 2011. 06. 003
F ank A, Ko e B, T iesch E, e al (1998) On he bipa i e a elling salesman p oblem. Tech. ep., Uni-
e si ä Bonn. Ins i u ü Ökonome ie und Ope a ions Resea ch
Ga cía A, Tejel J (2017) Polynomially sol able cases o he bipa i e a eling salesman p oblem. Eu J
Ope Res 257(2):429–438. h ps:// doi. o g/ 10. 1016/j. ejo . 2016. 07. 060
Ga ey M, Johnson D (1979) Compu e s and In ac abili y: A Guide o he Theo y o NP-Comple eness.
F eeman, USA
Gha ehgozli A, Yu Y, de Kos e R e al (2014a) An exac me hod o scheduling a ya d c ane. Eu J Ope
Res 235(2):431–447. h ps:// doi. o g/ 10. 1016/j. ejo . 2013. 09. 038
Gha ehgozli A, Yu Y, Zhang X e al (2014b) Polynomial ime algo i hms o minimize o al a el ime
in a wo-depo au oma ed s o age/ e ie al sys em. T ansp Sci 51(1):19–33. h ps:// doi. o g/ 10. 1287/
sc. 2014. 0562
Glo e F, Gu in G, Yeo A e al (2001) Cons uc ion heu is ics o he asymme ic TSP. Eu J Ope Res
129(3):555–568. h ps:// doi. o g/ 10. 1016/ S0377- 2217(99) 00468-3
Goe igk M, G ün B, Heßle P (2013) B anch and bound algo i hms o he bus e acua ion p oblem.
Compu Ope Res 40(12):3010–3020. h ps:// doi. o g/ 10. 1016/j. co . 2013. 07. 006
Hao J, O lin J (1994) A as e algo i hm o inding he minimum cu in a di ec ed g aph. J Algo
17(3):424–446. h ps:// doi. o g/ 10. 1006/ jagm. 1994. 1043
Kese la A, Pe e s B (1994) Analysis o dual-shu le au oma ed s o age/ e ie al sys ems. J Manu Sys
13(6):424–434. h ps:// doi. o g/ 10. 1016/ 0278- 6125(95) 90066-T
Ko ács G, Tuza Z, Viz á i B e al (2018) A no e on he poly ope o bipa i e TSP. Disc e e Appl Ma h
235:92–100. h ps:// doi. o g/ 10. 1016/j. dam. 2017. 09. 009
Kuhn HW, Yaw B (1955) The Hunga ian me hod o he assignmen p oblem. Na al Res Logis Q 2(1–
2):83–97. h ps:// doi. o g/ 10. 1002/ na . 38000 20109
Malmbo g C (2000) In e lea ing models o he analysis o win shu le au oma ed s o age and e ie al
sys ems. In J P od Res 38(18):4599–4610. h ps:// doi. o g/ 10. 1080/ 00207 54005 02055 32
Man X, Zheng F, Chu F e al (2021) Bi-objec i e op imiza ion o a wo-depo au oma ed s o age/ e ie al
sys em. Ann Ope Res 296(1):243–262. h ps:// doi. o g/ 10. 1007/ s10479- 019- 03222-1
34
J.-N.Buckow e al.
Melle R, Mungwa ana A (1997) Mul i-shu le au oma ed s o age/ e ie al sys ems. IIE T ans
29(10):925–938. h ps:// doi. o g/ 10. 1023/A: 10185 92017 528
Pazou J, Ca lo H (2015) Wa ehouse eshu ling: Insigh s and op imiza ion. T ansp Res Pa E Logis
T ansp Re 73:207–226. h ps:// doi. o g/ 10. 1016/j. e. 2014. 11. 002
Robe i R, To h P (2012) Models and algo i hms o he asymme ic a eling salesman p oblem:
an expe imen al compa ison. EURO J T ansp Logis ics 1(1):113–133. h ps:// doi. o g/ 10. 1007/
s13676- 012- 0010-0
Roodbe gen K, Vis I (2009) A su ey o li e a u e on au oma ed s o age and e ie al sys ems. Eu J Ope
Res 194(2):343–362. h ps:// doi. o g/ 10. 1016/j. ejo . 2008. 01. 038
Van den Be g J, Gademann A (1999) Op imal ou ing in an au oma ed s o age/ e ie al sys em wi h dedi-
ca ed s o age. IIE T ans 31(5):407–415. h ps:// doi. o g/ 10. 1023/A: 10075 45122 755
Vis I, Ca lo H (2010) Sequencing wo coope a ing au oma ed s acking c anes in a con aine e minal.
T ansp Sci 44(2):169–182. h ps:// doi. o g/ 10. 1287/ sc. 1090. 0298
Vis I, Roodbe gen K (2009) Scheduling o con aine s o age and e ie al. Ope Res 57(2):456–467.
h ps:// doi. o g/ 10. 1287/ op e. 1080. 0621
Yu Y, Liu Y, Yu H (2022) Op imal wo-class-based s o age policy in an AS/RS wi h wo depo s a oppo-
si e ends o he aisle. In J P od Res 60(15):4668–4692. h ps:// doi. o g/ 10. 1080/ 00207 543. 2021.
19345 90