A Model o he Mul idepo Mul iple T a elling
Salesman P oblem and Ad anced Resolu ion
S a egies
Juan Pablo Fiesco , Bea iz And es(B), and Raul Pole
Resea ch Cen e on P oduc ion Managemen and Enginee ing (CIGIP), Uni e si a Poli ècnica
de València (UPV), Camino de Ve a S/N, 46022 Valencia, Spain
{j iesco,band es, pole }@cigip.up .es
Abs ac . This pape del es in o he Mul idepo Mul iple T a elling Salesman
P oblem (MDMTSP), an ex ension o he TSP ha p esen s addi ional complexi-
ies. A e iew o he s a e o he a is pe o med, om which a MDMTSP mixed
in ege linea p og amming model is ex ac ed. Fo his model, a new objec i e
unc ion and new a iables a e added o co e he need o balance he numbe o
ci ies o be isi ed by each salesman. Va ious s a egies a e also in es iga ed o
educe he compu a ion imes associa ed wi h he NP-Ha d MDMTSP. The p o-
posed ma hema ical model is no only an abs ac heo y, bu will also be in eg a ed
in o he AI-Deli e y Op imise solu ion o he AIDEAS p ojec . This in eg a ion
ep esen s a s ep owa ds he manu ac u ing indus y o he u u e, whe e a i icial
in elligence and p ocess op imisa ion will wo k oge he o d i e compe i i eness
and business success.
Keywo ds: Mul iple T a elling Salesmen ·P oblem Solu ion App oaches ·
Modelling
1 In oduc ion
The Mul iple T a elling Salesman P oblem (MTSP) expands upon he T a elling Sales-
man P oblem (TSP) by in oducing mul iple salesmen asked wi h isi ing a se o ci ies
exac ly once be o e e u ning o hei s a ing poin , ypically a depo , a he minimum
a el cos . The MTSP has applica ions in op imisa ion p oblems like ehicle ou ing
p oblems (VRPs), ask assignmen s, machine and ope a o scheduling in manu ac u -
ing, in en o y managemen and wa ehouse eplenishmen , o o de -picking p oblems in
wa ehouses [1]. The MTSP p ohibi s mul iple isi s and sub ou s by dis inguishing i
om he ask assignmen p oblem. In he scena io wi h a single depo , all he salesmen
ini ia e and conclude hei ou s a a sole loca ion, bu when mul iple depo s a e p esen
(MDMTSP), each hos s a speci ic numbe o salesmen wi h lexibili y o e u n o ei he
hei o iginalo di e en depo s[2].As heMDMTSPisaNP-ha dp oblem, heobjec i e
o his pape is o p o ide a ious ad anced esolu ion s a egies o educe compu a ion
imes. This pape has been done wi hin he scope o he AI-D i en Indus ial Equipmen
© The Au ho (s), unde exclusi e license o Sp inge Na u e Swi ze land AG 2025
A. A. Juan e al. (Eds.): DSA ISC 2024, LNCS 14778, pp. 353–360, 2025.
h ps://doi.o g/10.1007/978-3-031-78238-1_32
354 J. P. Fiesco e al.
P oduc Li e Cycle Boos ing Agili y, Sus ainabili y and Resilience (AIDEAS) Ho izon
Eu ope p ojec . AIDEAS p oposes a se o in elligen solu ions o suppo he manu-
ac u ing phase in he machine y indus y. Solu ions include he p ocu emen op imise
(AI-PO), he ab ica ion op imise (AI-FO) and he deli e y op imise (AI-DO). The cu -
en pape ocuses on he AI-DO, which is an op imisa ion solu ion applied o suppo
he p oduc anspo a ion p oblem. Acco dingly, he pape pays a en ion o he de el-
opmen o ad anced echniques o add ess he MDMTSP. So his pape is o ganised
as ollows: Sec . 2summa ises he s a e o he a . Sec ion 3 o mula es he MDMTSP
and alida es he model wi h sho expe imen s. Sec ion 4desc ibes a se o ad anced
s a egies o educe he MDMTSP esolu ion imes. Finally, conclusions a e discussed
in Sec . 5.
2 S a e o he A
In he MTSP con ex , he au ho s discussing he p oblem coincide wi h he ac ha mo e
e icien heu is ic algo i hms a e equi ed, especially in la ge-scale da ase s, which high-
ligh s he need o de elop inno a i e esolu ion s a egies in his domain. Al hough exac
me hods p omise op imal solu ions, hey p o e imp ac ical o la ge ins ances due o
he p oblem’s complexi y. Along hese lines, [2] emphasises he e icacy o b anch-
and-bound me hods, especially when pai ed wi h well-selec ed ini ial bounds. A mo e
ecen s udy by [3] unde sco es he use o bo h exac and heu is ic echniques. Heu is ic
app oaches, such as gene ic algo i hms (GA) o an colony (AC), ha e gained a ou o
hei e iciency in ackling he MTSP. Fu he mo e, hyb id algo i hms ha blend me a-
heu is ics wi h local sea ches o clus e ing me hods [4] and ma heu is ics ha combine
exac me hods wi h heu is ics o me aheu is ics [5] ha e su aced o mi iga e compu a-
ional complexi y and con e gence ime. These di e se solu ion me hodologies e lec
a conce ed endea ou o e icien ly add ess he MTSP by s i ing o s ike a balance
be ween op imali y and p ac icali y.
Fo i sapplicabili y, heTSP has adi ionallybeen usedin anspo , p oduc dis ibu-
ion, p oduc ion planning and logis ics. Mo eo e , ecen ad ances in d one echnology
ha e led o academy and indus y in e es being shown in in es iga ing he applica ion o
unmanned ae ial ehicles (UAVs) [6]. Some s udies in he li e a u e ocus on he coope -
a ion o ucks and d ones o las -mile deli e y [7,8]. In ligh o his, [3] desc ibe eigh
mo e possible applica ion a eas, including mul i obo ask alloca ion and scheduling,
disas e managemen , and moni o ing and su eillance.
This pape ocuses on he MDMTSP, a TSP ex ension challenge ha has been
add essed in a ious ways. The wo k o [9] is pa icula ly no ewo hy, which del es in o
he applica ion o mul iple depo s and mul iple peddle s o he acili y loca ion p oblem.
Thei s udy inco po a es c ucial ac o s, such as ehicle au onomy and se ice equency
equi emen s, by p o iding aluable insigh in o eal-wo ld logis ics scena ios. Ano he
in e es ing con ibu ion is ha by [10] who in oduces he mul idepo elec ic ehicle
loca ion ou ing p oblem wi h ime windows by ex ending he classic VRP o include
elec ic ehicles and ene gy supply op ions.
A Model o he Mul idepo Mul iple T a elling Salesman P oblem 355
3 P oblem Fo mula ion
The MTSP in ol es op imising ou es o mul iple salesmen, each s a ing and ending
hei ou a a designa ed depo while isi ing a se o ci ies exac ly once. In he a ian
MDMTSP, he p oblem is compounded by conside ing mul iple po en ial depo s om
which salesmen can ini ia e hei ou es. The objec i e is o di ide he se o ci ies in o
subse s, each co esponding o a ou o a speci ic salesman, o ensu e ha e e y ci y is
isi ed exac ly once in each subse . Addi ionally, each ou mus commence and conclude
a i s espec i e depo , wi h a minimum equi emen o wo nodes isi ed du ing each
ou . The goal may include minimising he o al dis ance a elled by all he salesmen
o balancing hei wo kload. Figu e 1depic s a wo- ou e g aph by illus a ing he pa hs
ha each sales pe son will ake o isi ci ies and o e u n o hei espec i e depo s.
F om he analysis o he s a eo he a , he mixedin ege linea p og amming(MILP)
ou lined in [11] is aken as a e e ence o p opose ad anced echniques and o imp o e
esolu ion imes. The MILP uses h ee decision a iables:
•Xkij =1, i salespe son k isi s node j immedia ely a e node i; 0, o he wise.
•zi=1, i node i is he s a ing (o igin) node du ing a ou o any salespe son; 0,
o he wise.
•ui= isi ing ank o node i
Objec i e Func ion (1) seeks o minimise he o al cos , ep esen ed by he combined
leng h o m ou s.
Minimize n
i=1n
j=1:i=j(dij m
k=1Xkij)(1)
Subjec o:
n
i=1:i=jm
k=1Xkij =1∀j=1,2,...,n(2)
n
i=1:i=pXkip −n
j=1:j=pXkpj =0∀p=1,...,n,k=1,2,...,m(3)
n
i=1:i=jm
k=1Xkij ≥1∀k=1,2,...,m(4)
ui−uj+L·m
k=1Xkij ≤L−1+L·zj∀i,j=1,2,...,n:i= j(5)
1≤ui≤L∀i=1,2,...,n(6)
n
i=1zi=m(7)
Xkij ∈{0,1}∀i,j=1,...,n:i= j,k=1,2,...,m(8)
zi∈{0,1}∀i=1,...,n(9)
356 J. P. Fiesco e al.
Cons ain (2) ensu es ha each node is isi ed exac ly once du ing ou s. Flow
conse a ion Cons ain Se (3) manda es ha i a salespe son isi s a node, (s)he mus
also depa om i . Cons ain Se (4) ensu es ha each salespe son is assigned o a ou .
Cons ain s (5) and (6) p e en undesi able sub ou s, wi h L ep esen ing he maximum
numbe o nodes ha a salespe son can isi , calcula ed as L=n−2m +2. Fu he mo e,
cons ain (5) allows ha in he case whe e index i is he las node isi ed be o e a i ing
i s depo node (j), and whe e ui akes he highes acco ding o i s isi o de (L o
app oxima ely L), he a iable Xkij can also ake he alue one espec ing he limi a ion
on he igh -hand side o he cons ain because zjis equal o one.
Cons ain (7) speci ies he m s a ing nodes co esponding o m ou s. Las ly,
cons ain s (8) and (9) de ine he decision a iables u ilised in he model.
Wi h his o mula ion o he p oblem, wha is minimised is he o al dis ance a elled
by all he salespe sons. Howe e , ano he aspec o conside is he load o ci ies assigned
by each agen ; his amoun should be equi able o no sa u a e a salespe son. Thus [11]
p opose a new MILP model o he MDTSP wi h a min-max objec i e by adding he
a iable Smax. Inspi ed by his wo k, we p opose a new MILP ha minimises bo h he
o al ou e, and he de ia ion be ween he maximum and minimum numbe o loca ions
o isi , by penalising he solu ion wi h an imbalance in ou e alloca ion.
STMAX =numbe o loca ions isi ed on he longes ou e.
STMIN =numbe o loca ions isi ed on he sho es ou e.
The new Objec i e Func ion (10) minimises he o al cos o m ou s and he bias o
he maximum numbe o loca ions isi ed and a minimum numbe . Cons ain s (2)– (9)
emain he same, while cons ain s (11) and (12) calcula e he maximum and minimum
numbe o loca ions isi ed by all he salespe sons.
Minimise n
i=1n
j=1:i=j(dij m
k=1Xkij)+(STMAX −STMIN)·c(10)
n
i=1n
j=1:i=jXkij ≥STMIN∀k=1,2,...,m(11)
n
i=1n
j=1:i=jXkij ≤STMAX ∀k=1,2,...,m(12)
Nex a se o expe imen s alida ing he p oposed model is p esen ed by conside ing
small, medium and la ge da a size ins ances. A able wi h he expe imen esul s is
o e ed (Table 1). Each ins ance is ep esen ed by he numbe o cus ome s, he numbe
o ucks and depo s, which a e he same, he balance o he numbe o cus ome s isi ed
by each uck (100% indica es ha ucks isi he same numbe o cus ome s), he
o al cos , he GAP and he esolu ion ime. The sol e so wa e used in his esea ch is
GUROBI, which is gene ally employed o sol e MILP p oblems. The p oposed MILP
has been implemen ed as a Py hon applica ion unning on a CPU wi h 12 h Gen In el(R)
Co e(TM) i7-12700 2.10 GHz p ocesso (6 GB RAM). The GAP is calcula ed as he
absolu e di e ence be ween he a ge alue o he bes known solu ion and he cu en
bes solu ion, di ided by he absolu e alue o he bes known solu ion.
By analysing he esul s in Table 1, i can be concluded ha he exac me hod used can
achie e op imal solu ions in seconds o small ins ances. Howe e , o la ge ins ances,
he solu ion is a om op imal and limi s he ime o 15 min. This shows he need o
explo e new s a egies o sol e he p oblem.
A Model o he Mul idepo Mul iple T a elling Salesman P oblem 357
Fig. 1. Example o an MDMTSP and a solu ion.
Table 1. Ins ance expe imen s esul s.
Ins ance No.
Cus ome s
No.
T ucks
No.
Depo s
Balance To al
cos
GAP Time
(sec.)
2_10_S1 10 2 2 100.00% 428 0.00% 2.24
2_54_M1 54 2 2 100.00% 780 13.04% 900
2_89_M2 89 2 2 97.82% 1016 11.27% 900
2_96_M3 96 2 2 100.00% 1068 16.59% 900
2_100_M4 100 2 2 100.00% 1064 19.15% 900
4_30_L1 30 4 4 88.88% 564 26.96% 900
4_73_L2 73 4 4 95.00% 1118 37.31% 900
4_91_L3 91 4 4 95.83% 1324 56.48% 900
4_95_L4 95 4 4 96.00% 1350 55.91% 900
4 Ad anced Resolu ion S a egies o he MDMTSP
Sol ing he MDMTSP en ails de ising e icien algo i hms capable o handling he
combina o ial complexi y inhe en in de e mining op imal ou es while espec ing he
cons ain s imposed by mul iple depo s and he equi emen o isi ing each ci y exac ly
once. The MDMTSP is an NP-ha d p oblem, which means ha inding an op imal
solu ion can ake an exponen ial amoun o ime depending on he size o he p oblem.
This sec ion p oposes a se o ad anced echniques o imp o e he MDMTSP esolu ion
imes wi hou comp omising he solu ion quali y, bu by achie ing he op imal bounds.
358 J. P. Fiesco e al.
(i) E olu iona y app oaches: me aheu is ics, such as GA, AC o simula ed annealing
(SA),which expe imen wi h di e en pa ame e se ings, suchas popula ionsizes,
mu a ion a es and s opping c i e ia, o ind he combina ion ha bes wo ks o a
speci ic da ase [11].
(ii) Hyb id algo i hms: hey employ he combina ion o GA, AC o SA me aheu is-
ics o make he mos o he s eng hs o he di e en me hods and o imp o e
con e gence speed [4].
(iii) Imp o ed cons uc ion heu is ics: i in es iga es mo e sophis ica ed cons uc ion
heu is ics o gene a ing ini ial ou es, such as he modi ied Nea es Neighbou
Algo i hm, he Nea es Inse ion Algo i hm o he Bes Inse ion Heu is ic [12].
(i ) Relaxa ion app oaches: heya e employed o ans o m he MILP in oa con inuous
p oblem o ob ain ini ial solu ions. They use g adual imp o emen echniques o
a i e a a mo e op imal solu ion [13].
( ) Neighbou hood sea ch echniques: hey implemen neighbou hood sea ch ech-
niques, such as local sea ch o la ge neighbou hood sea ch, o explo e nea by
solu ions and i e a i ely imp o e he cu en solu ion.
( i) Pa allelisa ion echniques: hey in ol e he simul aneous execu ion o mul iple
compu a ions o mo e e icien ly sol e he p oblem. Pa allel GA use pa allelism
in he e alua ion and e olu ion o candida e solu ions, mul iple popula ions o
solu ions can be e ol ed concu en ly, and c osso e and mu a ion ope a ions a e
pe o med independen ly on di e en subse s o he popula ion [14].
( ii) Decomposi ion Techniques and Clus e ing: hey decompose he p oblem in o se -
e al smalle ones, de ine “clus e s” a ound Depo s. They di ide he MTSP in o a
se ies o subp oblems, each ep esen ing a ou o an indi idual salesman. They
sequen ially op imise each ou , possibly using a TSP sol e , and combine solu-
ions o o m he o e all solu ion. They di ide ci ies in o clus e s and assign each
clus e o a di e en salesman. Finally, he ou es connec ing clus e s a e op imised
[15].
( iii) Ma heu is ics: his combine exac me hods wi h heu is ics o me aheu is ics o
p o ide p esolu ions o he MILP [5].
I can be concluded ha he e is no an unique esolu ion s a egy o imp o ing he
MDMTSP, and ha he selec ed s a egies o sol e he MDMTSP depend on he p oblem
cha ac e is ics and he speci ic equi emen s o he applica ion. Expe imen ing wi h
a ious echniques and adjus ing pa ame e s can help making signi ican imp o emen s
in he speed and quali y o solu ions.
5 Conclusions and Fu u e Resea ch Lines
In conclusion, his pape p esen s a b ie s a e o he a o he MDMTSP, analyses an
MILP p oposed by Ka abulu e al. (2021) and p oposes a new o mula ion by adding
he minimisa ion o load balance o isi ed loca ions o he objec i e unc ion. Addi ion-
ally, a ious s a egies a e explo ed o educe he compu a ion imes associa ed wi h his
combina o ial p oblem. These s a egies include e olu iona y app oaches, hyb id algo-
i hms, imp o ed cons uc ion heu is ics, elaxa ion app oaches, neighbou hood sea ch
ools, pa allelisa ion echniques, decomposing app oaches, clus e ing and ma heu is ics.
A Model o he Mul idepo Mul iple T a elling Salesman P oblem 359
Fo a eal-wo ld applica ion o his p oblem, he po en ial o combining he MTSP wi h
depo managemen and depo loca ion design p oblems is highligh ed o o e ing a
comp ehensi e pe spec i e o add ess logis ics and dis ibu ion challenges.
Compu a ional expe imen s we e ca ied ou on small, medium and la ge da ase s,
o which he las ones a e capable o simula ing eal-wo ld p oblems. Small ins ances
app oxima e op imal solu ions in an a e age o wo seconds wi h 0% o GAP. Medium
ins ances do no achie e he op imal solu ion, al hough longe compu a ion imes imply
a educ ion in he GAP. Finally, he esolu ion o la ge da ase s exponen ially inc ease
compu a ional imes wi hou achie ing an op imal solu ion, which demons a es ha
he MDMTSP is an NP-ha d p oblem ha needs ad anced echniques o ob ain good
solu ions in sho e compu a ional imes. To all his, a se o nine ad anced esolu ion
s a egies is p oposed.
I is no ewo hy ha his esea ch aligns wi h he AIDEAS p ojec and i s solu ion, he
AIDEASDeli e yOp imise , an AI-based ool capableo op imising p oduc s o age and
deli e y. This solu ion no only ocuses on op imising s o age space, s o age condi ions
and p oduc anspo a ion, bu also p o ides op imisa ion o logis ics planning and
scheduling.
As u u e esea ch di ec ions, u he explo ing he applica ion o he p oposed
ad anced s a egies o imp o e he compu a ional e iciency o he MDMTSP is sug-
ges ed, as well as in eg a ing hese solu ions in o p ac ical sys ems like he AIDEAS
Deli e y Op imise o enhance logis ics managemen in eal business en i onmen s.
The e o e as a nex s ep o his esea ch, he decomposi ion o he p oblem in o
smalle ones by de ining clus e s a ound depo s and u ilising ma heu is ics o p o ide
p esolu ions o he MILP, a e p oposed o be implemen ed.
Acknowledgemen s. The esea ch ha led o hese indings ecei ed unding om he Ho izon
Eu ope Re .101057294 “AI-D i en Indus ial Equipmen P oduc Li e Cycle Boos ing Agili y,
Sus ainabili y, and Resilience (AIDEAS)”; he Regional Depa men o Inno a ion, Uni e -
si ies, Science, and Digi al Socie y o he Gene ali a Valenciana “P og ama In es igo” Re .
INVEST/2022/330, which he Eu opean Union suppo ed - Nex Gene a ionEU wi h Plan de Recu-
pe ación, T ans o mación y Resiliencia; he Regional Depa men o Inno a ion, Uni e si ies, Sci-
ence, and Digi al Socie y o he Gene ali a Valenciana Re . CIAEST/2022/39 “Doc o al esea ch
s a o ca y ou esea ch s ays in companies in he Valencia Region”; and he Vice-Rec o a e
o Resea ch o he Uni e si a Poli ècnica de València Re . PAID-06-23 “In elligen op imisa ion
algo i hms and models o p oduc ion planning and eplenishmen (ATENNEA)”.
Re e ences
1. Ma ai,R., Singh, S.,Lal, M.: T a eling salesmanp oblem:an o e iewo applica ions, o mu-
la ions, and solu ion app oaches. In: T a eling Salesman P oblem, Theo y and Applica ions.
InTech (2010). h ps://doi.o g/10.5772/12909
2. Bek as,T.: Themul iple a eling salesmanp oblem:an o e iewo o mula ionsand solu ion
p ocedu es. Omega (Wes po ) 34(3), 209–219 (2006). h ps://doi.o g/10.1016/j.omega.2004.
10.004
3. Cheikh ouhou, O., Khou i, I.: A comp ehensi e su ey on he mul iple a eling salesman
p oblem: applica ions, app oaches and axonomy. Compu . Sci. Re . 40. (2021). h ps://doi.
o g/10.1016/j.cos e .2021.100369
360 J. P. Fiesco e al.
4. Jiang, C., Wan, Z., Peng, Z.: A new e icien hyb id algo i hm o la ge scale mul iple a el-
ing salesman p oblems. Expe Sys . Appl. 139 (2020). h ps://doi.o g/10.1016/j.eswa.2019.
112867
5. Guzman, E., And es, B., Pole , R.: Models and algo i hms o p oduc ion planning, scheduling
and sequencing p oblems: a holis ic amewo k and a sys ema ic e iew. J. Ind. In . In eg .
27 (2022). h ps://doi.o g/10.1016/j.jii.2021.100287
6. Khou i,I., Laoui i,A., Adjih,C.: Asu eyo ecen ex ended a ian so he a elingsalesman
and ehicle ou ing p oblems o unmanned ae ial ehicles. D ones 3(3), 1–30 (2019). h ps://
doi.o g/10.3390/d ones3030066
7. Zhang, R., Dou, L., Xin, B., Chen, C., Deng, F., Chen, J.: A e iew on he uck and d one
coope a i e deli e y p oblem Unmanned Sys . (2023). h ps://doi.o g/10.1142/S23013850
24300014
8. Rinaldi, M., P ima es a, S., Bugaj, M., Ros áš, J., Guglie i, G.: De elopmen o heu is ic
app oaches o las -mile deli e y TSP wi h a uck and mul iple d ones. D ones 7(7) (2023).
h ps://doi.o g/10.3390/d ones7070407
9. Chan, Y., Bake , S.F., Chan, Y., Dij, D.: The Mul iple Depo , Mul iple T a eling Salesmen
Facili y-Loca ionP oblem:VehicleRange,Se ice F equency,andHeu is icImplemen a ions
(2005). www.else ie .co n/loca e/mcm
10. Paz, J.C., G anada-Eche e i, M., Escoba , J.W.: The mul i-depo elec ic ehicle loca ion
ou ing p oblem wi h ime windows. In . J. Ind. Eng. Compu . 9(1), 123–136 (2018). h ps://
doi.o g/10.5267/j.ijiec.2017.4.001
11. Ka abulu , K., Öz op, H., Kandille , L., Tasge i en, M.F.: Modeling and op imiza ion o mul-
iple a eling salesmen p oblems: An e olu ion s a egy app oach. Compu . Ope . Res. 129
(2021). h ps://doi.o g/10.1016/j.co .2020.105192
12. U sani, Z., U sani, A.A.: Augmen ed ou cons uc ion heu is ics o he a elling salesman
p oblem. In . J. Ind. Op im. 4(2), 131–144 (2023). h ps://doi.o g/10.12928/ijio. 4i2.7875
13. Riccia di, L.A., Vasile, M.: Sol ing mul i-objec i e dynamic a elling salesman p oblems
by elaxa ion. In: GECCO 2019 Companion - P oceedings o he 2019 Gene ic and E olu-
iona y Compu a ion Con e ence Companion, pp. 1999–2007. Associa ion o Compu ing
Machine y, Inc., (2019). h ps://doi.o g/10.1145/3319619.3326837
14. Dhanalakshmi, R., Pa hiban, P., Anbuchezhian, N.: Op imisa ion o mul iple a elling sales-
man p oblem using me aheu is ic me hods. In . J. En e p. Ne w. Manag. 13(3), 199–215
(2022). h ps://doi.o g/10.1504/IJENM.2022.125803
15. Romanuke, V.V.: Deep clus e ing o he a eling salesman p oblem o pa allelize i s solu ion.
Compu . Ope . Res. 165 (2024). h ps://doi.o g/10.1016/j.co .2024.106548
