Pe is, Ma eo; A che i, Claudia; Ca a uzza, Diego; Ogie , Maxime; Seme , F édé ic
A icle
A B anch-P ice-and-Cu algo i hm o he Mul i-
Commodi y wo-echelon Dis ibu ion P oblem
EURO Jou nal on T anspo a ion and Logis ics (EJTL)
P o ided in Coope a ion wi h:
Associa ion o Eu opean Ope a ional Resea ch Socie ies (EURO), F ibou g
Sugges ed Ci a ion: Pe is, Ma eo; A che i, Claudia; Ca a uzza, Diego; Ogie , Maxime; Seme ,
F édé ic (2024) : A B anch-P ice-and-Cu algo i hm o he Mul i-Commodi y wo-echelon
Dis ibu ion P oblem, EURO Jou nal on T anspo a ion and Logis ics (EJTL), ISSN 2192-4384, Else ie ,
Ams e dam, Vol. 13, Iss. 1, pp. 1-13,
h ps://doi.o g/10.1016/j.ej l.2024.100139
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/325210
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 ps://c ea i ecommons.o g/licenses/by/4.0/
Con en s lis s a ailable a ScienceDi ec
EURO Jou nal on T anspo a ion and Logis ics
jou nal homepage: www.else ie .com/loca e/ej l
A B anch-P ice-and-Cu algo i hm o he Mul i-Commodi y wo-echelon
Dis ibu ion P oblem
Ma eo Pe is a,∗, Claudia A che i b, Diego Ca a uzza c, Maxime Ogie c, F édé ic Seme c
aUni . Lille, In ia, CNRS, Cen ale Lille, UMR 9189 CRIS AL, F-59000 Lille, F ance
bDepa men o In o ma ion Sys ems, Decision Sciences and S a is ics, ESSEC Business School, Ce gy-Pon oise, F ance
cUni . Lille, CNRS, In ia, Cen ale Lille, UMR 9189 CRIS AL, F-59000 Lille, F ance
ARTICLE INFO
Keywo ds:
Two echelon ou ing p oblems
Mul iple commodi ies
Spli deli e y
B anch-P ice-and-Cu
ABSTRACT
In he Mul i-Commodi y wo-echelon Dis ibu ion P oblem (MC2DP), mul iple commodi ies a e dis ibu ed in
a wo-echelon dis ibu ion sys em in ol ing supplie s, dis ibu ion cen es and cus ome s. Each supplie may
p o ide di e en commodi ies and each cus ome may eques se e al commodi ies as well. In he i s echelon,
capaci a ed ehicles pe o m di ec ips o anspo he commodi ies om he supplie s o he dis ibu ion
cen es o consolida ion pu poses. In he second echelon, each dis ibu ion cen e owns a lee o capaci a ed
ehicles o deli e he commodi ies o he cus ome s h ough mul i-s op ou es. Commodi ies a e compa ible,
i.e., hey can be mixed in he ehicles. Finally, cus ome eques s can be spli by commodi ies, ha is, a
cus ome can be isi ed by se e al ehicles, bu he o al amoun o each commodi y has o be deli e ed by a
single ehicle. The aim o he MC2DP is o minimize he o al anspo a ion cos o sa is y cus ome demands.
We p opose a se co e ing o mula ion o he MC2DP whe e he exponen ial numbe o a iables ela es
o he ou es in he deli e y echelon. We de elop a B anch-P ice-and-Cu algo i hm (BPC) o sol e he
p oblem. The p icing p oblem esul s in sol ing an Elemen a y Sho es Pa h P oblem wi h Resou ce Cons ain s
(ESPPRC) pe dis ibu ion cen e. We ackle he ESPPRC wi h a label se ing dynamic p og amming algo i hm
which inco po a es ng-pa h elaxa ion and a bidi ec ional labelling sea ch. P icing heu is ics a e in oked o
speed up he p ocedu e. In addi ion, he o mula ion is s eng hened by in eg a ing capaci y cu s and wo
amilies o alid inequali ies speci ic o he mul iple commodi ies aspec o he p oblem.
Ou app oach sol es o op imali y 439 o e he 736 benchma k ins ances om he li e a u e. The op imali y
gap o he unsol ed ins ances is 2.1%, on a e age.
1. In oduc ion
In a wo-echelon dis ibu ion sys em, goods a e ans e ed om
o igins (depo s, supplie s) o des ina ions (cus ome s) ia in e medi-
a e acili ies (sa elli es, dis ibu ion cen es) (see Guas a oba e al.,
2016). In he collec ion echelon, la ge ehicles b ing goods om he
o igins o he in e media e acili ies whe e consolida ion ope a ions
a e pe o med. Whe eas, in he deli e y echelon, smalle ehicles a e in
cha ge o dis ibu ing he goods o he inal cus ome s. Rou ing deci-
sions a e usually equi ed in bo h echelons. Two-echelon sys ems ake
ad an age o consolida ing goods a in e media e acili ies and using
di e en lee s wi hin each echelon o educe o e all anspo a ion
cos s. An example o his deli e y s a egy can be encoun e ed in ci y
logis ics (Ca a uzza e al.,2017;C ainic e al.,2023) whe e he aim is
also o g an he access in u ban a eas only o en i onmen al- iendly
ehicles ha usually ha e a small capaci y.
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (M. Pe is), [email p o ec ed] (C. A che i), [email p o ec ed] (D. Ca a uzza),
[email p o ec ed] (M. Ogie ), [email p o ec ed] (F. Seme ).
In his a icle, we conside he wo-echelon dis ibu ion p oblem
in oduced in Gu e al. (2022), namely he Mul i-Commodi y wo-echelon
Dis ibu ion P oblem (MC2DP). In his con ex , o igins, in e media e
acili ies and des ina ions a e e e ed o as supplie s,dis ibu ion cen es
and cus ome s, espec i ely. The e a e ew ehicle ou ing p oblems
which explici ly deal wi h mul iple commodi ies wi hin a wo-echelon
dis ibu ion sys em. To he bes o ou knowledge, among hese p ob-
lems, he MC2DP is he only one conside ing a many- o-many se ing.
In ac , in he MC2DP, he commodi y eques ed by a cus ome is
no p e-assigned o a speci ic supplie , so i can be collec ed a any
supplie o subse o supplie s whe e i is a ailable. The amoun o he
commodi ies a ailable a he supplie s is limi ed. In con as wi h he
usual se ing in he li e a u e, he MC2DP equi es ou ing decisions
only in he deli e y echelon. Indeed, commodi ies a e collec ed om
h ps://doi.o g/10.1016/j.ej l.2024.100139
Recei ed 31 Augus 2023; Recei ed in e ised o m 5 July 2024; Accep ed 11 July 2024
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
A ailable online 14 July 2024
2192-4376/© 2024 The Au ho (s). Published by Else ie B.V. on behal o Associa ion o Eu opean Ope a ional Resea ch Socie ies (EURO). This is an open access
a icle unde he CC BY license ( h p://c ea i ecommons.o g/licenses/by/4.0/ ).
M. Pe is e al.
he supplie s and b ough o he dis ibu ion cen es ia di ec ound
ips. In he deli e y echelon, a lee o ehicles pe o ming ou es
s a ing and ending a he same dis ibu ion cen e is used o deli e he
commodi ies o he cus ome s. All ehicles in ol ed in he dis ibu ion
sys em a e capaci a ed and commodi ies a e compa ible, i.e., hey can
be mixed inside all ehicles. Finally, as in he Commodi y cons ained
Spli Deli e y Vehicle Rou ing P oblem (C-SDVRP) (A che i e al.,2016),
cus ome s can be isi ed by mul iple ehicles as long as he demand
o a single commodi y is se ed by a single ehicle. The aim o he
MC2DP is o de e mine a dis ibu ion plan o sa is y cus ome de-
mands while espec ing he capaci y o he ehicles and no exceeding
he commodi y a ailabili ies a he supplie s and such ha he o al
anspo a ion cos is minimized. The MC2DP inds an applica ion
in he sho and local esh ood supply chains (Be i and Mulligan,
2016) whe e a me s supply di e en ag icul u al p oduc s o can eens,
es au an s o supe ma ke s h ough indi ec sales. Commonly, a single
decision make , such as an associa ion o a me s, coo dina es bo h he
collec ion and deli e y echelons. In his con ex , he a me s a e less
nume ous han deli e y poin s since he maximal supply o one a me
can co e he demand o se e al cus ome s. Hence, he collec ion
om he a me s is usually pe o med ia di ec ound ips. Then,
he dis ibu ion cen es pe o m he consolida ion ope a ions and he
deli e ies o he cus ome s which a e done by ehicles pe o ming
ou es. We e e o Gu e al. (2022) o mo e de ails abou he p oblem
applica ion.
The au ho s in Gu e al. (2022) p oposed a compac Mixed In ege
Linea P og amming (MILP) o mula ion and a sequen ial heu is ic o
he MC2DP. The au ho s decompose he MC2DP in wo subp oblems:
one o he collec ion om supplie s, and he o he one o he deli e y
o cus ome s. The collec ion subp oblem is modelled as a MILP and
sol ed wi h a comme cial sol e while he deli e y subp oblem is
sol ed by an Adap i e La ge Neighbou hood Sea ch (ALNS) algo i hm.
The con ibu ion o his pape is o p esen an exended model and
o p opose he i s e e exac app oach based on a B anch-P ice-and-
Cu (BPC) algo i hm o sol e he MC2DP. Simila exac app oaches
ha e ecen ly been p oposed o deal wi h wo-echelon ehicle ou ing
p oblems (see e.g. Ma ques e al.,2020;Li e al.,2022;Mhamedi e al.,
2022;Ma ques e al.,2022).
Howe e , ou BPC algo i hm is designed o ake in o accoun explic-
i ly he mul i-commodi y dimension. Speci ically, ou algo i hm elies
on a se co e ing o mula ion o he MC2DP whe e he exponen ially-
many numbe o a iables co espond o he ou es in he deli e y ech-
elon s a ing and ending a each dis ibu ion cen e. We also s eng hen
he o mula ion by he inse ion o capaci y cu s, alid inequali ies
a ising om he se co e ing poly ope (Balas and Ng,1989) and a new
amily o alid inequali ies based on he numbe pa i ioning p oblem
poly ope. While capaci y cu s a e classical inequali ies de i ed o he
Capaci a ed Vehicle Rou ing P oblem (CVRP) (see Lapo e e al.,1985),
he o he wo amilies o inequali ies ackle he mul i-commodi y aspec
o he p oblem. Finally, se e al s a e-o -a speed-up echniques a e also
inco po a ed in ou BPC algo i hm.
The emainde o he pape is o ganized as ollows. Sec ion 2
p o ides a li e a u e e iew. In Sec ion 3, a o mal desc ip ion o he
MC2DP is p o ided. In Sec ion 4, a se co e ing o mula ion is p e-
sen ed along wi h di e en amilies o alid inequali ies. Ou B anch-
P ice-and-Cu algo i hm is desc ibed in Sec ion 5. Finally, in Sec-
ion 6we analyse he esul s ob ained by he p oposed algo i hm on
he benchma k ins ances in oduced in Gu e al. (2022) o assess i s
e ec i eness.
2. Li e a u e e iew
In his sec ion, we e iew he exis ing li e a u e on he wo-echelon
dis ibu ion p oblems, wi h pa icula a en ion o he ones dealing
wi h mul iple commodi ies. The i s wo-echelon ou ing p oblem
in oduced by Jacobsen and Madsen (1980) was mo i a ed by a speci ic
applica ion. Newspape s ha e o be dis ibu ed om a p in ing o ice
o sales poin s possibly passing h ough some ans e poin s whose
loca ions a e o be decided. C ainic e al. (2004,2009) p oposed a
o mal desc ip ion o a ich class o wo-echelon ou ing p oblems
along wi h some economic insigh s. Howe e , he seminal p oblem in
his class, namely he wo-echelon Capaci a ed Vehicle Rou ing P oblem
(2E-CVRP), was in oduced in he li e a u e and s udied o he i s
ime in Pe boli e al. (2011). In he 2E-CVRP, a single commodi y has
o be ans e ed om a single o igin o se e al des ina ions h ough
some in e media e acili ies. Two lee s o capaci a ed ehicles pe o m
ou es in he wo echelons o anspo he commodi y om he o igin
o he in e media e acili ies and om he in e media e acili ies o he
des ina ions. The objec i e o he 2E-CVRP is o minimize he o al
anspo a ion cos o he dis ibu ion sys em. The au ho s p oposed
wo ma h-heu is ics o sol e he p oblem, a di ing and a sub-MIP
heu is ic.
The 2E-CVRP and ela ed p oblems ha e ecei ed inc easing a en-
ion in ecen yea s and many a ian s ha e been add essed, e.g., 2E-
CVRP wi h (i) ime windows (Mhamedi e al.,2022); (ii) mobile
sa elli es (Li e al.,2020); (iii) synch oniza ion (G angie e al.,2016)
and bi-synch oniza ion (Li e al.,2021b); (i ) simul aneous pickup and
deli e y (Li e al.,2022); ( ) elec ic ehicles (B eunig e al.,2019) and
ba e y swapping s a ions (Jie e al.,2019); ( i) eal- ime ansshipmen
capaci y a ying (Li e al.,2018); ( ii) co e ing op ions (En ho en
e al.,2020); ( iii) deli e y op ions (Zhou e al.,2018); (ix) s ochas ic
demands (Sluijk e al.,2022). The in e es ed eade may e e o Cuda
e al. (2015), Li e al. (2021a) and Sluijk e al. (2023) o ecen su eys
on he subjec .
Acco ding o he exis ing li e a u e, he as majo i y o he wo-
echelon ou ing p oblems deal wi h he single commodi y case. Apa
om he MC2DP, which is add essed in his pape , only a ew wo ks
in eg a e mul iple commodi ies in a wo-echelon ou ing p oblem (e.g.
Dellae e al.,2021;Jia e al.,2023;Gu e al.,2022). In Dellae e al.
(2021), he au ho s ex ended he 2E-CVRP by in oducing mul iple
o igins and mul iple commodi ies. In addi ion, ha d ime windows
a e imposed o he deli e y a he des ina ions. In hei p oblem,
cus ome s ha e a commodi y demand om a speci ic o igin, i.e., he e
is a one- o-one se ing. Se e al ma hema ical o mula ions a e p oposed
and a BPC algo i hm is de ised o sol e he p oblem. In Jia e al.
(2023), he p oblem se ing is simila o he one o Dellae e al.
(2021). Howe e , he mul i-commodi y aspec is handled wi h mo e e-
s ic ions: only wo o igins a e conside ed and each des ina ion equi es
one commodi y pe o igin (one- o-one se ing). The au ho s de eloped
an ALNS algo i hm o sol e la ge-scale ins ances o he p oblem. The
MC2DP in oduced in Gu e al. (2022) di e s om Dellae e al.
(2021) and Jia e al. (2023) o h ee easons: (i) he e is a many-
o-many se ing o he commodi ies, i.e. any commodi y eques ed
by a cus ome can be se ed om any supplie ; (ii) supplie s p o ide
commodi ies in limi ed amoun s; (iii) ou ing decisions a e no equi ed
in he collec ion echelon.
3. P oblem desc ip ion
In he Mul i-Commodi y wo-Echelon Dis ibu ion P oblem (MC2DP),
a se o commodi ies is dis ibu ed in a sys em in ol ing a se o
supplie s (o igins) , a se o dis ibu ion cen es (in e media e acili ies)
and a se o cus ome s (des ina ions) . The sys em is spli in wo
echelons: he collec ion echelon whe e he commodi ies a e collec ed
a he supplie s and b ough o he dis ibu ion cen es, and he de-
li e y echelon whe e he commodi ies a he dis ibu ion cen es a e
deli e ed o he cus ome s. Mo e p ecisely, in he collec ion echelon,
each supplie 𝑖∈p o ides a maximal amoun 𝑃𝑖𝑘 ≥0 o each
commodi y 𝑘∈. No e ha a supplie 𝑖∈migh no supply a
commodi y 𝑘∈, and in ha case, 𝑃𝑖𝑘 akes alue 0. An unlimi ed
lee o homogeneous ehicles o capaci y 𝑄𝑆pe o ms di ec ound
ips om he dis ibu ion cen es o collec he commodi ies om he
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
2
M. Pe is e al.
supplie s. The ehicles can anspo any subse o commodi ies. Due
o he limi ed capaci y o he ehicles, di ec ound ips be ween a
dis ibu ion cen e 𝑜∈and a supplie 𝑖∈may be pe o med by
se e al ehicles. The p oblem associa ed wi h he collec ion ope a ions
can be modelled as a Mul i-commodi y Capaci a ed ixed-cha ge Ne wo k
Design P oblem (MCNDP, Magnan i and Wong,1984) wi h a speci ic
cos s uc u e: he e is a s ep-wise cos unc ion de ined by a uni a y
cos associa ed wi h each ehicle used be ween a dis ibu ion cen e
and a supplie .
Di e en ly, he p oblem o dis ibu ing he commodi ies om he
dis ibu ion cen es o he cus ome s is a mul i-depo e sion o he
Commodi y cons ained Spli Deli e y Vehicle Rou ing P oblem (C-SDVRP).
Each cus ome 𝑗∈has a demand 𝐷𝑗𝑘 ≥0 o all commodi ies
𝑘∈. The eques o cus ome 𝑗is iden i ied by se 𝑗= {𝑘∈
∶𝐷𝑗𝑘 >0}. Each dis ibu ion cen e owns an unlimi ed lee o
homogeneous and capaci a ed ehicles o capaci y 𝑄𝐷which pe o ms
ou es o deli e he commodi ies o he cus ome s. Each ehicle has
o end i s ou e a i s s a ing dis ibu ion cen e. As in he collec ion
echelon, a ehicle can be loaded wi h any commodi ies. Wi hou loss
o gene ali y, we suppose 𝑄𝐷≥max{∑𝑘∈𝑗𝐷𝑗𝑘 ∶𝑗∈}. Fu he mo e,
cus ome eques s can be spli , i.e., di e en ehicles can se e he
same cus ome . Howe e , he demand o a single commodi y canno
be spli : i has o be deli e ed by a single ehicle. No e ha di ec ips
om supplie s o cus ome s and in e -connec ions be ween dis ibu ion
cen es a e no allowed.
Finally, he collec ion and deli e y ope a ions aking place in he
wo echelons a e coo dina ed a he dis ibu ion cen es by means o he
so-called load synch oniza ion s a egy (D exl,2012): he o al amoun
o each commodi y collec ed a he supplie s by each dis ibu ion cen e
mus be su icien o se e he cus ome demands o ha commodi y
deli e ed by a ehicle o ha dis ibu ion cen e.
We o mula e he MC2DP on a di ec ed weighed g aph = (,).
Se =∪∪con ains a e ex o each supplie , dis ibu ion cen e
and cus ome . A c se =𝑆∪𝐷is de ined as he union o wo se s
o a cs which model he possible ehicle a els in he wo echelons.
Speci ically, se 𝑆= (×) ∪ (×)includes he a cs modelling
he di ec ips om supplie s o dis ibu ion cen es in he collec ion
echelon, whe eas 𝐷= (×)∪(×)∪(×)con ains all a cs be ween
cus ome s and be ween dis ibu ion cen es and cus ome s. Each a c
(𝑖, 𝑗) ∈ is assigned wi h a non-nega i e cos 𝐶𝑖𝑗 which ep esen
he anspo a ion cos o a ehicle a e sing (𝑖, 𝑗). The a c cos s a e
symme ic and sa is y he iangula inequali y. In g aph , a ou e in
he deli e y echelon is a non-emp y ci cui s a ing and ending a a
dis ibu ion cen e 𝑜∈. A ou e is easible i he o al amoun o
commodi ies deli e ed o he cus ome s isi ed along he ou e does
no exceed ehicle capaci y 𝑄𝐷. The cos o any easible ou e 𝑟is
𝐶𝑟=∑(𝑖,𝑗)∈(𝑟)𝐶𝑖𝑗 , whe e (𝑟)is he se o a cs a e sed by he ou e.
Finally, he o al anspo a ion cos o he dis ibu ion sys em a ising
om he MC2DP is he sum o he cos o he di ec ound ips in he
collec ion echelon and he ou ing cos s in he deli e y echelon.
The aim o he MC2DP is o de e mine a dis ibu ion plan, i.e., he
di ec ound ips in he collec ion echelon and he ou es in he deli -
e y echelon, which sa is ies he cus ome eques s, does no exceed he
commodi y a ailabili ies a he supplie s, sa is ies he ehicle capaci ies
in bo h echelons and espec s he load synch oniza ion cons ain s
while minimizing he o al anspo a ion cos .
4. P oblem o mula ion
We model he MC2DP by means o a se co e ing o mula ion,
whe e he exponen ially-many a iables a e associa ed wi h he ou es
in he deli e y echelon.
Fo each dis ibu ion cen e 𝑜∈, we de ine 𝑜as he se o all
easible ou es s a ing and ending a 𝑜. The se o all easible ou es is
deno ed by =⋃𝑜∈𝑜. We de ine a bina y coe icien 𝑎𝑟
𝑗𝑘 wi h alue
one i commodi y 𝑘∈is deli e ed o cus ome 𝑗∈by ou e 𝑟∈
and ze o o he wise.
Fo each supplie 𝑖∈and each dis ibu ion cen e 𝑜∈, we
in oduce an in ege a iable 𝑥𝑖𝑜 o ep esen he numbe o ehicles
a e sing a c (𝑖, 𝑜) ∈ . Fo each 𝑖∈,𝑜∈and 𝑘∈, we de ine
a non-nega i e con inuous a iable 𝑞𝑘
𝑖𝑜 ha ep esen s he amoun o
commodi y 𝑘collec ed a supplie 𝑖by dis ibu ion cen e 𝑜. Finally,
o each ou e 𝑟∈, we in oduce a bina y a iable 𝜆𝑟 aking alue
one i 𝑟is selec ed in he solu ion and ze o o he wise.
The Se Co e ing o mula ion [SC] o he MC2DP eads as ollows:
[SC] min ∑
(𝑖,𝑜)∈
2𝐶𝑖𝑜𝑥𝑖𝑜 +∑
𝑟∈
𝐶𝑟𝜆𝑟(1)
s. . ∑
𝑜∈
𝑞𝑘
𝑖𝑜 ≤𝑃𝑖𝑘 ∀𝑖∈,∀𝑘∈(2)
∑
𝑘∈
𝑞𝑘
𝑖𝑜 ≤𝑄𝑆𝑥𝑖𝑜 ∀𝑖∈,∀𝑜∈(3)
∑
𝑟∈
𝑎𝑟
𝑗𝑘𝜆𝑟≥1 ∀𝑗∈,∀𝑘∈𝑗(4)
∑
𝑖∈
𝑞𝑘
𝑖𝑜 ≥∑
𝑟∈𝑜∑
𝑗∈
𝑎𝑟
𝑗𝑘𝐷𝑗𝑘𝜆𝑟∀𝑜∈,∀𝑘∈(5)
𝑥𝑖𝑜 ∈Z≥0∀𝑖∈,∀𝑜∈(6)
𝑞𝑘
𝑖𝑜 ∈R≥0∀𝑖∈,∀𝑜∈,∀𝑘∈(7)
𝜆𝑟∈ {0,1} ∀𝑟∈(8)
Objec i e unc ion (1) minimizes he o al anspo a ion cos . Con-
s ain s (2) ensu e ha he commodi y a ailabili ies a each supplie
a e espec ed. Cons ain s (3) gua an ee ha a su icien numbe o
ehicles pe o m he collec ion ope a ions and ha he capaci y o hese
ehicles is no exceeded. Co e ing Cons ain s (4) impose ha each
commodi y equi ed by a cus ome is se ed by a leas one ou e. In
addi ion, he load synch oniza ion cons ain linking he collec ion and
deli e y echelons is exp essed in cons ain s (5): he quan i y o each
commodi y collec ed by each dis ibu ion cen e has o be la ge enough
o sa is y he demand o ha commodi y deli e ed by a ou e o ha
dis ibu ion cen e. Finally, Cons ain s (6),(7) and (8) de ine a iable
domains.
4.1. Valid inequali ies
In his sec ion, we in oduce ou amilies o alid inequali ies con-
side ed o s eng hen o mula ion [SC]. Two o hese inequali ies a e
known in he con ex o ehicle ou ing p oblems, while he o he wo
a e ailo ed o deal wi h he mul i-commodi y aspec o he MC2DP.
No e ha such inequali ies a e alid o he C-SDVRP, hence o he
MC2DP.
In wha ollows, gi en a subse o cus ome s ′⊆, we de ine
𝐷(′) = ∑𝑗∈′∑𝑘∈𝑗𝐷𝑗𝑘 o be he o al demand eques ed by he
cus ome s in ′. In addi ion, we in oduce a bina y coe icien 𝑏𝑟
𝑖𝑗 wi h
alue one i ou e 𝑟∈ a e ses a c (𝑖, 𝑗) ∈ and ze o o he wise.
Finally, we de ine 𝑒𝑟
𝑗=∏𝑘∈𝑎𝑟
𝑗𝑘 o be a bina y coe icien equal
o one i ou e 𝑟deli e s all he commodi ies o subse ⊆𝑗 o
cus ome 𝑗∈and ze o o he wise.
Bounds on he numbe o ehicles
The ollowing inequali ies se bounds on he numbe o ehicles in
he collec ion and deli e y echelons:
∑
(𝑖,𝑜)∈
𝑥𝑖𝑜 ≥⌈𝐷()
𝑄𝑆⌉(9)
and
∑
𝑟∈
𝜆𝑟≥⌈𝑣⌉(10a)
∑
𝑟∈
𝜆𝑟≤min{||,2𝑣}.(10b)
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
3
M. Pe is e al.
In inequali ies (10a) and (10b), alues 𝑣and 𝑣 a e ob ained by sol ing
an ins ance o he Bin Packing P oblem (BPP), whe e bins ha e size
equal o he ehicle capaci y 𝑄𝐷, and each cus ome demand has a
co esponding i em o be packed wi h size 𝐷𝑗𝑘. P ecisely, we sol e an
in ege p og am o he BPP on such an ins ance wi h a comme cial
sol e wi hin a sho ime limi : 𝑣and 𝑣 a e he ob ained lowe and
uppe bounds. I he ins ance is sol ed o op imali y wi hin he ime
limi , 𝑣=𝑣 holds. The igh hand-side o (10b) is he minimum be ween
wice alue 𝑣 (see Fede g uen and Simchi-Le i,1995) and he numbe
o cus ome s.
Capaci y cu s
Lapo e e al. (1985) in oduced he capaci y cu s o deal wi h he
Capaci a ed Vehicle Rou ing P oblem:
∑
𝑟∈(∑
(𝑖,𝑗)∈𝛿−(′)
𝑏𝑟
𝑖𝑗 )𝜆𝑟≥⌈𝐷(′)
𝑄𝐷⌉∀′⊆,(11)
whe e 𝛿−(′) = {(𝑖, 𝑗) ∈ ∶𝑖∉′, 𝑗 ∈′}is he se o a cs o g aph
eaching a e ex in ′. Gi en a subse o cus ome s ′, inequali y (11)
s a es ha a leas ⌈𝐷(′)∕𝑄𝐷⌉ ehicles o he deli e y echelon a e
equi ed o co e he eques s o he cus ome s in ′.
Se co e ing poly ope
We p esen a amily o alid inequali ies inspi ed by he ace -
de ining inequali ies p oposed in Balas and Ng (1989) o he se
co e ing poly ope. Al hough hese inequali ies we e p oposed se e al
yea s ago, o he bes o ou knowledge, hey ha e no ye been used
in BPC algo i hms o ehicle ou ing p oblems. Howe e , hey a e
simila o he s ong minimum numbe o ehicles inequali ies in oduced
by A che i e al. (2011) in he con ex o a BPC algo i hm o he spli
deli e y ehicle ou ing p oblem wi h ime windows.
Le us i s b ie ly p esen a o mula ion o he se co e ing p ob-
lem. Le be a se o elemen s o be co e ed, and be a se o
subse s o . We deno e by 𝑐𝑗 he cos associa ed o subse 𝑗∈,
and 𝑑𝑖𝑗 a bina y pa ame e ha akes alue one i elemen 𝑖∈is in
subse 𝑗∈, and ze o o he wise. Le 𝑥𝑗be a bina y decision a iable
aking alue one i subse 𝑗∈is selec ed, ze o o he wise. An in ege
p og amming o mula ion o he se co e ing p oblem is
min ∑
𝑗∈
𝑐𝑗𝑥𝑗
s. . ∑
𝑗∈
𝑑𝑖𝑗 𝑥𝑗≥1 ∀𝑖∈
𝑥𝑗∈ {0,1} ∀𝑗∈
Gi en a subse ′⊆, he inequali ies in oduced in Balas and Ng
(1989) eads as ollows:
2∑
𝑗∈′
𝑥𝑗+∑
𝑗∈
′
𝑥𝑗≥2,
whe e ′= {𝑗∈∶𝑑𝑖𝑗 = 1,∀𝑖∈′}is he se o he elemen s o
which co e ′and
′= {𝑗∈∶∑𝑖∈′𝑑𝑖𝑗 ≥1 ∧ ∏𝑖∈′𝑑𝑖𝑗 = 0} is he
se o he elemen s o which con ain some, bu no all, he elemen s
in ′. The inequali ies exp ess how subse ′may be co e ed: ei he i
su ices o selec a unique elemen in ha co e s ′, i.e., an elemen
in ′, o a leas wo elemen s in ha pa ially co e ′ha e o be
selec ed, i.e., a leas wo elemen s in
′. Unde speci ic condi ions,
hese cons ain s a e ace de ining o he se co e ing poly ope.
In wha ollows, we adap hese inequali ies o he MC2DP o
exp ess how he subse s o commodi ies equi ed by a gi en cus ome
may be co e ed. Fo he ease o eadabili y, we in oduce he ollowing
no a ion. Le 𝑗∈be a cus ome and 𝑗⊆𝑗be a subse o he
commodi ies eques ed by 𝑗. We deno e by 𝑗
𝑗⊆ he subse o
ou es deli e ing all commodi ies in 𝑗 o 𝑗, i.e., 𝑗
𝑗= {𝑟∈∶
𝑒𝑟
𝑗𝑗= 1}.
In addi ion, we w i e
𝑗
𝑗⊆ o he subse o ou es which
deli e some o he commodi ies in 𝑗 o 𝑗, bu no all o hem,
i.e.,
𝑗
𝑗= {𝑟∈∶∑𝑘∈𝑗𝑎𝑟
𝑗𝑘 ≥1 ∧ 𝑒𝑟
𝑗𝑗= 0}.
The se co e ing poly ope inequali ies o he MC2DP a e de ined
as ollows:
2∑
𝑟∈𝑗
𝑗
𝜆𝑟+∑
𝑟∈
𝑗
𝑗
𝜆𝑟≥2 ∀𝑗∈,∀𝑗⊆𝑗.(12)
Inequali ies (12) s a e ha subse o commodi ies 𝑗⊆𝑗o cus ome
𝑗∈can be co e ed ei he by a single ou e in 𝑗
𝑗o by a leas
wo ou es in
𝑗
𝑗. No e ha hese inequali ies a e meaning ul only i
|𝑗|≥3. Indeed, i |𝑗|= 2, hey can be e ie ed as an agg ega ion
o Co e ing Cons ain s (4).
Numbe pa i ioning poly ope
We p opose a no el amily o alid inequali ies which exploi s
he mul i-commodi y aspec o he MC2DP. Mo e p ecisely, gi en a
cus ome 𝑗∈, hese inequali ies speci y he possible combina ions
o ou es o deli e he se o commodi ies 𝑗 equi ed by cus ome 𝑗.
Fo each cus ome 𝑗∈, we deno e by 𝑙
𝑗 he subse o ou es
which deli e exac ly 𝑙= 1,…,|𝑗|commodi ies o 𝑗, i.e., 𝑙
𝑗= {𝑟∈
∶∑𝑘∈𝑗𝑎𝑟
𝑗𝑘 =𝑙}.
Equali ies
|𝑗|
∑
𝑙=1
𝑙∑
𝑟∈𝑙
𝑗
𝜆𝑟=|𝑗|∀𝑗∈(13)
ensu e ha he selec ed ou es ha se e cus ome 𝑗will exac ly b ing
|𝑗|commodi ies o cus ome 𝑗. As an example, le
𝑗∈be a cus ome
ha ing a demand o h ee commodi ies, i.e., |
𝑗|= 3. Equali y (13) o
cus ome
𝑗s a es ha he commodi ies o
𝑗can be co e ed by (i) a
single ou e o 3
𝑗o (ii) one ou e o 2
𝑗and a ou e o 1
𝑗o (iii) h ee
ou es o 1
𝑗.
P oposi ion 1. Equali ies (13) a e alid o he MC2DP. Mo e p ecisely,
inequali ies ∑|𝑗|
𝑙=1 𝑙∑𝑟∈𝑙
𝑗
𝜆𝑟≥|𝑗|,∀𝑗∈, a e implied by Co e ing
Cons ain s (4) and inequali ies
|𝑗|
∑
𝑙=1
𝑙∑
𝑟∈𝑙
𝑗
𝜆𝑟≤|𝑗|∀𝑗∈(14)
a e alid o he MC2DP.
P oo . I is s aigh o wa d ha equali ies (14) a e alid o he
MC2DP. Hence, we only need o show ha ∑|𝑗|
𝑙=1 𝑙∑𝑟∈𝑙
𝑗
𝜆𝑟≥|𝑗|,∀𝑗∈
, a e implied by Co e ing Cons ain s (4). Le 𝑗∈be a cus ome .
By summing up he Co e ing Cons ain s (4) associa ed wi h 𝑗and
swapping he summa ion o de , we ob ain
∑
𝑟∈∑
𝑘∈𝑗
𝑎𝑟
𝑗𝑘𝜆𝑟≥|𝑗|.
Le 𝑟
𝑗deno e he subse o commodi ies deli e ed o cus ome 𝑗by
ou e 𝑟. We ha e ∑𝑘∈𝑗𝑎𝑟
𝑗𝑘 =|𝑟
𝑗|. The p oo ollows om pa i ioning
he se o ou es as =⋃|𝑗|
𝑙=0 𝑙
𝑗, whe e we deno ed by 0
𝑗 he subse
o ou es which do no isi 𝑗. Indeed, i holds
|𝑗|≤|𝑗|
∑
𝑙=0 ∑
𝑟∈𝑙
𝑗|𝑟
𝑗|𝜆𝑟=|𝑗|
∑
𝑙=1
𝑙∑
𝑟∈𝑙
𝑗
𝜆𝑟.□
Rema k ha i we model he MC2DP by means o a se pa i ioning
o mula ion, i.e., we impose he equali y in Cons ain s (4), Equali-
ies (13) become i ial. Indeed, hey can be e ie ed as an agg ega ion
o he pa i ioning cons ain s.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
4
M. Pe is e al.
Gi en a cus ome 𝑗∈and 𝑙= 1,…,|𝑗|, we in oduce an auxilia y
a iable 𝑦𝑙
𝑗∈Z≥0de ined as 𝑦𝑙
𝑗∶= ∑𝑟∈𝑙
𝑗
𝜆𝑟. Now, le
𝑗∶= {𝑦𝑗∈Z|𝑗|
≥0∶|𝑗|
∑
𝑙=1
𝑙𝑦𝑙
𝑗≤|𝑗|}
be he se o he in ege poin s which sa is y inequali y (14), ew i en
in e ms o 𝑦𝑙
𝑗 a iables.
P oposi ion 2. The inequali ies de ining he con ex hull o 𝑗,𝑗∈, a e
alid o he MC2DP.
De e mining he ex e nal desc ip ion o a con ex se is no an easy
ask, in pa icula in la ge dimensions. Howe e , gi en ha cus ome s
equi e a mos h ee commodi ies in he benchma k ins ances o Gu
e al. (2022) o he MC2DP, we explici ly de i e he ex e nal desc ip-
ion o he con ex hull o se s 𝑗⊆Z3,𝑗∈. I he numbe o
commodi ies is g ea e han h ee, so wa e o polyhed al ans o ma-
ions such as PORTA (Ch is o and Löbel,2009) o PANDA (Lö wald
and Reinel ,2015) can be used o de e mine he ex e nal desc ip ion
o he con ex hull o se s 𝑗,𝑗∈.
No e ha inequali ies (14) a e meaning ul only o cus ome s 𝑗∈
who equi e a leas h ee commodi ies, i.e., |𝑗|≥3. The ex e nal
desc ip ion o he con ex hull o se s 𝑗,𝑗∈such ha |𝑗|= 3 eads
as ollows:
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
𝑦1
𝑗+ 2𝑦2
𝑗+ 3𝑦3
𝑗≤3(a)
𝑦1
𝑗−𝑦2
𝑗≥0(b)
𝑦2
𝑗≥0(c)
𝑦3
𝑗≥0.(d)
(15)
Inequali ies (15c) and (15d) a e i ial, indeed, hey a e implied by he
de ini ion o a iables 𝑦𝑙
𝑗. The e o e, inequali ies (15a) and (15b) a e
he only meaning ul ones in he case o a cus ome 𝑗∈ equi ing h ee
commodi ies (|𝑗|= 3); in e ms o 𝜆 a iables, hey a e exp essed
espec i ely as
|𝑗|
∑
𝑙=1
𝑙∑
𝑟∈𝑙
𝑗
𝜆𝑟≤|𝑗|∀𝑗∈∶|𝑗|= 3 (16)
∑
𝑟∈1
𝑗
𝜆𝑟−∑
𝑟∈2
𝑗
𝜆𝑟≥0 ∀𝑗∈∶|𝑗|= 3.(17)
In conclusion, he numbe pa i ioning poly ope alid inequali ies
we conside a e (16) and (17).
5. B anch-P ice-and-Cu algo i hm
We sol e o mula ion [SC] by means o a B anch-P ice-and-Cu
(BPC) algo i hm (Ba nha e al.,1998), i.e., a a ian o he b anch-
and-bound algo i hm which deals wi h in ege p og amming model
wi h exponen ially-many a iables. Speci ically, a each node o he
b anch-and-bound ee, he Mas e P oblem (MP), ha is he linea
elaxa ion o o mula ion [SC], is sol ed by a column gene a ion p o-
cedu e (Des osie s and Lübbecke,2005). I he solu ion o he MP is
ac ional, iola ed alid inequali ies o Sec ion 4.1 may be inse ed
and he column gene a ion p ocedu e is epea ed while some alid
inequali ies a e iola ed. Finally, b anching ules a e applied o ensu e
he in eg ali y o he solu ion. We impose a ime limi as a e mina ion
c i e ion o ou BPC algo i hm.
In his sec ion, we desc ibe he main componen s o ou BPC al-
go i hm. Speci ically, in Sec ion 5.1 we p esen he column gene a-
ion scheme applied in ou BPC algo i hm. In Sec ion 5.2, we de ail
he managemen o he alid inequali ies, and hei impac on he
p icing p oblem. B anching s a egies and accele a ing echniques a e
p esen ed in Sec ions 5.3 and 5.4, espec i ely.
5.1. Column gene a ion
A each node o he b anch-and-bound ee, a column gene a ion
p ocedu e sol es he MP de ined on he exponen ially-many a iables
𝜆𝑟,𝑟∈, which co espond o he ou es in he deli e y echelon.
The s a ing poin is he Res ic ed Mas e P oblem (RMP). The column
gene a ion p ocedu e i e a i ely sol es a Res ic ed Mas e P oblem
(RMP), i.e., he MP es ic ed o a subse o a iables 𝜆𝑟. A each
i e a ion o he p ocedu e, a e he RMP is sol ed, a subp oblem,
named p icing p oblem is sol ed. The aim o he p icing p oblem is o
iden i y a a iable (column) wi h he smalles educed cos . I such a
column has a nega i e educed cos , i is added o he RMP in o de o
dec ease (in a minimiza ion p oblem) he cu en alue o he solu ion,
and he column gene a ion p ocedu e i e a es. The p ocedu e ends
when he solu ion o he p icing p oblem is a non nega i e educed
cos column, p o ing he op imali y o he MP.
Mo e p ecisely, he p icing p oblem is
[PP] min{
𝐶𝑟∶𝑟∈}
whe e
𝐶𝑟deno es he educed cos o 𝜆𝑟 a iable. No e ha se o ou es
can be pa i ioned pe dis ibu ion cen e, i.e., =⋃𝑜∈𝑜whe e
𝑜is he se o ou es s a ing and ending a 𝑜. Hence, sol ing [PP]
can be done by sol ing sequen ially ||independen p oblems wi h he
same s uc u e:
[PP(𝑜)] min{
𝐶𝑟∶𝑟∈𝑜}, 𝑜 ∈.
Speci ically, he aim o p oblem [PP(𝑜)] is o de e mine he mos
nega i e educed cos 𝜆𝑟,𝑟∈𝑜, o o de ec ha none o hem exis s.
The column gene a ion p ocedu e e mina es once all p oblems [PP(𝑜)],
𝑜∈do no yield any nega i e educed cos a iable.
In he ollowing, we de ail how a p oblem [PP(𝑜)] o 𝑜∈is
o mula ed and sol ed. By deno ing 𝜌𝑗𝑘 ≥0,∀𝑗∈, 𝑘 ∈𝑗and
𝜎𝑜𝑘 ≥0,∀𝑜∈, 𝑘 ∈as he op imal dual p ices associa ed wi h
Cons ain s (4) and (5), espec i ely, he educed cos o a 𝜆𝑟,𝑟∈𝑜
a iable is de ined as ollows:
𝐶𝑟=𝐶𝑟−∑
𝑗∈∑
𝑘∈𝑗
𝑎𝑟
𝑗𝑘(𝜌𝑗𝑘 −𝐷𝑗𝑘𝜎𝑜𝑘).(18)
As men ioned in Sec ion 3, he deli e y echelon is a mul i-depo
e sion o he C-SDVRP. Hence, he p oblem [PP(𝑜)] is he p icing p ob-
lem a ising in B anch-P ice-and-Cu app oaches o he C-SDVRP (see
A che i e al.,2015;Gschwind e al.,2019) and is o mula ed as an
Elemen a y Sho es Pa h P oblem wi h Resou ce Cons ain s (ESPPRC) on
a mul i-g aph (𝑜) = ((𝑜),(𝑜)). Such g aph is analogous o he one
p esen ed in Gschwind e al. (2019) o o mula e he ESPPRC in he
con ex o he C-SDVRP. Ve ex se (𝑜)con ains wo copies 𝑜′and 𝑜′′
o dis ibu ion cen e 𝑜and wo copies 𝑗′and 𝑗′′ o each cus ome 𝑗∈.
Each a c o se (𝑜)is associa ed wi h wo esou ces: demand
𝐷and
cos
𝐶. A c se (𝑜)con ains:
1. an a c (𝑖′′, 𝑗′) o each a c (𝑖, 𝑗) ∈ o model he mo emen o
a ehicle om e ex 𝑖 o e ex 𝑗; he demand and cos a e se
o
𝐷𝑖′′𝑗′∶= 0 and
𝐶𝑖′′𝑗′∶= 𝐶𝑖𝑗 , espec i ely.
2. an a c (𝑗′, 𝑗′′)𝑗 o each cus ome 𝑗∈and each subse
𝑗⊆𝑗 o model he deli e y o he commodi ies o 𝑗 o
𝑗; he demand and cos a e se o
𝐷𝑗
𝑗′𝑗′′ ∶= ∑𝑘∈𝑗𝐷𝑗𝑘 and
𝐶𝑗
𝑗′𝑗′′ ∶= − ∑𝑘∈𝑗(𝜌𝑗𝑘 −𝐷𝑗𝑘𝜎𝑜𝑘), espec i ely.
Sol ing p oblem [PP(𝑜)] esul s in sea ching o nega i e educed cos
elemen a y pa hs in (𝑜) om 𝑜′′ o 𝑜′such ha he esou ce consump-
ion (demand) does no exceed he ehicle capaci y 𝑄𝐷.
To do so, we adop a wo phase p ocedu e:
Phase 1 compu es he Pa e o-op imal (demand, cos ) pai s (
𝐷𝑗
𝑗′𝑗′′ ,
𝐶𝑗
𝑗′𝑗′′ ) o each cus ome 𝑗∈.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
5
M. Pe is e al.
Phase 2 sol es he ESPPRC on mul i-g aph (𝑜)which includes all
a cs o ype (𝑖′′, 𝑗′), and only he Pa e o-op imal a cs o ype
(𝑗′, 𝑗′′)𝑗 ha ha e been compu ed in phase 1. P ecisely, he
ESPPRC is sol ed by means o a label se ing dynamic p o-
g amming echnique (Feille e al.,2004) which wo ks wi h an
implici e sion o he bidi ec ional labelling sea ch (see Righini
and Salani,2006;Bode and I nich,2012). The elemen a i y con-
s ain s a e he bo leneck o such p ocedu e, hence, we pa ially
elax i by sol ing he ng-pa h elaxa ion (Baldacci e al.,2011)
o he ESPPRC. Fo each cus ome 𝑗∈, we conside a ixed
size ng-neighbou hood which includes he 10 closes cus ome s
o 𝑗and 𝑗i sel . Rema k ha such elaxa ion allows a ou e
o se e he same commodi y o he same cus ome mul iple
imes. Hence, he coe icien s o he cons ain s and alid in-
equali ies need o be upda ed acco dingly: e.g., in he Co e ing
Cons ain s (4),𝑎𝑟
𝑗𝑘 becomes an in ege coe icien exp essing
he numbe o imes cus ome 𝑗∈is deli e ed wi h commodi y
𝑘∈𝑗by ou e 𝑟∈.
The eade may e e o A che i e al. (2015) and Gschwind e al.
(2019) o u he de ails. The esolu ion o he ESPPRCs is he bo -
leneck o ou algo i hm, hence, we heu is ically sol e he ESPPRC
wi h he objec i e o quickly inding a nega i e educed cos column.
P ecisely, we apply he same heu is ic algo i hms o sol e he ESPPRC
as hose used in he column gene a ion app oach o he C-SDVRP
p oposed in Pe is e al. (2023). One o hese heu is ics is a wo-phase
algo i hm which exploi s he mul i-commodi y aspec o he p oblem,
while he o he s a e based on educing he p icing mul i-g aph by
es ic ing he se o neighbou s o he cus ome s and by limi ing he
o al numbe o spli s in a ou e. When all he heu is ics ail o iden i y
a nega i e educed cos column, we sol e he ESPPRC exac ly.
5.2. Managemen o he alid inequali ies
In his sec ion, we i s desc ibe how he alid inequali ies p esen ed
in Sec ion 4.1 a e conside ed in he p icing p oblem. Then, we p esen
he cu ing s a egy adop ed in ou BPC algo i hm.
Impac o he alid inequali ies on he p icing p oblem
Fi s , no e ha inequali y (9) imposes a lowe bound on he numbe
o ehicles used in he collec ion echelon. The e o e, i has no impac on
he p icing p oblem. The o he inequali ies p esen ed in Sec ion 4.1 a e
all obus , i.e. hey do no change he s uc u e o he p icing p oblem,
and hei associa ed dual p ices ha e o be in eg a ed in o he objec i e
unc ion o p icing p oblems [PP(𝑜)], 𝑜∈, i.e. on he cos o a cs in
mul i-g aph (𝑜).
The a c cos s in mul i-g aph (𝑜)a e modi ied in he ollowing way:
Inequali ies (10a) and (10b).Le 𝜏+≥0and 𝜏−≤0be he op imal
dual p ices associa ed wi h alid inequali ies (10a) and (10b)
espec i ely. The alue 𝜏+∕2 + 𝜏−∕2 is sub ac ed om he cos
o a cs o ype (𝑖′′, 𝑗′), i e ices 𝑖o 𝑗 ep esen dis ibu ion
cen e 𝑜.
Inequali ies (11).Le 𝜉′≥0be he op imal dual p ices associa ed
wi h he capaci y cu (11) de ined o e he subse o cus ome s
′⊆. Le 𝛿−(′)be he subse o a cs in g aph en e ing in
e ices o ′. The alue 𝜉′is sub ac ed om he cos o a cs
(𝑖′′, 𝑗′), o all (𝑖, 𝑗) ∈ 𝛿−(′).
Inequali ies (12).Le 𝛾𝑗𝑗≥0be he op imal dual p ices associa ed
wi h he inequali y (12) iden i ied by cus ome 𝑗∈and
commodi y subse 𝑗⊆𝑗. The alue 2𝛾𝑗𝑗is sub ac ed om
he cos o a cs (𝑗′, 𝑗′′)′
𝑗, o all ′
𝑗⊆𝑗 ha con ain a leas
all he commodi ies o 𝑗, i.e., 𝑗⊆′
𝑗. The alue 𝛾𝑗𝑗is
sub ac ed om he cos o a cs (𝑗′, 𝑗′′)′
𝑗 o all ′
𝑗 ha con ain
some, bu no all, commodi ies o 𝑗, i.e. ′
𝑗∩𝑗≠∅and
′
𝑗∩𝑗≠ 𝑗.
Inequali ies (16) and (17).Le 𝑗∈be a cus ome equi ing exac ly
h ee commodi ies (|𝑗|= 3) and le 𝜓≥0and 𝜒≤0be he
op imal dual p ices associa ed wi h inequali ies (16) and (17)
de ined on 𝑗. Fo all 𝑗⊆𝑗, he cos o a c (𝑗′, 𝑗′′)𝑗is
modi ied as ollows: alue |𝑗|𝜓is sub ac ed, alue 𝜒is added
i |𝑗|= 2, and alue 𝜒is sub ac ed i |𝑗|= 1.
Managemen o he alid inequali ies in he RMP
Valid inequali ies on ehicle bounds, namely (9),(10a) and (10b),
a e included in he o mula ion om he beginning o he solu ion p o-
cedu e. Di e en ly, a cu gene a ion p ocedu e manages he inse ion
o iola ed inequali ies (11),(12),(16) and (17) in he RMP. Such a
p ocedu e is called a each node o he b anch-and-bound ee o le el
a mos equal o 5, i he associa ed solu ion o he RMP is ac ional.
Speci ically, i sepa a es he inequali ies hie a chically acco ding o
he sequence : (11),(12),(16), and (17). When he sepa a ion o a
gi en inequali y ails, we sepa a e he nex one in he abo e o de . The
sepa a ion o inequali ies (11) is done using he heu is ic algo i hms
p esen ed in Ralphs e al. (2003), namely he ex ended sh inking heu is ic
and he g eedy sh inking heu is ic. Then, al hough, inequali ies (12)
a e exponen ially-many, he size o he p oblem ins ances allows he
sepa a ion by enume a ion. The same sepa a ion s a egy is applied o
inequali ies (16) and (17), whose numbe is linea in he numbe o
cus ome s ||. Finally, we limi he numbe o inequali ies (11) o 100
in each cu gene a ion ound. Fo he o he inequali ies, we include all
he iola ed inequali ies.
5.3. B anching s a egies
Le (𝑥, 𝑞,
𝜆)be a ac ional op imal solu ion o he MP a a ce -
ain node o he b anch-and-bound ee. We conside se en b anching
ules ha a e hie a chically applied. In addi ion o hese ules, he
co ec ness o he algo i hm equi es he sepa a ion o a amily o alid
inequali ies, namely he s ong-deg ee inequali ies. Rules 1 and 3 a e
speci ic o he MC2DP, while he o he ones and he amily o alid
inequali ies a e used o sol e he C-SDVRP by B anch-and-P ice. The
in e es ed eade can e e o Gschwind e al. (2019) o mo e de ails
abou he b anching s a egy o he C-SDVRP.
Rule 1 is on he numbe o ehicles a e sing an a c in he collec ion
echelon, i.e., on alue 𝑥𝑖𝑜,𝑖∈,𝑜∈. Since 𝜆𝑟 a iables a e
no conce ned by his ule, he e is no impac on he p icing
p oblem.
Rule 2 is on he numbe o ehicles used a each dis ibu ion cen e
𝑜∈in he deli e y echelon, i.e., on alue ∑𝑟∈𝑜
𝜆𝑟.
Rule 3 o ces he assignmen o a deli e y o a dis ibu ion cen e.
Speci ically, gi en a dis ibu ion cen e 𝑜∈, a cus ome
𝑗∈and a commodi y 𝑘∈𝑗, we b anch on alue 𝑝𝑜
𝑗𝑘 ∶=
∑𝑟∈𝑜𝑎𝑟
𝑗𝑘
𝜆𝑟. The b anching decisions ela ed o his ule can be
exp essed as ollows: commodi y 𝑘 equi ed by cus ome 𝑗is
ei he deli e ed om dis ibu ion cen e 𝑜, i.e. ∑𝑜′∈⧵{𝑜}∑𝑟∈𝑜′
𝑎𝑟
𝑗𝑘𝜆𝑟= 0; o no deli e ed om 𝑜, i.e. ∑𝑟∈𝑜𝑎𝑟
𝑗𝑘𝜆𝑟= 0. No e
ha bo h decisions en ail modi ica ions in he p icing p oblem.
As an example, i he i s decision is imposed, hen we p e en
he p icing p oblem om gene a ing ou es s a ing and ending
a dis ibu ion cen es 𝑜′∈⧵{𝑜}and deli e ing commodi y 𝑘 o
cus ome 𝑗. A cs o ype (𝑗′, 𝑗′′)𝑗, wi h 𝑗⊆𝑗and 𝑘∈𝑗,
a e emo ed om all mul i-g aphs (𝑜′),𝑜′∈⧵{𝑜}.
Rule 4 is on he numbe o isi s o each cus ome 𝑗∈ om a
dis ibu ion cen e 𝑜∈.
Rule 5 conside s he low on he edges in he deli e y echelon coming
om a speci ic dis ibu ion cen e.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
6
M. Pe is e al.
Rules 6 and 7 implemen he Ryan and Fos e b anching ules (Ryan
and Fos e ,1981) which o ce he wo cus ome eques s o be
se ed by di e en ou es o by he same ou e. Such ules imply
he addi ion o non- obus cons ain s in he RMP . The manage-
men o he associa ed dual a iables in he labelling algo i hm
used o sol e he p icing p oblem can be ound in Gschwind
e al. (2019).
These se en ules a e su icien o ensu e he co ec ness o he
algo i hm when only elemen a y ou es a e p esen in o mula ion
[SC]. Indeed, Rule 1 gua an ees he in eg ali y o he a iables o he
collec ion echelon. Then, ega ding he deli e y echelon, Rule 3 assigns
he deli e ies o a speci ic dis ibu ion cen e. Once hese assignmen s
a e done, Rules 2 and 4–7 a e enough o gua an ee he co ec ness o
he algo i hm. Indeed, he deli e y echelon is a mul i-depo e sion
o he C-SDVRP and such ules ensu e he in eg ali y o a solu ion
o he C-SDVRP (see Gschwind e al.,2019). Howe e , as men ioned
in Sec ion 5.1, we elax he elemen a i y equi emen o he ou es
in he second echelon ia he ng-pa h elaxa ion when sol ing he
p icing p oblem. Consequen ly, o mula ion [SC] may con ain ou es
ha se e he same commodi y o he same cus ome mo e han once.
In such a case, applying only Rules 1–7 migh lead o a ac ional
solu ion as shown by Gschwind e al. (2019) o he C-SDVRP. Hence,
a e applying Rule 7, s ong-deg ee inequali ies (Con a do e al.,2014)
ha e o be sepa a ed o ensu e p o iding an in ege solu ion. The
s ong-deg ee inequali ies ead as:
∑
𝑟∈
𝜉𝑟
𝑗𝑘𝜆𝑟≥1 ∀𝑗∈,∀𝑗∈𝑗,
whe e 𝜉𝑟
𝑗𝑘 is a bina y coe icien wi h alue one i ou e 𝑟∈
deli e s cus ome 𝑗∈wi h commodi y 𝑘∈𝑗. In ou b anching
s a egy, when none o he se en ules a e applicable, we sepa a e hese
inequali ies. As o Rules 6 and 7, hese inequali ies a e non- obus . The
managemen o he associa ed dual a iables in he labelling algo i hm
in oked o sol e he p icing p oblem is desc ibed in Con a do e al.
(2014).
The b anch-and-bound ee is explo ed acco ding o a bes -bound
i s s a egy o a ou he imp o emen o he dual bound. The s a e-
gies o selec he b anching decisions a e p esen ed in he ollowing.
Fo ule 2, we b anch on he ac ional alue closes o 0.5. Fo ules 6
and 7, we b anch on he i s ac ional alue ha is ound. Fo all he
o he ules, we conside a wo- ound s ong b anching p ocedu e (S.,
2012) simila o he one p esen ed in Pessoa e al. (2020). In he
i s ound, we e alua e a mos 100 b anching candida es acco ding
o he p oduc ule (Ach e be g,2007). Mo e p ecisely, each candida e
gi es ise o wo b anching decisions 𝑑1and 𝑑2and is e alua ed
by applying such decisions o he RMP and by sol ing i wi hou
gene a ing columns. Then, each candida e is assigned wi h a sco e
𝑠𝑐(𝑑1, 𝑑2) = max{𝜖, 𝛥𝐿𝐵1} × max{𝜖, 𝛥𝐿𝐵2}, whe e 𝜖= 10−6 and 𝛥𝐿𝐵𝑖
is he inc ease o he lowe bound ob ained by applying decision 𝑑𝑖 o
he RMP. The h ee candida es wi h he highes sco es a e sen o he
second ound, whe e he same e alua ion c i e ion is used o selec he
winning candida e. Di e en ly om he i s ound, he e, 𝐿𝐵1and 𝐿𝐵2
a e he alues o he RMP a e a single column gene a ion i e a ion
whe e he p icing p oblem is sol ed heu is ically.
The s ong b anching p ocedu e is employed in nodes o he b anch-
and-bound ee o le el a mos 5. In he o he le els, we e alua e he
b anching candida es based on he ac ional alue closes o 0.5 o all
he ules.
5.4. Accele a ing s a egies
The BPC algo i hm inco po a es he ollowing accele a ing s a e-
gies:
Ini ializa ion o se .We ini ialize he se o ou es o a oid
e y la ge dual p ices a he i s i e a ions o he column
gene a ion p ocedu e which may slow down he p icing so-
lu ion (Desaulnie s,2010). Speci ically, o each dis ibu ion
cen e 𝑜∈, we include ound- ips (0-𝑗-0) o each cus-
ome 𝑗∈, which deli e he commodi ies o each subse
𝑗⊆𝑗 eques ed by 𝑗. In addi ion, we modi ied he andom-
ized Cla ke-W igh algo i hm (CW) (Cla ke and W igh ,1964)
p oposed in Ba a a e al. (2008) o ake in o accoun he mul i-
commodi y aspec o ou p oblem. The algo i hm is un 10 imes
pe dis ibu ion cen e and he ob ained ou es a e inse ed in o
.
Heu is ic column gene a o s. Be o e sol ing he p icing p oblem o
op imali y, we conside heu is ic column gene a o s o speed
up he solu ion o p oblems [PP(𝑜)], 𝑜∈. As men ioned
in Sec ion 5.1, each p oblem [PP(𝑜)] is he p icing p oblem
a ising in a BPC algo i hm o he C-SDVRP. Hence, we apply
he same heu is ic scheme used in Pe is e al. (2023) which
p o ed o be e ec i e in accele a ing such p icing p oblems.
This scheme conside s wo educed g aph heu is ics and he
wo-phase heu is ic in oduced in Pe is e al. (2023) which
p o ed o be e ec i e in dealing wi h he mul i-commodi y
aspec o he C-SDVRP. The wo educed g aph heu is ics educe
he size o mul i-g aphs (𝑜),𝑜∈by limi ing bo h he
possibili ies o a elling be ween cus ome s and o deli e ies
o cus ome s. In he wo-phase heu is ic, he aim o he i s
phase is o compu e a se o p omising cus ome sequences by
sol ing he ESPPRC on a modi ied e sion o mul i-g aphs (𝑜)
whe e only one deli e y pe cus ome is allowed. Speci ically,
when isi ing a cus ome , he leas consuming commodi y is
deli e ed and all he p o i able dual p ices a e collec ed. In he
second phase, o each o he cus ome sequences gene a ed by
he i s phase, we sol e he ESPPRC on he associa ed acyclic
g aphs o ob ain all nega i e educed cos ou es a ising om
he sequence. We e e o Pe is e al. (2023) o mo e de ails.
Res ic ed mas e heu is ic. We in oke a es ic ed mas e heu is ic,
which consis s in sol ing he o mula ion [SC] es ic ed o
he subse o a iables gene a ed so a , o ob ain good uppe
bounds. Such a echnique helps o educe he in eg ali y gap (see
A che i e al.,2013). No e ha a iables 𝜆𝑟a e hen bina y. We
call he es ic ed mas e heu is ic e e y 1000 explo ed nodes in
he b anch-and-bound ee as well as when he ime limi o he
algo i hm is eached. In his la e case, we apply a local sea ch
p ocedu e based on an adap ed e sion o he ma hema ical
p og amming ope a o p oposed o he C-SDVRP in Gu e al.
(2019). Speci ically, we gene alized such an ope a o o deal
wi h he wo-echelon case. When he es ic ed mas e heu is ic
is called du ing he ee explo a ion a ime limi o 3seconds is
imposed, while he ime limi is 30 seconds when he algo i hm
e mina es.
6. Compu a ional expe imen s
We implemen ed he BPC algo i hm in C++ and compiled i in
elease mode unde a 64-bi e sion o MS Visual S udio 2019. IBM
CPLEX 12.9.0 (64-bi e sion) is used as a sol e . We pe o med he
expe imen s on a 64-bi Windows machine equipped wi h a In el(R)
Xeon(R) Sil e 4214 p ocesso wi h 24 co es hype - h eaded o 48
i ual co es, wi h a base clock equency o 2.2 GHz, and 96 GB o
RAM. Fo each un o he algo i hm, we impose one hou ime limi
and allow a single h ead.
In his sec ion, i s , we desc ibe he cha ac e is ics o he bench-
ma k ins ances o he MC2DP in oduced in Gu e al. (2022). Then,
we discuss he impac o alid inequali ies (12),(16) and (17). Finally,
we e alua e he e ec i eness o he BPC algo i hm agains sol ing he
compac o mula ion o he MC2DP p esen ed in Gu e al. (2022) wi h
a comme cial sol e and we p esen he esul s ob ained by he BPC
algo i hm on he benchma k ins ances.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
7
M. Pe is e al.
Table 1
Cha ac e is ics o he se s o ins ances.
Se # Cha ac e is ics
|| || ||Desc ip ion
S64 8 30 2, 3 Base se
S
164 8 30 2, 3 Unbalanced supplie loca ions (6-2)
S
264 8 30 2, 3 Unbalanced supplie loca ions (8-0)
S
164 8 30 2, 3 Unbalanced cus ome loca ions (5-10, wi h 𝛿= −5,30)
S
264 8 30 2, 3 Unbalanced cus ome loca ions (5-10, wi h 𝛿= 10,30)
S
364 8 30 2, 3 Unbalanced cus ome loca ions (10-5, wi h 𝛿= −5,30)
S
464 8 30 2, 3 Unbalanced cus ome loca ions (10-5, wi h 𝛿= 10,30)
S𝑂32 8 30 2 Unbalanced a ailable amoun s a he supplie s
S𝑎𝑑𝑑
164 10 30 2, 3 Inc eased numbe o supplie s o 10
S𝑎𝑑𝑑
264 12 30 2, 3 Inc eased numbe o supplie s o 12
S𝑎𝑑𝑑
164 8 50 2, 3 Inc eased numbe o cus ome s o 50
S𝑎𝑑𝑑
264 8 70 2, 3 Inc eased numbe o cus ome s o 70
Small 36 4, 6 10, 15, 20, 25 2, 3 Small ins ances
6.1. Benchma k ins ances
Gu e al. (2022) in oduced a i icial ins ances as well as ins ances
a ising om a eal-wo ld case s udy in he con ex o a sho and local
esh ood supply chain. In he ollowing compu a ional expe imen s,
we only conside he a i icial ins ances. Indeed, he sizes o he in-
s ances based on he case s udy a e oo la ge o be ackled e icien ly
wi h he BPC algo i hm.
Fi s , Gu e al. (2022) gene a ed a base se o 64 a i icial ins ances
Swi h wo dis ibu ion cen es (||= 2), eigh supplie s (||= 8) and
30 cus ome s (||= 30). The ea u es o he deli e y echelon a e based
on he 64 small ins ances p oposed in A che i e al. (2016) o he C-
SDVRP. Each C-SDVRP ins ance gi es ise o a MC2DP ins ance whe e
he loca ions o one dis ibu ion cen e and 15 cus ome s a e he ones
o he C-SDVRP ins ance. Such dis ibu ion cen e and 15 cus ome s a e
duplica ed and hei loca ions a e modi ied by applying a ansla ion
o pa ame e 𝛿= (30,30) o hei coo dina es. Cus ome demands a e
also as in he C-SDVRP ins ance. Fou supplie s a e andomly loca ed
a ound each dis ibu ion cen e. The a ailabili y o each commodi y
a he supplie s is calcula ed as a ac ion o he o al demand. The
commodi y a ailabili ies a e he same o all he supplie s.
Then, Gu e al. (2022) p oduced 12 addi ional se s o ins ances
by applying modi ica ions o one o he cha ac e is ics o he base
se , such as he supplie s/cus ome s loca ions, he numbe o suppli-
e s/cus ome s o he a ailable quan i ies a he supplie s. In all se s o
ins ances, he numbe o dis ibu ion cen es is ixed a wo. In Table 1,
we summa ize he main cha ac e is ics o all se s o ins ances. Each
ow o he able ep esen s a se o ins ances. The columns o he able
epo : se : he name o he se o ins ances; #: he numbe o ins ances
in he se ; ||: he numbe o supplie s; ||: he numbe o cus ome s;
||: he numbe o commodi ies; desc ip ion: a b ie desc ip ion o he
main cha ac e is ic o he se . In such an en y, we w i e 𝑛1−𝑛2
o exp ess he dis ibu ion o he supplie s/cus ome s a ound each
dis ibu ion cen e, meaning ha 𝑛1supplie s/cus ome s a e loca ed
a ound one dis ibu ion cen e and 𝑛2a e loca ed a ound he o he one.
Pa ame e 𝛿is a ansla ion pa ame e used o de e mine he loca ions
o he cus ome s/supplie s a ound he wo dis ibu ion cen es. We
e e o Gu e al. (2022) o u he de ails ega ding he gene a ion
o he se o ins ances.
6.2. Impac o alid inequal ies
In his sec ion, we assess he impac o alid inequali ies. To do so,
we conside he 32 ins ances o base se Sha ing h ee commodi ies.
Indeed, as men ioned in Sec ion 4.1, i he numbe o commodi ies is
equal o wo, inequali ies (12),(16) and (17) can be e ie ed as an
agg ega ion o Co e ing Cons ain s (4).
We examine he ollowing ou a ian s o he BPC algo i hm.
BPC: alid inequali ies on bounds on he numbe o ehicles a e
inse ed, and no alid inequali ies is sepa a ed in he cou se o he
algo i hm; BPC+CC: only capaci y cu s ( alid inequali ies (11)) a e sep-
a a ed; BPC+SC+NP: only he inequali ies a ising om he se co e ing
poly ope (SC), i.e., inequali ies (12), and he ones a ising om he
numbe pa i ioning poly ope (NP) a e sepa a ed, i.e., inequali ies (16)
and (17), a e sepa a ed; BPC+CC+SC+NP: all alid inequali ies a e
sepa a ed.
Each ow o Table 2 co esponds o a BPC a ian . The i s wo
columns epo he a e age lowe bound (a g.LB) and ime (a g. [s])
a he oo node o he b anch-and-bound- ee. The nex ou columns
show he esul s a he end o he execu ion o he co esponding
BPC a ian : he a e age numbe o nodes o he b anch-and-bound
ee (a g.#nodes), he a e age lowe bound a e mina ion (a g.LB) he
a e age ime (a g. [s]) and he numbe o ins ances sol ed o op imali y
(#op ./#ins .) o e he 32 ins ances.
As expec ed, BPC yields he wo s esul s sol ing only six ins ances
ou o he 32 conside ed. Va ian BPC+SC+NP sol es an addi ional
ins ance w. . . BPC, howe e , he imp o emen o he lowe bound
a he oo node is medioc e. The bes esul s a e ob ained when
he well-es ablished capaci y cu s a e sepa a ed, namely wi h a i-
an s BPC+CC and BPC+CC+SC+NP. Bo h a ian s sol e he same 14
ins ances o op imali y and yield he bes lowe bounds a he oo
node, being on a e age equal o 1000.35 and 1001.31 in BPC+CC
and BPC+CC+SC+NP, espec i ely. The same ema k applies o he
lowe bounds a e mina ion which is on a e age equal o 1039.61
in BPC+CC and BPC+CC+SC+NP. In bo h cases, lowe bounds a he
oo node and a e mina ion imp o e signi ican ly wi h espec o
BPC. We also obse e ha he addi ion o inequali ies (12),(16) and
(17) in BPC+CC+SC+NP sligh ly imp o es he esul s wi h espec
o BPC+CC in e ms o lowe bounds a he oo node, numbe o
explo ed b anch-and-bound nodes and solu ion ime. Hence, we choose
BPC+CC+SC+NP as he con igu a ion o ou BPC algo i hm.
6.3. E alua ion o he BPC algo i hm
The aim o his sec ion is o e alua e he e ec i eness o he BPC
algo i hm. To do so, we compa e he esul s ob ained by he BPC
algo i hm on he ins ances o se small wi h he ones ob ained by
sol ing a compac o mula ion o he MC2DP on he same ins ances
wi h CPLEX 12.8. The la e esul s a e e ie ed om Gu e al. (2022)
and we e ob ained on a machine wi h In el (R) Co e(TM) i7-4600U
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100139
8
