Two-indexed formulation of the traveling salesman problem with multiple drones performing sidekicks and loops

Ra e, Alexande
A icle — Published Ve sion
Two-indexed o mula ion o he a eling salesman
p oblem wi h mul iple d ones pe o ming sidekicks and
loops
OR Spec um
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Ra e, Alexande (2024) : Two-indexed o mula ion o he a eling salesman
p oblem wi h mul iple d ones pe o ming sidekicks and loops, OR Spec um, ISSN 1436-6304,
Sp inge , Be lin, Heidelbe g, Vol. 47, Iss. 1, pp. 67-104,
h ps://doi.o g/10.1007/s00291-024-00785-9
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323266
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:67–104
h ps://doi.o g/10.1007/s00291-024-00785-9
ORIGINAL ARTICLE
Two‑indexed o mula ion o  he a eling salesman
p oblem wi hmul iple d ones pe o ming sidekicks
andloops
Alexande Ra e1
Recei ed: 31 Janua y 2024 / Accep ed: 28 July 2024 / Published online: 29 Augus 2024
© The Au ho (s) 2024
Abs ac
Ae ial d one deli e y has g ea po en ial o imp o e package deli e y ime, as
d ones can ly au onomously o e obs acles a a possibly highe speed han ucks.
The bene i s o d ones in deli e y can e en be inc eased in a uck-and-d one an-
dem whe e a uck ca ies mul iple d ones and eleases hem a ad an ageous places,
i.e., he a eling salesman p oblem wi h mul iple d ones (TSPmD). We ocus on
a gene al e sion o his p oblem wi h makespan minimiza ion, whe e he d ones
ha e wo op ions a e se ing he cus ome : hey can e u n o any node he uck
isi s a a la e s age (sidekick) o e u n o he same node hey we e launched om
(loop)—e en a he depo . We in oduce an e icien wo-indexed mixed-in ege
linea p og am (MILP) o his TSPmD and show how o adap he MILP o co e
wo p oblem a ian s, namely he mul iple lying sidekick a eling salesman p ob-
lem and he a eling salesman p oblem wi h d one. Ou MILP o mula ion is an
e icien o mula ion, as i ou pe o ms eigh s a e-o - he-a MILP o mula ions o
hese p oblem a ian s in nea ly all la ge ins ances. In a nume ical s udy, we p o-
ide new op imal solu ions wi h up o 28 nodes o benchma k pu poses. Mo eo e ,
we analyze he impac o allowing d one loops on makespan minimiza ion in gen-
e al and a he depo . We ind ha loops mainly become ele an when d ones a el
as e han ucks, esul ing in a e age makespan sa ings o up o 2.7%.
Keywo ds Unmanned ae ial ehicles· Rou ing· Las -mile deli e y· Mixed-in ege
linea p og am· Benchma k ins ances
* Alexande Ra e
ARa [email protected]
1 Depa men o Ope a ions, Ingols ad School o Managemen , Ca holic Uni e si y Eichs ä -
Ingols ad , Au de Schanz 49, 85049Ingols ad , Ge many
68
A.Ra e
1 In oduc ion
Pa cel deli e y ia ae ial d ones is much conside ed in academia (e.g., Mu ay
and Chu 2015) and also in p ac ice (e.g., Ga ne 2016) as d ones can inc ease he
deli e y speed (e.g., Mu ay and Raj 2020). The bene i s o d ones can e en be
inc eased when a uck eleases he d ones a ad an ageous places o se e cus-
ome s. This p oblem was ini ially in oduced by Mu ay and Chu (2015) unde
he name lying sidekick a eling salesman p oblem (FSTSP) and in es iga ed
by many publica ions (e.g., Ha e al. 2018). In he FSTSP, d ones ha e o pe -
o m a sidekick, meaning hey e u n o a node he uck isi s a any la e s age
in i s ou (see Fig.1a). This is con as ed by d ones pe o ming loops, which
means ha hey e u n o he same node hey a e launched om (see Fig.1b). We
call he p oblem when a d one launched om a mobile uck may pe o m bo h
sidekicks and loops a eling salesman p oblem wi h d one (TSPD) and a e-
ling salesman p oblem wi h mul iple d ones (TSPmD) i he uck is equipped
wi h mul iple d ones. Only a ew publica ions conside loops, he eby (Sche me
e al. 2019) al eady ound ha d ones pe o m loops in he inal ound ou ing i
hese a e allowed. As uck-and-d one andems a e challenging o sol e and only
a ew publica ions conside loops, he ollowing ques ion a ises: How high is he
impac o addi ionally conside ing loops on minimizing he o al deli e y ime
and, in con as , how much e o (in e ms o un ime inc ease) does i ake?
In his pape , we in oduce a gene al e sion o he TSPmD wi h sidekicks
and loops while minimizing he makespan. The gene al e sion means ha d one
ligh s a e no es ic ed by limi a ions ha a e no se physically (e.g., an endu -
ance limi ), i.e., in ou e sion, d ones can launch and e u n o any uck’s node
and e en pe o m loops a he depo . These depo loops a e, o example, no con-
side ed by Tiniç e al. (2023). This p oblem is no ep esen ed in he li e a u e,
and hus, he li e a u e also lacks sui able benchma k ins ances. We ill his gap
and in oduce a compac and e icien wo-indexed mixed-in ege linea p og am
(MILP) o mula ion o his TSPmD. Mo eo e , we show how o adjus his MILP
o co e he well-known a ian s mul iple lying sidekick a eling salesman
p oblem (mFSTSP) and he TSPD. The MILP o mula ions o he TSPmD and
he wo p oblem a ian s a e easily implemen ed and ou pe o m in o al eigh
s a e-o - he-a MILP o mula ions o hese p oblem a ian s, i.e., hey ind he
op imal solu ion as e . As a esul , he MILP allows us o p esen op imal solu-
ions wi h up o 28 nodes o all h ee p oblems o benchma k pu poses. In a
nume ical s udy, we analyze he impac o allowing d one loops on minimizing
he makespan and he un ime o a MILP sol e . Mo eo e , we analyze he impac
Fig. 1 Illus a ion o d one ou es
69
Two‑indexed o mula ion o  he a eling salesman p oblem…
o loops pe o med a he depo and conduc an a-pos e io i cos analysis o show
he impac o loops on las -mile deli e y cos s.
This pape con ibu es o he li e a u e as ollows Fi s , we in oduce a gene al
e sion o he TSPmD wi h makespan minimiza ion. Second, we p esen an e icien
MILP o mula ion wi h only wo-indexed a iables and adjus he MILP o co e
he well-known p oblem a ian s mFSTSP and TSPD. We benchma k ou MILP o
ou MILP o mula ions o he mFSTSP ( h ee wi h h ee d ones, one wi h a single
d one) and ou MILP o mula ions o he TSPD and ind ha ou MILP o mula-
ion ou pe o ms all o hem in la ge ins ances. Thi d, we p esen new op imal solu-
ions o he TSPmD, he mFSTSP, and he TSPD o he ins ances o Mu ay and
Chu (2015) and Bouman e al. (2018) o up o 28 nodes o benchma k pu poses.
Fou h, we p esen manage ial insigh s on allowing d one loops in gene al and spe-
ci ically pe o med a he depo - also including an a-pos e io i cos analysis.
The s uc u e o his pape is as ollows. In Sec .2, we desc ibe he decisions
and assump ions in de ail. In Sec .3, we p esen he ele an li e a u e and delimi
ou p oblem se ing and me hodology o his li e a u e. Nex , we in oduce he
MILP in Sec .4. We show how o adjus he MILP o co e he p oblem a ian s
mFSTSP and TSPD in Sec .5. In Sec .6, we desc ibe he ins ances o which we
p esen benchma k esul s, analyze and benchma k he un ime, and gi e manage ial
insigh s on allowing d one loops. Las , in Sec .7, we summa ize he esul s and gi e
a b ie ou look.
2 P oblem se ing
We decide on he ou ing o one uck and i s equipped mul iple homogeneous
d ones ha need o isi ce ain nodes, i.e., cus ome s. Addi ionally, we decide i a
cus ome is se ed by uck o by d one. Fo his, we minimize he makespan, i.e.,
he ime un il he las ehicle has e u ned o he depo , s a ing wi h he i s elease
a ime ze o. The peculia i y o he conside ed p oblem se ing is ha we conside
mul iple d ones, and hese can pe o m bo h sidekicks and loops - e en a he depo .
Addi ionally, we make he ollowing assump ions:
• T a eling imes o he uck and he d ones gene ally di e , and hus, di e en
speeds and dis ance me ics can be conside ed.
• The uck has an unlimi ed capaci y. I ollows ha all cus ome s can be se ed
by uck in one ou , and also he numbe o d ones ca ied by he uck is un e-
s ic ed. This unlimi ed numbe o d ones is also conside ed by (e.g., Tiniç
e al. 2023). We show how o limi he numbe o d ones in Sec .5.3, bu a he
expense o allowing a single loop pe node.
• Mul iple d ones can launch o land a he same ime (e.g., Ra e e al. 2023), i.e.,
we conside unlimi ed launch and e u n pla o ms. This migh be a limi a ion o
he p oposed MILP o mula ion.
• D ones ha e an endu ance limi , i.e., maximum ligh ime pe ligh .
• Assump ions ega ding cus ome s (e.g., Mu ay and Chu 2015):
70
A.Ra e
• All cus ome s mus be se ed once by uck o by d one.
• Some cus ome s canno be se ed by d ones, bu all by uck.
• A d one can se e one cus ome pe ip and has o e u n o he uck a e -
wa ds.
• Assump ions ega ding synch oniza ion:
• I d ones e u n o a node, he uck con inues i s ou a his node as soon as
all e u ning d ones ha e landed.
• D ones mus be picked up by he uck wi hin a ce ain ime (e.g., Mu ay and
Chu 2015; Ra e e al. 2023). This allows o a oid un ealis ic ou es whe e he
d one has o wai o almos he comple e uck’s ou a a node, o example,
a he end o he ou . F om a p ac ical poin o iew, we assume ha d ones
educe hei speed o a ce ain ex en when a i ing a a node be o e he uck,
ollowing he d one mus be picked up wi hin i s endu ance limi .
• D ones only e u n o he uck a a node he uck isi s. This node mus be
he same node hey a e launched om (loop) o a node he uck isi s la e in
i s ou (sidekick).
• The e may be mul iple loops a each node.
• D ones can pe o m loops a he depo . Wi hou loss o gene ali y, hese a e
pe o med a he end o he uck’s ou , which esul s in wai ing imes a he
end o he ou (e.g., Dell’Amico e al. 2021). No e ha in con as o he li e -
a u e, a solu ion migh be ha all cus ome s a e se ed by d ones ha pe o m
a loop a he depo , and hus, he uck does no lea e he depo p o ided ha
all cus ome s can be se ed by d ones and a e in endu ance ange.
• The e a e no se ice, p epa a ion, o endez ous imes o ucks and d ones.
• We do no conside loading o ba e y change imes o d ones as his could be
done while he uck is a eling (e.g., Ra e e al. 2023). Howe e , we show how
o add manual ba e y change imes o ou MILP o mula ion.
• Fo benchma k es s and u he analysis, we conside he ollowing wo p oblem
a ian s:
• mFSTSP: We limi he numbe o d ones o m and p e en d ones om pe -
o ming loops.
• TSPD: We limi he numbe o d ones o one.
2.1 Exempla y ou ing plan
Fo a be e unde s anding o he p oblem se ing, Fig.2 p esen s an example ou ing
o he uck and i s equipped d ones se ing en cus ome s. Cus ome s (
C1
,...,
C10
)
a e numbe ed in he o de o se ing. S a ing a he depo ,
C1
is se ed by he uck
i s , whe e one d one is launched o pe o m a sidekick o se e
C2
. The uck and
he d one mee again a
C3
, whe e a second d one pe o ms a loop and se es
C4
.
No e ha he uck con inues i s ou as soon as bo h d ones ha e e u ned om
se ing
C2
and
C4
. Nex , he uck se es cus ome
C5
and launches a d one o pe -
o m a sidekick o se e
C7
. No e ha he d one can e u n o any node, he uck

71
Two‑indexed o mula ion o  he a eling salesman p oblem…
isi s a a la e s age as long as he ligh ime is wi hin he endu ance limi . A
C6
, a
second d one is launched o pe o m a sidekick o se e
C8
. Bo h d ones e u n o he
uck a
C9
. The uck and i s d ones e u n o he depo a e wa ds, whe e again, one
d one is launched o se e
C10
in a loop. The ou is inished as soon as his d one
e u ns. Thus, he uck wai s a he depo o he d one o e u n.
3 Rela ed li e a u e
In his sec ion, we di e en ia e his pape om he ele an li e a u e ega ding
uck-and-d one andems, whe e one o mul iple ucks a e equipped wi h a leas
one d one. We mainly ocus on li e a u e ha includes a MILP o mula ion wi hou
complex assump ions ha a e no conside ed in ou p oblem se ing, e.g., ba e y
consump ion. Fi s , we p esen he li e a u e whe e d ones only pe o m sidekicks,
and second, we p esen he li e a u e whe e d ones can pe o m bo h sidekicks and
loops. Las , we p esen u he a ian s o uck-and-d one andems. We ecommend
he pape o O o e al. (2018) o an ex ensi e e iew o d one ope a ions and Boy-
sen e al. (2021) o a mo e ecen li e a u e e iew.
3.1 Sidekicks
The FSTSP is ini ially in oduced by Mu ay and Chu (2015) who p esen a h ee-
indexed MILP o mula ion wi h makespan minimiza ion, which has di icul ies o
be sol ed o op imali y i ins ances wi h ele en nodes a e conside ed. As a esul ,
Dell’Amico e al. (2021), F ei as e al. (2023), Yu e al. (2023) and Boccia e al.
(2023) in oduced imp o ed modeling app oaches, which accele a e a s anda d
sol e . Boccia e al. (2023) addi ionally in oduce a b anch-and-cu app oach ha
ou pe o ms hei MILP o mula ion. Fu he , mul iple publica ions conside close
p oblem se ings wi h ei he a di e en objec i e o ex ensions like an inc eased
numbe o ucks o d ones. So, Mu ay and Raj (2020) in oduce he mFSTSP,
whe e he uck is equipped wi h mul iple d ones. Mul iple d ones a e also consid-
e ed by Sei ied (2019), Ca ani e al. (2021), Dell’Amico e al. (2021) and Tamke
Fig. 2 Exempla y ou ing plan o en cus ome s se ed by a uck and i s equipped d ones
72
A.Ra e
and Busche (2021) addi ionally conside mul iple ucks. The au ho s p esen a
MILP o mula ion, and Ca ani e al. (2021) and Tamke and Busche (2021) also an
exac me hod based on a b anch-and-cu algo i hm. Ha e al. (2018) (single uck)
and Sac amen o e al. (2019) (mul iple ucks) ocus on cos minimiza ion and p e-
sen bo h a MILP and heu is ic solu ion app oaches. Mosh e -Ja adi e al. (2020)
conside an objec i e ha minimizes he cus ome s’ wai ing imes, which equals a
makespan minimiza ion bu wi hou conside a ion o he ehicles’ e u n imes o
he depo .
3.2 Sidekicks andloops
The e a e only a ew publica ions conside ing bo h sidekicks and loops. Howe e ,
Sche me e al. (2019) show ha he inal ound ou ing migh include d one loops
as well. The au ho s analyze—among o he hings— he numbe o loops and
sidekicks pe o med in a uck-and-d one andem wi h mul iple ucks and d ones.
D ones’ speed was ound o be a signi ican in luencing ac o on pe o med loops.
Tiniç e al. (2023) p opose wo MILP o mula ions and a b anch-and-cu app oach
and analyze—among o he hings— he impac o loops on he objec i e o cos
minimiza ion i he uck is equipped wi h an unlimi ed numbe o d ones. The
au ho s ind ha allowing d ones o pe o m loops can signi ican ly educe ou ing
cos s. Howe e , an analysis o he impac o minimizing he makespan when pe -
mi ing loops, especially a he depo , is missing. Mo eo e , he au ho s ha e ce -
ain assump ions ha es ic d one ligh s, e.g., d ones a e no pe mi ed o pe o m
loops a he depo .
Dell’Amico e al. (2021) de i e mul iple benchma k esul s o he ins ances o
Mu ay and Chu (2015) o di e en d one se ings, including loops, conside ing
a single d one. Sche me e al. (2020), Robe i and Ru hmai (2021), El-Adle e al.
(2021) and Dell’Amico e al. (2022) p esen wo-indexed o mula ions o a TSPD.
While Sche me e al. (2020) addi ionally in oduce an exac b ach-and-cu app oach
and Robe i and Ru hmai (2021) a b anch-and-p ice app oach ha a e capable o
sol ing la ge ins ances, El-Adle e al. (2021) accele a e he sol e by adding uppe
and lowe bounds by, e.g., s a ing wi h an ini ial solu ion ha is gene a ed by a
g eedy inse ion heu is ic and addi ionally assess he da a in a p e-p ocessing s ep
o educe he numbe o possible d one a cs. Dell’Amico e al. (2022) p esen an
enhanced 2-indexed MILP o mula ion and ou pe o m s a e-o - he-a MILP o -
mula ions om he li e a u e, e.g., Robe i and Ru hmai (2021). Wang e al. (2017)
analyze po en ial makespan sa ings by d ones and de i e mul iple wo s -case
esul s. Conside ing mul iple d one deli e y op ions, Ra e e al. (2023) p esen bo h
a MILP o mula ion and heu is ics solu ion app oach o a p oblem se ing whe e
d ones may launch om ucks and addi ionally om he depo o mic odepo s.
3.3 Va ian s o  uck‑and‑d one andems
Ka ak and Abdelghany (2019) and Mosh e -Ja adi e al. (2020) e alua e uck-and-
d one andems whe e he uck does no se e cus ome s bu only launches d ones a
73
Two‑indexed o mula ion o  he a eling salesman p oblem…
ad an ageous places o pe o m loops. Salama and S ini as (2020) ex end his p ob-
lem by addi ionally allowing he uck o se e cus ome s. Chang and Lee (2018) also
only conside d one loops and se he d one launching spo s lexible by making use o
he k-means clus e ing algo i hm. The uck ou ing is de e mined by sol ing he TSP
in a second s ep. Aga z e al. (2018) (single d one) and Mo andi e al. (2023) (mul i-
ple d ones) conside a a ian whe e d ones ha e he possibili y o e a e sing a cs. In
addi ion, Mo andi e al. (2023) allow d ones o isi mul iple nodes pe ip. This is also
conside ed by Poikonen and Golden (2020), who addi ionally ake he d ones’ ene gy
consump ion in o accoun . Ki jacha oenchai e al. (2019) and İb oşka e al. (2023) con-
side a mul iple TSPD p oblem whe e he assump ion ha a d one migh only e u n o
he same uck is elaxed, and hus, d ones can e u n o a di e en uck. On he con-
a y, he numbe o d one ligh s is es ic ed by conside ing a mos one launch and
e u n pe node, and loops may be only pe o med a he depo . I a loop is pe o med
a he depo , he d one is excluded om he uck’s ou s.
3.4 Di e en ia ion o heli e a u e
Table1 summa izes he majo assump ions, he objec i e, he la ges numbe o a ia-
bles’ indices in he MILP o mula ion, and he la ges ins ance size (including he depo
once) sol ed o op imali y wi h he MILP o mula ion and wi h o he exac me hod i
in oduced. The li e a u e o pa ag aph ”Va ian s o uck-and-d one andems” is no
included due o he la ge di e ence o he p oblem se ing.
Ou p oblem se ing majo di e s om he li e a u e by he un es ic ed numbe o
d ones, he objec i e, and he gene al ligh se ings o d ones, i.e., we also ake d ones
pe o ming loops a he depo in o accoun . As a esul , ou p oblem se ing is he mos
gene al TSPmD o mula ion so a .
F om a me hodological poin o iew, ou MILP is he only one ha has wo-
indexed a iables while conside ing d one loops and mul iple d ones. The e a e ou
wo-indexed o mula ions o he TSPD (El-Adle e al. 2021; Sche me e al. 2020;
Robe i and Ru hmai 2021; Dell’Amico e al. 2022) and one publica ion wi h a wo-
indexed o mula ion o he mFSTSP (Sei ied 2019). Mo eo e , we can sol e ins ances
wi h he la ges numbe o cus ome s wi hou any p e-p ocessing s eps o lowe and
uppe bounds.
The uck-and-d one andem p esen ed in his pape ex ends he one o Ra e e al.
(2023). In con as o hei pape , we minimize he makespan, ha e addi ional assump-
ions (e.g., we conside he e u n ime o d ones o he depo ), and an enhanced mod-
eling e sion o some cons ain s accele a ing he un ime o he sol e .
4 Two‑indexed TSPmD o mula ion
In his sec ion, we p esen he MILP o mula ion o he TSPmD. Fi s , in Sec .4.1,
we desc ibe he p oceeding o c ea ing he wo-indexed o mula ion. Second, in
Sec .4.2, he used index se s, pa ame e s, and a iables a e in oduced. Thi d, in
Sec .4.3, he MILP o mula ion is p esen ed.
74
A.Ra e
4.1 P oceeding o  wo‑indexed o mula ion
A ull ligh o a d one can be in e p e ed as a h ee-node so ie (i,c,j) including he
launch node i, he se ed cus ome c, and he landing node j (Mu ay and Chu 2015),
and hus consis ing o he ou bound ligh o he cus ome and he e u n ligh o he
Table 1 Compa ison o he ele an li e a u e on uck-and-d one andems
No e ha each publica ion lis ed conside s d ones pe o ming sidekicks.
∗
The au ho s added lowe and
uppe bounds and a p e-p ocessing s ep be o e unning he MILP,
∗∗
no d one loops allowed a he depo ,
∗∗∗
d one loops allowed a he depo , bu he d one is hen excluded om i s uck’s ou
Assump ions Objec i e Ins ance size
# T ucks # D ones
(pe
uck)
Loops Cos s Makespan #
Va iables’
indices
MILP O he
exac
me hod
Mu ay and Chu
(2015)
1 1
✓
3 –
Ha e al. (2018) 1 1
✓
3 11
Dell’Amico e al.
(2021)
1 1
✓
2 14
F ei as e al. (2023) 1 1
✓
5 11
Boccia e al. (2023) 1 1
✓
3 20 40
Yu e al. (2023) 1 1
✓
3 11
Sac amen o e al.
(2019)
n1
✓
3 13
Sei ied (2019) 1 m
✓
2 14
Mu ay and Raj (2020) 1 m
✓
4 9
Mosh e -Ja adi e al.
(2020)
1m4 10
Ca ani e al. (2021) 1 m
✓
3 25 25
Dell’Amico e al.
(2021)
1m
✓
3 11
Tamke and Busche
(2021)
n m
✓
5 9 30
El-Adle e al. (2021) 1 1
✓
✓
232
∗
Dell’Amico e al.
(2021)
1 1
✓
✓
3 11
Robe i and Ru hmai
(2021)
1 1
✓
✓
2 10 40
Dell’Amico e al.
(2022)
1 1
✓
✓
2 20
Sche me e al. (2020) 1 1
✓
✓
2 20 20
Tiniç e al. (2023) 1
∞
✓∗∗
✓
3 13 20
Wang e al. (2017)n m
✓
✓
Sche me e al. (2019)n m
✓
∗∗∗
✓
3 11
Ra e e al. (2023)n m
✓
✓
3 15
This pape 1
∞
✓
✓
2 28
81
Two‑indexed o mula ion o  he a eling salesman p oblem…
Cons ain s34–36 a e a ian s o Cons ain s28, 30 and 31 conside ing a single
d one and loops. Cons ain s 37 ensu e ha he d one only launches o pe o m
loops i i was ca ied by he uck a node j. The e may be only loops i he d one
e u ns om a sidekick o a d one a els on he uck o node j (Cons ain s38).
Las , Cons ain s39 ensu e ha he e may be mul iple loops pe node.
5.3 TSPmD: limi ed numbe o d ones
To conside a TSPmD wi h a limi ed numbe o d ones
m∈ℕ
, he ollowing con-
s ain s need o be added o Cons ain s2–27, 29, 33 and 37-39:
These cons ain s a e simila o Cons ain s34–36, howe e , hey limi he numbe
o d ones used o m ins ead o 1. No e ha a limi a ion o his o mula ion wi h mul-
iple d ones is ha each d one can pe o m a maximum o one loop pe node.
6 Nume ical expe imen s
In his sec ion, we desc ibe he ins ances o which we p esen new benchma k solu-
ions (Sec .6.1). Nex , we analyze he un ime sol ing he MILP and compa e he
un ime o ou MILP o MILPs o he mFSTSP and he TSPD om he li e a u e
(35)
𝜋i
,
j≤xi
,
j∀i,j∈I
0
∶i≠j
(36)
∑
c
∈I
D
(
�
yi,c−𝜆i,c
)
≤1∀i∈I
0
(37)
∑
i∈
I
0
𝜋i,j+
∑
c∈
I
D
(
�
yc,j−2⋅𝜆j,c
)
≥0∀j∈I
0
(38)
𝜆
j,k≤
∑
c
∈I
D
(
�
yc,j−𝜆j,c
)
+
∑
i
∈I
0
∶
i
≠
j
𝜋i,j∀j∈I0,k∈I
D
(39)
𝜙
i,i≥
∑
c∈I
D
2⋅ D
i,c
⋅𝜆i,c∀i∈I
0
(40)
∑
j∈
I
𝜋0,j+
∑
c∈
I
D
(
�
y0,c−𝜆0,c
)
=
m
(41)
𝜋i
,
j≤m
⋅
xi
,
j∀i,j∈I
0
∶i≠j
(42)
∑
c
∈I
D
(
�
yi,c−𝜆i,c
)
≤m∀i∈I
0

82
A.Ra e
(Sec .6.2). Las , we analyze he impac o loops in gene al and especially a he
depo on makespan minimiza ion. We also conduc an a-pos e io i cos analysis.
The MILPs a e implemen ed in OPL, sol ed using CPLEX 12.10., and execu ed
on an AMD Ryzen9 3950X wi h 32 GB o RAM (single h ead). Each ins ance has
a un ime limi o 3600s.
6.1 Benchma k ins ances
Fo expe imen s, we conside he publicly a ailable ins ance se s o Mu ay and Chu
(2015) and Bouman e al. (2018). De ailed solu ions o each indi idual ins ance o
benchma k pu poses can be ound in AppendixA o he ins ances o Mu ay and
Chu (2015) and in AppendixB o he ins ances o Bouman e al. (2018). We p e-
sen esul s o hese ins ances o he TSPmD, he mFSTSP (
m=3
), and he TSPD.
6.1.1 Ins ances o Mu ay andChu (2015)
Mu ay and Chu (2015) published wel e ins ances wi h ele en nodes ( en cus om-
e s and he depo ) whose loca ions a e uni o mly dis ibu ed in an
8×8
mile egion.
The au ho s conside wo endu ance limi s o 20 and 40 min and h ee di e en
d one- o- uck speed a ios
𝛼∈{0.6, 1.0, 1.4}
. Simila endu ance limi s a e consid-
e ed by, e.g., Ra e e al. (2023). Thus, he e a e 72 ins ances o which we p esen
esul s o benchma k pu poses. Wi hin he ins ances, he uck ollows a Manha an
dis ance while he d one lies he Euclidean pa h. 80–90% o all cus ome s can be
se ed ia d ones. No e ha we do no conside he launching and endez ous imes
ha a e included in hese ins ances.
6.1.2 Ins ances o Bouman e al. (2018)
Bouman e al. (2018) published ins ances wi h 20 and 50 cus ome s ha a e uni-
o mly dis ibu ed wi h coo dina es om 0 o 100. F om hese ins ances, we con-
side 16, 20, 24, 28, and 32 nodes as in El-Adle e al. (2021). These a e d awn by
aking he i s 16, 20, 24, 28, and 32 nodes om he ins ance wi h he nex -la ges
numbe o nodes, i.e., 16 and 20 nodes om ins ances wi h 20 nodes, and 24, 28,
and 32 nodes om ins ances wi h 50 nodes. The endu ance limi is se o 30, and
d ones ha e he same speed as he uck. Bo h d ones and he uck a el he Euclid-
ean pa h. This is an uncommon assump ion. Howe e , he a el ime is impo an ,
which depends on he speed and dis ance, so we a y he a el ime by inc easing
he d one speed in he analyses. All cus ome s can be se ed by d ones.
6.2 Run ime analysis
To show he e iciency o ou MILP o mula ion o he TSPmD and also o he
wo p oblem a ian s, we analyze hei un ime in his sec ion. Fi s , in Sec .6.2.1,
we compa e he un ime o he TSPmD, he mFSTSP, and he TSPD. Second, in
83
Two‑indexed o mula ion o  he a eling salesman p oblem…
Sec .6.2.2, we benchma k ou MILP’s un ime wi h a o al o eigh MILP o mula-
ions om he li e a u e, sol ing ou p oblem a ian s.
6.2.1 Run ime analysis o  heTSPmD and he wo p oblem a ian s
In his sec ion, we analyze he un ime o sol ing ou MILP o he TSPmD and he
wo p oblem a ian s, he mFSTSP wi h
m=3
and he TSPD. Table3 epo s he
esul s o he ins ances agg ega ed by he numbe o nodes
|I0|
and he endu ance
e. The able shows he numbe o ins ances sol ed o op imali y, he a e age un ime
needed in seconds, and he a e age op imali y gap i he sol e could no ind he
op imal solu ion wi hin 3600s.
Findings Fo he ins ances o Mu ay and Chu (2015), we could ind all op imal
solu ions excep wo i one d one is conside ed (TSPD). In pa icula , i is no iceable
o all hese ins ances ha he op imal solu ion is ound much as e when mul i-
ple d ones a e conside ed and when he endu ance is lowe . This is because he e
a e mo e d one ligh s in he op imal solu ion conside ing he TSPmD, esul ing in
sho e uck ou es. In addi ion, a lowe endu ance educes he numbe o easible
ligh op ions.
Fo he ins ances o Bouman e al. (2018), we could ind all op imal solu ions o
ins ances wi h 16 and 20 nodes, eigh o en op imal solu ions o ins ances wi h 24
nodes, and up o h ee op imal solu ions o ins ances wi h 28 nodes when conside -
ing he TSPmD, he mFSTSP, and he TSPD. In con as o he ins ances o Mu -
ay and Chu (2015), no signi ican change in un ime can be obse ed i mul iple
d ones a e conside ed. This is because d ones a e less compe i i e owa ds he uck
in hese ins ances as bo h ollow he Euclidean pa h and, hus, he compu a ion ime
mainly a ises om he uck ou ing.
6.2.2 Run ime compa ison o heli e a u e
The wo-indexed MILP o mula ion o he TSPmD, mFSTSP, and TSPD p esen ed
in his pape can sol e ins ances wi h mo e nodes han he MILP o mula ions om
he li e a u e (see also Table1). So, Mu ay and Chu (2015) could no sol e one o
he 72 ins ances wi h ele en nodes o op imali y. Conside ing he ins ances o Bou-
man e al. (2018), El-Adle e al. (2021) could ind op imal solu ions o up o wo
ou o he en ins ances wi h 24 nodes. Howe e , i is di icul o compa e he MILPs
based on esul s in he li e a u e, as hey ha e sligh ly di e en assump ions, a di e -
en sol e (o e sion o sol e ) is used, and hey we e un on a compu e wi h di -
e en RAM. Thus, o show he e iciency o ou MILP o mula ion in compa ison o
he li e a u e, we implemen ed in o al eigh MILP o mula ions om he li e a u e.
6.2.2.1 P oblem a ian : mFSTSP We implemen ed he ou -indexed MILP o Mu -
ay and Raj (2020) wi h an au oma ed launch and eco e y sys em, he h ee-indexed
MILP o Ca ani e al. (2021), and he h ee-indexed MILP wi h c ossing so ie a i-
ables o Dell’Amico e al. (2021) in OPL. The MILP o mula ions mainly di e om
ou MILP by he la ge numbe o indices and cons ain s and by conside ing he
depo wice, i.e., o he s a and end o he ou . The MILP o mula ions we e cho-
84
A.Ra e
Table 3 Agg ega ed esul s o ins ances o Mu ay and Chu (2015) and Bouman e al. (2018)
P oblem a ian 1 P oblem a ian 2
TSPmD mFSTSP (m = 3) TSPD
|I0|
eOp CPU [s] Gap (%) Op CPU [s] Gap (%) Op CPU [s] Gap (%)
Mu ay and Chu (2015) 11 20 36/36 3 0 36/36 6 0 36/36 90 0
11 40 36/36 3 0 36/36 14 0 34/36 850 0
Summa y 72/72 3 72/72 10 70/72 470
Bouman e al. (2018) 16 30 10/10 6 0 10/10 6 0 10/10 11 0
20 30 10/10 349 0 10/10 227 0 10/10 275 0
24 30 8/10 1211 1 8/10 1093 0 8/10 1301 1
28 30 2/10 3197 3 3/10 3139 3 2/10 3285 4
32 30 0/10 3600 9 0/10 3600 11 0/10 3600 12
Summa y 30/50 1673 31/50 1613 30/50 1694
85
Two‑indexed o mula ion o  he a eling salesman p oblem…
sen, as Mu ay and Raj (2020) ini ially in oduced he mFSTSP and Ca ani e al.
(2021) and Dell’Amico e al. (2021) de eloped a MILP ha is easie o sol e. We
es ed he MILP o mula ions o he ins ances o Mu ay and Chu (2015) and Bou-
man e al. (2018). No e ha he MILP o Ca ani e al. (2021) equi es a d one speed
ha is a leas he uck’s speed. Thus, only a subse o he ins ances o Mu ay and
Chu (2015) is conside ed. Fu he mo e, we adjus ed he MILP o Ca ani e al. (2021)
by endu ance cons ain s simila o Cons ain s 13 and 14, and we added cons ain s
ensu ing ha some cus ome s canno be se ed by d one, bu by uck. This is al eady
included in he MILP o mula ions o Mu ay and Raj (2020) and Dell’Amico e al.
(2021).
Table4 p esen s he agg ega ed esul s sol ing all h ee MILPs and ou MILP
o mula ion o he mFSTSP. The column Gap shows he a e age op imali y gap i
he sol e canno ind he op imal solu ion wi hin 3600s. No e ha all MILP o -
mula ions ep esen he same p oblem se ing o he mFSTSP wi h h ee d ones
ha can only pe o m sidekicks. Fo implemen ing he MILPs, we also conside
he enhanced modeling assump ions o accele a e he MILP sol e p esen ed in he
pape s (simila o Cons ain 3).
Findings The MILP o Mu ay and Raj (2020) canno no sol e any ins ance
conside ed. Fo he ins ances o Bouman e al. (2018), he MILP canno e en ind
a single lowe bound. This is in line wi h he indings o Mu ay and Raj (2020)
hemsel es, who only ound op imal solu ions o 66% o he conside ed ins ances
wi h eigh cus ome s. Con a y, he MILPs o Ca ani e al. (2021) and Dell’Amico
e al. (2021) can sol e he ins ances o Mu ay and Chu (2015). Conside ing la ge
ins ances, he MILP o Ca ani e al. (2021) sol es up o wo ins ances wi h 24 nodes,
and he MILP o Dell’Amico e al. (2021) sol es se en ins ances wi h 16 nodes o
op imali y. Ou MILP o mula ion, howe e , no only inds all op imal solu ions o
he ins ances o Mu ay and Chu (2015) wi h a low un ime o 10s bu also up
o h ee op imal solu ions o ins ances o Bouman e al. (2018) wi h 28 nodes. I
he op imal solu ion canno be ound, he gaps a e a he small. Only he MILP o
Ca ani e al. (2021) has a lowe un ime o he ins ances o Mu ay and Chu (2015)
bu can only sol e a subse o all conside ed ins ances. Thus, ou MILP o mula ion
o he mFSTSP ou pe o ms he MILP o mula ions o Mu ay and Raj (2020) and
Dell’Amico e al. (2021) o all conside ed ins ances, and he MILP o mula ion o
Ca ani e al. (2021) o la ge ins ances.
In “Appendix C”, we u he benchma k ou MILP o he MILP o Boccia
e al. (2023) o he special case o
m=1
, inding ha we ou pe o m i o la ge
ins ances.
6.2.2.2 P oblem a ian : TSPD We implemen ed he MILPs o Sche me e al. (2020),
Robe i and Ru hmai (2021) and El-Adle e al. (2021), and he wo-indexed MILP
o Dell’Amico e al. (2022) o a TSPD in OPL. The o mula ions o Robe i and
Ru hmai (2021) and El-Adle e al. (2021) di e om ou MILP by conside ing addi-
ional a iables acking he d one’s ou , e en i i is ca ied on he uck. Mo eo e ,
Sche me e al. (2020), Robe i and Ru hmai (2021) and Dell’Amico e al. (2022)
conside he depo wice, i.e., o he s a and end o he ou . The MILP o mula ions
a e chosen o compa ison, as hey a e e icien MILP o mula ions o he TSPD.
86
A.Ra e
Table 4 Agg ega ed esul s unning he MILPs o Mu ay and Raj (2020) and Dell’Amico e al. (2021), and om his pape o he ins ances o Mu ay and Chu (2015)
and Bouman e al. (2018)
All MILP o mula ions ep esen an mFSTSP ( h ee d ones, sidekicks, no loops) wi h he same objec i e and assump ions.
∗
We modi ied he MILP by endu ance con-
s ain s
MILP o Mu ay and Raj
(2020)
MILP o Ca ani e al. (2021)
∗
MILP o Dell’Amico e al.
(2021)
Ou MILP (mFSTSP)
|
I
0|
eOp CPU [s] Gap (%) Op CPU [s] Gap (%) Op CPU [s] Gap (%) Op CPU [s] Gap (%)
Mu ay and Chu (2015) 11 20 0/36 3600 93 24/24 3 0 36/36 108 0 36/36 6 0
11 40 0/36 3600 98 24/24 2 0 36/36 132 0 36/36 14 0
Summa y 0/72 3600 48/48 2 72/72 120 72/72 10
Bouman e al. (2018) 16 30 0/10 3600 100 10/10 390 0 7/10 1646 5 10/10 6 0
20 30 0/10 3600 100 3/10 2881 7 0/10 3600 25 10/10 227 0%
24 30 0/10 3600 100 2/10 3070 9 0/10 3600 34 8/10 1093 0
28 30 0/10 3600 100 0/10 3600 12 0/10 3600 46 3/10 3139 3
32 30 0/10 3600 100 0/10 3600 16 0/10 3600 64 0/10 3600 11
Summa y 0/50 3600 15/50 2708 7/50 3209 31/50 1613

87
Two‑indexed o mula ion o  he a eling salesman p oblem…
Again, we es ed he MILP o mula ions o he ins ances o Mu ay and Chu
(2015) and Bouman e al. (2018). Howe e , only a subse o he ins ances o Mu ay
and Chu (2015) is sui able o Robe i and Ru hmai (2021) and El-Adle e al. (2021)
because bo h MILP o mula ions equi e a d one speed ha is a leas he same as
he uck’s speed. The MILPs o Sche me e al. (2020) and El-Adle e al. (2021) a e
addi ionally adjus ed by endu ance cons ain s ha limi he wai ing imes o d ones
(simila o Cons ain s 13 and 14). This is al eady conside ed by Robe i and Ru h-
mai (2021) and Dell’Amico e al. (2022). No e ha o implemen ing he MILPs,
we also conside he enhanced modeling assump ions o accele a e he MILP sol e
p esen ed in he pape s (simila o Cons ain 3), bu no lowe o uppe bounds o
any p e-p ocessing s eps as in El-Adle e al. (2021). Table5 p esen s he agg ega ed
esul s sol ing he MILPs. No e ha all MILP o mula ions ep esen he same p ob-
lem se ing o he TSPD wi h one d one ha can pe o m bo h sidekicks and loops.
Findings The MILP o Robe i and Ru hmai (2021) wo ks qui e well o
ins ances o Mu ay and Chu (2015), sol ing all o hem o op imali y. Fo la ge
ins ances, howe e , no one ins ance wi h 16 o mo e nodes could be sol ed. The
MILP o Sche me e al. (2020) wo ks bes o he ins ances o Mu ay and Chu
(2015), as all 72 ins ances could be sol ed op imally wi h he lowes un ime on
a e age, bu , on he o he hand, i has di icul ies sol ing he ins ances wi h 16 o
mo e nodes. The MILP o Dell’Amico e al. (2022) has a simila pe o mance com-
pa ed o he MILP o Sche me e al. (2020) o he ins ances o Mu ay and Chu
(2015) bu wo ks be e o la ge ins ances. Running he MILP o El-Adle e al.
(2021), i ou pe o ms ou MILP o ins ances o Mu ay and Chu (2015) whe e he
d one has a leas he uck’s speed. Fu he mo e, ega ding he ins ances o Bouman
e al. (2018), op imal solu ions o all en ins ances wi h 16 and 20 nodes and i e
ou o en ins ances wi h 24 nodes can be ound. In con as , ou MILP o mula ion
can addi ionally be sol ed o op imali y o h ee mo e ins ances wi h 24 nodes and
wo ins ances wi h 28 nodes. Mo eo e , he a e age un ime and he op imali y gap
a e signi ican ly lowe . Thus, ou MILP o mula ion o he TSPD ou pe o ms he
li e a u e o la ge ins ances. Addi ionally, i should be no ed ha ou MILP o mu-
la ion is mo e gene al compa ed o Robe i and Ru hmai (2021) and El-Adle e al.
(2021) as d ones migh ha e lowe speeds han ucks, and also in compa ison o
Sche me e al. (2020) and Dell’Amico e al. (2022) as mul iple d ones can be con-
side ed wi hou any inc ease in un ime.
Summa y Ou wo-indexed MILP o mula ion ou pe o ms all eigh conside ed
MILP o mula ions om he li e a u e o la ge ins ances, inding solu ions o
ins ances wi h a la ge numbe o nodes. I op imali y canno be p o en, he op imal-
i y gap is, mo eo e , he lowes compa ed o all o he MILPs. Only o he ins ances
o Mu ay and Chu (2015) ou MILP o mula ion does no pe o m bes . Please no e
ha o he exac solu ion me hods, e.g., he b anch-and-p ice o Robe i and Ru h-
mai (2021), migh s ill ou pe o m ou MILP o mula ion.
6.2.2.3 Value o linea elaxa ion a  he oo node Fu he , we compa e he alue
o he linea elaxa ion a he oo node o all conside ed MILPs o he mFSTSP
and he TSPD. Fo his, Table6 shows he gap be ween he op imal solu ion, i
a ailable, and else he bes - ound solu ion sol ing all MILPs and he alue o he
88
A.Ra e
Table 5 Agg ega ed esul s unning he MILPs o Sche me e al. (2020), El-Adle e al. (2021) and Dell’Amico e al. (2022), and om his pape o he ins ances o Mu -
ay and Chu (2015) and Bouman e al. (2018)
All MILP o mula ions ep esen a TSPD (single d one, sidekicks, and loops) wi h he same objec i e and assump ions.
∗
We modi ied he MILP by endu ance cons ain s
MILP o Sche me e al.
(2020)
∗
MILP o Robe i and
Ru hmai (2021)
MILP o El-Adle e al.
(2021)
∗
MILP o Dell’Amico
e al. (2022)
Ou MILP (TSPD)
|
I
0|
eOp CPU [s] Gap (%) Op CPU [s] Gap (%) Op CPU [s] Gap (%) Op CPU [s] Gap (%) Op CPU [s] Gap (%)
Mu ay and
Chu (2015)
11 20 36/36 9 0 24/24 238 0 24/24 93 0 36/36 11 0 36/36 90 0
11 40 36/36 17 0 24/24 76 0 23/24 399 1 36/36 28 0 34/36 850 0
Summa y 72/72 13 48/48 157 47/48 246 72/72 19 0 70/72 470
Bouman
e al.
(2018)
16 30 9/10 418 16 0/10 3600 19 10/10 27 0 9/10 441 1 10/10 11 0
20 30 3/10 3185 9 0/10 3600 28 10/10 576 0 6/10 2531 2 10/10 275 0
24 30 0/10 3600 11 0/10 3600 30 5/10 2165 4 1/10 3292 7 8/10 1301 1
28 30 0/10 3600 13 0/10 3600 81 0/10 3600 9 0/10 3600 11 2/10 3285 4
32 30 0/10 3600 17 0/10 3600 88 0/10 3600 17 0/10 3600 15 0/10 3600 12
Summa y 12/50 2880 0/50 3600 25/50 1994 16/50 2693 30/50 1694
89
Two‑indexed o mula ion o  he a eling salesman p oblem…
Table 6 Gap [%] be ween he op imal solu ion i a ailable and he alue o he linea elaxa ion a he oo node o all conside ed MILPs o he ins ances o Mu ay and
Chu (2015) and Bouman e al. (2018)
∗
We modi ied he MILP by endu ance cons ain s
mFSTSP TSPD
Mu ay and
Raj (2020)
(% )
Ca ani e al.
(2021)
∗
(%)
Dell’Amico
e al. (2021)
(%)
Ou MILP
(%)
Sche me
e al. (2020)
∗
(%)
Robe i and
Ru hmai
(2021) (%)
El-Adle
e al.
(2021)
∗
(%)
Dell’Amico
e al. (2022)
(%)
Ou MILP
Mu ay and
Chu (2015)
11 20 100 63 69 68 56 59 57 69 70
11 40 100 56 63 62 53 57 54 67 68
Summa y 100 59 66 65 54 58 55 68 69
Bouman e al.
(2018)
16 30 100 76 83 97 61 62 82 79 97
20 30 100 75 87 99 62 63 86 81 98
24 30 100 73 90 99 58 59 91 79 98
28 30 100 72 90 99 57 58 92 78 98
32 30 100 72 89 99 56 57 93 78 98
Summa y 100 74 88 99 59 60 89 79 98
90
A.Ra e
linea elaxa ion a he oo node. The esul s o all conside ed MILPs o he
mFSTSP and he TSPD a e epo ed.
Findings We obse e ha ou MILP o mula ion ne e has he lowes gap o
he linea elaxa ion a he oo node o bo h he mFSTSP and he TSPD. Con-
side ing he mFSTSP Ca ani e al. (2021) has he lowes gap. Conside ing he
TSPD, on he o he hand, he MILP o El-Adle e al. (2021) has he bes alue
o linea elaxa ion o he ins ances o Mu ay and Chu (2015) (TSPD), and he
MILP o Robe i and Ru hmai (2021) o he ins ances o Bouman e al. (2018).
Howe e , we ind ha he gap a he oo node is no di ec ly a good indica o o
an e icien MILP o mula ion as Robe i and Ru hmai (2021) could no sol e a
single ins ance o Bouman e al. (2018) o op imali y despi e ha ing a good alue
o he linea elaxa ion a he oo node. Mo eo e , we obse e ha ou MILPs’
alue o he linea elaxa ion a di ec subsequen nodes inc eases signi ican ly o
all conside ed p oblem a ian s.
6.3 Impac o d one loops
D one loops as an addi ional ou ing op ion o d ones migh educe he makespan
𝜏∗
, bu on he o he hand, conside ing loops migh inc ease he sol e ’s un ime on
a e age, which in u n can be p oblema ic, as uck-and-d one andems a e di icul
o sol e e en o heu is ic solu ion app oaches (e.g., Sac amen o e al. 2019). So,
Sche me e al. (2019) al eady ound ha d ones pe o m loops in he solu ions, and
Tiniç e al. (2023) ound ha loops migh educe o al ou ing cos s. Howe e , in
he solu ions p esen ed by Dell’Amico e al. (2021), d ones do no pe o m a single
loop. Thus, in he ollowing, we gi e de ailed insigh s on he makespan educ ion
and he un ime inc ease when allowing loops compa ed o p ohibi ing all kinds o
loops o he ins ances o Mu ay and Chu (2015) and Bouman e al. (2018) sol -
ing he TSPD and he TSPmD wi h a ying endu ance limi s e, and uck- o-d one
speed a ios
𝛼
. Fo his, we only compa e ins ances sol ed op imally o he case
wi h and wi hou d one loops.
6.3.1 Ins ances o Mu ay andChu (2015)
Table7 p esen s he educ ion o he makespan
𝜏∗
and he inc ease in he un ime
o he MILP sol e in pe cen i d ones can pe o m loops. Fo his, he makespan
conside ing loops is compa ed o he makespan i loops a e o bidden. We gene a e
esul s o wo endu ance limi s (
e=20
,
e=40
), and i e speed ac o s (
𝛼=0.6
,
𝛼=1.0
,
𝛼=1.4
,
𝛼=2.0
,
𝛼=2.8
). These a e wo addi ional speed ac o s (
𝛼=2.0
,
𝛼=2.8
) compa ed o he da a conside ed in Mu ay and Chu (2015) as he speed
has a signi ican impac on he numbe o pe o med loops (Sche me e al. 2019).
Each en y p esen s he a e age
𝜏∗
educ ion o un ime inc ease o up o wel e
ins ances. No e ha he e migh be less han wel e ins ances conside ed i hey a e
no sol ed o op imali y. A nega i e en y in column “Run ime inc ease [%]“ means
he e is a dec ease in un ime.
97
Two‑indexed o mula ion o  he a eling salesman p oblem…
Appendix A: Benchma k esul s o ins ances o Mu ay andChu
(2015)
The ollowing Tables11 and 12 p esen esul s o he ins ances o Mu ay and
Chu (2015) o he endu ance o
e=20
and
e=40
. The ins ance names a e sim-
ila o Dell’Amico e al. (2021).
Appendix B: Benchma k esul s o ins ances o Bouman e al. (2018)
The ollowing Tables13, 14, 15, 16 and 17 p esen he esul s o he ins ances o
Bouman e al. (2018). The ins ance names a e simila o El-Adle e al. (2021) and
he esul s a e spli up o each conside ed numbe o nodes.
Appendix C: Benchma k es wi h heMILP o Boccia e al. (2023)
We u he es he MILP o Boccia e al. (2023) because his MILP seems o
be an e icien o mula ion. This MILP only conside s a single d one pe o m-
ing sidekicks. Thus, we addi ionally benchma k ou MILP o he special case
o an mFSTSP wi h
m=1
o hei h ee-indexed MILP o mula ion. Simila o
ou MILP, he MILP o Boccia e al. (2023) conside s wo-indexed a iables o
d one ligh s. Howe e , a h ee-indexed a iable acks i he uck a els an a c
(i,j) while he d one se es a cus ome k. Mo eo e , he MILP is an a c-based
o mula ion. We es ed he MILP o mula ion o he ins ances o Mu ay and
Chu (2015) and Bouman e al. (2018). As he ins ances o Mu ay and Chu (2015)
conside he case ha only a subse o cus ome s can be se ed by d one, he
MILP o Boccia e al. (2023) is adjus ed by cons ain s simila o Cons ain s4
o 6.
Conside ing he ins ances o Mu ay and Chu (2015), he MILP o mula ion
o Boccia e al. (2023) pe o ms be e han ou MILP o mula ion (Table18).
Howe e , when conside ing la ge ins ances, he MILP has se e e un ime issues,
while ou MILP o mula ion can sol e 2 ins ances wi h 28 nodes.
One majo d awback o he MILP o mula ion o Boccia e al. (2023) is ha
hey elimina e sub ou s by a o mula ion ha is based on subse s. As a esul ,
he e is a huge amoun o cons ain s, which canno e en be gene a ed in OPL in
a easonable amoun o ime. To ackle his p oblem, Boccia e al. (2023) de elop
a b anch-and-cu app oach ha igno es he sub ou elimina ion in he i s s ep.

98
A.Ra e
Table 11 Resul s o ins ances o Mu ay and Chu (2015) wi h an endu ance o 20
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
20140810T123437 1 51.3825 4 – 51.3825 5 – 54.3926 14 –
20140810T123437 2 51.6111 5 – 51.6111 6 – 51.6111 8 –
20140810T123437 3 52.8225 8 – 52.8225 10 – 54.0684 17 –
20140810T123437 4 65.6225 5 – 65.6225 8 – 66.8684 9 –
20140810T123437 5 24.4390 1 – 32.0655 8 – 45.3353 239 –
20140810T123437 6 24.0264 2 – 28.9400 8 – 43.9153 241 –
20140810T123437 7 39.8664 7 – 43.2069 13 – 46.5813 28 –
20140810T123437 8 53.1454 7 – 57.7700 16 – 59.3813 20 –
20140810T123437 9 21.8536 1 – 24.9912 9 – 39.2035 687 –
20140810T123437 10 21.9720 1 – 25.7710 8 – 36.9077 160 –
20140810T123437 11 32.3077 2 – 34.4110 8 – 39.3002 52 –
20140810T123437 12 45.1077 3 – 47.7507 9 – 51.5645 29 –
20140810T123440 1 43.8455 4 – 43.8455 7 – 46.4304 31 –
20140810T123440 2 46.2455 7 – 46.2455 12 – 49.3737 42 –
20140810T123440 3 51.6277 9 – 51.6277 8 – 53.6616 19 –
20140810T123440 4 64.4277 6 – 64.4277 9 – 66.4616 10 –
20140810T123440 5 31.6066 2 – 32.2263 2 – 39.7498 198 –
20140810T123440 6 34.0066 2 – 34.0066 1 – 40.3790 85 –
20140810T123440 7 40.7304 1 – 40.7304 2 – 43.3126 29 –
20140810T123440 8 53.5304 1 – 53.5304 2 – 55.7960 31 –
20140810T123440 9 31.6066 1 – 31.6066 1 – 35.5331 9 –
20140810T123440 10 34.0066 1 – 34.0066 1 – 36.0764 9 –
20140810T123440 11 40.7304 1 – 40.7304 1 – 40.7304 4 –
20140810T123440 12 53.5304 1 – 53.5304 1 – 53.5304 8 –
20140810T123443 1 69.5865 1 – 69.5865 4 – 69.5865 5 –
20140810T123443 2 71.5839 4 – 71.7473 3 – 72.0639 7 –
20140810T123443 3 75.9039 2 – 76.0673 2 – 76.1447 2 –
20140810T123443 4 88.7039 3 – 88.8673 2 – 89.1839 5 –
20140810T123443 5 39.7845 4 – 42.2634 4 – 54.7521 222 –
20140810T123443 6 43.9992 5 – 45.0943 6 – 55.1268 106 –
20140810T123443 7 60.8333 5 – 60.8333 5 – 62.2491 11 –
20140810T123443 8 73.8724 6 – 76.3401 26 – 80.0971 79 –
20140810T123443 9 24.5760 1 – 27.6100 2 – 41.9314 724 –
20140810T123443 10 30.9760 1 – 30.9760 1 – 42.9348 86 –
20140810T123443 11 43.7760 2 – 43.7760 1 – 51.4056 11 –
20140810T123443 12 56.5760 1 – 56.5760 1 – 62.6175 8 –
99
Two‑indexed o mula ion o  he a eling salesman p oblem…
Table 12 Resul s o ins ances o Mu ay and Chu (2015) wi h an endu ance o 40
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
20140810T123437 1 33.8109 8 – 35.5186 75 – 49.1189 2946 –
20140810T123437 2 32.6510 7 – 35.3759 25 – 46.3113 490 –
20140810T123437 3 40.9090 10 – 49.2858 71 – 52.6868 221 –
20140810T123437 4 54.5333 47 – 62.5748 58 – 65.4868 238 –
20140810T123437 5 24.4390 1 – 28.4013 27 – 42.8354 3600 7.8%
20140810T123437 6 24.0264 1 – 28.4688 11 – 41.6015 1155 –
20140810T123437 7 35.8290 5 – 36.4363 9 – 43.3913 220 –
20140810T123437 8 48.6273 6 – 50.5161 12 – 56.1913 397 –
20140810T123437 9 21.8536 1 – 24.9912 6 – 37.8082 1771 –
20140810T123437 10 21.9720 2 – 25.7710 9 – 36.9077 879 –
20140810T123437 11 26.4022 1 – 29.3975 18 – 39.3002 86 –
20140810T123437 12 37.3724 1 – 42.1352 17 – 51.2536 134 –
20140810T123440 1 32.3895 1 – 35.5331 22 – 45.1029 993 –
20140810T123440 2 34.0066 1 – 37.2360 53 – 44.4461 1014 –
20140810T123440 3 45.3532 10 – 45.3532 16 – 52.3083 620 –
20140810T123440 4 58.1532 10 – 58.9284 14 – 66.3969 610 –
20140810T123440 5 31.6066 1 – 32.2263 2 – 39.7498 497 –
20140810T123440 6 34.0066 0 – 34.0066 1 – 39.6581 157 –
20140810T123440 7 40.7304 1 – 40.7304 1 – 43.3126 37 –
20140810T123440 8 53.5304 1 – 53.5304 1 – 55.7960 36 –
20140810T123440 9 31.6066 1 – 31.6066 1 – 35.5331 24 –
20140810T123440 10 34.0066 0 – 34.0066 1 – 36.0764 11 –
20140810T123440 11 40.7304 1 – 40.7304 1 – 40.7304 8 –
20140810T123440 12 53.5304 1 – 53.5304 1 – 53.5304 1 –
20140810T123443 1 37.4695 2 – 37.5843 5 – 54.0129 2117 –
20140810T123443 2 35.1953 1 – 38.5950 7 – 56.5729 1894 –
20140810T123443 3 47.4513 1 – 54.6474 23 – 66.1746 314 –
20140810T123443 4 65.6295 1 – 69.2538 7 – 81.4603 418 –
20140810T123443 5 24.2916 1 – 31.2183 9 – 48.5789 3600 20.7%
20140810T123443 6 30.0160 0 – 35.0597 9 – 48.4864 1993 –
20140810T123443 7 42.8160 0 – 44.3748 3 – 56.8793 354 –
20140810T123443 8 55.6160 0 – 56.5760 2 – 68.3988 181 –
20140810T123443 9 23.6160 0 – 27.6100 2 – 41.9314 3086 –
20140810T123443 10 30.0160 0 – 30.9760 2 – 42.9348 473 –
20140810T123443 11 42.8160 0 – 42.8160 0 – 51.3950 30 –
20140810T123443 12 55.6160 0 – 55.6160 0 – 62.6175 8 –
100
A.Ra e
Table 13 Resul s o ins ances o Bouman e al. (2018) wi h 16 nodes
|I0|
=
16
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
Uni o m-61-n20 346.9223 28 – 347.0919 27 – 347.0919 73 –
Uni o m-62-n20 353.7019 2 – 353.7019 2 – 353.7019 2 –
Uni o m-63-n20 370.1349 2 – 372.9289 2 – 372.9289 2 –
Uni o m-64-n20 357.9113 9 – 357.9113 9 – 357.9113 10 –
Uni o m-65-n20 368.6511 4 – 368.6511 3 – 368.6511 4 –
Uni o m-66-n20 426.5167 2 – 426.5167 2 – 426.5167 2 –
Uni o m-67-n20 372.7803 1 – 372.7803 1 – 372.7803 2 –
Uni o m-68-n20 423.3365 2 – 423.3443 2 – 423.3365 3 –
Uni o m-69-n20 363.4143 5 – 363.4143 5 – 363.4143 7 –
Uni o m-70-n20 410.1439 7 – 410.1439 6 – 410.1439 7 –
Table 14 Resul s o ins ances o Bouman e al. (2018) wi h 20 nodes
|I0|
=
20
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
Uni o m-61-n20 351.4622 1113 – 351.4622 895 – 351.5212 958 –
Uni o m-62-n20 374.1195 1497 – 374.1195 452 – 374.1195 379 –
Uni o m-63-n20 391.7060 28 – 394.5000 33 – 394.5000 57 –
Uni o m-64-n20 368.7314 425 – 368.7314 524 – 368.7314 578 –
Uni o m-65-n20 381.0652 42 – 381.0652 39 – 390.5601 215 –
Uni o m-66-n20 434.9542 57 – 435.1632 111 – 436.2728 108 –
Uni o m-67-n20 391.4744 40 – 391.4744 29 – 391.4744 40 –
Uni o m-68-n20 435.6068 24 – 435.6068 22 – 435.6068 40 –
Uni o m-69-n20 380.4329 218 – 380.4329 126 – 380.4329 331 –
Uni o m-70-n20 422.6549 41 – 422.6549 38 – 422.6549 40 –
101
Two‑indexed o mula ion o  he a eling salesman p oblem…
Table 15 Resul s o ins ances o Bouman e al. (2018) wi h 24 nodes
|I0|
=
24
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
Uni o m-71-n50 415.8466 681 – 415.8466 625 – 415.8466 1057 –
Uni o m-72-n50 410.1562 30 – 410.1562 31 – 410.1562 32 –
Uni o m-73-n50 391.3397 317 – 391.3397 173 – 394.5155 487 –
Uni o m-74-n50 467.6828 345 – 467.6828 297 – 467.6828 472 –
Uni o m-75-n50 463.6015 1810 – 463.6015 973 – 463.6015 680 –
Uni o m-76-n50 394.2924 3600 5.3% 394.2924 3600 1.2% 394.2924 3600 2.1%
Uni o m-77-n50 452.9030 139 – 452.9030 197 – 458.7309 467 –
Uni o m-78-n50 410.8227 1040 – 410.8227 886 – 412.8484 2192 –
Uni o m-79-n50 412.1437 547 – 412.1437 553 – 412.1437 422 –
Uni o m-80-n50 391.7442 3600 1.6% 391.7442 3600 1.6% 397.2048 3600 4.0%
Table 16 Resul s o ins ances o Bouman e al. (2018) wi h 28 nodes
|I0|
=
28
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
Uni o m-71-n50 441.6016 3600 3.0% 441.6016 3600 3.8% 446.9016 3600 5.6%
Uni o m-72-n50 449.6584 355 – 449.6584 470 – 449.6584 448 –
Uni o m-73-n50 445.8629 3600 1.9% 445.8796 3600 0.3% 449.0387 3600 2.2%
Uni o m-74-n50 470.8405 3600 0.4% 470.8406 2843 – 470.8407 3600 0.4%
Uni o m-75-n50 473.0050 3600 4.7% 473.2393 3600 4.1% 473.0050 3600 4.9%
Uni o m-76-n50 407.4875 3600 7.5% 407.4875 3600 7.9% 407.7456 3600 10.5%
Uni o m-77-n50 480.5687 2820 – 480.5687 2879 – 485.5172 3600 2.4%
Uni o m-78-n50 459.4857 3600 1.4% 459.4857 3600 1.0% 462.1742 3600 1.5%
Uni o m-79-n50 447.7367 3600 7.5% 447.7367 3600 6.4% 447.7367 3600 7.4%
Uni o m-80-n50 449.3641 3600 6.2% 449.3641 3600 7.1% 454.8248 3600 9.0%
102
A.Ra e
Table 17 Resul s o ins ances o Bouman e al. (2018) wi h 32 nodes
|I0|
=
32
P oblem a ian 1: P oblem a ian 2:
TSPmD mFSTSP (m = 3) TSPD
Ins ance
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
𝜏∗
CPU (s) Gap
Uni o m-
71-n50
478.3559 3600 5.8% 478.3559 3600 6.2% 483.6558 3600 7.2%
Uni o m-
72-n50
493.0942 3600 2.5% 493.0942 3600 3.8% 493.0942 3600 4.3%
Uni o m-
73-n50
488.0547 3600 3.9% 490.4018 3600 6.2% 497.0028 3600 7.7%
Uni o m-
74-n50
478.5537 3600 11.2% 518.4635 3600 17.4% 480.7702 3600 13.6%
Uni o m-
75-n50
500.3800 3600 9.8% 510.0112 3600 13.4% 525.9658 3600 16.3%
Uni o m-
76-n50
496.0703 3600 20.1% 480.0877 3600 16.7% 484.6235 3600 19.2%
Uni o m-
77-n50
515.3738 3600 5.6% 511.1739 3600 4.5% 518.2364 3600 7.4%
Uni o m-
78-n50
504.8168 3600 5.2% 505.1834 3600 4.7% 507.7490 3600 5.4%
Uni o m-
79-n50
454.3164 3600 9.9% 479.9965 3600 15.5% 467.9651 3600 13.2%
Uni o m-
80-n50
447.2753 3600 13.2% 458.6088 3600 18.4% 481.3873 3600 24.6%
Table 18 Agg ega ed esul s unning he MILPs o Boccia e al. (2023) and om his pape o he
ins ances o Mu ay and Chu (2015) and Bouman e al. (2018)
MILP o Boccia e al.
(2023)
Ou MILP (mFSTSP,
m
=
1
)
|I0|
eOp CPU (s) Gap Op CPU (s) Gap
Mu ay and Chu (2015) 11 20 36/36 34 0% 36/36 94 0%
11 40 36/36 28 0% 35/36 783 0%
Summa y 72/72 31 71/72 439
Bouman e al. (2018) 16 30 10/10 720 0% 10/10 9 0%
20 30 0/10 – – 10/10 139 0%
24 30 0/10 – – 8/10 1115 3%
28 30 0/10 – – 2/10 3111 5%
32 30 0/10 – – 0/10 3600 10%
Summa y 10/50 – 30/50 1595

103
Two‑indexed o mula ion o  he a eling salesman p oblem…
Acknowledgemen s The au ho s g a e ully hank he anonymous e iewe s, he depa men edi o , and
he edi o o hei aluable ecommenda ions, which ha e signi ican ly imp o ed ou pape .
Funding Open Access unding enabled and o ganized by P ojek DEAL.
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
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
Aga z N, Bouman P, Schmid M (2018) Op imiza ion app oaches o he a eling salesman p oblem
wi h d one. T ansp Sci 52(4):965–981. h ps:// doi. o g/ 10. 1287/ sc. 2017. 0791
Boccia M, Mancuso A, Masone A, S e le C (2023) A new MILP o mula ion o he lying sidekick a e-
ling salesman p oblem. Ne wo ks 82(3):254–276. h ps:// doi. o g/ 10. 1002/ ne . 22172
Boysen N, Fed ke S, Schwe d ege S (2021) Las -mile deli e y concep s: a su ey om an ope a ional
esea ch pe spec i e. OR Spec um 43(1):1–58. h ps:// doi. o g/ 10. 1007/ s00291- 020- 00607-8
Bouman, P., Aga z, N., Schmid , M.: Ins ances o he TSP wi h D one (and some solu ions) ( 1.2).
Zenodo (2018). Las access: 14 Feb 2023
Ca ani S, Io i M, Robe i R (2021) Exac me hods o he a eling salesman p oblem wi h mul iple
d ones. T ansp Res Pa C Eme g Technol 130:103280. h ps:// doi. o g/ 10. 1016/j. c. 2021. 103280
Chang YS, Lee HJ (2018) Op imal deli e y ou ing wi h wide d one-deli e y a eas along a sho e uck-
ou e. Expe Sys Appl 104:307–317. h ps:// doi. o g/ 10. 1016/j. eswa. 2018. 03. 032
Dell’Amico M, Mon emanni R, No ellani S (2021) D one-assis ed deli e ies: new o mula ions o
he lying sidekick a eling salesman p oblem. Op im Le 15:1617–1648. h ps:// doi. o g/ 10.
1007/ s11590- 019- 01492-z
Dell’Amico M, Mon emanni R, No ellani S (2021) Modeling he lying sidekick a eling salesman
p oblem wi h mul iple d ones. Ne wo ks 78(3):303–327. h ps:// doi. o g/ 10. 1002/ ne . 22022
Dell’Amico, M., Mon emanni, R., No ellani, S.: Benchma k ins ances and op imal solu ions o he
a eling salesman p oblem wi h d one. a Xi p ep in a Xi : 2107. 13275 (2021)
Dell’Amico M, Mon emanni R, No ellani S (2022) Exac models o he lying sidekick a eling
salesman p oblem. In T ans Ope Res 29(3):1360–1393. h ps:// doi. o g/ 10. 1111/ i o . 13030
El-Adle AM, Ghoniem A, Haoua i M (2021) Pa cel deli e y by ehicle and d one. J Ope Res Soc
72(2):398–416. h ps:// doi. o g/ 10. 1080/ 01605 682. 2019. 16711 56
F ei as JC, Penna PHV, To olo TAM (2023) Exac and heu is ic app oaches o uck-d one deli e y
p oblems. EURO J T ansp Logis 12:100094. h ps:// doi. o g/ 10. 1016/j. ej l. 2022. 100094
Ga ne , J.: JD.com’s D one deli e y p og am akes ligh in Ru al China. Wo ld Wide Web (2016).
Las Access 17 May 2022
Ha QM, De ille Y, Pham QD, Hà MH (2018) On he min-cos a eling salesman p oblem wi h d one.
T ansp Res Pa C Eme g Technol 86:597–621. h ps:// doi. o g/ 10. 1016/j. c. 2017. 11. 015
İb oşka B, Özpeyni ci S (2023) Özpeyni ci: mul iple a eling salespe son p oblem wi h d ones: Gen-
e al a iable neighbo hood sea ch app oach. Compu Ope Res 160:106390. h ps:// doi. o g/ 10.
1016/j. co . 2023. 106390
Ka ak A, Abdelghany K (2019) The hyb id ehicle-d one ou ing p oblem o pick-up and deli e y
se ices. T ansp Res Pa C Eme g Technol 102:427–449. h ps:// doi. o g/ 10. 1016/j. c. 2019. 03.
021
Ki jacha oenchai P, Ven esca M, Mosh e -Ja adi M, Lee S, Tanchoco JMA, B unese PA (2019) Mul-
iple a eling salesman p oblem wi h d ones: ma hema ical model and heu is ic app oach. Com-
pu Indus Eng 129:14–30. h ps:// doi. o g/ 10. 1016/j. cie. 2019. 01. 020
104
A.Ra e
Mille CE, Tucke AW, Zemlin RA (1960) In ege p og amming o mula ion o a eling salesman
p oblem. J ACM 7(4):326–329. h ps:// doi. o g/ 10. 1145/ 321043. 321046
Mo andi N, Leus R, Ma uschke J, Yaman H (2023) The a eling salesman p oblem wi h d ones: he
bene i s o e a e sing he a cs. T ansp Sci 57(5):1340–1358. h ps:// doi. o g/ 10. 1287/ sc. 2022.
0230
Mosh e -Ja adi M, Hemma i A, Winkenbach M (2020) A uck and d ones model o las -mile deli e y:
a ma hema ical model and heu is ic app oach. Appl Ma h Model 80:290–318. h ps:// doi. o g/ 10.
1016/j. apm. 2019. 11. 020
Mosh e -Ja adi M, Lee S, Winkenbach M (2020) Design and e alua ion o a mul i- ip deli e y model
wi h uck and d ones. T ansp Res Pa E Logis T ansp Re 136:101887. h ps:// doi. o g/ 10. 1016/j.
e. 2020. 101887
Mu ay CC, Chu AG (2015) The lying sidekick a eling salesman p oblem: op imiza ion o d one-
assis ed pa cel deli e y. T ansp Res Pa C Eme g Technol 54:86–109. h ps:// doi. o g/ 10. 1016/j. c.
2015. 03. 005
Mu ay CC, Raj R (2020) The mul iple lying sidekicks a eling salesman p oblem: pa cel deli e y wi h
mul iple d ones. T ansp Res Pa C Eme g Technol 110:368–398. h ps:// doi. o g/ 10. 1016/j. c. 2019.
11. 003
O o A, Aga z N, Campbell J, Golden B, Pesch E (2018) Op imiza ion app oaches o ci il applica ions o
unmanned ae ial ehicles (UAVs) o ae ial d ones: a su ey. Ne wo ks 72(4):411–458. h ps:// doi.
o g/ 10. 1002/ ne . 21818
Poikonen S, Golden B (2020) Mul i- isi d one ou ing p oblem. Compu Ope Res 113:104802. h ps://
doi. o g/ 10. 1016/j. co . 2019. 104802
Ra e A, Fon aine P, Kuhn H (2023) D one loca ion and ehicle lee planning wi h ucks and ae ial
d ones. Eu J Ope Res 308(1):113–130. h ps:// doi. o g/ 10. 1016/j. ejo . 2022. 10. 015
Robe i R, Ru hmai M (2021) Exac me hods o he a eling salesman p oblem wi h d one. T ansp Sci
55(2):315–335. h ps:// doi. o g/ 10. 1287/ sc. 2020. 1017
Ra e A, Fon aine P, Kuhn H (2023) D one ne wo k design o eme gency esupply o pha macies and
ambulances. A ailable a SSRN 4569199
Sac amen o D, Pisinge D, Røpke S (2019) An adap i e la ge neighbo hood sea ch me aheu is ic o he
ehicle ou ing p oblem wi h d ones. T ansp Res Pa C Eme g Technol 102:289–315. h ps:// doi.
o g/ 10. 1016/j. c. 2019. 02. 018
Salama M, S ini as S (2020) Join op imiza ion o cus ome loca ion clus e ing and d one-based ou -
ing o las -mile deli e ies. T ansp Res Pa C Eme ging Technol 114:620–642. h ps:// doi. o g/ 10.
1016/j. c. 2020. 01. 019
Sche me D, Moeini M, Wend O (2019) A ma heu is ic o he ehicle ou ing p oblem wi h d ones and
i s a ian s. T ansp Res Pa C Eme g Technol 106:166–204. h ps:// doi. o g/ 10. 1016/j. c. 2019. 06.
016
Sche me D, Moeini M, Wend O (2020) A b anch-and-cu app oach and al e na i e o mula ions o he
a eling salesman p oblem wi h d one. Ne wo ks 76(2):164–186. h ps:// doi. o g/ 10. 1002/ ne . 21958
Sei ied, K.: The a eling salesman p oblem wi h one uck and mul iple d ones. A ailable a SSRN
3389306 (2019)
Tamke F, Busche U (2021) A b anch-and-cu algo i hm o he ehicle ou ing p oblem wi h d ones.
T ansp Res Pa B Me hodol 144:174–203. h ps:// doi. o g/ 10. 1016/j. b. 2020. 11. 011
Tiniç GO, Ka asan OE, Ka a BY, Campbell JF, Ozel A (2023) Exac solu ion app oaches o he mini-
mum o al cos a eling salesman p oblem wi h mul iple d ones. T ansp Res Pa B Me hodol
168:81–123. h ps:// doi. o g/ 10. 1016/j. b. 2022. 12. 007
Wang X, Poikonen S, Golden B (2017) The ehicle ou ing p oblem wi h d ones: se e al wo s -case
esul s. Op im Le 11(4):679–697. h ps:// doi. o g/ 10. 1007/ s11590- 016- 1035-3
Yu VF, Lin S-W, Jodiawan P, Lai Y-C (2023) Sol ing he lying sidekick a eling salesman p oblem by a
simula ed annealing heu is ic. Ma hema ics 11(20):4305
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps
and ins i u ional a ilia ions.