Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoff

Faldum, S e an; Macha e, Sa ah; Gschwind, Timo; I nich, S e an
A icle — Published Ve sion
Pa ial dominance in b anch-p ice-and-cu algo i hms o
ehicle ou ing and scheduling p oblems wi h a single-
segmen adeo
OR Spec um
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Faldum, S e an; Macha e, Sa ah; Gschwind, Timo; I nich, S e an (2024) : Pa ial
dominance in b anch-p ice-and-cu algo i hms o ehicle ou ing and scheduling p oblems wi h a
single-segmen adeo , OR Spec um, ISSN 1436-6304, Sp inge , Be lin, Heidelbe g, Vol. 46, Iss. 4,
pp. 1063-1097,
h ps://doi.o g/10.1007/s00291-024-00766-y
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/313820
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 (2024) 46:1063–1097
h ps://doi.o g/10.1007/s00291-024-00766-y
1 3
ORIGINAL ARTICLE
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms
o  ehicle ou ing andscheduling p oblems
wi hasingle‑segmen adeo
S e anFaldum1 · Sa ahMacha e2· TimoGschwind2 · S e anI nich1
Recei ed: 5 Janua y 2024 / Accep ed: 6 May 2024 / Published online: 26 June 2024
© The Au ho (s) 2024
Abs ac
Fo many a ian s o ehicle ou ing and scheduling p oblems sol ed by a b anch-
p ice-and-cu (BPC) algo i hm, he p icing subp oblem is an elemen a y sho es -
pa h p oblem wi h esou ce cons ain s (SPPRC) ypically sol ed by a dynamic-p o-
g amming labeling algo i hm. Sol ing he SPPRC subp oblems consumes mos o
he o al BPC compu a ion ime. C i ical o he pe o mance o he labeling algo-
i hms and hus he BPC algo i hm as a whole is he use o e ec i e dominance
ules. Classical dominance ules ely on a pai wise compa ison o labels and ha e
been used in many labeling algo i hms. In con as , pa ial dominance desc ibes si u-
a ions whe e se e al labels oge he a e needed o domina e ano he label, which can
hen be sa ely disca ded. In his wo k, we conside SPPRCs, whe e a linea adeo
desc ibes he ela ionship be ween wo esou ces. We de i e a uni ied pa ial domi-
nance ule o be used in ad hoc labeling algo i hms o sol ing such SPPRCs as well
as insigh s in o i s p ac ical implemen a ion. We in oduce pa ial dominance o wo
impo an a ian s o he ehicle ou ing p oblem, namely he elec ic ehicle ou -
ing p oblem wi h ime windows wi h a pa ial echa ge policy and he spli -deli e y
ehicle ou ing p oblem wi h ime windows (SDVRPTW). Compu a ional expe i-
men s show he e ec i eness o he app oach, in pa icula o he SDVRPTW, lead-
ing o an a e age educ ion o 20% o he o al BPC compu a ion ime, wi h sa ings
o 30% o he mo e di icul ins ances equi ing mo e han 600s o compu a ion
ime.
Keywo ds B anch-p ice-and-cu · Pa ial dominance· Column gene a ion· Labeling
algo i hm· Vehicle ou ing and scheduling
Ex ended au ho in o ma ion a ailable on he las page o he a icle
1064
S.Faldum e al.
1 3
1 In oduc ion
Fo many a ian s o he ehicle ou ing p oblem (VRP, To h and Vigo 2014),
b anch-and-p ice (BP, Desaulnie s e al. 2005) based algo i hms cons i u e he lead-
ing exac solu ion me hodology (Cos a e al. 2019). A BP algo i hm is a b anch-and-
bound algo i hm in which he lowe bounds a e compu ed by column gene a ion.
Column gene a ion is an i e a i e p ocedu e ha can ackle linea p og ams con ain-
ing a huge numbe o a iables. A each i e a ion, i sol es a es ic ed mas e p ob-
lem (RMP) comp ising only a subse o he a iables o he o iginal linea p og am
and one o se e al p icing subp oblems o dynamically gene a e missing a iables
wi h nega i e educed cos o o p o e ha no such a iable exis s. Cu ing planes
a e added o s eng hen he linea elaxa ions gi ing ise o a b anch-p ice-and-
cu (BPC) algo i hm. Fo de ails on he heo y o BPC, we e e o Ba nha e al.
(1998), Lübbecke and Des osie s (2005).
The mas e p og am is o en an ex ended se -pa i ioning o se -co e ing o -
mula ion o selec ing he bes ou es, while he p icing subp oblem is an elemen-
a y sho es -pa h p oblem wi h esou ce cons ain s (SPPRC) ypically sol ed by
dynamic-p og amming labeling algo i hms ( o an o e iew o SPPRCs and labe-
ling algo i hms, see I nich and Desaulnie s 2005). In a labeling algo i hm, pa ial
pa hs a e g adually ex ended in a ne wo k om a gi en sou ce
o
o a sink
d
( he
o igin and des ina ion depo in he con ex o VRPs) seeking o a esou ce easible
minimum-cos
o
-
d
-pa h. The pa ial pa hs a e ep esen ed by labels ha s o e in o -
ma ion on he accumula ed esou ce consump ion up o he endpoin o he pa ial
pa hs. He ein, esou ces a e quan i ies necessa y o compu e he educed cos and,
e.g., he load onboa d and he s a o he se ice, a he end o he pa ial pa h.
In pa icula , esou ces a e used o decide on he easibili y o pa ial pa hs. The
p opaga ion o he labels along he a cs o he ne wo k is pe o med wi h he help o
esou ce ex ension unc ions (REFs, I nich 2008). C ucial o he pe o mance o a
labeling algo i hm is he dominance ela ion be ween pa ial pa hs. The dominance
ela ion is a ela ion be ween labels (i.e., pa ial pa hs) used o iden i y and disca d
hose ha canno lead o a be e solu ion o he SPPRC han possible wi h a known
pa ial pa h. Dominance is ypically ealized by compa ing he esou ce alues o
he labels and a oids he enume a ion o all easible pa ial pa hs ha can be ound
in he ne wo k.
Classical dominance ela ions ha ha e been used in many labeling algo i hms
ely on a pai wise compa ison o labels. In o mally speaking, i one o he labels
is wo se han he o he , i can be sa ely disca ded. Fo mally, we assume ha he
ne wo k
(V,A)
wi h sou ce
o∈V
and sink
d∈V
a e gi en. Fo a pa ial pa h
p
,
i.e., an
o
-i-pa h ending a some e ex
i∈V
, any i-
d
-pa h
q
ha p o ides a easi-
ble
o
-
d
-pa h
=(p,q)
is called a easible ex ension o
p
. Now, pai wise dominance
be ween wo pa ial pa hs can be cha ac e ized wi h he help o easible ex ensions
as ollows:
P oposi ion 1 (Pai wise Dominance) Le
p1
and
p2
be wo di e en pa ial pa hs
ending a he same e ex
i∈V
. I , o each easible ex ension
q2
o
p2
,
1065
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
(i) he pa h
q2
is also a easible ex ension o
p1
, i.e.,
1=(p1,q2)
is easible
(ii) o he e exis s a easible ex ension
q1
o
p1
( he ex ension
q1
is allowed o di e
om
q2
) so ha
1=(p1,q1)
is easible,
and
1
has a smalle o iden ical educed cos han
2
, hen he pa ial pa h
p2
is
domina ed.
Because he condi ions(i) and(ii) in P oposi ion1 a e di icul o e i y o
wo a bi a y pa ial pa hs
p1
and
p2
, labeling algo i hms ypically es su icien
condi ions, so-called dominance ules. Dominance ules do no di ec ly conside
ex ensions, bu hey compa e he esou ce alues o he labels o
p1
and
p2
.
In con as o pai wise dominance, pa ial dominance desc ibes he si ua ion ha se -
e al labels oge he a e, in o mally speaking, be e han ano he label which can hen be
sa ely disca ded. A o mal cha ac e iza ion o pa ial dominance is gi en in he ollowing
p oposi ion.
P oposi ion 2 (Pa ial Dominance) Le
P
be a se o pa ial pa hs and
p2∉P
be
ano he pa ial pa h all ending a he same e ex
i∈V
. I , o each easible ex en-
sion
q2
o
p2
, he e exis s a
p1∈P
such ha he condi ion(i) o he condi ion(ii)
o P oposi ion1 is ul illed and he esul ing
o
-
d
-pa h
1
has a smalle o iden ical
educed cos han
2=(p2,q2),
hen he pa ial pa h
p2
is domina ed.
The no ion o pa ial dominance e lec s he concep ha any pa h
p1∈P
gene -
ally ul ills he dominance condi ions in P oposi ion1 only o some ex ensions
q2
o
p2
, i.e.,
p1
pa ially domina es
p2
. Conside ing all he pa hs in
P
oge he , all ex en-
sions
q2
o
p2
a e domina ed so ha
p2
can be disca ded.
In he VRP li e a u e, pa ial dominance has been employed in di e en si ua-
ions like SPPRCs wi h a adeo be ween esou ces, handling elaxa ions o he
elemen a i y condi ion in SPPRCs, and o he use cases (see Sec .2). The ocus o
his pape is on pa ial dominance o SPPRCs wi h a adeo be ween esou ces
and, in pa icula , on he mos basic ype o such a adeo , i.e., a linea adeo
wi h a single linea piece as depic ed in Fig.1. An example o a linea adeo can
be ound in he con ex o he elec ic ehicle ou ing p oblem wi h ime windows
(EVRPTW) wi h pa ial echa ging (Schneide e al. 2014): Ba e y elec ic ehi-
cles ha e a limi ed d i ing ange, which can be ex ended by cha ging he ba e y a
dedica ed echa ging s a ions. The adeo is be ween he amoun o be echa ged
and he ime equi ed o do so. Longe cha ging inc eases he d i ing ange, bu may
hinde he imely a i al a la e cus ome s due o hei se ice ime windows. In
Fig.1, he x-axis ep esen s he ime when a se ice can begin, and he y-axis ep e-
sen s he amoun o ene gy ha could be easibly echa ged: Being ea ly in he ime
window [a,b] allows mo e ene gy (up o u) o be echa ged, while being la e limi s
i (down o l).
In gene al, Fig.1 shows he easible domain o wo esou ces
x
and
y
o a pa -
ial pa h ep esen ed by label
F
. Fo he esou ce
x
, he minimum easible esou ce
consump ion is
Fa
and he maximum easible esou ce consump ion is
Fb
. Likewise,
i is
Fl
and
Fu
o he esou ce
y
. Fo bo h esou ces, smalle alues a e p e e able.
1066
S.Faldum e al.
1 3
The adeo unc ion
cha ac e izes he na u e o he adeo : Whene e we allow
esou ce
x
o inc ease by one uni ( ecall ha smalle alues a e p e e able), he con-
sump ion o esou ce
y
can be dec eased by
m
uni s, i.e., he slope o
is
−m
.
The con ibu ions o his pape a e he ollowing. We p o ide a o mal cha ac-
e iza ion o linea adeo s be ween esou ces wi h a single linea piece wi hin
SPPRCs and de i e a uni ied pa ial dominance ule o be used in ad hoc labeling
algo i hms o he solu ion o co esponding SPPRCs as well as insigh s on i s p ac-
ical implemen a ion. Ou esul s apply o bo h he elemen a y and he non-elemen-
a y e sion o he SPPRC. Fu he mo e, we exempli y he applica ion o pa ial
dominance o wo impo an a ian s o he VRP wi h a linea adeo in hei
SPPRC p icing subp oblems, namely he EVRPTW wi h a pa ial echa ge policy
and he spli -deli e y ehicle ou ing p oblem wi h ime windows (SDVRPTW).
Finally, we epo an ex ensi e compu a ional analysis o using pa ial dominance
compa ed o he classical pai wise dominance o he EVRPTW and he SDVRPTW
on hei s anda d benchma ks.
The emainde o he pape is s uc u ed as ollows. In Sec . 2, we ca ego ize
di e en use cases in which pa ial dominance has been used wi hin SPPRC sub-
p oblems and e iew he co esponding li e a u e. Sec ion3 p o ides he heo e i-
cal analysis o pa ial dominance o linea adeo s be ween esou ces. Sec ion4
de ails i s applica ion o he EVRPTW and he SDVRPTW. Ou compu a ional
s udy on he EVRPTW and he SDVRPTW is epo ed in Sec .5. Final conclusions
a e d awn in Sec .6.
2 Li e a u e e iew
Pa ial dominance has been used o di e en ypes o SPPRC subp oblems. We ca -
ego ize in o linea adeo unc ions and non-linea adeo unc ions desc ibing
he ela ionship o wo esou ces, pa ial dominance in SPPRC wi h elemen a i y
cons ain s, and o he o ms o pa ial dominance.
Fig. 1 T adeo wi h a single
linea piece be ween wo
esou ces
x
and
y
x
y
ab
u
l
S
domina ed a ea D(S)
m
1

1067
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
Linea T adeo Func ions Fi s , SPPRC subp oblems ha ha e a adeo be ween
wo esou ces can bene i om pa ial dominance. This ype o dominance s a ed
wi h he wo ks (Ioachim e al. 1998, 1999) o ai plane ligh scheduling. In his
applica ion, he only esou ces a e ime and educed cos such ha a pa ial pa h
can be comple ely cha ac e ized by a con inuous, piecewise linea adeo unc ion.
The seminal pape o Desaulnie s e al. (1998) cla i ies when and how such linea
adeo s be ween esou ces esul om esou ce cons ain s in ex ensi e pa h-based
o mula ions sol ed wi h column-gene a ion algo i hms: Resou ce cons ain s in
he mas e p og am e e ing o esou ce le els a e ices o a a cs esul in lin-
ea node/ e ex and a c cos s. Fo con inuous, piecewise linea adeo unc ions,
Desaulnie s and Villeneu e (2000) de eloped an implici o m o pa ial dominance
o he espec i e SPPRC subp oblems: Whene e he minimum o se e al ade-
o unc ions o a se o pa hs is comple ely below he adeo unc ion o ano he
pa h, his pa h can be elimina ed. Such con inuous, piecewise linea adeo unc-
ions be ween wo esou ces a ise in se e al ehicle scheduling and ou ing p ob-
lems. Examples o his o m o pa ial dominance used o sol ing SPPRC subp ob-
lems a e he VRP wi h so ime windows (Libe a o e e al. 2010), he ime-window
assignmen VRP (Splie and Gabo 2015; Splie e al. 2018), he ac i e-passi e VRP
(Tilk e  al. 2018), he ime-dependen VRP wi h ime windows (VRPTW) (Le a-
Rome o e al. 2020), and he SDVRPTW wi h linea weigh - ela ed cos (Luo e al.
2017).
The handling o piecewise de ined unc ions pe label is somewha incon en-
ien , in pa icula when he numbe o pieces is no bounded (by a small ins ance-
independen numbe ). Fo he EVRPTW wi h pa ial echa ges (Desaulnie s e al.
2016b) and he SDVRPTW (Desaulnie s 2010), he e is only one linea piece which
includes he case o a single poin . The EVRPTW and he SDVRPTW a e he wo
VRP a ian s ha we conside in he compu a ional analysis, see Sec .4. In a ol-
low up publica ion on a a ian o he in en o y- ou ing p oblem, Desaulnie s e al.
(2016a) apply simila solu ion me hods, because also his p oblem can be modeled
wi h REFs wi h no mo e han one linea piece.
E en i we did no ind wo ks sugges ing pa ial dominance o some applica-
ions, i should also be applicable when sol ing SPPRC subp oblems o he ollow-
ing p oblems: he dial-a- ide p oblem wi h ide- ime cons ain s (Gschwind and
I nich 2015), he synch onized pickup and deli e y p oblem (Gschwind 2015), he
uck-and- aile VRP wi h quan i y-dependen ans e imes (Ro henbäche e  al.
2018), and he VRP wi h pa ial ou sou cing (Balle e al. 2020). This lis should no
be conside ed comple e.
Non-Linea T adeo Func ions Also non-linea adeo s be ween some esou ce
and educed cos ha e been conside ed. Compa ing piecewise de ined non-linea
adeo unc ions and he ewi h es ablishing a pa ial dominance is mo e in ica e
bu s ill bene icial. In he VRPTW wi h con ex incon enience cos unc ions (He
e al. 2019), a cus ome -speci ic adeo unc ion is de ined o e he cus ome ’s ime
windows.
Elemen a i y Pa ial dominance imp o es dominance o elaxa ions o he elemen-
a y SPPRC: Fo he SPPRC wi h 2-cycle elimina ion (Houck e al. 1980; Kohl e al.
1999), i.e., sho cycles o he o m (i, j, i), wo labels ha ha e mu ually di e en
1068
S.Faldum e al.
1 3
p edecesso e ices can domina e ano he label by esou ce alues. Fo he SPPRC
wi h k-cycle elimina ion, i.e., all cycles o leng h up o k a e o bidden, I nich and Vil-
leneu e (2006) gene alize his pa ial dominance. Up o six labels wi h di e en p e-
decesso sequences a e needed o 3-cycle elimina ion. Fo he gene al case, I nich
and Villeneu e p o e ha no mo e han
k!(k−1)!
di e en p edecesso sequences
a e needed. Fo a SPPRC wi h combined 2-cycle and k-cycle elimina ion, Bode and
I nich (2014) u he gene alize he pa ial dominance. Such a combined cycle elimina-
ion occu s in BPC algo i hms o he capaci a ed a c ou ing p oblem when b anching
decisions and k-cycle ee subp oblems de ined on he s ee ne wo k a e conside ed
simul aneously. Fo he SPPRC subp oblem o he minimum la ency p oblem, Bulhões
e al. (2018) de i e a pa ial dominance o he ng- ou e elaxa ion o he subp oblem.
In his con ex , a i s label ha domina es a second label wi h espec o all esou ces
bu no wi h espec o he ng- ou e es ic ions (i canno be ex ended o one o se e al
cus ome s o which he second label can be ex ended) does howe e pa ially domina e
he second. This pa ial dominance esul s in so-called domina ed ex ensions, i.e., e -
ices o which an ex ension o he second label can be sa ely a oided. Full dominance
occu s when a label canno be ex ended ei he due o he se o domina ed ex ensions
o due o ng- ou e es ic ions. These ideas we e u he exploi ed by Cos a e al. (2021)
whe e e en s onge a c-ng- ou e dominance ules we e p o en in he con ex o selec-
i e p icing (Desaulnie s e al. 2019).
O he Fo ms o Pa ial Dominance We ound some wo ks using a pa ial domi-
nance ha does no all in o one o he abo e ca ego ies. Fo he basic mul i-com-
pa men VRP, Heßle and I nich (2023) use labels ha ep esen pa ial pa hs o
which (a leas ) one easible packing o deli e y i ems in o compa men exis s.
The decision abou he conc e e packing inally used is, howe e , pos poned un il
he pa ial pa h eaches he des ina ion. In pa icula , one label gene ally ep esen s
many al e na i e packings. Pa ial dominance is used o allow ha packings o one
label a e domina ed by some packings o a second label.
Two-a c ixing using educed cos s as sugges ed by Desaulnie s e al. (2020) is an
accele a ion echnique o sol ing SPPRC p icing p oblems as e wi hou comp o-
mising op imali y o he o e all BPC app oach. Sequences o wo consecu i e a cs
ha canno occu in an op imal solu ion a e iden i ied and he labeling algo i hm
ensu es ha a e a e sing he i s a c o he sequence, he label is no ex ended
along he second a c. In o de o main ain op imali y o he p icing, a label mus be
ex ended by he in o ma ion which (second) a cs mus no be used o an ex ension.
This in o ma ion mus be aken in o accoun in he dominance. The au ho s ely on
pa ial dominance, since o he wise he majo i y o he labels is no compa able wi h
he s anda d pai wise dominance.
3 Pa ial dominance o linea dec easing adeo unc ions
In his sec ion, we o mally de ine he linea adeo be ween wo esou ces and
desc ibe he basic heo y o pa ial dominance be ween labels. Fu he mo e, we
add ess gene al issues o he applica ion o pa ial dominance wi hin labeling algo-
i hms o SPPRCs. Finally, we p o ide some de ails o ou implemen a ions.
1069
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
3.1 Basic heo y
We assume ha he linea adeo exis s be ween wo esou ces wi h eal- alued
esou ce alues
x
and
y
. Fo a pa ial pa h and i s label
F
, a p ope adeo can be
desc ibed by a segmen 
S
in
ℝ2
wi h endpoin s
(Fa
,Fu)
and
(Fb
,
Fl)
wi h
Fa<Fb
and
Fu>Fl
, see Fig. 1. Fo mally, he segmen is he con ex hull o i s endpoin s, i.e.,
S=
con
({(Fa
,
Fu)
,
(Fb
,
Fl)})
. The in ui i e in e p e a ion o he adeo desc ibed by
he segmen is ha i esou ce
x
is allowed o inc ease by one uni , he consump ion o
esou ce
y
can be dec eased by
m=(Fu−Fl)∕(Fb−Fa)>0
uni s.
E e y poin 
(x,y)
on he segmen 
S
can be desc ibed wi h he help o a linea unc-
ion
∶
ℝ
1
→ℝ
1
de ined by
No e ha we ha e in en ionally de ined his unde lying unc ion
on he en i e eal
space, and no only on he in e al
[Fa
,
Fb]
. Mo eo e , we can also cope wi h he
case o a one-poin segmen , i.e., ha he wo endpoin s
(Fa
,Fu)
and
(Fb
,
Fl)
a e
iden ical, i.e.,
Fa=Fb
and
Fl=Fu
. In his case, we s ill use (1) by de ining he
(nega i e) slope o be
m=1
. Wi h his de ini ion, also he in e se o
is well-
de ined, i is
x= −1(y)=Fa−
1
∕m
⋅
(y−Fu)
.
Fo bo h esou ces, smalle alues a e p e e able so ha a combina ion
(x,y)
o wo
esou ce alues (he ea e e e ed o as a poin ) domina es
(x�
,y�)
i
x≤x′
and
y≤y′
hold. G aphically speaking, a poin
(x,y)
domina es all poin s ha lie on he op igh
o i . This dominance be ween poin s can be ex ended o se s. In pa icula , o he seg-
men 
S
, he domina ed a ea is
see also Fig.1.
3.1.1 Full dominance
We i s desc ibe he s anda d ull dominance wi h espec o he wo esou ces ha a e
aded agains each o he . No e ha a pa ial pa h ypically has mo e esou ces han jus
hese wo. As a consequence, he ollowing condi ions o ull dominance ega ding he
wo esou ces a e only necessa y condi ions o dominance be ween labels (see also he
dominance o he EVRPTW and he SDVRPTW desc ibed in Sec s.4.1 and4.2).
We assume ha wo labels
F1
and
F2
wi h co esponding segmen s
S1
de ined by
(Fa
1,Fu
1)
and
(
F
b
1
,F
l
1)
and
S2
de ined by
(Fa
2,Fu
2)
and
(
F
b
2
,F
l
2)
a e gi en. Label
F1
ully
domina es
F2
i
S2⊂D(S1)
. An example whe e
S2
lies comple ely in he domina ed
a ea o
S1
is illus a ed in Fig.2.
Full dominance can be e i ied using he ollowing ou condi ions, which mus all
hold ue:
(1)
y= (x)=Fu−m
⋅
(x−Fa).
D(S)={(x�
,
y�)∈
ℝ
2∶ ∃(x
,
y)∈S
wi h
(x
,
y)
domina es
(x�
,
y�)},
(DC1)
Fa
1
≤
Fa
2,
1070
S.Faldum e al.
1 3
Condi ion(DC1) compa es he minimum x- alues and checks whe he
Fa
1
lies u -
he on he le han
Fa
2
. Likewise, condi ion(DC2) compa es he minimum y- alues
and checks whe he
Fl
1
is below
Fl
2
. Condi ion (DC3) compa es he alues o
1
and
2
a
x=Fa
2
. Finally, Condi ion(DC4) compa es he alues o
1
and
2
a
x
=F
b
2
.
The ou dominance condi ions a e isualized in Fig.2.
I bo h segmen s
S1
and
S2
consis o a single poin each, i.e.,
Fa
1
=F
b
1
and
Fa
2
=F
b
2
,
hese condi ions collapse in o he s anda d dominance o he o m
Fa
1
≤
Fa
2
and
Fl
1
≤F
l
2
be ween independen esou ces, i.e., (DC1) and (DC2).
3.1.2 Pa ial dominance
We now cha ac e ize pa ial dominance be ween he wo esou ces o which a adeo
occu s. Reusing he same no a ion as in Sec .3.1.1, we de ine ha a label
F1
pa ially
domina es
F2
i
Recalling ha ull dominance equi es
S2⊂D(S1)
, we speak o a p ope pa ial
domina ion i (2) and
S2⊄D(S1)
a e ul illed. In he spi i o P oposi ion2, a se
F
o labels oge he domina es a label
F2
, i
(DC2)
Fl
1
≤F
l
2,
(DC3)
Fu
1−(
F
a
2−
F
a
1)
⋅m
1
≤F
u
2,
(DC4)
Fu
1
−(F
b
2
−F
a
1
)⋅m
1
≤F
l
2,
(2)
D(
S
1)∩
S
2
≠
�.
(3)
S
2⊂
⋃
F
1
∈F
D(S1)
.
Fig. 2 Full dominance o seg-
men 
S1
o e 
S2
x
y
a2b2
u2
l2
a1b1
u1
l1
S2
S1
(DC1 )
(DC2 )
(DC3 )
(DC4 )
1077
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
pa ially domina es
S3
om he le , and
S2
pa ially domina es
S3
o e a cen-
al piece. I he labeling algo i hm i s compa es
S2
and
S3
, i neglec s his
ac . The subsequen compa ison o
S1
and
S3
esul s in a pa ial dominance
o
S1
o e
S3
om he le . The esul ing se o undomina ed poin s comp ises
mo e han hal o he o iginal segmen 
S3
. I he o de o he wo pai wise
compa isons is swapped, pa ial dominance om he le o
S1
o e
S3
allows
he subsequen pa ial dominance om he le o
S2
o e
S3
. In compa ison,
he emaining se o undomina ed poin s o
S3
is much smalle .
(ii) The capabili y o pa ially domina e ano he label can be educed o los . Con-
side he example shown in Fig.4b. I depic s h ee segmen s
S1
,
S2
, and
S3
,
whe e segmen 
S2
ully domina es
S3
, and segmen 
S1
pa ially domina es
S2
and
S3
om he le . I i s
S1
pa ially domina es
S2
, hen
S2
is upda ed o
desc ibe he emaining se o undomina ed poin s as highligh ed by he hick
line. Now, he educed segmen
S2
only pa ially domina es
S3
om he igh .
Bo h
S1
and
S2
oge he a e needed o comple ely domina e
S3
.
Possibili y(2) A second ype o implemen a ion s o es wo segmen s: he ini ial
segmen 
S
as well as he emaining se 
Su
o undomina ed poin s. We assume ha he
ini ial segmen is ep esen ed by
Fa
,Fb
,Fl
,
and
Fu
. S o ing
Su
can be accomplished
by in oducing ou addi ional a ibu es
Fa
,Fb
,Fl
, and
Fu
. No e ha he wo a ib-
u es
Fa
and
Fb
a e su icien , because
Fu= (Fa)
and
Fl= (Fb)
and he unc ion
can be exp essed wi h he o iginal a ibu es.
This ype o implemen a ion is deno ed double bookkeeping in he ollowing,
because i keeps he in o ma ion abou bo h he la ges possible segmen o domina -
ing o he labels as well as he segmen o undomina ed poin s ha we wan o become
as small as possible ( ecall ha he label is comple ely domina ed once his se is he
emp y se ). Hence, double bookkeeping o e comes he abo e disad an age(ii). How-
e e , because he s o ed in o ma ion is limi ed o only wo segmen s, no dominance
o e cen al pieces can be pe o med so ha disad an age(i) emains.
Possibili y(3) S o ing a a iable numbe o segmen s allows o exac ly desc ibe
he ini ial segmen 
S
as well as he se s o domina ed and undomina ed poin s o a
pa ial pa h esul ing om all possible ypes o pa ial dominance (PD1–PD6b), in
pa icula including dominance o e a cen al piece. Fo mally, i pa ial domina ion
has been pe o med wi h a subse
F
o labels
F1∈F
, hen he se o undomina ed
poin s is
and may consis o up o
|F|+1
segmen s. Al e na i ely, s o ing he complemen
S2
∩
⋃F1∈
FD(S
1)
, i.e., he se o domina ed poin s, may equi e ep esen ing
|F|
seg-
men s. I
S2
is gi en, domina ed poin s can be ep oduced om undomina ed poin s,
and ice e sa. We can o malize he se o undomina ed poin s o a pa ial pa h wi h
he help o a a iable numbe K o sub-segmen s
S1,u,…,SK,u
wi h
S
u=
⋃K
k=1
Sk,
u
.
Pa ial dominance can hen be ealized simila o possibili ies (1) and (2) by
g adually educing he se o undomina ed poin s
Su
. This equi es upda ing all
S
u
2=S2⧵
⋃
F1∈
F
D(S1
)

1078
S.Faldum e al.
1 3
sub-segmen s
S1,u
2
,…,S
K,u
2
acco dingly. In pa icula , in each upda e, some sub-seg-
men s may emain unchanged, some sub-segmen s may become emp y se s (and can
be elimina ed), some sub-segmen s may be educed (i domina ed om he le o
om he igh ), and some sub-segmen s may decompose in o wo new sub-segmen s
(i domina ed o e cen al pieces).
O e all, his ype o ep esen a ion o e comes bo h o he abo e disad an ages(i)
and(ii). The d awback is ha he numbe o sub-segmen s is a iable, which is mo e
complex o implemen . E en mo e, i equi es he alloca ion and dealloca ion o
memo y du ing he dominance algo i hm slowing down he compu a ional speed in
which he dominance algo i hm can be comple ed. No e ha he dominance is ypi-
cally he mos ime-c i ical pa o a labeling algo i hm.
We now commen on he wo possibili ies o ep esen a iable numbe s o seg-
men s o pa ial pa hs.
Possibili y(a) A i s ype o implemen a ion main ains he classical one- o-one
co espondence be ween pa ial pa hs and labels. All ini ial and in e media e in o -
ma ion abou a pa ial pa h, i s capabili y o domina e o he labels, and i s own s a e
o being pa ially domina ed a e s o ed wi hin a single label ( he o iginal label c e-
a ed a ini ializa ion) whose a ibu es a e upda ed whene e i is pa ially domi-
na ed by o he labels. In pa icula , in each label he segmen 
S
is ep esen ed and
main ained using he o iginal a ibu es
Fa
,Fb
,Fl
,
and
Fu
. Fu he mo e, he K sub-
segmen s
(
S
k,u
)
K
k=1
can be desc ibed wi h 4K addi ional alues
(
F
k,a
,F
k,b
,F
k,l
,F
k,u
)
K
k=1
(again 2K alues
(Fk,a
,
Fk,b)
su ice, since
Fk,l= (Fk,b)
and
Fk,u= (Fk,a)
and
is
known). A ini ializa ion, he assignmen s
K=1
and
S1,u=S
ha e o be made, i.e.,
F1,a=Fa,F1,b=Fb,F1,l=Fl
, and
F1,u=Fu
.
The main ad an age o possibili y (a) is ha all in o ma ion o a pa ial pa h
is s o ed only once (non- edundan , memo y e icien ). A disad an age is ha i
equi es a a iable-sized ep esen a ion o he sub-segmen s o ei he domina ed o
undomina ed poin s o he segmen 
S
. This may be ime-c i ical when labels hem-
sel es a e s o ed in dynamically alloca ed memo y and hei a iable-sized a ibu es
a e also s o ed in dynamically alloca ed memo y. Mo eo e , he pai wise compa i-
son is mo e in ica e om a implemen a ion poin o iew.
Possibili y(b) In con as , some wo ks men ion ha hey c ea e se e al labels pe
pa ial pa h when con enien o s o ing he in o ma ion abou pa ial domina ion o
in he p esence o mul iple ex ensions pe a c, e.g., when i ems can al e na i ely be
loaded in di e en compa men s o a ehicle (Che kesly and Gschwind 2022; Ae s-
Veens a e al. 2023). An al e na i e ype o implemen a ion could, o example, use
labels like wi h double bookkeeping in possibili y(2). Ins ead o es ic ing pa ial
dominance o PD1–PD4, pa ial dominance o e cen al pieces can be es ablished
by c ea ing a new copy
F′
2
o a label
F2
whene e wo sub-segmen s a e c ea ed
om one sub-segmen o undomina ed poin s. One sub-segmen is hen s o ed in
he o iginal label
F2
and he o he sub-segmen in he new copy
F′
2
. In gene al, wi h
his implemen a ion, a pa ial pa h wi h se o undomina ed poin s
S
u=
⋃K
k=1
Sk,
u
is
ep esen ed by K labels, one o each sub-segmen 
(
S
k,u
)
K
k=1
. In he spi i o double
1079
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
bookkeeping, each label main ains he ini ial segmen 
S
using he o iginal a ibu es
Fa
,Fb
,Fl
,
and
Fu
and i s co esponding sub-segmen
Sk,u
wi h he addi ional a ib-
u es
Fa
,Fb
,Fl
, and
Fu
.
3.3 Implemen a ion de ails o ou labeling algo i hm
Conce ning possibili ies(a) and (b) o ep esen a iable numbe s o segmen s in
pa ial dominance, we see no s ong poin in possibili y(b) excep o being a he
simple o code. In compa ison, possibili y(a) allows o keep all in o ma ion abou a
pa ial pa h wi hin a single label.
Rega ding he al e na i es (1)–(3) o main ain and u ilize dominance in o ma-
ion, he main ques ion is whe he o no pa ial dominance o e a cen al piece is
essen ial. To answe his ques ion, we ecommend o conduc p e es s o quan i y
how o en he pa ial dominance ypesPD5, PD6a, and PD6b occu compa ed o
pa ial dominance om he le and om he igh . On he basis o such p e es s (see
also Sec .4), we decided no o conside pa ial dominance o e a cen al piece in
ou BPC algo i hms. The addi ional compu a ional o e head o cope wi h a a iable
numbe o segmen s is high. In compa ison, he impac caused by addi ional domi-
nance was low, i.e., we did no see a s ong educ ion in he numbe o labels and
dominance es s when omi ing pa ial dominance o e a cen al piece.
I is clea ha double bookkeeping, i.e., possibili y(2), leads o a s onge domi-
nance compa ed o possibili y (1). The necessa y addi ion o he (o en in ege )
a ibu es
Fa
,Fb
,Fl
, and
Fu
o a label
F
is a he ha mless o a compu e imple-
men a ion; he main e ec is a sligh ly highe memo y consump ion and, as a conse-
quence, a possible highe numbe o cache misses.
The e is one mo e e inemen ela ed o double bookkeeping ha we would like
o discuss now. Recall ha he esou ces whose dependency is desc ibed by he seg-
men a e p oblem-speci ic. Independen om a speci ic p oblem, he segmen o a
gi en label
Fi
e e ing o a e ex i is ypically used o de ine he segmen o an
ex ension o a e exj ep esen ed by label
Fj
. REFs
Re ij
a e used o his pu pose
(see Sec .4 o examples), i.e.,
(
F
a
j
,F
b
j
,F
l
j
,F
u
j
)=Re ij(F
a
i
,F
b
i
,F
l
i
,F
u
i)
. This o e s he
oppo uni y o ini ialize he se o undomina ed poin s
Su
j
o a newly c ea ed label
Fj
based on in o ma ion abou pa ial dominance o i s p edecesso
Fi
. The ela ed
a ibu es a e compu ed wi h he same REFs as
The ad an age is ha labels
Fj
wi h a smalle se o undomina ed poin s
Su
j
can be
elimina ed soone , i.e., wi h less applica ions o pa ial dominance.
In summa y, we ha e chosen possibili y(2), i.e., double bookkeeping, oge he
wi h he e inemen ha undomina ed se s o poin s a e p opaga ed wi h REFs.
(
F
a
j
,F
b
j
,F
l
j
,F
u
j
)=Re ij(F
a
i
,F
b
i
,F
l
i
,F
u
i
)
.
1080
S.Faldum e al.
1 3
4 Two a ian s o  heVRPTW
In his sec ion, we p esen wo a ian s o he VRPTW wi h adeo esou ces and
discuss he applica ion as well as speci ic adap a ions o he heo y om Sec .3 o
hese a ian s. Fi s , we o mally de ine he VRPTW as he base p oblem o he
conside ed a ian s and in oduce he common no a ion, ollowed by a desc ip ion
o he wo a ian s, namely he EVRPTW and he SDVRPTW. Fo con enience, we
use he same no a ion, e.g., o index se s, o all a ian s e en hough hei de ini-
ion may be sligh ly di e en . The co ec meaning should be clea om he con-
ex . We hen desc ibe he use o pa ial dominance wi hin he labeling algo i hms o
sol e he p icing subp oblems o column-gene a ion app oaches o he EVRPTW
and he SDVRPTW.
The VRPTW can be de ined on a di ec ed g aph
G=(V,A)
. The e ex se
V=N∪{o,d}
comp ises he cus ome e ices
N
and wo copies
o
and
d
o he
depo . A a el ime
ij
and ou ing cos 
cij
a e associa ed wi h each a c
(i,j)∈A
. Bo h
a el imes and ou ing cos s a e assumed o sa is y he iangle inequali y. Fo each
e ex
i∈V
, a non-nega i e demand
qi
, a se ice du a ion
si
, and a ime window
[ei,li]
in which he se ice mus s a a e gi en. We assume
qo=qd=si=si=0
o
he depo copies
o
and
d
. A lee
K
o homogeneous ehicles each wi h a capaci y o
Q
is a ailable a he common depo o se e he cus ome s. The VRPTW is he p ob-
lem o inding a mos
|K|
ehicle ou es such ha he o al ou ing cos is minimized,
each cus ome is se ed by exac ly one ou e, and each ou e is easible, i.e., i is an
elemen a y
o
-
d
-pa h in
G
sa is ying he capaci y and ime-window cons ain s. Fo
u he de ails on he VRPTW and i s solu ion by BPC-based app oaches, we e e
o Cos a e al. (2019).
The EVRPTW is an ex ension o he VRPTW ha akes in o accoun he lim-
i ed d i ing ange o elec ic comme cial ehicles and he possibili y o echa g-
ing he ehicle’s ba e y en ou e a echa ging s a ions. We conside wo a i-
an s o he EVRPTW ha employ a so-called pa ial echa ging policy whe e
any amoun o ene gy can be echa ged when isi ing a echa ging s a ion. The
wo a ian s di e in he numbe o allowed echa ges pe ou e: a mos a single
(S) o mul iple (M) echa ges a e allowed. They a e e e ed o as EVRPTW-
S and EVRPTW-M, espec i ely, in he ollowing. To model hese EVRPTW
a ian s, he se
R
o echa ging s a ions can be added o he e ex se
V
, i.e.,
V=N∪{o,d}∪R
. Each ehicle in he homogeneous lee is equipped wi h an
elec ic ba e y o maximum capaci y
B
. Mo eo e , each a c
(i,j)∈A
is associ-
a ed wi h an ene gy consump ion
bij
. As desc ibed by Desaulnie s e al. (2016b),
we assume ha he ba e y capaci y and he ene gy consump ions a e gi en in
echa ging ime uni s so ha , e.g.,
B
equals he ime o ully echa ge a com-
ple ely emp y ba e y. In pa icula , he e is a one- o-one ela ionship be ween
he echa ging du a ion and he amoun o echa ged ene gy, i.e., echa ging o
Δ
uni s o ime inc eases he s a e o cha ge (SoC) by exac ly
Δ
uni s. A ou e
is easible in he EVRPTW, i i is easible o he unde lying VRPTW ( iming
cons ain s now include also echa ging imes) and he SoC is ne e nega i e o
1081
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
g ea e han he ba e y’s capaci y
B
. In addi ion, he numbe o echa ges pe
ou e mus comply wi h he echa ging policy (S o M). Also he EVRPTW has
he objec i e o minimizing he o al ou ing cos . A de ailed desc ip ion o he
conside ed EVRPTW a ian s and co esponding BPC algo i hms o hei solu-
ion can be ound in Desaulnie s e al. (2016b), Desaulnie s e al. (2020) and
Duman e al. (2021).
The SDVRPTW is a elaxa ion o he VRPTW in which cus ome s may be isi ed
mo e han once, i.e., he cus ome demands can be sa is ied h ough mul iple isi s by
di e en ehicles. This also allows inding easible solu ions o ins ances wi h cus ome
demands
qn>Q
. Con a y o he VRPTW, a ou e in he SDVRPTW is no only cha -
ac e ized by a sequence o cus ome s bu also by a co esponding deli e y pa e n
𝜌
which speci ies he quan i ies
d𝜌n
deli e ed o each cus ome 
n
isi ed on he ou e.
A ou e is capaci y- easible i he sum he quan i ies
d𝜌n
does no exceed he ehicle
capaci y
Q
. Each cus ome ’s demand mus be ul illed by he sum o ecei ed deli e y
quan i ies o all ou es. Again, he objec i e is he minimiza ion o he o al ou ing
cos .
Desaulnie s (2010) p oposed a BPC app oach o he SDVRPTW in which only
ou es wi h ex eme deli e y pa e n ha e o be explici ly conside ed. In an ex eme
deli e y pa e n, only one cus ome 
n
ecei es a spli deli e y, i.e.,
0<d𝜌n<qn
. All
o he cus ome s ecei e ei he a ze o deli e y (
d𝜌n=0
) o a ull deli e y (
d𝜌n=qi
).
Rou es wi h gene al deli e y pa e ns a e conside ed implici ly in he RMP by con ex
combina ions o ou es wi h ex eme deli e y pa e ns. Fo de ails we e e o Desaul-
nie s (2010), A che i e al. (2011).
4.1 Labeling wi hpa ial dominance o  heEVRPTW
We now show how pa ial dominance can be used in he labeling algo i hm
p oposed by Desaulnie s e al. (2016b) o sol e he elemen a y SPPRC p icing
p oblem o he EVRPTW. A e isi ing a echa ging s a ion, he e is a ade-
o be ween ime and SoC: he mo e ene gy o cha ge, he la e he ime, bu he
highe he SoC. Since he amoun o be echa ged, i.e., he echa ging du a ion,
depends on he pa o he pa ial pa h a e his echa ging s a ion, i can only
be de e mined a pos e io i. Consequen ly, he labels mus main ain he ele an
adeo segmen o easible imes, which implies di e en echa ging du a ions
and achie able SoCs. I no echa ging s a ion has been isi ed on he pa ial pa h,
he e is no adeo , i.e., he segmen educes o a single poin . Fo he sake o
b e i y, we only b ie ly discuss he esou ces and dominance ules used in he
o iginal algo i hm. We also limi he p esen a ion o he o wa d pa o he labe-
ling, since he backwa d labeling is simila . Fo mo e de ails on he o iginal labe-
ling algo i hm, see Desaulnie s e al. (2016b).
A pa ial pa h
p
s a ing a he o igin depo
o
and ending a e ex
i∈V
is
ep esen ed by a label
Fi
=(Fcos
i
,Fload
i
,(F
cus
n
i
)
n∈N
,F ch
i
,F Min
i
,F Max
i
,F Max
i)
. The
6+|N|
componen s o he label ha e he ollowing meaning:
Fcos
i
: he educed cos o pa h
p
;
1082
S.Faldum e al.
1 3
Fload
i
: he accumula ed cus ome demands along pa h
p
;
Fcus n
i
: o each
n∈N
, he numbe o imes cus ome  n has been isi ed along
pa h
p
;
F ch
i
: he numbe o echa ges pe o med along pa h
p
;
F Min
i
: he ea lies se ice s a ime a e exi assuming ha , i a echa ging s a-
ion is isi ed p io oi along
p
, a minimum echa ge ha ensu es ba e y
easibili y up oi has been pe o med;
F Max
i
: he ea lies se ice s a ime a e ex i assuming ha , i a echa ging s a-
ion is isi ed p io o i along
p
, a maximum echa ge espec ing ime-win-
dow easibili y up oi has been pe o med;
F Max
i
: wi h he a i icial assump ion ha echa ging is possible a all e i-
ces,
F Max
deno es he maximum possible echa ging du a ion a e exi
assuming ha , i a echa ging s a ion is isi ed p io oi along
p
, a mini-
mum echa ge ha ensu es ba e y easibili y up o i has been pe o med.
No e ha his assump ion is used only o p opaga e he in o ma ion along
he pa h, bu a eal echa ge ne e occu s a a cus ome .
To simpli y he no a ion, we omi he index
i
o he esiding e ex so ha we
w i e, e.g.,
Fcos
ins ead o
Fcos
i
.
Ins ead o modeling he SoC di ec ly, Desaulnie s e al. implici ly ep esen ed
i by he maximum easible addi ional echa ging du a ion
F Max
(= maximum
easible amoun o ene gy o be echa ged) wi h espec o he ea lies se ice
s a ime
F Min
a he cu en e ex. Wi h his ep esen a ion, o bo h adeo
esou ces ime and maximum possible echa ging du a ion, smalle alues a e
p e e able. The e o e, he heo y o Sec .3 is immedia ely applicable o ealize
pa ial dominance. Mo eo e , by he abo e de ini ion o he ba e y ela ed da a
(capaci y, consump ion, and echa ging a e), he nega i e slope o all adeo
unc ions is
m=1
, which simpli ies he ep esen a ion and dominance condi ions.
As a esul ,
so ha only he h ee a ibu es
F Min
,
F Max
,
F Max
a e needed o desc ibe he ade-
o and he co esponding segmen . The classical dominance ule o Desaulnie s
e al. (2016b) o pai wise dominance is as ollows. Le
F1
and
F2
be wo labels ep-
esen ing pa ial pa hs ending a he same e ex
i
. Label
F1
domina es
F2
, i
Fa
=F
Min
,
F
b=F Max
,
Fl=F Max −(F Max −F Min)
,
F
u
=F
Max
,

1083
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
In he EVRPTW-S,
F ch
1
≤F
ch
2
is addi ionally equi ed. Since segmen s ha e iden-
ical slope wi h
m1=m2=1
, condi ions (DC1)–(DC3) imply condi ion (DC4).
Al e na i ely, one could equi e condi ions(DC1), (DC2), and(DC4), which imply
condi ion(DC3).
Ha ing iden ical slopes also simpli ies pa ial dominance be ween wo ade-
o segmen s. Fi s , he wo segmen s can ne e ha e a p ope in e sec ion (see
Sec .3.1.2) meaning ha only PD1 and PD3 a e ele an ( ecall ha we do no
employ pa ial dominance o e a cen al piece). Second, also he iden i ica ion o
hem is simpli ied. Fo PD1, condi ions(DC1) and(DC3) a e ul illed (implying
(DC4)), while condi ion(DC2) is iola ed. Fo PD3, condi ions(DC2) and(DC3)
a e ul illed (implying (DC4)), while condi ion(DC1) is iola ed. Fu he mo e,
he de e mina ion o he undomina ed poin s is simpli ied (see Table 2), since
he adeo unc ion and i s in e se a e iden ical wi h (nega i e) slopes gi en by
m=1
.
Finally, o ime windows and a el imes de ined by in ege alues, all ba e y
ela ed da a can also be assumed o be in ege . Thus, he easible domains o he
adeo esou ces ime and SoC can be educed o in ege s, and ounding can be
applied o he segmen s in pa ial dominance as desc ibed in Sec .3.1.2. The in e-
ge assump ion is sa is ied o he s anda d benchma k ins ances o he EVRPTW
used in he compu a ional expe imen s p esen ed in Sec .5.
4.2 Labeling wi hpa ial dominance o  heSDVRPTW
In he ollowing, we de ail he applica ion o pa ial dominance o he labeling algo-
i hm o Desaulnie s (2010) o p icing ou es and associa ed ex eme deli e y pa -
e ns o he SDVRPTW. He e, he p icing subp oblem is an elemen a y SPPRC com-
bined wi h he linea elaxa ion o a bounded knapsack p oblem. Since he e is a dual
p ice o each uni o be deli e ed o a cus ome , he e is a adeo be ween he wo
esou ces ehicle load and educed cos : The ques ion o how much o deli e o he
(unique) cus ome ecei ing a spli deli e y is, in u n, he ques ion o how much o
ea n om each uni deli e ed. Simila o he echa ging du a ion in he EVRPTW,
he quan i y o be deli e ed is no known when isi ing he spli cus ome . The e o e,
he label ep esen s his adeo wi h a segmen indica ing he possible ehicle load
(implying he deli e y quan i y o he spli cus ome ) and he achie able educed cos .
I no spli deli e y has been made along a pa ial pa h, he e is no adeo , esul ing in
a single-poin segmen .
Fo b e i y, we only p esen he a ibu es o a label and he dominance ules o
he o iginal algo i hm only o he case o o wa d labeling (backwa d labeling is
F
cos
1≤F
cos
2,
Fload
1≤Fload
2,
Fcus n
1≤Fcus n
2∀n∈N
,
and (DC
1
)
–
(DC
3
)
.
1084
S.Faldum e al.
1 3
symme ic wi h espec o he adeo ). A pa ial pa h
p
om sou ce
o
o a e ex
i∈V
is ep esen ed by a label
Fi
=(Fcos
i
,F ime
i
,Fload
i
,(F
cus
n
i
)
n∈N
,F
spli
i
,FsMax
i
,Fs𝜋
i)
wi h
6+|N|
componen s de ined as ollows:
Fcos
i
: he educed cos o pa h
p
wi hou he cos o a po en ial spli deli e y;
F ime
i
: he ea lies se ice s a ime a e ex
i
;
Fload
i
: he accumula ed cus ome demands o ull deli e ies along pa h
p
;
Fcus n
i
: o each
n∈N
, he numbe o imes cus ome n has been isi ed along pa h
p
;
Fspli
i
: bina y indica o whe he o no a spli deli e y has occu ed on pa h
p
;
FsMax
i
: he maximum quan i y ha can be deli e ed o he spli deli e y cus ome
on pa h
p
;
Fs𝜋
i
: dual p ice pe uni deli e ed o he spli deli e y cus ome on pa h
p
.
Smalle alues a e p e e able o bo h adeo esou ces load and educed cos . As
a esul , he heo y o Sec .3 is also applicable he e, and he segmen desc ibing he
adeo in he SDVRPTW is de ined by
which a e gi en by he ou componen s
Fload
,
Fcos
,
FsMax
, and
Fs𝜋
whe e he la -
e desc ibes he nega i e slope
m
. Howe e , unlike o he EVRPTW, he nega i e
slopes gi en by
m=Fs𝜋
a e gene ally di e en o di e en labels so ha a p ope
in e sec ion is possible. Consequen ly, no di ec simpli ica ions can be made.
The classical ule o Desaulnie s (2010) o pai wise dominance is as ollows: Le
F1
and
F2
be wo labels ep esen ing pa ial pa hs ending a he same e ex
i
, hen
label
F1
domina es
F2
, i
Fa
=F
load
,
F
b=Fload +FsMax
,
Fl=Fcos −FsMaxFs𝜋
,
F
u
=F
cos
,
F
ime
1≤F
ime
2,
Fspli
1≤Fspli
2,
Fcus n
1≤Fcus n
2∀n∈N
,
and (DC1)–(DC4).
1085
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
Fo pa ial dominance be ween labels, all ypes PD1–PD6b a e ele an . Finally, i is
known ha , o each SDVRPTW ins ance, he e exis s an op imal solu ion in which
all deli e y quan i ies a e in ege , unde he p econdi ion ha all demand alues and
he ehicle capaci y a e in ege (A che i e al. 2006). The in ege assump ion is sa -
is ied o he s anda d benchma k ins ances used in Sec .5, so ha ounding is appli-
cable as desc ibed in Sec .3.1.2.
5 Compu a ional esul s
In his sec ion, we epo an ex ensi e compu a ional s udy o pa ial dominance
wi hin he BPC algo i hms o he EVRPTW and he SDVRPTW. The wo BPC
algo i hms we e implemen ed in C++ and compiled in o 64-bi single- h ead code
wi h MS Visual S udio 2019. CPLEX 20.10 wi h de aul pa ame e s (excep o he
ime limi and allowing only a single h ead) was used o eop imize he RMPs. All
compu a ions we e pe o med on he high pe o mance compu ing clus e Elwe-
i sch o he RPTU Kaise slau e n-Landau, consis ing o se e al In el Xeon Gold
6126 p ocesso s unning a 2.60GHz. No e ha he pe o mance o a single h ead
on he clus e is compa able o ha o a s anda d desk op p ocesso .
5.1 BPC algo i hms
The BPC algo i hms o he EVRPTW and he SDVRPTW sha e he same code
basis, which is adap ed o each o he p oblem a ian s. The base code uses se e al
accele a ion echniques ha a e well es ablished in he li e a u e. Fo he EVRPTW,
he compu a ional se up o he BPC algo i hm is comple ely iden ical o ha used in
Desaulnie s e al. (2020). Fo he SDVRPTW, a modi ied se up seems mo e a o a-
ble. Bo h compu a ional se ups a e summa ized below.
P icing To speed up he p icing, we apply bidi ec ional labeling wi h a dynamic
hal -way poin using he ime as he mono one esou ce (Tilk e  al. 2017), i.e.,
F Min
o he EVRPTW and
F ime
o he SDVRPTW. Fu he mo e, ins ead o sol -
ing he s ongly
NP
-ha d elemen a y e sions o he SPPRCs, we ely on he well-
known ng-pa h elaxa ions o hem (Baldacci e al. 2011). In ou implemen a ion,
he neighbo hood sizes a e se o 14 (EVRPTW) and 4 (SDVRPTW). In addi ion,
we use he concep o un eachable cus ome s who canno be eached due o hei
esou ce le els (Feille e al. 2004). We use p icing heu is ics based on amilies o
a c- educed ne wo ks as p oposed by Desaulnie s e al. (2008), whe e he ne wo ks
ha e a limi ed numbe o incoming and ou going a cs o each cus ome e ex. The
numbe o a cs chosen in ou implemen a ion a e 2, 5, 10, 15 (EVRPTW) and 3, 10
(SDVRPTW). Fo he SDVRPTW, we addi ionally conside ano he heu is ic p ic-
ing s a egy ha only allows ull deli e ies and ze o deli e ies o cus ome s, i.e.,
spli deli e ies a e dis ega ded, esul ing in an SPPRC wi hou adeo s. The la e
s a egy is combined wi h he a c- educed ne wo ks. Finally, ou labeling algo i hms
a e based on a bucke -based implemen a ion using a one-dimensional bucke ing on
he ime esou ce (Sadyko e al. 2021).
1086
S.Faldum e al.
1 3
Valid Inequali ies To s eng hen he linea elaxa ion o he mas e p og am,
ounded capaci y inequali ies (RCIs, Nadde 2002) and subse - ow inequali ies
(SRIs, Jepsen e al. 2008) a e added as wo amilies o alid inequali ies. Viola ed
inequali ies a e sepa a ed only a he oo node (le el ze o) o he EVRPTW and
up o le el one o he sea ch ee o he SDVRPTW. Fo he SDVRPTW, addi ional
inequali ies ha uppe bound he low by one on e e y pai o an i-pa allel cus ome
a cs a e also dynamically added (see Desaulnie s 2010,Co olla y 2, Eq.(7), and
Sec .5.2.2). The sepa a ion p ocedu es add inequali ies o he RMP only i hey a e
iola ed by a leas 0.05.
RCIs a e obus cu s because hei dual p ices can be inco po a ed by modi y-
ing he educed cos o he associa ed a cs; hey do no change he s uc u e o he
p icing p oblem. Fo he SDVRPTW, RCIs a e c i ical o he o e all pe o mance
o ou BPC algo i hm and a e, he e o e, ex ensi ely sepa a ed using he ex ended
and g eedy sh inking heu is ics o Ralphs e al. (2003), he ou e-based algo i hm
o A che i e al. (2011) o he SDVRPTW, and using an exac mixed-in ege p o-
g amming (MIP) o mula ion ollowing he ideas o Ma inelli e al. (2013). The
ou e-based algo i hm is in oked only when he sh inking heu is ics ail o ind a
iola ed RCI. Simila ly, he MIP is only used i he ou e-based algo i hm also ails
o iden i y a iola ed RCI. To a oid p ohibi i ely long compu a ion imes, CPLEX is
gi en a ha d ime limi o 10s o sol ing he MIP. Fo he EVRPTW, RCIs a e less
impo an and only he sh inking heu is ics a e used.
SRIs a e non- obus cu s so ha , o each ac i e SRI, an addi ional esou ce needs
o be added in he labeling algo i hms making he p icing p oblem mo e di icul
o sol e. The e o e, we use he limi ed memo y a ian o he SRIs as p oposed by
Pecin e al. (2017a). Fu he mo e, as done in mos wo ks, we limi ou sel es o SRIs
wi h ow se s o size h ee. Ou implemen a ion uses he same sepa a ion algo i hm
and e ex memo y as p esen ed by Pecin e al. (2017b).
B anching B anching is necessa y o inally ensu e in ege solu ions. Fo he
EVRPTW, we use he hie a chical b anching scheme o Desaulnie s e al. (2016b),
i.e., we b anch on (i) he o al numbe o ou es, (ii) he o al numbe o echa ges,
(iii) he o al numbe o echa ges a a echa ging s a ion, and (i ) he o al low on
an a c.
Fo he SDVRPTW, we use he scheme o Desaulnie s (2010), i.e., we b anch on
(i) he o al numbe o ou es, (ii) he o al numbe o isi s o a cus ome , (iii) he
o al low on an a c, and (i )whe he wo a cs a e used in succession.
On all le els, we selec a b anching a iable wi h ac ional alue closes o0.5.
The sea ch ee is explo ed using a bes -bound i s node selec ion s a egy.
Fo he SDVRPTW, we addi ionally apply s ong b anching as ollows. In each
node o he sea ch ee, a se o b anching candida es is selec ed by conside ing a
gi en numbe o b anching a iables wi h he la ges ac ional alues. Fo each can-
dida e, a ough e alua ion o bo h child nodes is pe o med by sol ing he RMP wi h
he co esponding b anching cons ain wi hou any column gene a ion. The mos
p omising candida e is selec ed acco ding o he p oduc ule p oposed by Ach e -
be g (2007). A he oo node, he maximum size o he candida e se is 15, and he
size o he candida e se dec eases by wo o each le el o he sea ch ee. How-
e e , he minimum size o he candida e se is i e. No e ha his implemen a ion o
1093
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
applica ion o pa ial dominance has been exempli ied o wo a ian s o he EVRPTW
wi h a pa ial echa ge policy and he SDVRPTW, wo impo an a ian s o VRP.
Compu a ional esul s on s anda d benchma k ins ances o he conside ed p oblems
ha e e ealed he ollowing main insigh s. On a pe p icing p oblem basis, i.e., on uly
iden ical ins ances o SPPRCs, we ha e ound ha he labeling algo i hms applying pa -
ial dominance ne e pe o med wo se han hei coun e pa s wi h classical pai wise
dominance. Fu he mo e, pa ial dominance has p o ed mo e bene icial o he p icing
p oblems o he mo e di icul EVRPTW and SDVRPTW ins ances. I has also p o ed
mo e bene icial o he EP ins ances a he han o heu is ic p icing i e a ions on educed
ne wo ks. O e all, o he SDVRPTW, a e age speedups o up o 40% (EPs o he mo e
di icul ins ances) could be ealized by using pa ial dominance. Fo he wo EVRPTW
a ian s, sa ings we e much smalle . This beha io can be explained by he ac ha much
less labels ac ually show a adeo in he EVRPTW a ian s (33% and 46%) compa ed o
62% in he SDVRPTW. Such a s aigh o wa d analysis can, hus, help o a p io i es ima e
a po en ial gain om implemen ing pa ial dominance. We lea e i o u u e esea ch o
conduc ela ed expe imen s o o he p oblems wi h a linea adeo and a single seg-
men , such as he dial-a- ide p oblem wi h ide- ime cons ain s, he synch onized pickup
and deli e y p oblem, he uck-and- aile VRP wi h quan i y-dependen ans e imes,
and he VRP wi h pa ial ou sou cing (see Sec .2). In addi ion, he conside a ion o non-
linea adeo s may be he nex s ep in gene alizing pa ial dominance. The la e is el-
e an , e.g., o mo e ealis ic cha ging unc ions o ba e y elec ic ehicles.
Finally, we ha e ound ha he esul s o he indi idual p icing ins ances do
ansla e also o an imp o emen o an o e all BPC, which employs many well-
es ablished accele a ion echniques and whose pe o mance is in luenced also by
many o he e ec s ha a e no immedia ely ela ed o he solu ion o he p icing
p oblems. Again, hese bene i s a e subs an ial o he SDVRPTW while hey
a e a he mino o he EVRPTW. Fu u e esea ch could conside non-linea
adeo s and mo e han one segmen , o which he ca ego iza ion as well as he
compu e implemen a ion become much mo e complica ed.
Table 4 Da a o Fig.5a o he EVRPTW-S
All p icing p oblems (AP) Exac p icing p oblems (EP)
Comp Labels Dominance Time Labels Dominance Time
ime
≥
#Ins ances AP-L AP-D AP-T EP-L EP-D EP-T
0 168 0.9957 0.9948 0.9739 0.9880 0.9704 0.9875
1 148 0.9955 0.9944 0.9751 0.9870 0.9672 0.9859
10 98 0.9954 0.9938 0.9786 0.9852 0.9564 0.9819
60 64 0.9956 0.9938 0.9795 0.9830 0.9456 0.9729
100 55 0.9960 0.9939 0.9802 0.9835 0.9432 0.9701
600 29 0.9961 0.9934 0.9753 0.9812 0.9319 0.9501
1200 25 0.9969 0.9937 0.9728 0.9835 0.9274 0.9525
1800 22 0.9970 0.9937 0.9699 0.9824 0.9226 0.9393
3600 19 0.9972 0.9940 0.9710 0.9839 0.9265 0.9413

1094
S.Faldum e al.
1 3
Appendix
In Tables4, 5, and 6, we p o ide he unde lying alues o Fig.5. Fo he solu ions
o he oo node, we dis inguish wo cases: we agg ega e o e all p icing p ob-
lems (AP) sol ed o only he exac p icing p oblems (EP) de ined o e he ull
ne wo k. The ables display he geome ic mean o a ios o he numbe o c ea ed
labels (-L), he numbe o dominance es s (-D), and he solu ion ime (-T) in sec-
onds. In addi ion, we il e esul s acco ding o di e en o al compu a ion imes
in seconds. The column #Ins ances gi es he co esponding numbe o ins ances.
Table 4 p o ides he alues o he EVRPTW-S, Table5 o he EVRPTW-M,
and Table6 o he SDVRPTW.
Acknowledgemen s This esea ch was suppo ed by he Deu sche Fo schungsgemeinscha (DFG) unde
G an s GS83/1-1 and IR122/10-1 o P ojec 418727865. This suppo is g a e ully acknowledged.
Table 5 Da a o Fig.5b o he EVRPTW-M
All p icing p oblems (AP) Exac p icing p oblems (EP)
Comp Labels Dominance Time Labels Dominance Time
ime
≥
#Ins ances AP-L AP-D AP-T EP-L EP-D EP-T
0 168 0.9943 0.9926 0.9671 0.9860 0.9574 0.9603
1 156 0.9942 0.9923 0.9683 0.9853 0.9545 0.9583
10 113 0.9938 0.9915 0.9710 0.9830 0.9427 0.9470
60 71 0.9939 0.9908 0.9708 0.9795 0.9250 0.9331
100 65 0.9941 0.9907 0.9714 0.9797 0.9227 0.9310
600 43 0.9950 0.9907 0.9682 0.9811 0.9141 0.9181
1200 31 0.9952 0.9907 0.9639 0.9802 0.9078 0.9015
1800 28 0.9957 0.9908 0.9617 0.9827 0.9059 0.9019
3600 24 0.9956 0.9909 0.9604 0.9818 0.9039 0.9037
Table 6 Da a o Fig.5c o he SDVRPTW
All p icing p oblems (AP) Exac p icing p oblems (EP)
Comp Labels Dominance Time Labels Dominance Time
ime
≥
#Ins ances AP-L AP-D AP-T EP-L EP-D EP-T
0 504 0.8302 0.6793 0.8059 0.7817 0.6250 0.7093
1 362 0.8245 0.6587 0.7882 0.7709 0.5974 0.6795
10 207 0.8080 0.6217 0.7555 0.7519 0.5567 0.6350
60 122 0.7945 0.5953 0.7297 0.7404 0.5334 0.6077
100 97 0.7886 0.5835 0.7190 0.7318 0.5208 0.5957
600 49 0.7706 0.5536 0.6898 0.7302 0.5154 0.5897
1200 34 0.7678 0.5506 0.6857 0.7339 0.5240 0.5979
1800 29 0.7628 0.5444 0.6807 0.7374 0.5284 0.6026
3600 21 0.7445 0.5191 0.6578 0.7293 0.5175 0.5938
1095
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
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
Ach e be g T (2007) Cons ain in ege p og amming. Ph.D. hesis, Technische Uni e si ä Be lin,
Fakul ä II—Ma hema ik und Na u wissenscha en, Be lin, Ge many
Ae s-Veens a M, Che kesly M, Gschwind T (2023) A uni ied b anch-p ice-and-cu algo i hm o mul i-
compa men pickup and deli e y p oblems. Les Cahie s du GERAD G-2023-26, G oupe d’é udes
e de eche che en analyse des décisions, GERAD, Mon éal QC H3T 2A7, Canada
A che i C, Spe anza MG, He z A (2006) A abu sea ch algo i hm o he spli deli e y ehicle ou ing
p oblem. T ansp Sci 40(1):64–73
A che i C, Boucha d M, Desaulnie s G (2011) Enhanced b anch and p ice and cu o ehicle ou ing
wi h spli deli e ies and ime windows. T ansp Sci 45(3):285–298
Baldacci R, Mingozzi A, Robe i R (2011) New ou e elaxa ion and p icing s a egies o he ehicle
ou ing p oblem. Ope Res 59(5):1269–1283
Balle AC, Dabia S, Dullae WEH, Vigo D (2020) The ehicle ou ing p oblem wi h pa ial ou sou cing.
T ansp Sci 54(4):1034–1052
Ba nha C, Johnson E, Nemhause G, Sa elsbe gh M, Vance P (1998) B anch-and-p ice: column gene a-
ion o sol ing huge in ege p og ams. Ope Res 46(3):316–329
Bianchessi N, I nich S (2019) B anch-and-cu o he spli deli e y ehicle ou ing p oblem wi h ime
windows. T ansp Sci 53(2):442–462
Bode C, I nich S (2014) The sho es -pa h p oblem wi h esou ce cons ain s wi h
(k,2)
-loop elimina ion
and i s applica ion o he capaci a ed a c- ou ing p oblem. Eu J Ope Res 238(2):415–426
Bulhões T, Sadyko R, Uchoa E (2018) A b anch-and-p ice algo i hm o he minimum la ency p oblem.
Compu Ope Res 93:66–78
Che kesly M, Gschwind T (2022) The pickup and deli e y p oblem wi h ime windows, mul iple s acks,
and handling ope a ions. Eu J Ope Res 301(2):647–666
Cos a L, Con a do C, Desaulnie s G (2019) Exac b anch-p ice-and-cu algo i hms o ehicle ou ing.
T ansp Sci 53(4):946–985
Cos a L, Con a do C, Desaulnie s G, Pecin D (2021) Selec i e a c-ng p icing o ehicle ou ing. In
T ans Ope Res 28(5):2633–2690
Desaulnie s G (2010) B anch-and-p ice-and-cu o he spli -deli e y ehicle ou ing p oblem wi h ime
windows. Ope Res 58(1):179–192
Desaulnie s G, Villeneu e D (2000) The sho es pa h p oblem wi h ime windows and linea wai ing
cos s. T ansp Sci 34(3):312–319
Desaulnie s G, Des osie s J, Loachim I, Solomon MM, Soumis F, Villeneu e D (1998) A uni ied ame-
wo k o de e minis ic ime cons ained ehicle ou ing and c ew scheduling p oblems. In: C ainic
TG, Lapo e G (eds) Flee managemen and logis ics. Sp inge , Cham, pp 57–93
Desaulnie s G, Des osie s J, Solomon M (eds) (2005) Column gene a ion. Sp inge , New Yo k
Desaulnie s G, Lessa d F, Hadja A (2008) Tabu sea ch, pa ial elemen a i y, and gene alized
k
-pa h ine-
quali ies o he ehicle ou ing p oblem wi h ime windows. T ansp Sci 42(3):387–404
Desaulnie s G, Rakke JG, Coelho LC (2016) A b anch-p ice-and-cu algo i hm o he in en o y- ou ing
p oblem. T ansp Sci 50(3):1060–1076
Desaulnie s G, E ico F, I nich S, Schneide M (2016) Exac algo i hms o elec ic ehicle- ou ing p ob-
lems wi h ime windows. Ope Res 64(6):1388–1405
1096
S.Faldum e al.
1 3
Desaulnie s G, Pecin D, Con a do C (2019) Selec i e p icing in b anch-p ice-and-cu algo i hms o ehi-
cle ou ing. EURO J T ansp Logis 8:147–168
Desaulnie s G, Gschwind T, I nich S (2020) Va iable ixing o wo-a c sequences in b anch-p ice-and-
cu algo i hms on pa h-based models. T ansp Sci 54(5):1170–1188
Dolan ED, Mo é JJ (2002) Benchma king op imiza ion so wa e wi h pe o mance p o iles. Ma h P o-
g am 91(2):201–213
Duman EN, Taş D, Ça ay B (2021) B anch-and-p ice-and-cu me hods o he elec ic ehicle ou ing
p oblem wi h ime windows. In J P od Res 60(17):5332–5353
Feille D, Dejax P, Gend eau M, Guéguen C (2004) An exac algo i hm o he elemen a y sho es
pa h p oblem wi h esou ce cons ain s: applica ion o some ehicle ou ing p oblems. Ne wo ks
44(3):216–229
Gschwind T (2015) A compa ison o column-gene a ion app oaches o he synch onized pickup and
deli e y p oblem. Eu J Ope Res 247(1):60–71
Gschwind T, I nich S (2015) E ec i e handling o dynamic ime windows and i s applica ion o sol ing
he dial-a- ide p oblem. T ansp Sci 49(2):335–354
He Q, I nich S, Song Y (2019) B anch-and-cu -and-p ice o he ehicle ou ing p oblem wi h ime win-
dows and con ex node cos s. T ansp Sci 53(5):1409–1426
Heßle K, I nich S (2023) Pa ial dominance in b anch-p ice-and-cu o he basic mul i-compa men
ehicle ou ing p oblem. INFORMS J Compu 35(1):50–65
Houck D, Pica d J, Quey anne M, Vemugan i R (1980) The a elling salesman p oblem as a cons ained
sho es pa h p oblem: heo y and compu a ional expe ience. Opsea ch 17:93–109
Ioachim I, Gélinas S, Des osie s J, Soumis F (1998) A dynamic p og amming algo i hm o he sho es
pa h p oblem wi h ime windows and linea node cos s. Ne wo ks 31:193–204
Ioachim I, Des osie s J, Soumis F, Bélange N (1999) Flee assignmen and ou ing wi h schedule syn-
ch oniza ion cons ain s. Eu J Ope Res 119(1):75–90
I nich S (2008) Resou ce ex ension unc ions: p ope ies, in e sion, and gene aliza ion o segmen s. OR
Spec um 30(1):113–148
I nich S, Desaulnie s G (2005) Sho es pa h p oblems wi h esou ce cons ain s. In: Desaulnie s G,
Des osie s J, Solomon M (eds) Column gene a ion. Sp inge , New Yo k, pp 33–65
I nich S, Villeneu e D (2006) The sho es pa h p oblem wi h esou ce cons ain s and
k
-cycle elimina-
ion o
k≥3
. INFORMS J Compu 18(3):391–406
Jepsen M, Pe e sen B, Spoo endonk S, Pisinge D (2008) Subse - ow inequali ies applied o he ehicle-
ou ing p oblem wi h ime windows. Ope Res 56(2):497–511
Kohl N, Des osie s J, Madsen O, Solomon M, Soumis F (1999)
2
-pa h cu s o he ehicle ou ing p ob-
lem wi h ime windows. T ansp Sci 33(1):101–116
Le a-Rome o G, Mi anda B on JJ, Soulignac FJ (2020) Linea edge cos s and labeling algo i hms: he
case o he ime-dependen ehicle ou ing p oblem wi h ime windows. Ne wo ks 76(1):24–53
Libe a o e F, Righini G, Salani M (2010) A column gene a ion algo i hm o he ehicle ou ing p oblem
wi h so ime windows. 4OR 9(1):49–82
Luo Z, Qin H, Zhu W, Lim A (2017) B anch and p ice and cu o he spli -deli e y ehicle ou ing p ob-
lem wi h ime windows and linea weigh - ela ed cos . T ansp Sci 51(2):668–687
Lübbecke M, Des osie s J (2005) Selec ed opics in column gene a ion. Ope Res 53(6):1007–1023
Ma inelli R, Poggi M, Sub amanian A (2013) Imp o ed bounds o la ge scale capaci a ed a c ou ing
p oblem. Compu Ope Res 40(8):2145–2160
Nadde D (2002) Polyhed al heo y. In: Gu in G, Punnen A (eds) The a eling salesman p oblem and i s
a ia ions, olume12 o combina o ial op imiza ion, chap e 2. Kluwe , Do d ech , pp 29–116
Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Imp o ed b anch-cu -and-p ice o capaci a ed ehicle
ou ing. Ma h P og am Compu 9(1):61–100
Pecin D, Con a do C, Desaulnie s G, Uchoa E (2017) New enhancemen s o he exac solu ion o he
ehicle ou ing p oblem wi h ime windows. INFORMS J Compu 29(3):489–502
Ralphs T, Kopman L, Pulleyblank W, T o e L (2003) On he capaci a ed ehicle ou ing p oblem. Ma h
P og am 94(2–3):343–359
Ro henbäche A-K, D exl M, I nich S (2018) B anch-and-p ice-and-cu o he uck-and- aile ou ing
p oblem wi h ime windows. T ansp Sci 52(5):1174–1190
Sadyko R, Uchoa E, Pessoa A (2021) A bucke g aph–based labeling algo i hm wi h applica ion o ehi-
cle ou ing. T ansp Sci 55(1):4–28
Schneide M, S enge A, Goeke D (2014) The elec ic ehicle- ou ing p oblem wi h ime windows and
echa ging s a ions. T ansp Sci 48(4):500–520
1097
1 3
Pa ial dominance inb anch‑p ice‑and‑cu algo i hms o …
Solomon MM (1987) Algo i hms o he ehicle ou ing and scheduling p oblems wi h ime window con-
s ain s. Ope Res 35(2):254–265
Splie R, Gabo AF (2015) The ime window assignmen ehicle ou ing p oblem. T ansp Sci
49(4):721–731
Splie R, Dabia S, Van Woensel T (2018) The ime window assignmen ehicle ou ing p oblem wi h
ime-dependen a el imes. T ansp Sci 52(2):261–276
Tilk C, Ro henbäche A-K, Gschwind T, I nich S (2017) Asymme y ma e s: dynamic hal -way poin s in
bidi ec ional labeling o sol ing sho es pa h p oblems wi h esou ce cons ain s as e . Eu J Ope
Res 261(2):530–539
Tilk C, Bianchessi N, D exl M, I nich S, Meisel F (2018) B anch-and-p ice-and-cu o he ac i e-passi e
ehicle- ou ing p oblem. T ansp Sci 52(2):300–319
To h P, Vigo D (eds) (2014) Vehicle ou ing: p oblems, me hods, and applica ions. MOS-SIAM Se ies on
Op imiza ion. Socie y o Indus ial and Applied Ma hema ics, Philadelphia
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.
Au ho s and A ilia ions
S e anFaldum1 · Sa ahMacha e2· TimoGschwind2 · S e anI nich1
* Timo Gschwind
[email p o ec ed]
S e an Faldum
s [email p o ec ed]
Sa ah Macha e
[email p o ec ed]
S e an I nich
i nic[email p o ec ed]
1 Chai o Logis ics Managemen , Gu enbe g School o Managemen andEconomics, Johannes
Gu enbe g Uni e si y Mainz, Jakob-Welde -Weg 9, 55128Mainz, Ge many
2 Chai o Logis ics, School o Business andEconomics, RPTU Kaise lau e n-Landau,
Go lieb-Daimle -S aße 42, 67663Kaise lau e n, Ge many