Minimizing delays of patient transports with incomplete information: A modeling approach based on the vehicle routing problem

Adelhü e, Dennis; B aun, K is in; Lie s, F auke; Tschuppik, Sebas ian
A icle — Published Ve sion
Minimizing delays o pa ien anspo s wi h incomple e
in o ma ion: A modeling app oach based on he ehicle
ou ing p oblem
OR Spec um
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Adelhü e, Dennis; B aun, K is in; Lie s, F auke; Tschuppik, Sebas ian (2024) :
Minimizing delays o pa ien anspo s wi h incomple e in o ma ion: A modeling app oach based
on he ehicle ou ing p oblem, OR Spec um, ISSN 1436-6304, Sp inge , Be lin, Heidelbe g, Vol. 47,
Iss. 2, pp. 565-604,
h ps://doi.o g/10.1007/s00291-024-00788-6
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323265
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Vol.:(0123456789)
OR Spec um (2025) 47:565–604
h ps://doi.o g/10.1007/s00291-024-00788-6
ORIGINAL ARTICLE
Minimizing delays o pa ien anspo s wi hincomple e
in o ma ion: Amodeling app oach based on he ehicle
ou ing p oblem
DennisAdelhü e1· K is inB aun1,2 · F aukeLie s1· Sebas ianTschuppik1
Recei ed: 8 Sep embe 2023 / Accep ed: 22 Augus 2024 / Published online: 10 Sep embe 2024
© The Au ho (s) 2024
Abs ac
We in es iga e a challenging ask in ambula o y ca e, he minimizing o delays o
pa ien anspo s. In p ac ice, a limi ed numbe o ehicles is a ailable o non- es-
cue anspo s. Fu he mo e, he dispa che a ely has access o comple e in o ma-
ion when es ablishing a anspo plan o dispa ching he ehicles. I addi ional
anspo is eques ed on demand hen schedules need o be upda ed, which can lead
o long delays. We model he scheduling o pa ien anspo s as a ehicle ou ing
p oblem wi h gene al ime windows and sol e i as a mixed-in ege linea p oblem
ha is modi ied whene e addi ional anspo in o ma ion becomes a ailable. We
p opose a modeling app oach ha is designed o de e mine ai and s able plans.
Fu he mo e, we show ha he model can easily be modi ied when anspo s need
o sa is y addi ional equi emen s, e.g., du ing pandemics, exempla ily he Co id-19
pandemic. To show he applicabili y and e iciency o ou modeling app oach, we
conduc a nume ical s udy using his o ical da a om he egion o Middle F anco-
nia. The esul s e eal and show ha , by applying ma hema ical op imiza ion—o ,
o be mo e p ecise by sol ing mixed-in ege linea p oblem o mula ions—one can
signi ican ly dec ease delays and ha e conside able po en ial o op imized pa ien
anspo s.
Keywo ds OR in heal h se ices· Vehicle ou ing· Heu is ics· Mixed-in ege linea
op imiza ion· Pa ien anspo
* K is in B aun
[email p o ec ed]
1 Depa men o Da a Science, F ied ich-Alexande -Uni e si ä E langen-Nü nbe g, Caue s aße
11, 91058E langen, Ge many
2 F aunho e Ins i u e o In eg a ed Ci cui s IIS, No dos pa k 84, 90411Nu embe g, Ge many
566
D.Adelhü e e al.
1 In oduc ion
In a heal hca e sys em, pa ien anspo needs o be well planned o ensu e a unc-
ioning sys em. Because such a sys em consis s o many componen s, e.g., heal h
p omo ion, p ima y ca e, specialized se ices, and hospi als, anspo ing pa ien s
wi hou delays is by no means i ial, especially when he espec i e anspo s a e
no eme gencies and can be pos poned. This could be he case when a pa ien needs
o be anspo ed home om a hospi al o when pa ien s ecei e ce ain ea men s a
a speci ic des ina ion. While in p inciple hose anspo s could be ca ied ou by he
ehicles ha ca y ou escue anspo s, a di e en lee is ypically used o o he
pa ien anspo s in Ge many. In con as o escue anspo s, pa ien anspo s
allow delays, hough hey a e no desi able. Scheduling hem is a challenge due o
di e en easons. While he numbe o ehicles in he anspo lee is limi ed, he
d i e s’ wo k shi s need o be espec ed. Mo eo e , a ehicle can anspo only one
pa ien a once. Finally, no all anspo eques s a e known a he ime when he
plans a e es ablished: Many anspo s a e eques ed du ing he day when a anspo
schedule is al eady in ope a ion. The las poin in pa icula can lead o long delays
o pa ien s wai ing o hei anspo , as i is o en impossible o handle all ans-
po s a once.
A na u al scheduling app oach is a g eedy app oach: whene e a anspo is
eques ed, he ehicle ha can each he pa ien mos quickly is dispa ched. This
app oach is pe o med in Middle F anconia, acco ding o he local dispa che , he
In eg ie e Lei s elle Nü nbe g (ILS). Fo he esul ing anspo plans, op imiza ion
po en ial is usually dis ega ded and some imes anspo s e en ha e o be esched-
uled o he ollowing day. As a mo i a ion, we p o ide some s a is ics abou he
anspo da a in he ollowing.
1.1 S a is ics abou  hepa ien anspo s
We conside he numbe o anspo s om Janua y 2020 o July 2021. In Fig.1a,
we plo he numbe o pa ien anspo s. The numbe o weekly anspo s on week-
ends, especially on Sundays, is dec easing, while he o al numbe o anspo s
shows a simila o de o magni ude. O e he u n o he yea , due o Ch is mas
and o he holidays, ewe anspo s a e eques ed. In 2020, he e is ano he small
dec ease s a ing in Ap il. The e is no such decline be o e 2020, so his is likely due
o he onse o he Co id-19 pandemic. Fu he , we plo he pe cen age o anspo s
ha in ol ed an pa ien ei he in ec ed, o , a leas , suspec ed o be in ec ed, wi h
Co id-19. These a e ep esen ed by he black po ion o he ba s in Fig. 1a. Fo
be e isibili y, he pe cen age o Co id-19 anspo s is also gi en in Fig.1b. In
he peak phase, up o
60%
o all anspo s ha e been classi ied as in ec ed cases.
This is—as he e a e a lo o suspec ed cases—no he ac ual numbe o in ec ions.
Howe e , he end gi en in Fig.1b is qui e simila o he numbe o ac ual Co id-19
cases in Middle F anconia, c . Robe Koch Ins i u e (2020). This end is shown in
he ed pa o he plo .
567
Minimizing delays o pa ien anspo s wi hincomple e…
Fu he mo e, we conside he numbe o anspo s du ing he cou se o a
day in Fig.2: T anspo s a e dis inguished depending on he ime when hey a e
eques ed and he numbe o eques ed anspo s pe hou is plo ed o he same
ime window as be o e. The majo i y o he anspo s a e eques ed a 6 am o
la e . The peak is in he la e mo ning, he ea e he numbe slowly dec eases.
A e abou 7 pm, he numbe o anspo s is again ela i ely low compa ed o
he p e ious hou s.
(a) Absolu enumbe o anspo s,dis inguished on he basis
whe he he pa ien is known obe in ec ed (black ba s) o no
(g a
y
ba s).
(b)Pe cen ageo known Co id-19 ans-
po s and o alnumbe o Co id-19 cases
in he ca chmen a ea o he ILS.
Fig. 1 S a is ics on he numbe s o anspo s and he pe cen age o known Co id-19 anspo s o he
a ailable da a
Fig. 2 Numbe o plannable and ad hoc anspo s, di e en ia ed by he a ge ime
568
D.Adelhü e e al.
The numbe o plannable anspo s1 is shown in he g ay ba s, while he black
ba s ep esen he numbe o ad hoc anspo s.2 In he ea ly mo ning hou s, i.e.,
be ween 6 and 8 am a lo o anspo s a e ad hoc ones. A e ha , un il noon, mos
anspo s a e plannable. Then, he pe cen age o ad hoc anspo s inc eases o e he
cou se o he day. A e 3 pm, mo e han
80%
o all anspo s a e ad hoc anspo s.
1.2 Ou con ibu ion
In his pape , we model he p oblem o inding ai schedules o pa ien anspo s.
In ou case, ‘ ai ’ means ha he maximum delay o e all pa ien anspo s is min-
imized as he i s p io i y, be o e, secondly, he o al delay o e all anspo s is
minimized. Besides he aim o dis ibu ing he minimal delay among he pa ien s
oughly uni o mly we need o espec he d i e s’ shi s whene e possible.
We p esen wo app oaches o handle anspo s ha a e eques ed du ing
he cou se o he day: On he one hand, i he dispa che has knowledge o he
eques ed anspo in ad ance, bu does no ye know he ime i is supposed o
happen ( o example a pa ien needs o be aken home a e a ea men ), so-called
dummy anspo s a e in oduced o block ehicle capaci ies. These anspo s can
be expec ed due o, o example, eques s ha ypically come in a speci ic imes
o he day o as ollow-up anspo s. On he o he hand, whene e an ad hoc ans-
po becomes known o he dispa che , we eop imize he pa o he schedule ha
has no ye begun and es ablish a new schedule ha inco po a es he ad hoc ans-
po . The model is based on he ehicle ou ing p oblem wi h gene al ime windows
(VRPGTW) ha was in oduced in Iba aki e al. (2005). We sol e he op imiza ion
p oblems using s a e-o - he-a sol e s o MIP ha we enhance wi h heu is ics in
o de o imp o e hei unning ime. We demons a e ha one can modi y ou p o-
posed model whene e necessa y by in oducing a gene al and adap able way o add
new inequali ies, equa ions and penal y a iables. As an applica ion, we discuss he
issues ha need o be aken in o accoun du ing he Co id-19 pandemic o minimize
he isk o in ec ion and how o model hem. In ou nume ical s udy, we show ha
ou op imized p ocedu e o scheduling anspo s is e ec i e and e icien in p ac-
ice. Rega ding in ec ious illnesses, we show ha anspo ing pa ien s ha a e (a
leas suspec ed o be) in ec ed using sepa a e ehicles is desi able.
In se e al key poin s, ou app oach di e s om p e ious wo k. Fi s ly, a he han
ea ing ai ness as a sepa a e model pa ame e , we inco po a e i di ec ly in o ou
objec i e unc ion. Secondly, ou me hodology ensu es obus ness wi hou he use
o andom a iables. Thi dly, a he han ocusing on op imizing equi ed ime o
e u ned dis ance, we p io i ize minimizing delays o pa ien s e en i his causes
de ou s o ehicles. Ou esea ch is based on a dynamic and de e minis ic ehicle
ou ing p oblem (VRP) and employs a wai - i s s a egy. Finally, because escue
and non- escue anspo s in Ge many use sepa a e ehicle lee s, we also use a
1 T anspo s ha a e known when es ablishing a schedule.
2 T anspo s ha become known du ing he day.

569
Minimizing delays o pa ien anspo s wi hincomple e…
sepa a e lee dedica ed solely o pa ien anspo s, dis inc om he lee designa ed
o escue ehicles. We discuss hese poin s in mo e de ail in ou li e a u e e iew in
Sec .2.
1.3 S uc u e o  hepape
In Sec .2, we p esen ela ed wo k conce ning ehicle ou ing p oblems and o he
p oblems a ising in he heal hca e sec o . Fu he mo e, we show ou chosen way
o modeling he VRPGTW. The eupon, in Sec .3, he pa ien anspo p oblem is
desc ibed on an abs ac le el. We i s de ine di e en anspo s and discuss he
amoun o in o ma ion a ailable a he ime o planning. We also in oduce ech-
niques o modi ying models on an abs ac le el. In Sec .4, we discuss how he
pa ien anspo p oblem can be modeled as a MIP. Subsequen ly, he model is
modi ied o inco po a e he equi ed upda es when a p e iously unknown anspo
is eques ed. We hen desc ibe how o inco po a e Co id-19- ela ed equi emen s,
including disin ec ion ime and he goal o sepa a ing known Co id-19 anspo s
om o he eques s as a as possible.
In Sec .5, we elabo a e on algo i hmic me hods o imp o e he unning ime o
ou models’ sol ing p ocess and e alua e he me hods by using he a ailable his o i-
cal da a. In pa icula , we compa e ou me hods o an implemen a ion simula ing he
cu en scheduling p ac ice a he ILS. Finally, in Sec .6, we discuss ou esul s and
p o ide some ideas o u u e esea ch.
2 Li e a u e e iew
Since he VRP gene alizes he a eling salespe son p oblem (TSP), i is na u ally
NP-ha d. Be o e we p esen ou chosen app oach o model he VRP in Sec .2.5, we
p esen an o e iew o esea ch abou VRPs in he li e a u e. Fu he , we p esen
and discuss some li e a u e conce ning anspo p oblems in heal hca e ha ha e
been discussed in he con ex o ma hema ical op imiza ion. Finally, we classi y ou
p oblem depending on hese indings.
2.1 Vehicle ou ing p oblems
The VRP p esen ed in Dan zig and Ramse (1959) is a gene aliza ion o he well-
known TSP: Gi en an (un-)di ec ed g aph, and gi en a ixed nonnega i e in ege m
and a ixed node, he ques ion is whe he he gi en g aph can be pa i ioned in o a
mos m Hamil onian cycles ha sha e only he gi en ixed node. The in e p e a ion
gi en in Dan zig and Ramse (1959) is ha he gi en numbe m is he numbe o
a ailable ehicles o ca y ou (pe ol) deli e ies such ha each cus ome is se ed
exac ly once by exac ly one ehicle and ha each ehicle s a s and ends i s ou a a
depo (which co esponds o he gi en ixed node). Fo a gene al o e iew o ehi-
cle ou ing p oblems, we e e o Vigo and To h (2014). In his wo k, an o e iew o
di e en me hods o modeling and sol ing a ia ions o ehicle ou ing p oblems
570
D.Adelhü e e al.
and i s modi ica ions a e p esen ed and e alua ed, including b anch-and-bound-
algo i hms, b anch-and-cu -algo i hms, se -co e ing-based algo i hms and heu is ic
me hods, among o he s. I is also possible o model VRPs as MIPs. This is also ou
solu ion app oach since we use s a e-o - he-a so wa e in ou nume ical s udy. In
Sec .2.5 we jus i y his choice in mo e de ail.
The wo ks o Co deau e al. (2007a, b) p esen an o e iew o di e en p ob-
lem classes o ehicle ou ing p oblems. Two gene aliza ions a e he ehicle ou -
ing p oblems wi h ime windows and he ehicle ou ing p oblem wi h pick-up and
deli e y. The la e one usually con ains ime windows, so one mos ly omi s he
pick-up and deli e y pa . In ou wo k, we use he VRPGTW which was in oduced
in Iba aki e al. (2005). Con a y o he ehicle ou ing p oblem wi h ime windows,
he bounds on a ge imes can be so , i.e., hei iola ion is penalized, o ha d,
i.e., he co esponding cons ain s need o be sa is ied. Vidal e al. (2020) discusses
many cu en VRP ex ensions, such as se ice quali y, equi y, and wo king hou s,
among o he s. Ano he gene aliza ion discussed in Iba aki e al. (2005) is he dial-
a- ide p oblem. This p oblem aims o model anspo s o passenge s. Thus, human
ac o s like hei sa is ac ion mus also be included. Fo an o e iew we simply e e
o Ho e al. (2018).
VRPs a e ei he s a ic o dynamic and ei he de e minis ic o s ochas ic. In a
s a ic VRP, all anspo s a e known be o ehand, while in a dynamic one hey can
change o e ime. Fu he , new anspo s can be eques ed o e ime. The dis inc-
ion be ween de e minis ic and s ochas ic VRP depends on whe he some da a is
unce ain.
2.2 Dynamic VRPs
Dynamic VRPs equi e mo e sophis ica ed solu ion echniques, while s a ic
VRPs a e, in compa ison, usually easy o sol e by applying s a e-o - he a MIP
app oaches. Be beglia e al. (2010), Pillac e al. (2013), Bek as e al. (2014) p esen
o e iews o dynamic VRPs. The i s consis s o a collec ion o p oblems while
he la e ocuses on he dis inc ion be ween pe iodic and con inuous sol ing me h-
ods. A pe iodic sol ing me hod e-op imizes he p oblem a e a ce ain ( ixed) ime
pe iod o as soon as new da a is a ailable while a con inuous sol ing me hod is
pe o med h oughou he whole day. Ano he o e iew om Psa a is e al. (2016)
u he in oduces a new classi ica ion scheme o dynamic VRPs ha consis s o
ele en c i e ia, o example he ype o he objec i e unc ion (i.e., whe he one min-
imizes cos s, dis ances, a el imes, e c.), he lee size, he ype o ime cons ain s
and he solu ion me hod.
Ano he solu ion me hod o dynamic VRPs is gi en in Fe ucci e al. (2013).
The e, he au ho s in oduce dummies o p ecau iona ily schedule ad hoc anspo s
o a eas whe e new eques s a e likely o occu . Fu he , he e a e di e en possi-
bili ies, how cu en ly wai ing ehicles can beha e o handle incoming anspo
eques s be e . The wo k o Mi o ić-Minić and Lapo e (2004) desc ibes di e en
wai ing s a egies, namely he d i e- i s s a egy whe e a ehicle lea es i s cu en
loca ion as soon as possible. In con as o he d i e- i s s a egy, o he wai - i s
571
Minimizing delays o pa ien anspo s wi hincomple e…
s a egy, he ehicle wai s as long as possible. Fu he , wo mix u es o bo h a e
in oduced. Due o he s ochas ic p obabili y dis ibu ion o new cus ome s’ loca-
ion, heu is ics ocusing on he wai ing loca ion a e conside ed.
2.3 S ochas ic VRPs
In addi ion o dynamic VRPs, unce ain ies add ano he laye o complexi y. S o-
chas ic VRPs can consis o di e en ypes o unce ain ies. The wo k o Soe ke
e al. (2022) summa izes whe e hose may occu : The main sou ce o unce ain y
is demand, which e e s o he numbe o eques s, as well as whe e, i , and when
hey will occu . Fu he mo e, he en i onmen may be unce ain, such as luc ua ing
a el imes due o a ic. Finally, one may ha e unce ain esou ces, which means
ha he a ailabili y o , o example, ehicles and d i e s is no gua an eed. Fu he
o e iews o e s ochas ic VRPs can, o example, be ound in Be han e al. (2014),
Oyola e al. (2018). The wo k o Oyola e al. (2017) ocuses on solu ion me hods
o hese p oblems. Be simas and an Ryzin (1991) is one o he i s wo ks dis-
cussing dynamic and s ochas ic VRPs. The e, he au ho s p opose heu is ics o sol e
hese mo e di icul p oblems. Also, Fla be g e al. (2007) dis inguishes s ochas ic,
dynamic and dynamic/s ochas ic VRPs. They u he men ion ha i is help ul o
ga he pa ien da a o de e mine a p obabili y dis ibu ion. Simila ly, he mo e cu -
en su ey Ri zinge e al. (2015) in es iga e hese h ee ypes o VRPs.
S ochas ic VRPs a e equen ly sol ed wi h Ma ko Decision P ocesses (MDPs).
A gene al MDP has ou componen s: s a es, ac ions, ansi ions, and ewa ds. Fo
VRPs, each s a e con ains he ehicle(s)’ cu en loca ion, a i al ime a he cu en
node, and he s a us o all cus ome s. An ac ion assigns imes o cus ome s, and an-
si ions a e used o changing om one s a e o he nex a e an ac ion is chosen. The
ewa d is de e mined by how he p oblem is de ined and wha speci ic goals a e se ,
e.g. minimizing a el imes, maximizing he numbe o isi ed cus ome s o balanc-
ing he wo kload be ween d i e s.
Unlike gene al MDPs, ou e-based MDPs explici ly model ou e plans as
sequences o possible u u e ac ions, he eby ede ining he easible ac ion space.
This enables eal- ime decisions ha di ec ly adjus and op imize u u e ou es. This
also implies ha s a es in ou e-based MDPs now include ou es. Ulme e al. (2017)
shows ha MDP and ou e-based MDP o mula ions a e equi alen when using a
sligh ly es ic ed o mula ion o he Bellman equa ion.
Kim e al. (2005) and Kim e al. (2016) apply MDPs o sol e s ochas ic VRPs
wi h unce ain a el imes. The i s uses heu is ics and eal- ime da a, while he
la e deals wi h nons a iona y s ochas ic a el imes and a emp s o de e mine a
p obabili y dis ibu ion. Fu he mo e, Kim e al. (2005) op imizes d i e a endance
imes and ehicle co e age, which a e ixed in ou case. In bo h cases, he cus ome s
and hei demands a e known in ad ance. Fu he , Zhang e al. (2021), Wang e al.
(2021) and Schilde e al. (2014) sol e s ochas ic e sions o a dial-a- ide p oblem
wi h unce ain a el imes.
In Secomandi and Ma go (2008), he au ho s assume ha hey ha e comple e
in o ma ion abou all cus ome s, wi h he excep ion o s ochas ic demands. As a
572
D.Adelhü e e al.
esul , due o limi ed capaci y, ehicles may be equi ed o e u n o he depo du ing
eplanning. MDPs and heu is ics a e used o sol e he p oblem o a single ehicle
wi h known p obabili y dis ibu ions.
The e is also some wo k o be done o add ess he unce ain y conce ning whe he
mul iple eques s will occu a all. In Ulme e al. (2020), possible cus ome loca-
ions a e known be o ehand. Addi ionally, he numbe o eques s is a ailable. Yu
e al. (2019) discusses acan axi ou ing, which in ol es deciding whe e axis ha
a e no cu en ly anspo ing passenge s should d i e o wai . In his case, cus ome
eques s may appea om any posi ion. This is handled by clus e ing posi ions in o
zones, esul ing in a disc e e ac ion space. Bo h wo ks use MDPs o sol e s ochas-
ic VRPs. Thomas (2007) also sol es a dynamic and s ochas ic VRP wi h unknown
eques s. The au ho pays special a en ion on he ques ion whe e ehicles should
wai .
O he solu ion me hods ea u e combina ions o MDPs wi h olling ho izon
app oaches Ma golis e al. (2022) and gene ic an colony algo i hms Hansha and
Ombuki-Be man (2007).
Many applica ions can be modeled as o de picking and deli e y p oblems. In
Zhang e al. (2017, 2019), he au ho s conside deli e y o business- o-cos ume
and online- o-o line supe ma ke s, espec i ely. A mo e gene al wo k can be ound
in Chen and Xu (2006) whe e a VRP o minimizing he d i en oad dis ance is
modeled and e alua ed on benchma k ins ances. In con as o hei app oach, we
minimize delays and no a oad dis ance. In Gend eau e al. (1999), he main ques-
ion is o decide whe he ad hoc anspo s should be accep ed o ejec ed wha is
no possible in heal hca e. Du ing he whole ime pe iod, he p oblem is op imized
con inuously. Kok e al. (2012) in oduce a new model, namely a VRP wi h ime-
dependen a el imes. Va ying a el imes, such as hose caused by a ic jams,
a e aken in o accoun in his speci ic model. The a el ime is de e mined by he
o igin and des ina ion, as well as he eques ed depa u e ime. By inco po a ing his
in o ma ion, he au ho s in end o enhance he eliabili y o planned ou es. In Be -
simas e al. (2019), he au ho s apply he solu ion o snapsho s o handle ano he
dynamic VRP, namely scheduling ad hoc anspo s o online axi ou ing. In ou
wo k, we conside a dynamic and de e minis ic VRP.
2.4 T anspo p oblems inheal hca e
The e is also a lo o wo k ha model passenge anspo ing p oblems ha occu in
heal hca e as ehicle ou ing p oblems. The wo k o Hulsho e al. (2012) is a ax-
onomy o heal hca e decisions and hus, a good o e iew. In Beaud y e al. (2010)
and Ke gosien e al. (2011), he pa ien anspo p oblem wi hin a hospi al is con-
side ed. In he o me one, hey assume ha he hospi al is one building, while in he
la e one, he buildings o he hospi al a e sp ead o e he whole ci y—in his spe-
ci ic example, in Tou s (F ance). A s a ic e sion o he VRP o he pa ien anspo
p oblem is discussed in Melach inoudis e al. (2007), an example o a wo k abou
escue anspo s is Gend eau e al. (2001). Impo an wo k in he ield o pa ien
anspo in he Eu opean a ea is desc ibed in an den Be g and an Essen (2019),
579
Minimizing delays o pa ien anspo s wi hincomple e…
anspo s o
Tplan
a e ca ied ou , anspo s o
Tad hoc
need o be inco po a ed and
he schedule usually has o be upda ed. Fo anspo s
T∈Tsemi
, no a ge ime is
ye de ined. When one ea s hem as ad hoc anspo s, he dispa che igno es hem
un il hei a ge ime becomes known.
Al e na i ely, he es ima ed a ge ime
es
T
could guide scheduling, ea ing he
anspo as a plannable anspo in
Tplan
. I he ac ual a ge ime di e s, he dis-
pa che adjus s acco dingly. I ea lie , i is ea ed ad hoc; i la e , he ehicle wai s.
Howe e , since es ima ed imes may a y signi ican ly, a maximum wai ing ime is
in oduced. I a ehicle exceeds his wai ing ime, i is eassigned, ea ing he ans-
po as ad hoc and dele ing he dummy anspo . This is o malized as ollows:
De ini ion 7 (Dummy anspo ) A anspo T is called a dummy anspo , i
i)
T∈Tsemi
, i.e., i is semiplannable,
ii) i s a ge ime is es ima ed wi h
es
T
≥
0
, and,
iii) i has a wai ing ime
wT≥0
a e which T will be ea ed as an ad hoc anspo .
The se o dummy anspo s is deno ed as
Tdummy
.
To es ima e he a ge ime, his o ical da a o medical expe ise can be used.
An example o a scena io whe e dummy anspo s a e applicable in p ac ice in
ou eal-wo ld example a e e u n ips om dialysis. We come back o his in
Sec .4.2.1.
This concludes he discussion o he pa ien anspo p oblem. In he ollowing
sec ion, we model he speci ic op imiza ion p oblems and desc ibe how hey can be
sol ed, also when inco po a ing semiplannable and ad hoc anspo s.
4 Ma hema ical op imiza ion
The pa ien anspo p oblem desc ibed in he p e ious sec ion is now modeled
as a VRPGTW. This ype o modeling has p o ed o be he mos app op ia e o
ou applica ion’s p ac ical equi emen s and s anda ds as discussed in Sec . 2.5.
We begin by modeling he plannable pa ien anspo p oblem in Sec .4.1. Then,
we ex end his o mula ion o semiplannable and ad hoc anspo s in Sec .4.2.1
be o e we elabo a e on he modeling o equi emen s o he Co id-19 pandemic in
Sec .4.2.2.
4.1 Modeling hepa ien anspo p oblem asaVRPGTW
To model ou p oblem, we use he VRPGTW o mula ion om Sec .2.5. Assume
we ha e n plannable anspo s (De ini ion1) om
Tplan
ha ha e o be scheduled

580
D.Adelhü e e al.
wi h m ehicles. We begin by explaining how he plannable model is c ea ed. The
pa ame e s o he VRPGTW a e de ined as ollows:
•
N∶= {1, …,n}
is he se o plannable anspo s. Each node i co esponds o
anspo
Ti
. The depo is deno ed as node 0 and has a copy
n+1
. The ehicles
s a a 0 and end hei ip a
n+1
. This a oids modeling issues and does no
ha e o he implica ions.
•
K∶= {1, …,m}
is he se o a ailable ehicles.
•
AN∶= {(
i
,
j
)∈
N
×
N
∶
i≠j
}
is he se o a cs ‘be ween wo anspo s’. An
a c
(i,j)∈AN
is used i and only i a ehicle ca ies ou
Tj
di ec ly a e ans-
po
Ti
.
•
AK∶= {(0, j)∶j∈N}∪{(i,n+1)∶i∈N}∪{(0, n+1)}
is he se o a cs
om he depo o all
j∈N
, om each
i∈N
o i s depo and he a c
(0, n+1)
ha is used by a ehicle i i does no anspo any pa ien s.
• The dig aph is
G∶= (V,A)
wi h
V∶= N∪{0, n+1}
and
A∶= AN∪AK
.
• Fo each
i∈N
,
i
is he a ge ime o anspo
Ti
.
• Fo
k∈K
,
[ak,bk]⊆ℝ+
deno es he shi o he d i e (s) o ehicle k.
• Fo
i,j∈N
,
𝜏i,j≥0
deno es he ime a ehicle needs o each
Oj
a e s a ing
anspo
Ti
, i.e., he sum o
di
and he a el ime
dis i,j≥0
om
Di
o
Oj
.
• Fo
j∈N
,
𝜏k
0,j
>
0
deno es he a el ime o ehicle
k∈K
o each
Oj
om i s
depo and
𝜏k
j,n+1
>
0
deno es he a el ime o ehicle
k∈K
o each i s depo
om
Dj
. We se
𝜏k
0,n+1
∶=
0
o all
k∈K
. We need he supe sc ip k he e, since
he e can be mul iple depo s.
The a iables o ou model a e:
•
xi,j,k∈{0, 1}
is he bina y a iable ha indica es whe he ehicle k a els om
node i o j, i.e., whe he ehicle k ca ies ou anspo
Tj
di ec ly a e i ca ies
ou anspo
Ti
.
• Fo all
i∈N
,
yi∶= yi,k∈ℝ+
deno es he ime when ehicle k a i es a node i,
i.e., when anspo
Ti
s a s. We only need one a iable o each anspo
Ti
as a
mos one ehicle se es i .
•
y0,k∈ℝ+
deno es he ime when a ehicle s a s i s ip and
yn+1,k∈ℝ
deno es
he ime when i ends i s ip. He e we need a a iable o each ehicle.
As a choice o an objec i e unc ion ha e alua es he quali y o he schedule ade-
qua ely, we use piecewise linea measu es o quali y ha we will linea ize whene e
necessa y. To simpli y no a ion, we hus in oduce he ollowing concep o penal y
weigh s:
De ini ion 8 (Penal y weigh s) Le
Λ
be a se o a iables. A penal y weigh is a
pa ame e
𝛾∈ℝ
ha is used o penalize all a iables
𝜆∈Λ
. The penal y se
Γ
con-
ains he uples
(𝛾,Λ)
. Using his ep esen a ion, an objec i e unc ion has he o m
581
Minimizing delays o pa ien anspo s wi hincomple e…
Since ou goal is o c ea e a ai schedule, we a emp o minimize he maximum
delay h oughou he day. To his end, we in oduce a penal y pa ame e
𝛾max >0
.
Fu he , we minimize he indi idual delays (possibly weigh ed by
𝛾i
), yielding he
(piecewise linea ) measu e o quali y
as we de ined i in De ini ion4. Objec i e unc ion(3) can be easily linea ized, as
one can see in he Objec i e unc ion (4a) and Cons ain s(4h), (4i) o he ollowing
MIP whe e ou (linea ized) ins ance is o mula ed:
We can ep esen he cu en penal ies o he delays using he penal y weigh s o
De ini ion8 by
so we do no s a e he delays explici ly in he ollowing.
∑
(𝛾,Λ)∈Γ
∑
𝜆∈Λ
𝛾⋅𝜆
.
(3)
𝛾
max ⋅max{0, y1− 1,…,yn− n}+
∑
i∈N
𝛾imax{0, yi− i
}
(4a)
min
𝛾max ⋅Δmax +
∑
i∈N
𝛾iΔ
i
(4b)
s. Cons ain s (1b)−(1e),
(4c)
yi+𝜏i,j−yj≤Mi,j(1−xi,j,k)∀k∈K,(i,j)∈AN,
(4d)
y
i,k+𝜏
k
i,j
−yj,k≤Mi,j(1−xi,j,k)∀k∈K,(i,j)∈AK
,
(4e)
ak
≤
y0,k
∀
k
∈
K,
(4 )
yn
+
1,k≤bk∀k∈K,
(4g)
i
≤
yi∀i∈N,
(4h)
yi−
i
≤
Δi∀
i
∈
N
,
(4i)
0
≤
Δi
≤
Δmax ∀i∈N,
(4j)
xi,j,k∈{
0, 1
}∀k∈K
,
(i
,
j)∈A,
(4k)
yi
,
k
≥
0∀i∈N,k∈K.
Γ ∶= {(
1, {Δ
i
∣i∈N}
)}
∪
{(
𝛾
max
,{Δ
max
}
)},
582
D.Adelhü e e al.
The emaining cons ain s o Model(4a) ha a e no di ec ly aken o e om he
gene al o mula ion model he ollowing: Cons ain s(4e) and (4 ) a e ha d bounds
ha ensu e shi imes a e me and easible schedules as in oduced in De ini ion2
a e ob ained. Cons ain (4g) p e en s a ehicle om s a ing a anspo be o e i s
a ge ime.
Wi h he solu ion o Model(4a), we can consequen ly es ablish a easible sched-
ule: I
xi,j,k=1
hen ehicle k ca ies ou anspo
Tj
a e ca ying ou anspo
Ti
. Thus, om he op imal solu ion
(x∗
,y∗)
, i is possible o econs uc he pa h o
ehicle k om 0 o
n+1
o he o m
( k1,…, ks),
whe e
s∈ℕ
deno es he numbe
o anspo s o he espec i e ehicle. Along wi h he op imal a i al imes
y∗
, an
op imal schedule is ob ained.
4.2 Ex ending heplannable o mula ion
So a , we ha e modeled he p oblem o inding op imal schedules o anspo s
o which all in o ma ion is known, i.e., plannable anspo s. This model is now
ex ended o handle anspo s wi h incomple e in o ma ion, including ad hoc ans-
po s. In addi ion, using he Co id-19 pandemic as an example, we p opose and
model how o ea he si ua ion o endemic diseases, o , o be mo e p ecise, when a
pa ien is a leas suspec ed o be in ec ed wi h a highly in ec ious disease.
We begin by in oducing labels o anspo s:
De ini ion 9 (T anspo labels) A ( anspo ) label is a unc ion
𝜙∶T
plan
∪T
semi
∪T
dummy
∪T
ad hoc →
{
0, 1
}
ha indica es whe he a anspo
T∈Tplan ∪Tsemi ∪Tdummy ∪Tad hoc
ul ills some p ope y. Mul iple labels can be
collec ed in a label se
Φ
.
Label in o ma ion may include whe he a anspo in ol es in ec ious diseases,
needs o ul ill ce ain p io i ies, o he ques ion whe he ce ain equipmen is
needed. Ano he example can be he in o ma ion abou he ype (plannable, sem-
iplannable, ad hoc, dummy) o a anspo . Recall ha all ypes o anspo s a e
de ined in De ini ions1, 5, 6 and 7. A simila se can also be in oduced o ehi-
cles, e.g., o indica ing whe he ce ain equipmen is a ailable. In his case, only
such ehicles can handle anspo s ha need his equipmen . Using he de ini ion
o labels om De ini ion9, we can in oduce addi ional cons ain s o he pa ien
anspo p oblem on an abs ac le el. These cons ain s can be ha d o so , he la -
e using penal y weigh s and addi ional a iables.
Now we a e p esen ing di e en modeling possibili ies ha allow us o ex end
Model (4a) in a ious ways. Le
Φ
be a se o labels. One possibile ex ension is
o limi he numbe o anspo s pe ehicle wi h a label
𝜙∈Φ
o a ixed numbe
a∈ℕ
. This can be modeled by
(5)
∑
(i,j)∈A
xi,j,k⋅𝜙(Ti)≤a∀k∈K
.
583
Minimizing delays o pa ien anspo s wi hincomple e…
I a speci ic label is no o impo ance hen we can jus omi i . Wi h
a=1
, each
ehicle can handle a mos one anspo o a speci ic ype. Le
𝜙1,𝜙2∈Φ
and
assume ha i is no allowed o handle a anspo j wi h
𝜙2(Tj)=1
immedia ely
a e a anspo
Ti
wi h
𝜙1(Ti)=1
. This is ep esen ed by adding cons ain s
o Model(4a). Na u ally, i is also possible o se
𝜙1=𝜙2
and, hus, p ohibi he
handling o simila anspo s a e ano he .
4.2.1 Inco po a ion o  anspo s wi hincomple e in o ma ion
We now look a how o modi y he plannable o mula ion, i s o handle semiplannable
anspo s, and hen o handle ad hoc anspo s. The e o e, we apply he s a egy o
he ope a ional phase ha ha e been p oposed in Sec .3. In ac , simila o he planning
phase, his means c ea ing o ex ending he VRP o mula ion and sol ing he esul ing
MIP.
Whene e possible, we es ima e he a ge imes o semiplannable anspo s and
ea dummy anspo s like plannable anspo s. In o he wo ds, in Model(4a),
N
is
modi ied such ha he nodes co esponds o he anspo s in
Tplan ∪Tdummy
and he
ex ended VRP is sol ed. To ake he da a-d i en na u e o dummy anspo s in o
accoun , we es ablish he ollowing ules: Fi s ly, o he maximum delay as a measu e
o quali y, delays o dummy anspo s a e no aken in o accoun , i.e., only he delays
o he ini ial plannable anspo s a e ele an . Secondly, he indi idual delay o dummy
anspo s is a quali y o measu e and is weigh ed by some pa ame e
𝛾i
o
Ti∈Tdummy
.
Thus, a e inco po a ing he dummy anspo s, Objec i e (4a) o Model(4a) is
Wi h he scheduling o
Tplan
, he planning phase is comple ed.
In addi ion o semiplannable anspo s, he dispa che s usually need o inco po a e
ad hoc anspo s. They a e called whene e such a anspo has o be scheduled a a
ce ain ime
𝜎
on he ly. Wi h a schedule al eady in place, some ehicles a e al eady on
hei ou . The e o e, we need o eop imize ou schedule.
We now in oduce some no a ion. Le
𝜎∈ℝ+
be a gi en poin o ime. The se
V𝜎⊆V
deno es he nodes ha co espond o anspo s known be o e an ad hoc ans-
po is eques ed a
𝜎
. Using he op imal solu ion
(x∗
,y∗)
o Model(4a) a
𝜎
, he se
deno es he schedule ha is ca ied ou a
𝜎
. I no ad hoc anspo s ha e been
eques ed be o e
𝜎
, we ha e
P𝜎
=P0
, i.e., he solu ion o he plannable model.
T anspo s al eady in ope a ion a e no changed. They a e elemen s o he se
(6)
𝜙1(Ti)
⋅
𝜙2(Tj)
⋅
xi,j,k=0∀k∈K,(i,j)∈A.
(7)
𝛾
max ⋅Δmax +
∑
i∈N,
T
i
∉T
dummy
𝛾iΔi+
∑
i∈N,
T
i
∈T
dummy
𝛾imax{0, yi− es
i}
.
P
𝜎∶=
{
(i,k,y∗
i)∈V𝜎×K×ℝ+∣∃j∈V𝜎∶x∗
i,j,k=1
}
584
D.Adelhü e e al.
ha con ains all anspo s whe e he ehicle is ei he on he way om
D
T
i
o
O
T
j
o
has s a ed o inished anspo
Tj
. I an ad hoc anspo is eques ed o some ime
poin
𝜎
hen anspo s o
P𝜎
ixed
a e no changed while he anspo s in
P𝜎⧵P𝜎
ixed
a e
emo ed o he schedule. This ensu es ha ehicles no ca ying ou anspo s a
𝜎
a e a ailable again since he schedule a e
𝜎
was dele ed. Thus, e e y anspo
scheduled a e
𝜎
, including he ad hoc anspo , can be escheduled by sol ing
Model(4a) wi h he addi ional es ic ion ha all anspo s in
P𝜎
ixed
a e unchanged.
The e o e, we i s upda e G by including he new ad hoc anspo in
V𝜎
and
A𝜎∶= {(i,j)∈A∶i,j∈V𝜎}
, espec i ely. The eupon, o ensu e ha ixed ans-
po s a e no changed, we in oduce wo addi ional cons ain s o Model(4a), namely
and
I we ha e dummy anspo s, we need o be cau ious abou hei wai ing imes
since, whene e a anspo
T∈Tdummy
exceeds i s wai ing ime, i is dele ed and
ea ed as an ad hoc anspo (once eques ed). Then, in o de o use he ehicle ha
should ha e handled T, we eop imize ou schedule.
4.2.2 Adjus ing hemodel du ing heCo id‑19 pandemic
To dec ease he isk o in ec ions o pa ien anspo s du ing he Co id-19 pan-
demic, i is desi able ha anspo s a e dis inguished in o wo ypes, depending on
whe he a pa ien is (suspec ed o be) in ec ed wi h Co id-19 o no , esul ing in an
addi ional p ope y o anspo s. F om now on, we e e o pa ien s wi h a suspec ed
in ec ion wi h Co id-19 as ‘in ec ed’ as well. In he ollowing, we will discuss some
ideas how such Co id-19 anspo s can be handled and p oceed wi h a ma hema i-
cal o mula ion how minimizing he isk o in ec ions can be inco po a ed in ou
Model(4a) using De ini ion9.
The e a e di e en possibili ies o dec ease he isk o in ec ions. In p ac ice,
when dealing wi h dange ous in ec ious diseases like Co id-19, he s a needs
o wea p o ec i e clo hing and he ehicle is disin ec ed a e e e y anspo . In
addi ion o hese p o ec i e measu es, i can be help ul o minimize he numbe o
changes om a Co id-19 anspo o a non-Co id-19 anspo . This will educe
he numbe o con ac s be ween pa ien s and s a and hus he isk o in ec ion e en
u he , e en i ehicles a e disin ec ed a e each anspo .
We p esen wo di e en app oaches: educing he numbe o ehicles ha a e
allowed o ca y in ec ed pa ien s and limi ing he numbe o in ec ed pa ien s pe
ehicle. In addi ion o he goal o educing he numbe o changes, hese app oaches
ha e been de eloped due o he ac ha he supply o p o ec i e clo hing is limi ed
and he e o e should be dis ibu ed as e icien ly as possible. Ne e heless, in bo h
P
𝜎
ixed ∶=
{
(i,k,y∗
i)∈P𝜎∣∀j∈V𝜎∶x∗
i,j,k=1⇒𝜎≥y∗
j,k−dis i,j
}
(8)
x
i
,
j
,
k
=
x
∗
i,j,k∀(
i,j,k,y
∗
i)∈P𝜎
ixed
(9)
y
j=y
∗
j
∀(i,j,k,y
∗
i
)∈P
𝜎
ixed.

585
Minimizing delays o pa ien anspo s wi hincomple e…
cases, we s ill aim o minimize he delays o pa ien s. This is inco po a ed by using
di e en penal y pa ame e s o , e.g., he delay and he numbe o changes in he
objec i e unc ion.
The addi ional ime o disin ec ion and changing o clo hes needs o be aken in o
accoun when es ablishing schedules. This is easily done by inc easing he du a ion
di
o each anspo by a cons an . Thus, i is no necessa y o in oduce addi ional con-
s ain s o Model(4a).
To indica e, o which anspo s addi ional Co id-19 equi emen s a e necessa y,
we in oduce a label
c∶T
→
{0, 1}
whe e
T⊆Tplan ∪Tsemi ∪Tdummy ∪Tad hoc
. A
alue o 1 co esponds o a pa ien ’s in ec ion. This label is used o c ea e addi ional
cons ain s. Fo sake o no a ion, we w i e
ci
ins ead o
c(Ti)
. Fu he mo e, we w i e
c
, meaning a anspo is no a Co id-19 anspo , wi h
ci=1−ci
o all
Ti∈T
. To
model a els om and o he depo adequa ly, we u he de ine
c0∶= cn+1∶= 0
and,
consequen ly,
c0∶= cn+1∶= 1
.
4.3 Minimizing henumbe o changes
To o malize minimizing he numbe o changes, we use he labels c and
c
wi h
Cons ain (6):
Equa ion(10) models ha no ehicle is allowed o ca y a non-Co id-19 anspo
di ec ly a e a Co id-19 anspo . We do no wish o p ohibi all changes because
o he wise, he solu ion quali y w. . . he delay would dec ease o we would no able
o c ea e easible schedules a all. The e o e, we use a so cons ain . Ins ead o
minimizing he numbe o changes, we in oduce he addi ional a iable
𝜆change
i,j,k
∈{0, 1
}
o
(i,j)∈AN
,
k∈K
and modi y (10) acco dingly:
Now he a iables
𝜆change
i,j,k
a e penalized using
𝛾change
and we modi y
Γ
by appending
he uple
(
𝛾change,{𝜆
change
i,j,k
∣(i,j)∈AN,k∈K
})
.
4.4 App oach 1: Minimizing henumbe o Co id‑19 ehicles
An op ion o educe con ac be ween unin ec ed and in ec ed pe sons is di iding he
ehicle lee in o di e en pools, i.e., one pool o ehicles ha only handle Co id-19
anspo s and one pool o non-Co id-19 anspo s. I is possible o addi ionally use
so-called loa e ehicles ha a e allowed o handle bo h ypes o anspo s o main ain
some deg ee o lexibili y. He e, he p o ec i e clo hing can be dis ibu ed among he
Co id-19 ehicles and he loa e ehicles so ha no ehicle is ca ying i needlessly.
The co esponding cons ain is
(10)
ci
⋅
cj
⋅
xi,j,k=0∀k∈K,(i,j)∈AN.
(11)
c
i⋅cj⋅xi,j,k=𝜆
change
i,j,k
∀k∈K,(i,j)∈AN
.
(12)
ci
⋅x
i,j,k
≤𝜆
ehicle
k
,∀k∈K,(i,j)∈A
.
586
D.Adelhü e e al.
He e, o
k∈K
,
𝜆 ehicle
k
a e new bina y a iables. They a e penalized using
𝛾 ehicle
k
,
i.e., we upda e
Γ
←Γ∪(𝛾
ehicle
,{𝜆
ehicle
k
∣k∈K
})
.
4.5 App oach 2: Limi ing henumbe o Co id‑19 anspo s o each ehicle
Ano he app oach o inco po a e Co id-19 equi emen s is o dis ibu e p o ec i e
clo hing equally among all ehicles. In his case, e e y ehicle is able o se e a
limi ed numbe o Co id-19 anspo s be o e i needs o e u n o i s depo o ob ain
new se s o clo hing. An ad an age o his app oach is ha each ehicle is able o
ca y ou Co id-19 anspo s wi h less delay han when sepa a ing he lee s com-
ple ely. Ne e heless, his modeling app oach migh inc ease he numbe o swi ches
be ween in ec ed and non-in ec ed pa ien s in ehicles.
To implemen he limi a ion o p o ec i e clo hing, we use a uple o a pen-
al y weigh and in ege a iables
𝜆
clo hing ∈ℕ
|K|
0
, namely
(𝛾clo hing,Λclo hing)
whe e
Λ
clo hing ∶= {𝜆
clo hing
k
∣k∈K
}
. The objec i e unc ion is inc eased by he penal y
alue e e y ime a ehicle has o e u n o he depo o ob ain new clo hing. Thus,
o all
k∈K
, we in oduce he cons ain
whe e
𝛼∈ℕ
is he amoun o se s o clo hes pe ehicle. Inequali y (13) is Con-
s ain (5), wi h he di e ence ha no e e y exceedance o
𝛼
is penalized. Ins ead,
e e y ime
𝛼
is eached again, we inc emen he a iable
𝜆clo hing
k
by one. In ou
model, i is no possible ha ehicles e u n o he depo du ing hei shi , and, hus,
we p ohibi his by choosing he penal y o his scena io qui e high. This means ha
a ehicle only exceeds i s limi when i is no a oidable, i.e., i he e a e mo e han
𝛼|K|
Co id-19 anspo s. Howe e , his ne e happens in ou nume ical s udy.
This concludes he modeling o he pa ien anspo p oblem. In he nex sec ion,
we p esen and discuss ou nume ical expe imen and show he e iciency o ou
plannable app oach and i s ex ensions.
5 Implemen a ion andnume ical esul s
In his sec ion, we p o ide de ails on he implemen a ion as well as he insigh s
ha can be ob ained om he op imized schedules. The models p esen ed in he
ea lie sec ion a e sol ed ia s a e-o - he-a a ailable global MIP sol e s like
Gu obi (Gu obi 2021) o SCIP (Bes uzhe a e al. 2021) which a e applying solu-
ion app oaches o MIPs, c . Land and Doig (2010), Wolsey (2020) o Wolsey and
Nemhause (1999). The a ionale behind he usage o a ailable sol e s is o enable
possible ans e o he de eloped app oaches o he p ac i ione s so ha hey can
also main ain he p og am in he u u e. Mo eo e , using a MIP o mula ion, we a e
able o inco po a e he ex ensions o pandemic equi emen s.
(13)
∑
(i,j)∈A
ci⋅xi,j,k≤𝛼(1+𝜆
clo hing
k
)
587
Minimizing delays o pa ien anspo s wi hincomple e…
All models and algo i hms we e implemen ed in Py hon 3.7.7. To sol e he MIPs,
we used Gu obi 9.0.2 on he NHR@FAU clus e s wi h In el Xeon E3-1240 5 o
In el Xeon E3-1240 6 CPUs, espec i ely. Each o hese has ou co es wi h 3.5
GHz each and a RAM o 32 GB.
We s a wi h he desc ip ion o a simula ed eali y o e alua e ou schedules in
Sec .5.1. The eupon we p esen some heu is ic app oaches in Sec .5.2 and, inally,
we e alua e he pe o mance o ou app oach in Sec .5.8. The e, we also co e he
inco po a ion o semiplannable anspo s and he ex ensions o co e issues and
p oblems o pa ien anspo s du ing he Co id-19 pandemic.
Fo all nume ical esul s, we use his o ical da a om 2019 o mid-2021, p o ided
by he ILS ha co e s egions in Middle F anconia. In p ac ice, his a ea is di ided
in o di e en coun ies, and each one is scheduled indi idually, wi h a anspo T
assigned based on i s o igin loca ion
OT
. Wi h ou op imiza ion s a egy, we p oceed
in a simila manne . Coun ies a e di e en in size and popula ion densi y. We ha e
u al coun ies wi h a low popula ion densi y in compa ison o hei size, as well
as u ban coun ies wi h a high popula ion densi y, wha causes a highe numbe o
anspo s and, hus, mo e di icul ins ances.
We op imize each day sepa a ely because hey do no in luence each o he as du -
ing he nigh almos no anspo s a e eques ed. Unless o he wise men ioned, we
speci y a ime limi o 60min. We will elabo a e on he ime limi in Sec .5.8.
We mus o e come some issues wi h he a ailable his o ical da a: On he one
hand, some anspo s a e s a ed inco ec ly, such as missing imes amps o loca-
ions. Missing da a ha e been handled du ing p ep ocessing by ei he es ima ing
a el imes using a dis ance ma ix o dele ing he co esponding anspo s i oo
much da a we e missing. Fo he es ima ion o a el imes, we e e o Lei häu-
se e al. (2022). On he o he hand, he e a e cases whe e he dispa che needs o
make decisions on he ly ha could ha e no been planned be o ehand. Fo exam-
ple, ehicles, can be len be ween di e en coun ies. Technically, each ehicle is
assigned o a speci ic coun y bu in excep ional ci cums ances and i necessa y, his
can be elaxed. Fu he , he dis inc ion be ween pa ien and escue anspo s can be
neglec ed when absolu ely necessa y. Mo eo e , i a anspo ’s delay is excessi e, i
can be pos poned o ano he day. We do no conside any decisions ou o he se o
ules o usual decision makings in ou model since we a e no in a posi ion o make
hem. In p ac ice, he se o easible schedules can possibly be imp o ed by inco po-
a ing expe decisions.
5.1 Implemen a ion o asimula ed eali y
Fo he eason men ioned abo e, we canno compa e ou schedules di ec ly o he
ones in he his o ical da a. So, in o de o e alua e he op imized schedules, we
equi e a baseline solu ion.
To ensu e he mos accu a e compa ison, we ha e implemen ed a simula ion
o he ILS’s decision making ha ope a es simila ly o he p ac ice. They apply a
g eedy app oach: E e y ime a anspo is necessa y, he ehicle ha would a i e
588
D.Adelhü e e al.
he as es is assigned o i . Howe e , ehicles cu en ly in ol ed in a anspo can-
no be used, and shi imes need o be espec ed whene e possible.
Fo he baseline implemen a ion, we hus so all plannable anspo s by hei a -
ge ime gi en in he his o ical da a. Then he ehicles a e assigned in ha o de : Fo
each ehicle, we calcula e he ea lies ime i could each he eques ed anspo ’s
o igin by adding he a el ime o he ime i is expec ed o become a ailable, which
is ei he he s a o i s shi o he expec ed end o he p e ious anspo . Fu he -
mo e, we check whe he he ehicle could each i s depo wi hou iola ing i s shi
imes using he es ima ed du a ion, i.e., expec ed a el imes, o he anspo .
The ehicle ha can ca y ou he anspo eques wi h he smalles delay is
assigned o i . I he e is mo e han one ehicle wi h minimal delay hen he one wi h
he sho es a el ime is chosen. In he case ha no ehicle can handle he anspo
wi hou iola ing i s shi imes, we choose he ehicle wi h he smalles shi ime
iola ion.
5.2 Heu is ic me hods o  heMIP sol e
We p esen some algo i hmic app oaches o speeding up he MIP solu ion p ocess
o he a ising models. This is necessa y because, while conduc ing ou nume ical
s udy (see Sec .5.8), we ha e ealized ha wi hou any imp o emen s, ou solu ion
app oach is incapable o sol ing many ins ances o op imali y. Fo he e alua ion
o he heu is ic me hods, we use a subse o eal his o ical da a, namely da a co -
esponding o 59 days (Janua y and Feb ua y 2020) om wo coun ies, o a o al
o 118 ins ances. The coun ies di e in size; he smalle one has abou 100,000 esi-
den s, he la ge one abou 500,000.
5.3 Using ap imal heu is ic
The i s heu is ic we ha e implemen ed is a p imal heu is ic ha aims o ind good
easible solu ions ea ly in he MIP solu ion p ocess. A e e y k h node o he b anch-
and-bound ee wi hin he MIP sol e , we en a i ely ound a pa o he op imal
solu ion o he LP elaxa ion. In e e y easible solu ion, he numbe o a iables
xi,j,k
ha a e se o 1 is gi en by
|K|+|V|
. Fo a p imal heu is ic, all alues o
xi,j,k
in he
solu ion o he LP elaxa ion a e so ed and a numbe o hem a e ixed in o de o
as e ob ain a easible MIP solu ion. He e, we ha e chosen he numbe o ehicles
|K|
and se he
|K|
g ea es a iables o 1. I a easible solu ion is ound by using his
s a solu ion hen i is used o he ollowing sol ing p ocess. O he wise, i is dis-
ca ded. I is impo an no o ix oo many a iables as he solu ion may hen become
in easible since we could, e.g., acciden ally schedule wo ehicles o he same ans-
po . Howe e , we also no e ha ixing oo ew a iables will no speed up he sol -
ing p ocess and ha he espec i e alues a e based on empi ical analysis.
595
Minimizing delays o pa ien anspo s wi hincomple e…
wo king a shi a his ime, so he a e age delay o hese pa ien s becomes e y
high. This con inues wi h he anspo s s a ing sho ly a e 6am. As he mo ning
shi imes do no s a ea lie han 6am and hey i s need o d i e o he o igin o
a anspo , i is no possible o each hese pa ien s wi hou a delay. In gene al, he
nigh shi s end a 6am. Thus, hey can p obably no handle hese anspo eques s
wi hou isking shi ime iola ions.
A mo e de ailed e alua ion is gi en in Fig.6. The ligh g ay a ea ep esen s he
o al numbe o a ailable ehicles o e one yea . Fo ins ance, a 4 am, he e a e 365
ehicles a ailable, as each day he e is one ehicle handling he nigh shi . The da k
g ay a ea indica es he le el o ehicle u iliza ion.
This e alua ion shows ha he ehicles wi h ea lie , i.e., mo ning shi imes
ha e o handle conside ably mo e anspo s. Vehicles a e wo king almos a ull
capaci y a leas un il noon. A e wa ds, less ad hoc anspo s a e eques ed and
he si ua ion eases. This means ha as soon as a ehicle becomes a ailable, i will
be assigned o some anspo . As ew ehicles a e a ailable a he beginning o a
day, some anspo s canno be handled on ime. These delays hen cause delays
o la e anspo s. This occu s because ehicles a e occupied by ea lie ans-
po s ha a e p e e ed as we minimize he maximum delay. In he a e noon, less
anspo s a e eques ed. Thus, mo e ehicles a e a ailable and he delays inally
dec ease.
This da a is impo an o p ac i ione s as i highligh s he c i ical pe iods o high
ehicle u iliza ion and he esul ing delays. Unde s anding hese pa e ns allows o
be e scheduling and esou ce alloca ion, ul ima ely imp o ing anspo e iciency
and educing delays.
Fig. 6 Agg ega ed numbe o a ailable and u ilized ehicles o e ime

596
D.Adelhü e e al.
5.9.2 Examples o semiplannable anspo s and u he equi emen s
This sec ion con ains some sample schedules o ou modeling app oach ex ensions
om Sec s.4.2.1 and 4.2.2. We ha e been unable o conduc a ull nume ical s udy
due o a lack o da a, bu we we e able o iden i y some exempla y days whe e ou
ex ensions wo ked well. Fo bo h, using dummy anspo s o semiplannable ans-
po s as well as inco po a ing Co id-19 equi emen s, we explain he p oblems wi h
he gi en da a be o e p esen ing some examples.
5.10 Using dummy anspo s o semiplannable anspo s
While ying o handle semiplannable anspo s (De ini ion 5) using dummy
anspo s (De ini ion7), he ollowing da a issues ha e occu ed: A he begin-
ning o he op imiza ion p ocess, each anspo T is assigned o he coun y o
he o igin loca ion
OT
. O en, he des ina ion
DT
is loca ed in ano he coun y.
In his case, pa ien s ha e o be anspo ed be ween di e en coun ies, causing
ou wa d and e u n ips op imized in di e en models. This leads o dummy
anspo s ha a e no applied in he ac ual e u n ip. In p ac ice, he dispa che
can assign such anspo s o he same coun y. Fu he mo e, in mo e ecen da a
p o ided by he ILS, a ype o dummy node is used o dialysis anspo s. As
soon as a dialysis is eques ed, wo anspo s a e c ea ed, including he e u n
ip on 23:59 on he same day. I s a ge ime is co ec ed as soon as i becomes
known. Thus, i a dialysis is c ea ed a leas one day be o e, hen i is a planna-
ble anspo bu i s e u n ip is no , al hough i is s a ed o be plannable in he
da a.
Due o hese easons, we p o ide an example day whe e he inco po a ion o a
dummy anspo leads o a signi ican ly be e esul .
Example 1 (Ad an ages o using dummy anspo s)
In Table2, one can see wo schedules ha ha e been es ablished on an example
day in 2019. Table2a is he cu en schedule sho ly be o e 11:00. A 11:00, a new
anspo is eques ed. This anspo is a e u n ip o a p e ious dialysis anspo
o which a dummy node has been c ea ed. The dummy node’s a ge ime was es i-
ma ed based on he du a ion o p e ious dialysis appoin men s a he same loca ion,
i.e., in he same hospi al. The ou wa d jou ney has ID 28 and he dummy node is
deno ed by d28. I is de e mined ha he new anspo wi h ID 20 co esponds o
his dummy node. Thus, i is dele ed and eplaced by he new anspo using he
new in o ma ion, i.e., he ac ual a ge ime.
Table2b shows he schedule c ea ed a 11:00. As can be seen, he ehicles allo-
ca ed o he anspo s no con ained in
P𝜎
ixed
o
𝜎=
11:00, ha e changed. This is
due o he ac ha he anspo is eques ed a li le la e han expec ed and ehicle
7 is a ailable a ha ime. The schedule shows ha i inishes i s p e ious anspo
597
Minimizing delays o pa ien anspo s wi hincomple e…
Table 2 A schedule be o e and
a e anspo 20 has been
eplaced by i s dummy node
d28.The second dummy node,
d24 o anspo 24, does no
co espond o a u u e anspo
and will hus no be eplaced
be o e he end o he day.The
in o ma ion abou he e u n ip
has become known a 11:00, all
ixed anspo s a e gi en below
he line, so he emaining ones
could be escheduled. As can be
seen, he delays emain he same
o all anspo s. No e ha he e
a e ela i ely ew anspo s in
he a e noon as hey a e o en
ad hoc ones and hus a e no
known a his poin .
ID (i)
i
kS a (
yi
) End
Δi
(a) Schedule be o e 11:00
28 06:45 0 06:45 07:52 0
4 07:30 13 07:30 11:57 0
24 08:00 0 08:00 08:33 0
23 08:00 6 08:03 11:01 3.8629
25 08:30 0 08:33 10:00 3.2262
11 08:45 7 08:45 09:46 0
6 09:00 5 09:40 10:02 4.2565
0 09:00 8 09:40 11:10 4.2565
26 09:45 10 09:45 11:01 0
2 09:45 7 09:47 10:37 2.0320
13 10:00 10 10:45 11:59 45.0436
3 10:00 1 10:33 11:46 33.8629
12 10:00 0 10:00 10:58 0.5156
14 10:00 5 10:14 10:56 14.6932
15 10:00 7 10:37 11:48 37.1338
21 10:00 10 10:05 10:43 4.8170
7 10:15 5 10:59 12:18 44.0412
16 10:30 0 10:58 11:44 27.8051
9 10:30 11 11:03 12:30 33.8629
18 10:40 10 11:23 12:22 43.1832
1 11:00 0 11:44 12:31 44.0945
d28 11:52 1 11:52 12:59 0
d24 12:33 10 12:33 13:08 0
17 15:30 2 15:30 18:21 0
(b) Schedule a 11:00
28 06:45 0 06:45 07:52 0
4 07:30 13 07:30 11:57 0
24 08:00 0 08:00 08:33 0
23 08:00 6 08:03 11:01 3.8629
25 08:30 0 08:33 10:00 3.2262
11 08:45 7 08:45 09:46 0
6 09:00 5 09:40 10:02 4.2565
0 09:00 8 09:40 11:10 4.2565
26 09:45 10 09:45 11:01 0
2 09:45 7 09:47 10:37 2.0320
13 10:00 10 10:45 11:59 45.0436
3 10:00 1 10:33 11:46 33.8629
12 10:00 0 10:00 10:58 0.5156
14 10:00 5 10:14 10:56 14.6932
15 10:00 7 10:37 11:48 37.1338
21 10:00 10 10:05 10:43 4.8170
7 10:15 5 10:59 12:18 44.0412
598
D.Adelhü e e al.
a 11:48, he new anspo is eques ed a 12:00 ins ead o he p esumed 11:52. So,
his ehicle can each he o igin o he e u n ip in ime.
The maximum delay in his example coun y is educed by 20min when com-
pa ed o he schedule c ea ed wi hou dummy nodes. As a esul , he o al delay
dec eases. In his case, we only c ea e one dummy node, which is la e eplaced,
and, he penal y weigh was se o
𝛾=0.5
o dummy anspo s. Taking his in o
accoun , his is a e y posi i e esul , and an e en g ea e imp o emen can be
p edic ed i mo e dummies a e used whene e app op ia e da a is a ailable.
5.11 Inco po a ing u he equi emen s
Now, we conside schedules when dealing wi h Co id-19 anspo s. The dis-
pa che does no ha e a special cou se o ac ion in he Co id-19 pandemic.
Ins ead, i ea s anspo s o in ec ed pa ien s in he same manne as o he ans-
po s. As a esul , e alua ing ou ex ension om Sec .4.2.2 agains he (simu-
la ed) eali y is no longe use ul, because explici minimiza ion o in ec ion isks
is no aken in o accoun .
Ins ead, we aim o ob ain new insigh s in o how he pandemic equi emen s
could be handled. The i s example shows how a compu ed pool di ision can look,
while he second one a emp s o compa e ou wo di e en app oaches discussed in
Sec .4.2.2 o handling Co id-19 anspo s.
In a pool di ision, he i s and second pools con ain ehicles ha anspo ei he
only Co id-19 pa ien s o no Co id-19 pa ien s a all. Floa e ehicles make up a
hi d pool. We e alua e he esul s and de ise a s a egy o implemen ing his pool
di ision in p ac ice.
Example 2 (Dis ibu ion o ehicles in an op imized pool di ision)
We ha e collec ed all in o ma ion abou anspo s ha ook place in some coun y
be ween 1s Janua y, 2020 and 30 h June, 2021. The pe cen age o Co id-19 ans-
po s is qui e low, as days wi h e y ew (o e en ze o) anspo s a e included. In
Table3, he pool di ision agg ega ed o e all Tuesdays is gi en. Floa e ehicles a e
mos ly used in he ea lie shi s. La e in he day, i is o en possible o use Co id-19
Table 2 (con inued) ID (i)
i
kS a (
yi
) End
Δi
16 10:30 0 10:58 11:44 27.8051
9 10:30 11 11:03 12:30 33.8629
18 10:40 9 11:23 12:22 43.1832
1 11:00 0 11:44 12:31 44.0945
20 12:00 7 12:00 13:10 0
d24 12:33 0 12:33 13:08 0
17 15:30 2 15:30 18:21 0
599
Minimizing delays o pa ien anspo s wi hincomple e…
ehicles. This migh be caused by a highe numbe o anspo s in he mo ning, as
discussed in Sec .1.
We can gain an in ui ion which ehicles a e a good choice o ixed Co id-19
ehicles using such ables. Depending on he numbe o Co id-19 anspo s on one
day, some o hese ehicles should be assigned o he Co id-19 ehicle pool. Simila
peculia i ies a e ob ained o di e en combina ions o coun ies and weekdays.
Because he exac dis ibu ion o anspo s, i.e., how many in ec ed pa ien s
should be anspo ed, is no known in ad ance, i is help ul o decide on he numbe
o ehicles o each pool depending on he cu en numbe o Co id-19 cases. We
assumed p e iously in Sec .1 ha hese numbe s can ha e a high co ela ion. Fu -
he mo e, i can be help ul o hold an addi ional loa e ehicle in ese e o allow
o any disc epancies.
We now compa e he wo op ions o handling Co id-19 anspo s ha ha e been
discussed in Sec .4.2.2. In o al, he e a e li le da a con aining a high pe cen age o
Co id-19 anspo s. Thus, we conside an example ha yields he same maximum
and o al delay o bo h heu is ic app oaches, bu he anspo s a e handled e y di -
e en ly depending on he app oach used. We will discuss hese di e ences conce n-
ing he ehicle lee .
Example 3 (Compa ison o he app oaches o handling Co id-19 anspo s) On
ou example day in Ap il 2020, 45 anspo s a e eques ed, 17 o which a e o
Co id-19 pa ien s. Semiplannable anspo s a e ea ed as ad hoc anspo s. Fo
he second app oach, limi ing he numbe o Co id-19 anspo s pe ehicle, we
assume ha each ehicle has wo se s o p o ec i e clo hing. In ou example, he e
a e 17 ehicles a ailable. In bo h schedules, 15 o hem a e used. In pa icula , bo h
Table 3 Op imized pools o ehicles in one example a ea and he example shi imes o Tuesdays. Fo
each shi ime, he numbe o handled anspo s, as well as he pe cen age o he alloca ion o each pool
a e gi en
Shi ime Numbe o Numbe o
ehicles
Co id-19 ans-
po s (%)
Non-Co id ehi-
cles (%)
Floa e
ehicles
(%)
06:00–14:00 1 189 2.9 94.2 2.9
07:00–15:00 1 191 1.5 91.2 7.3
08:00–16:00 1 161 2.9 90.0 7.1
08:30–16:30 1 135 1.5 93.9 4.6
09:00–17:00 2 237 0.8 95.2 4.0
10:00–18:00 2 128 4.6 94.3 1.1
10:30–18:30 1 119 2.9 97.1 0.0
11:00–19:00 1 37 6.7 93.3 0.0
14:00–22:00 1 69 7.3 90.9 1.8
15:00–22:00 1 14 9.1 90.9 0.0
16:00–24:00 1 20 10.5 89.5 0.0
22:00–06:00 1 9 0.0 100.0 0.0
600
D.Adelhü e e al.
app oaches use he same ehicles. Those wi h a shi ea ly in he mo ning a e no
equi ed because no anspo is eques ed.
I we minimize he numbe o Co id-19 ehicles used, h ee o he i een ehi-
cles a e Co id-19 ehicles, wi h i e addi ional ehicles se ing as loa e ehicles.
The e a e ou Co id-19 and six loa e ehicles in he o he case. Because he num-
be o anspo s i can handle is limi ed, a la ge pool is equi ed (and no penal-
ized). In ac , when minimizing he numbe o Co id-19 ehicles, some Co id-19
and loa e ehicles ca y ou a leas h ee Co id-19 anspo s, which is ha dly
penalized when dis ibu ing he clo hing equally.
One hing ha s ands ou in bo h schedules is ha e e y ehicle ha anspo s
any in ec ed pa ien ends i s shi wi h all anspo s o in ec ed pe sons. As a
esul , he penal y
𝛾change
is ne e applied. The ac ha his is possible wi h bo h
app oaches and also esul s in a ela i ely sho delay is a posi i e esul in e ms o
educing in ec ion isks. The longes delays occu la e in he e ening and canno be
a oided e en i we do no include any Co id-19 equi emen s aside om inc easing
anspo du a ion. This is due o a lack o a ailable ehicles a he same ime.
To summa ize, bo h app oaches ha e ad an ages and p oduce simila esul s
especially when he numbe o Co id-19 anspo s is ela i ely low in p ac ice. Fo
example, he amoun o p o ec i e clo hing a ailable may in luence he dispa che ’s
app oach. As his numbe g ows, he need o conside his limi a ion diminishes and
he dispa che s’ ocus may shi o minimizing con ac be ween in ec ed and non-
in ec ed pa ien s and d i e s. Ano he possibili y is o combine bo h app oaches,
dis ibu ing p o ec i e clo hing o all ehicles bu p o iding mo e o hose ha a e
likely o ha e mo e Co id-19 anspo s. A lee di ision, such as he one p e iously
men ioned, could be use ul in his ega d.
6 Conclusion and u u e esea ch
In his wo k, we ha e p oposed a solu ion app oach o scheduling pa ien anspo s
ha a e no escue anspo s. In o ma ion abou hese anspo s can be incomple e
and may only be pa ly known se e al hou s be o e hey a e equi ed. Ou objec i e
is minimizing he delay o pa ien s in a ai manne while espec ing shi imes.
We apply a VRPGTW o mula ion ha can hen be sol ed by s a e-o - he-a MIP
sol e s.
We implemen ed he MIP o mula ion o he cases o ull and incomple e in o -
ma ion. We classi y equi ed anspo s in o plannable anspo s ( ull in o ma ion),
semiplannable anspo s (almos ull in o ma ion bu he a ge ime is unknown)
and ad hoc anspo s (no in o ma ion abou he anspo a all). Ad hoc anspo s
a e inco po a ed by an i e a i e algo i hm ha sol es Model (4a) e e y ime ha
ull in o ma ion abou a anspo becomes known. Semiplannable anspo s can, on
he one hand, be ea ed like ad hoc anspo s o , on he o he hand, by in oducing
dummy anspo s wi h an es ima ed a ge ime. When using he second app oach,
hey a e ea ed like plannable anspo s. We ha e compa ed ou modeling app oach

601
Minimizing delays o pa ien anspo s wi hincomple e…
o he cu en scheduling p ac ice o he dispa che . The eby, we ha e exempla ily
obse ed ha he wai ing imes in he op imized schedules a e signi ican ly lowe
han hose ob ained ia a simula ion o he cu en scheduling p ac ice. To inco -
po a e semiplannable anspo s whe e signi ican imp o emen s can be seen, we
equi e mo e da a ha includes such anspo s. Using he cu en da a, we we e
only able o elabo a e on some examples.
We ha e ex ended he model so ha Co id-19 anspo s can be handled by
di e en ehicle lee s. S ill, he model emains sol able in eal ime and can be
sol ed wi h MIP-based algo i hms. We ha e ou lined algo i hmic app oaches,
which speed up he solu ion p ocess.
In summa y, we ha e p oposed a o mula ion o he scheduling p oblem o
pa ien anspo s ha can be used in p ac ice, also wi h u he ex ensions o he
pandemic si ua ion. Howe e , ex ensions a e no limi ed o his applica ion. We
a e able o dec ease he delays o pa ien s. Fu he , we can adhe e o d i e s’
shi imes mo e o en han a simula ion o he eali y can, while, in almos all
ins ances, e en p ese ing smalle delays. Wi h he a ailabili y o mo e da a, i is
expec ed ha he p oposed app oach will wo k e en be e .
Se e al esea ch di ec ions a e o in e es o he u u e. As al eady men ioned,
he usage o mul i-objec i e op imiza ion migh be help ul as we ha e con lic -
ing goals, e.g. minimizing delays and adhe ing o shi imes. Ano he po en ial
o imp o emen lies in inco po a ing semiplannable anspo s, whe e—assum-
ing mo e da a is a ailable—o he me hods, e.g., u he es ima ions o he du a-
ion and a ge ime o anspo s, can be implemen ed. Fu he mo e, he usage
o dummy nodes can be ex ended, so ha hey can be c ea ed o mo e ypes o
anspo han hose p esen ed he e o dialysis. Ou app oach can also be ans-
e ed o di e en scheduling o ou ing p oblems.
Acknowledgemen s We a e g a e ul o con inuous suppo om he ILS, Nu embe g, and o many
ui ul and s imula ing discussions wi h D .Ma c Gis icho sky and Ludwig Fuchs (bo h ILS). Resea ch
epo ed in his pape was suppo ed by p ojec Heal hFaCT unde BMBF g an 05M16WEC. Fu he -
mo e, his pape has ecei ed unding om he Eu opean Union’s Ho izon 2020 esea ch and inno a-
ion p og am unde he Ma ie Skłodowska-Cu ie g an ag eemen No 764759. The au ho s g a e ully
acknowledge he scien i ic suppo and HPC esou ces p o ided by he E langen Na ional High Pe o -
mance Compu ing Cen e (NHR@FAU) o he F ied ich-Alexande -Uni e si ä E langen-Nü nbe g
(FAU). The ha dwa e is unded by he Ge man Resea ch Founda ion (DFG).
Au ho con ibu ions No applicable.
Funding Open Access unding enabled and o ganized by P ojek DEAL. Resea ch epo ed in his pape
was suppo ed by p ojec Heal hFaCT unde BMBF g an 05M16WEC. Fu he mo e, his pape has
ecei ed unding om he Eu opean Union’s Ho izon 2020 esea ch and inno a ion p og am unde he
Ma ie Skłodowska-Cu ie g an ag eemen No 764759.
Da a a ailibili y No applicable.
Code a ailibili y No applicable.
Decla a ions
Con lic o in e es The e a e no Con lic o in e es .
602
D.Adelhü e e al.
E hics app o al No applicable.
Consen o pa icipa e No applicable.
Consen o publica ion No applicable.
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, Koch T, Ma in A (2005) B anching ules e isi ed. Ope Res Le 33(1):42–54
Allen M, Bhanji A, Willemsen J, Dud ield S, Logan S, Monks T (2020) A simula ion modelling oolki
o o ganising ou pa ien dialysis se ices du ing he co id-19 pandemic. PLoS One 15(8):1–13
Beaud y A, Lapo e G, Melo T, Nickel S, Jeppesen AB, Lapo e G, Melo T, Nickel S (2010) Dynamic
anspo a ion o pa ien s in hospi als. OR Spec um 32(1):77–107
Bek as T, Repoussis PP, Ta an ilis, CD (2014) Chap e  11: dynamic ehicle ou ing p oblems, pp
299–347
Be beglia G, Co deau J-F, Lapo e G (2010) Dynamic pickup and deli e y p oblems. Eu J Ope Res
202(1):8–15
Be han E, Beshah B, Ki aw D, Ab aham A (2014) S ochas ic ehicle ou ing p oblem: a li e a u e su ey.
J In Knowl Manag 13:10
Be simas D, Jaille P, Ma in S (2019) Online ehicle ou ing: he edge o op imiza ion in la ge-scale
applica ions. Ope Res 67(1):143–162
Be simas DJ, an Ryzin G (1991) A s ochas ic and dynamic ehicle ou ing p oblem in he Euclidean
plane. Ope Res 39:601–615
Bes uzhe a K, Besançon M, Chen WK, Chmiela A, Donkiewicz T, an Doo nmalen J, Ei le L, Gaul
O, Gam a h G, Gleixne A, Go wald L, G aczyk C, Halbig K, Hoen A, Hojny C, an de Huls R,
Koch T, Lübbecke M, Mahe SJ, Ma e F, Mühme E, Mülle B, P e sch ME, Reh eld D, Schlein
S, Schlösse F, Se ano F, Shinano Y, So anac B, Tu ne M, Vige ske S, Wegscheide F, Wellne P,
Weninge D, Wi zig J (2021) The SCIP Op imiza ion Sui e 8.0. ZIB-Repo 21-41, Zuse Ins i u e,
Be lin
Chen D, Pan S, Chen Q, Liu J (2020) Vehicle ou ing p oblem o con ac less join dis ibu ion se ice
du ing co id-19 pandemic. T ansp Res In e discip Pe spec 8:100233
Chen Z-L, Xu H (2006) Dynamic column gene a ion o dynamic ehicle ou ing wi h ime windows.
T ansp Sci 40(1):74–88
Co deau JF, Desaulnie s G, Des osie s J, Solomon MM, Soumis, F (2002) VRP wi h Time Windows
Co deau JF, Lapo e G, Po in JY, Sa elsbe gh MW (2007) T anspo a ion on demand. Handbooks Ope
Res Manag Sci 14:429–466
Co deau JF, Lapo e G, Sa elsbe gh MW, Vigo D (2007) Vehicle ou ing. Handbooks Ope Res Manag
Sci 14:367–428
Dan zig GB, Ramse JH (1959) The uck dispa ching p oblem. Manage Sci 6(1):80–91
Doe ne KF, Ha l RF (2008) Heal h ca e logis ics, eme gency p epa edness, and disas e elie : New
challenges o ou ing p oblems wi h a ocus on he aus ian si ua ion. In: Golden B, Ragha an S,
Wasil E (eds) The ehicle ou ing p oblem: la es ad ances and new challenges. Sp inge , Bos on,
pp 527–550
Eh go M (2005) Mul ic i e ia op imiza ion. Sp inge -Ve lag, Be lin, Heidelbe g
603
Minimizing delays o pa ien anspo s wi hincomple e…
Fe ucci F, Bock S, Gend eau M (2013) A p o-ac i e eal- ime con ol app oach o dynamic ehicle
ou ing p oblems dealing wi h he deli e y o u gen goods. Eu J Ope Res 225(1):130–141
Fiegl C, Pon ow C (2009) Online scheduling o pick-up and deli e y asks in hospi als. J Biomed In o m
42:624–632
Fla be g T, Hasle G, Klos e O, Nilssen EJ, Riise A (2007) Dynamic and s ochas ic ehicle ou ing in
p ac ice. Ope Res/Compu Sci In e aces Se ies 38:41–63
Gamchi NS, To abi SA, Jolai F (2021) A no el ehicle ou ing p oblem o accine dis ibu ion using si
epidemic model. OR Spec um 43:155–188
Gend eau M, Gue in F, Po in J-Y, Tailla d E (1999) Pa allel abu sea ch o eal- ime ehicle ou ing
and dispa ching. T ansp Sci 33(4):381–390
Gend eau M, Lapo e G, Seme F (2001) A dynamic model and pa allel abu sea ch heu is ic o eal-
ime ambulance eloca ion. Pa allel Compu 27(12):1641–1653
Gu obi Op imiza ion, LLC (2021) Gu obi Op imize Re e ence Manual
Hansha FT, Ombuki-Be man BM (2007) Dynamic ehicle ou ing using gene ic algo i hms. Appl In ell
27:89–99
Ho SC, Sze o WY, Kuo YH, Leung JM, Pe e ing M, Tou TW (2018) A su ey o dial-a- ide p oblems:
li e a u e e iew and ecen de elopmen s. T ansp Res Pa B: Me hodol 111:395–421
Hulsho PJ, Ko beek N, Bouche ie RJ, Hans EW, Bakke PJ (2012) Taxonomic classi ica ion o planning
decisions in heal h ca e: a s uc u ed e iew o he s a e o he a in o /ms. Heal h Sys 1:129–175
Iba aki T, Imaho i S, Kubo M, Masuda T, Uno T, Yagiu a M (2005) E ec i e local sea ch algo i hms o
ou ing and scheduling p oblems wi h gene al ime-window cons ain s. T ansp Sci 39(2):206–232
Ke gosien Y, Len é C, Pi on D, Billau J-C (2011) A abu sea ch heu is ic o he dynamic anspo a ion
o pa ien s be ween ca e uni s. Eu J Ope Res 214(2):442–452
Kim G, Ong YS, Cheong T, Tan PS (2016) Sol ing he dynamic ehicle ou ing p oblem unde a ic
conges ion. IEEE T ans In ell T ansp Sys 17:2367–2380
Kim S, Lewis ME, Whi e CC (2005) Op imal ehicle ou ing wi h eal- ime a ic in o ma ion. IEEE
T ans In ell T ansp Sys 6:178–188
Kok AL, Hans EW, Schu en JM (2012) Vehicle ou ing unde ime-dependen a el imes: he impac o
conges ion a oidance. Compu Ope Res 39:910–918
Land AH, Doig AG (2010) An au oma ic me hod o sol ing disc e e p og amming p oblems. In: Jünge
M, Liebling TM, Nadde D, Nemhause GL, Pulleyblank WR, Reinel G, Rinaldi G, Wolsey LA
(eds) 50 Yea s o In ege P og amming 1958–2008: F om he Ea ly Yea s o he S a e-o - he-A .
Sp inge , Be lin Heidelbe g, pp 105–132
Lei häuse N, Adelhü e D, B aun K, Büsing C, Comis M, Ge sing T, Johann S, Kos e AMCA, K umke
SO, Lie s F, Schmid E, Schneide J, S eiche M, Tschuppik S, W ede S (2022) Decision-suppo
sys ems o ambula o y ca e, including pandemic equi emen s: using ma hema ically op imized
solu ions. BMC Med In Decis Making 22:132
Madsen OB, Ra n HF, Rygaa d JM (1965) A heu is ic algo i hm o a dial-a- ide p oblem wi h ime win-
dows, mul iple capaci ies, and mul iple objec i es. Ann Ope Res 60:193–208
Ma golis JT, Song Y, Mason SJ (2022) A Ma ko decision p ocess model on dynamic ou ing o a ge
su eillance. Compu Ope Res 141:105699
Melach inoudis E, Ilhan AB, Min H (2007) A dial-a- ide p oblem o clien anspo a ion in a heal h-
ca e o ganiza ion. Compu Ope Res 34(3):742–759
Mi o ić-Minić S, Lapo e G (2004) Wai ing s a egies o he dynamic pickup and deli e y p oblem wi h
ime windows. T ansp Res Pa B: Me hodol 38:635–655
Oyola J, A n zen H, Wood u DL (2017) The s ochas ic ehicle ou ing p oblem, a li e a u e e iew, pa
II: solu ion me hods. EURO J T ansp Logis 6:349–388
Oyola J, A n zen H, Wood u DL (2018) The s ochas ic ehicle ou ing p oblem, a li e a u e e iew, pa
I: models. EURO J T ansp Logis 7:193–221
Pacheco J, Laguna M (2020) Vehicle ou ing o he u gen deli e y o ace shields du ing he co id-19
pandemic. Jou nal o Heu is ics 26(5):619–635
Pa agh SN, Co deau J-F, Doe ne KF, Ha l RF (2010) Models and algo i hms o he he e ogeneous
dial-a- ide p oblem wi h d i e - ela ed cons ain s. OR Spec um 34:593–633
Pillac V, Gend eau M, Gué e C, Medaglia AL (2013) A e iew o dynamic ehicle ou ing p oblems.
Eu J Ope Res 225(1):1–11
Psa a is HN, Wen M, Kon o as CA (2016) Dynamic ehicle ou ing p oblems: h ee decades and coun -
ing. Ne wo ks 67(1):3–31
604
D.Adelhü e e al.
Ri zinge U, Puchinge J, Ha l RF (2015) A su ey on dynamic and s ochas ic ehicle ou ing p oblems.
In J P od Res 54:215–231
Robe Koch Ins i u e (2020) Co ona i us disease 2019 (co id–19) – daily si ua ion epo o he Robe
Koch Ins i u e
Sa aşe SK, Ka a BY (2022) Mobile heal hca e se ices in u al a eas: an applica ion wi h pe iodic loca-
ion ou ing p oblem. OR Spec um 44:875–910
Schilde M, Doe ne KF, Ha l RF (2014) In eg a ing s ochas ic ime-dependen a el speed in solu ion
me hods o he dynamic dial-a- ide p oblem. Eu J Ope Res 238:18–30
Secomandi N, Ma go F (2008) Reop imiza ion app oaches o he ehicle- ou ing p oblem wi h s ochas-
ic demands. Ope Res 57:214–230
Soe ke N, Ulme MW, Ma eld DC (2022) S ochas ic dynamic ehicle ou ing in he ligh o p esc ip-
i e analy ics: a e iew. Eu J Ope Res 298:801–820
Thomas BW (2007) Wai ing s a egies o an icipa ing se ice eques s om known cus ome loca ions.
T ansp Sci 41:319–331
Ulme MW, Goodson JC, Ma eld DC, Thomas BW (2017) Dynamic ehicle ou ing: Li e a u e e iew
and modeling amewo k
Ulme MW, Goodson JC, Ma eld DC, Thomas BW (2020) On modeling s ochas ic dynamic ehicle
ou ing p oblems. EURO J T ansp Logis 9:100008
an den Be g PL, an Essen JT (2019) Scheduling non-u gen pa ien anspo a ion while maximizing
eme gency co e age. T ansp Sci 53(2):492–509
Vidal T, Lapo e G, Ma l P (2020) A concise guide o exis ing and eme ging ehicle ou ing p oblem
a ian s. Eu J Ope Res 286:401–416
Vigo D, To h P (eds) (2014) Vehicle Rou ing. SIAM, Philadelphia, PA
Wang A, Sub amanyam A, Gouna is CE (2021) Robus ehicle ou ing unde unce ain y ia b anch-
p ice-and-cu . Op im Eng 23:1895–1948
Wolsey LA (2020) Mixed in ege p og amming. John Wiley & Sons, L d, Hoboken, pp 1–10
Wolsey LA, Nemhause GL (1999) In ege and combina o ial op imiza ion. John Wiley & Sons, L d,
Hoboken
Yu X, Gao S, Hu X, Pa k H (2019) A Ma ko decision p ocess app oach o acan axi ou ing wi h
e-hailing. T ansp Res Pa B: Me hodol 121:114–134
Yu X, Shen S, Wang H (2021) In eg a ed ehicle ou ing and se ice scheduling unde ime and cancella-
ion unce ain ies wi h applica ion in noneme gency medical anspo a ion. Se Sci 13(3):172–191
Zhang J, Liu F, Tang J, Li Y (2019) The online in eg a ed o de picking and deli e y conside ing pick-
e s’ lea ning e ec s o an O2O communi y supe ma ke . T ansp Res Pa E: Logis T ansp Re
123:180–199
Zhang J, Wang X, Huang K (2017) On-line scheduling o o de picking and deli e y wi h mul iple zones
and limi ed ehicle capaci y. Omega 79:104–115
Zhang Y, Zhang Z, Lim A, Sim M (2021) Robus da a-d i en ehicle ou ing wi h ime windows. Ope
Res 69:469–485
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.