Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem

Ye, Jinwen; Pan uso, Gio anni; Pisinge , Da id
A icle
O de dispa ching and acan ehicles ebalancing o he
i s -mile ide-sha ing p oblem
EURO Jou nal on T anspo a ion and Logis ics (EJTL)
P o ided in Coope a ion wi h:
Associa ion o Eu opean Ope a ional Resea ch Socie ies (EURO), F ibou g
Sugges ed Ci a ion: Ye, Jinwen; Pan uso, Gio anni; Pisinge , Da id (2024) : O de dispa ching and
acan ehicles ebalancing o he i s -mile ide-sha ing p oblem, EURO Jou nal on T anspo a ion
and Logis ics (EJTL), ISSN 2192-4384, Else ie , Ams e dam, Vol. 13, Iss. 1, pp. 1-19,
h ps://doi.o g/10.1016/j.ej l.2024.100132
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/325206
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h ps://c ea i ecommons.o g/licenses/by-nc-nd/4.0/
Con en s lis s a ailable a ScienceDi ec
EURO Jou nal on T anspo a ion and Logis ics
jou nal homepage: www.else ie .com/loca e/ej l
O de dispa ching and acan ehicles ebalancing o he i s -mile
ide-sha ing p oblem
Jinwen Ye a,∗, Gio anni Pan uso a, Da id Pisinge b
aUni e si y o Copenhagen, Copenhagen, Denma k
bTechnical Uni e si y o Denma k, Copenhagen, Denma k
ARTICLE INFO
Keywo ds:
Fi s -mile
Ride-sha ing
O de dispa ching
Rebalancing
Rolling ho izon
ABSTRACT
Gi en a se o anspo eques s o a ansi s a ion and a se o homogeneous ehicle, bo h geog aphically
dispe sed in a business a ea, he Fi s -Mile Ride-Sha ing P oblem (FMRSP) consis s o inding leas cos ehicle
ou es o anspo passenge s o he s a ion by sha ed ides. In his pape we o mula e he p oblem as
a ma hema ical op imiza ion p oblem and s udy he e ec i eness o p e en i e mo emen s o idle ehicles
(i.e., ebalancing) in o de o an icipa e u u e demand. Tha is, we iden i y p omising ebalancing loca ions
based on his o ical da a and gi e he model incen i es o assign ehicles o such loca ion. We hen assess he
e ec i eness o such mo emen s by simula ing online usage o he ma hema ical model in a olling-ho izon
amewo k. The esul s show ha ebalancing is consis en ly p e e able bo h in e ms o p o i s and se ice
a e. Pa icula ly, in ope a ing con ex s whe e he s a ion is no cen ally loca ed, ebalancing mo emen s
inc ease bo h p o i s and se ice a es by a ound 30% on a e age.
1. In oduc ion
Ride-sha ing se ices, which a e linked o a educ ion o he numbe
o p i a e ca s on he oad, emissions and conges ion (Al-Abbasi e al.,
2019), ha e eme ged as a po en ial solu ion o he inc ease in oad
conges ion and ai pollu ion gene a ed by g owing u ban a eas and
popula ion (Taniguchi e al.,2014). Such se ices ha e ye signi ican
po en ial o de elopmen . As an example, acco ding o he NYC axicab
da a (Commission and Limousine,2023), du ing Janua y 2020 he e
we e 363,874 axi ips o he Pennsyl ania S a ion, a ai ly busy ansi
s a ion in New Yo k Ci y see Fig. 1(a), ha is, on a e age 12,129 axis
ips daily o he s a ion. O hese, only 6% we e sha ed by mul iple
passenge s, see Fig. 1(b), which lea es signi ican ma gins o mo e
e icien connec ions o he s a ion.
An e ec i e implemen a ion o ide-sha ing se ices equi es ad-
equa e esponses o po en ially equen changes in demand pa e ns
du ing he day ha may de e mine geog aphical misma ches be ween
demand as supply. Fig. 2 illus a es he loca ion o he eques s o ans-
po a ion o Pennsyl ania S a ion du ing Janua y 2014, showing ha
he majo i y o he eques s a i e om he No h-Eas a ea, whe eas
much ewe eques s a i e om he emaining zones o he ci y.
This sugges s implemen ing mechanisms ha p epa e he geog aphical
dis ibu ion o he lee in such a way o an icipa e demand and pe haps
educe wai ing and esponse imes as well as se ice a e.
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (J. Ye), [email p o ec ed] (G. Pan uso), [email p o ec ed] (D. Pisinge ).
The exis ing li e a u e s udy a ious aspec s o ide-sha ing se ices,
including p icing mechanisms (Bian and Liu,2019b,a;Bian e al.,
2020;Chen and Wang,2018), in eg a ion wi h public anspo (Shen
e al.,2018), o de dispa ching and ehicle ou es (Wang,2019;Chen
e al.,2020). Con e sely, s a egies o an icipa ing demand h ough,
e.g. p e en i e o ebalancing mo emen s (Wen e al.,2018), emain,
o a la ge ex en , an open esea ch ques ion. Pa icula ly, e icien
ways o simul aneously de e mine bo h dispa ching and ebalancing
mo emen s ha e, o he bes o ou knowledge, been neglec ed.
We con ibu e o illing his gap by p o iding a ma hema ical p o-
g amming model o join o de dispa ch and ebalancing decisions
in a i s -mile ide-sha ing se ice which anspo s passenge s om
hei ini ial loca ion o a common des ina ion (e.g., a ansi s a ion).
We will e e o his decision p oblem as he Fi s -Mile Ride-Sha ing
P oblem (FMRSP). In addi ion, we p opose a s a egy o iden i ying
p omising loca ions whe e o ebalance emp y ehicles. The model and
ebalancing s a egies a e es ed in a olling-ho izon amewo k which
simula es on-line usage.
The es o his pape is s uc u ed as ollows. In Sec ion 2we e iew
he ela ed li e a u e and unde line he con ibu ion o his a icle. In
Sec ion 3we o mally in oduce he p oblem and he co esponding
ma hema ical p og amming model. In Sec ion 4we desc ibe wo me h-
ods o deciding whe e o eloca e ehicles in an icipa ion o u u e
h ps://doi.o g/10.1016/j.ej l.2024.100132
Recei ed 9 Ma ch 2023; Recei ed in e ised o m 13 Ma ch 2024; Accep ed 26 Ma ch 2024
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
A ailable online 28 Ma ch 2024
2192-4376/© 2024 The Au ho (s). Published by Else ie B.V. on behal o Associa ion o Eu opean Ope a ional Resea ch Socie ies (EURO). This is an open access
a icle unde he CC BY-NC-ND license (
h p://c ea i ecommons.o g/licenses/by-nc-nd/4.0/ ).
J. Ye e al.
Fig. 1. Taxi ips o Penn S a ion. Da a om Commission and Limousine (2023).
Fig. 2. Dis ibu ion o ips o Penn S a ion.
demand. In Sec ion 5we desc ibe he simula ion amewo k and he
nume ical expe imen s we pe o med wi h he model and illus a e he
esul s. Finally, we d aw conclusions in Sec ion 6.
2. Li e a u e e iew
The ou ing decisions conside ed in he FMRSP sha e simila i ies
wi h hose in ol ed in well s udied ou ing p oblems. Among hese
we ind he Vehicle Rou ing P oblem (VRP). S a ing om he seminal
pape o Dan zig and Ramse (1959), se e al exac and heu is ics
algo i hms we e p oposed o sol e VRPs (B äysy and Gend eau,2005;
Be simas e al.,2019;To h and Vigo,2002) and se e al la o s o
he p oblem ha e been s udied, see e.g., he su eys (Kuma and Pan-
nee sel am,2012;Pillac e al.,2013;Lin e al.,2014;Ri zinge e al.,
2016;B aeke s e al.,2016). One o he majo di e ences be ween he
FMRSP and he di e en a ian s o he VRP is ha VRPs ypically
consis o designing ou s e u ning o he depo , while he FMRSP
designs open pa hs om he ehicle’s o igins o a common des ina ion.
A guably, a ( a ian o he) VRP would esemble mo e closely a las -
mile ide-sha ing p oblem whe e a ehicle depa s and e u ns o he
s a ion isi ing he des ina ions o a numbe o cus ome s. Fu he mo e,
FMRSPs ocus on anspo ing cus ome s om mul iple loca ions o
he des ina ion (s a ion) while VRPs a e ypically conce ned wi h he
deli e y o goods o cus ome s. This impac s he ypes o es ic ions
imposed on he ou es.
Pa icula ly, he FMRSP sha es ea u es wi h he Dial-a- ide P oblem
(DARP) and he Pick-up-and-deli e y P oblem (PDP) (Co deau and
Lapo e,2003;Ropke and Co deau,2009;Be beglia e al.,2010), which
a e gene aliza ions o he VRP. A comp ehensi e e iew o DARP and
PDP can be ound in Ho e al. (2018). The goal o he DARP is o
minimize he cos / ime o anspo a se o passenge by means o
a ixed lee o ehicles. Reques s ha e di e en pickup and deli e y
loca ions, and he ehicles can pick up mo e han one passenge s a a
ime. Also o he DARP di e en a ian s can be ound, such as whe e
he objec i e is o minimize he de ou o he cus ome s on boa d he
ehicles (P ei e and Schulz,2022). The DARP can be conside ed as
a a ian o he PDP. The PDP ypically deals wi h he anspo a ion
o goods while he DARP deals wi h passenge anspo a ion (Pa agh
e al.,2008). Thus, he di e ence be ween DARP and PDP is usually
exp essed in e ms o addi ional cons ain s o objec i es ha explici ly
ake use (in)con enience in o accoun (e.g., ime window and ehicle
capaci y cons ain s). The FMRSP can be seen as a special case o
DARP whe e passenge s a el o a common depo (s a ion) and wi h
addi ional se ice-speci ic cons ain s. In pa icula , he FMRSP akes
he desi ed a i al ime o accep ed cus ome s as cons ain s. This, in
u n, implici ly shapes easible ime window o he o he cus ome s
on boa d he same ehicle and o he newly a i ed cus ome s in a
olling ho izon op imiza ion amewo k. Pa icula ly, in his pape , we
s udy on-line dispa ch and ebalancing decisions. Tha is, we conside
he alloca ion o cus ome s eques s o ehicles as hey a i e and
while ehicles a e busy wi h o he anspo a ion eques s. This en ails
dealing wo ypes o cus ome s. Fi s , we ind cus ome s whose eques
has been accep ed in p e ious decision epochs and ha e no ye picked
up. These cus ome s eques s mus be sa is ied. Second, we ind new
cus ome s whose eques may o may no be accep ed, simila ly o a
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
2
J. Ye e al.
Table 1
Summa y o he a ailable li e a u e. Unde ‘‘Decisions’’ we epo he main decisions add essed by he a icle. Ma ching e e s o he assignmen
o cus ome s o ehicles. Rebalancing e e s o he assignmen o ehicles o zones. Unde ‘‘Se ice’’ we use RS o a gene al ide-sha ing se ice
and FM o a i s -mile ide-sha ing se ice. Unde ‘‘Model’’ a Yes o a No indica e whe he he s udy p o ides an op imiza ion model o no .
S udy Se ice Decisions Model Me hod
Shen e al. (2018) FM Flee size, ma ching, ou ing No Simula ion
Zhao e al. (2018) RS Ma ching Yes MILP, Heu is ics
Be simas e al. (2019) RS Ma ching Yes MILP, Heu is ics
Wang e al. (2018) RS Ma ching Yes MILP, Heu is ics
Chen e al. (2020) FM Ma ching Yes MILP
Lo i and Abdelghany (2022) RS Ma ching No Heu is ics
San os and Xa ie (2015) RS Ma ching Yes MILP
El ing and Ehmke (2021) RS Ma ching Yes Cons ain Sa is ac ion P oblem
Zheng and Pan uso (2023) FM Ma ching Yes MILP, Heu is ics
Fagnan and Kockelman (2018) RS Flee size, ma ching No Simula ion
Lokhandwala and Cai (2018) RS Ma ching No Simula ion
Mao e al. (2020) RS Rebalancing Yes MILP, Rein o cemen Lea ning
No uzoliaee and Zou (2022) RS Ma ching Yes MILP
Bei igo e al. (2022) RS Ma ching Yes MILP
Bongio anni e al. (2022) RS Ma ching Yes MILP
Walla e al. (2018) RS Zone pa i ion, ebalancing o idle ehicles Yes MILP, Poisson p ocess
Wen e al. (2018) RS Rebalancing o idle ehicles No Rein o cemen lea ning
Alonso-mo a e al. (2018) RS Ma ching, ebalancing o idle ehicles NoaMILP
Saya shad and Chow (2017) RS Ma ching, ebalancing o idle ehicles Yes MINLP
Ma e al. (2019a) RS Ma ching, ebalancing o idle ehicles No Queue heo y
aThe au ho s p o ide a e bal desc ip ion o he ma hema ical model.
p ice-collec ing TSP (Balas,1989) whe e isi ing cus ome s is op ional
and p o ides a ewa d. Finally, emp y ehicles may be mo ed o
ebalancing cen e s in o de o posi ion o u u e demand.
Due o he as de elopmen o GPS echnology and widesp ead use
o sma -phones, ide-sha ing se ices enabled by mobile applica ions
ha e a ac ed b oad a en ions. Comme cial companies such as Ube
and Didi ha e implemen ed e sions o he se ice (Xu e al.,2018;
Lin e al.,2018). The a en ion o he esea ch communi y has g own
p o iding bo h op imiza ion me hods (S iglic e al.,2015;Masoud
e al.,2017;Masoud and Jayak ishnan,2017;Alonso-mo a e al.,2018;
S iglic e al.,2018;Huang e al.,2014;Wang e al.,2018;Mou ad e al.,
2019) and ein o cemen lea ning me hods (Xu e al.,2018;Lin e al.,
2018;Li e al.,2019;Tang e al.,2019;Qin e al.,2019).
The FMRSP and, in gene al, ide-sha ing p oblems a e, howe e , a
ela i ely new amily o p oblems and he co esponding li e a u e is
somewha spa se. In wha ollows we e iew he a ailable li e a u e
be o e highligh ing how ou wo k ex ends he s a e-o - he-a . The
li e a u e is also summa ized in Table 1 o he eade ’s con enience.
Shen e al. (2018) s udy he in eg a ion o a FMRS se ice based
on au onomous ehicles (AVs) wi h public anspo a ion. The idea
is o p ese e high demand bus ou es while using sha ed AVs as an
al e na i e o low demand ou es. In a simula ion amewo k hey use
simple heu is ics o ma ch passenge s o ehicles and de ine ou es.
Chen e al. (2020) p o ide a mixed-in ege linea p og amming (MILP)
model o decide he assignmen o eques g oups o AV in FMRS
se ice. The objec i e is ha o minimizing ope a ional cos s. The
au ho s de ise a clus e -based solu ion me hod o deal wi h la ge-scale
ins ances. Zhao e al. (2018) add ess he join p oblem o op imally
ma ching passenge s and ehicles and ha o ou ing each ehicle.
The p oblem is o mula ed as a PDP wi h he addi ion o space– ime
windows. Wang e al. (2018) conside a ide-sha e se ing in which
a ide-sha e p o ide ecei es ip eques s o e ime om po en ial
pa icipan s. A ip can be ei he a d i e o a ide . This p ocess
gene a es wo disjoin se s o ip eques s. The au ho s ocus on inding
a s able ma ch be ween he wo se s. Be simas e al. (2019) s udy
he p oblem o assigning cus ome s o ehicles. The au ho s include
se ice-speci ic cons ain s, including ime windows and la es ime o
accep ing o ejec ing a anspo a ion eques . The au ho s add ess
he p oblem ia pe iodic e-op imiza ion. Lo i and Abdelghany (2022)
conside a se o passenge s equi ing a ide and s udy he p oblem
o assigning passenge s o ehicles. This se o passenge s is known a
he ime he p oblem is sol ed. Passenge s a e cha ac e ized by o igin,
des ina ion, ea lies pick-up ime, la es d op-o ime and willingness o
sha e he ide. The au ho s conside wo objec i es, namely maximizing
p o i and maximizing passenge s’ a el expe ience, measu ed in e ms
o ans e s and a el imes. The p oblem is sol ed by means o a
heu is ic. In he s udy o San os and Xa ie (2015) use s decide whe he
o sha e ei he hei own ca o a axi. They speci y pickup and d op-o
loca ion, ea lies pick-up ime, la es d op-o ime and he maximum
cos ole a ed. In addi ion, ca owne s also speci y he depa u e ime
and he maximum accep ed delay. The au ho s add ess he p oblem o
ma ching use s o ehicles and o de e mining he ou es. El ing and
Ehmke (2021) assess he economic po en ial o sha ed axi se ices.
He e a se ice ope a o collec s eques s om indi idual a ele s.
Based on e e y eques ’s o igin and des ina ion as well as he desi ed
pick-up ime, he se ice p o ide ma ches ehicles and a ele s and
builds a ou e plan o each ehicle. Zheng and Pan uso (2023) conside
a FMRS se ice whe e passenge s ha e o be anspo ed o a common
des ina ion. The p oblem consis s o assigning cus ome s o ehicles
and deciding ehicle ou es. T anspo eques s may be ejec ed. The
p oblem is o mula ed as a bi-objec i e MILP whe e he wo con lic ing
objec i es a e a el cos s and se ice a es. Fagnan and Kockelman
(2018) conside an AV-based ide-sha ing se ice. They use simula ion
o ind he bes lee size. In hei simula ion hey ma ch passenge s
o AVs based on speci ic ules, such as assigning passenge s o he
nea es ehicle. Thei s udy sha es simila i ies wi h (Lokhandwala and
Cai,2018) who also p opose a simula ion s udy o quan i ying he
en i onmen al impac o ide-sha ing wi h AVs o e adi ional axis. In
hei simula ion amewo k, passenge s a e assigned o ehicles based
on a de ailed algo i hm which akes in o accoun he p e e ences o he
cus ome and looks o sui able AV ou es. No uzoliaee and Zou (2022)
s udy he p oblem o assigning he mul iple eques s ( om di e en
o igins and des ina ions) o sha ed AVs wi h he scope o a oiding
undesi ed ide en- ou e ans e s. Bei igo e al. (2022) also s udy he
assignmen o eques s o ehicles in an AV-based ide-sha ing sys em
whe e use s di e acco ding o expec a ions in e ms o esponsi eness,
eliabili y, and p i acy. The au ho s assume possible ha p i a ely
owned eelance AVs can be hi ed on sho no ice. They p opose a
mul i-objec i es MILP which op imizes ehicle occupancy, numbe o
AVs used, se ice le el iola ion, and he wai ing imes. Bongio anni
e al. (2022) also s udy he p oblem o assigning passenge s o AVs.
They p opose a wo-phase heu is ic which assigns new eques s AVs
and subsequen ly e-op imizes such assignmen s h ough in a- and
in e - ehicle ou e mo es.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
3
J. Ye e al.
A numbe o s udies add ess he p oblem o ebalancing ehicles.
Wen e al. (2018) p opose a ein o cemen lea ning me hod o mo e
idle ehicles in a sha ed mobili y-on-demand sys ems. They es hei
solu ion me hod on a i s -mile ide-sha ing se ice in he ci y o
London. Mao e al. (2020) conside a axi sha ing sys ems wi h AVs.
They s udy he p oblem o de e mining he numbe o AVs o send om
a zone o he ci y o ano he in o de o minimize he expec ed cos o
eposi ioning AVs. They compa e a ein o cemen lea ning algo i hm
wi h an in ege p og amming model ha assumes ull knowledge o
u u e demand. Walla e al. (2018) p opose algo i hms o pa i ioning
he ope a ing a ea in o zones, es ima ing he eal- ime demand and
ebalancing idle ehicles. Saya shad and Chow (2017) p opose a queue-
based model o ma ching and ebalancing decisions. They assume
ha he numbe o idle ehicles is known in ad ance. Alonso-mo a
e al. (2018) design a ma ching algo i hm o on-demand ide-sha ing.
The me hod inco po a es ebalancing decisions o idle ehicles. The
au ho s desc ibe a MILP o mula ion o he p oblem and sol e he
p oblem ia a specialized p ocedu e ha begins by assigning passenge s
o ehicles and inding easible ips, and e mina es by ebalancing
idle ehicles. Ma e al. (2019a) s udy a mo e in ol ed sys em in which
a ide-sha ing lee is ope a ed join ly wi h public anspo se ices in
o de o a ange comple e on-demand jou neys o hei cus ome s. The
au ho s conside also he ebalancing o idle ehicles. They p opose a
queueing- heo e ic model o he p oblem.
As i is e iden in Table 1, he a ailable li e a u e has ypically
add essed ma ching decisions (i.e., he assignmen o passenge s o
ehicles) and ebalancing decisions (i.e., he assignmen o ehicles
o zones) sepa a ely. Fu he mo e, when ebalancing decisions a e
add essed, hey conce n mainly idle ehicles, ha is ehicles which
ha e no been dispa ched o cus ome eques s. Thus, ma ching and
ebalancing decisions ha e been unde s ood as sequen ial decisions.
Fi s , ehicles ma ch cu en eques s, hen he emaining ones may
be ebalanced. Finally, i is possible o no ice ha no all a icles ha
s udy ebalancing decisions p o ide an op imiza ion model o ha . We
ex end he s a e-o - he-a in he ollowing ways:
1. We add ess ma ching, ou ing and ebalancing decisions simul-
aneously. This en ails ha we do no necessa ily ebalance only
idle ehicles. In ou app oach, ehicles may mo e o p omising
demand a eas in ad ance, e en i his en ails gi ing up he p o i
o a cu en eques .
2. We conside online op imiza ion wi h binding accep ance o
anspo a ion eques s. This en ails ha a subse o he cus-
ome s ( hose whose eques has been accep ed in p e ious
decision p oblems) mus be se iced, while he emaining cus-
ome s ( hose newly a i ed) may be picked up i easible and
p o i able. A side e ec o his is ha p e iously and newly
accep ed cus ome s ha e an impac on he ime window o he
ehicle.
3. Fo his p oblem we p o ide an explici ma hema ical model.
The model includes se ice-speci ic cons ain s such as max-
imum wai ing ime, la es a i al ime, and he necessi y o
ul illing binding accep ance o anspo eques s.
4. We p opose simple echniques o iden i y p omising loca ions
whe e o ebalance.
5. We es ou model in a olling-ho izon simula ion amewo k
wi h pe iodic e-op imiza ion based on andomly gene a ed in-
s ances o assess he solu ions deli e ed by he model and,
pa icula ly, he ad an age p o ided by ebalancing ac i i ies.
I mus be no ed ha ebalancing decisions ha e been ex ensi ely
s udied in o he eme ging p oblems in sha ed mobili y. These include
ca sha ing (Illgen and Höck,2019;Folkes ad e al.,2020;Pan uso,
2022), bike sha ing (Faghih-Imani e al.,2017;Liu e al.,2016;Chemla
e al.,2013), scoo e sha ing (Oso io e al.,2021). Ne e heless, he e-
loca ion p oblem in ol ed is signi ican ly di e en . In he ide-sha ing
p oblem, a ehicle has o d i e (wi h i s own d i e ) o a mo e p omis-
ing loca ion. In he o he ehicle-sha ing p oblems, ehicles ha e o be
picked up by d i e s o se ice ehicles o be mo ed o mo e p omising
loca ions. The amoun o wo k in he la e is ypically much highe
and he eloca ion p oblem alone may in ol e complex op imiza ion
p oblems. Simila i ies may eme ge in he me hods used o p edic
demand occu ence. Howe e , we belie e he me hods p oposed a e no
immedia ely applicable due o he inhe en di e ences in he sys ems
and ypes o demand.
3. The i s -mile ide-sha ing p oblem
In his sec ion, we o mally in oduce he Fi s -Mile Ride-Sha ing
P oblem. We s a , in Sec ion 3.1, by p o iding a gene al in oduc ion
o he p oblem. Following, in Sec ion 3.2, we in oduce a ma hema ical
model o he FMRSP. In addi ion, in Appendix A we p o ide a able
ha summa izes he no a ion and in Appendix B we p o ide a simple
example ha illus a es possible easible solu ions o he p oblem.
3.1. P oblem s a emen
We conside he ope a o o a lee o ehicles 𝒦∶= {1,…, 𝐾}
conce ned wi h dispa ch and eloca ion decisions in o de o ensu e a
i s -mile ide-sha ing se ice. The lee is homogeneous wi h capaci y
𝑄. We assume he ope a o makes dispa ch and eloca ions decisions
pe iodically, e.g., e e y 5 o 10 min, as a esul o he a i al o
new anspo a ion eques s. We e e o hese decision imes as ‘‘( e)-
op imiza ion phases’’. A each e-op imiza ion phase, he a ailable
cus ome s can be pa i ioned in wo se s, namely 𝒩𝑃∶= {1,…, 𝑁𝑃}
which con ains he cus ome s whose anspo a ion eques had al-
eady been accep ed du ing a p e ious op imiza ion phase, and 𝒩𝐶∶=
{1,…, 𝑁𝐶}which con ains newly a i ed cus ome eques s which
ha e no been conside ed in p e ious op imiza ion phases. We assume
ha he cus ome s in 𝒩𝐶may be ei he accep ed (and hus assigned o
a ehicles) o ejec ed, while he cus ome s in 𝒩𝑃mus be picked up
( hus we assume accep ance decisions a e binding). Fo con enience
we se 𝒩𝑈∶= 𝒩𝐶∪𝒩𝑃.
All cus ome s a el o a common des ina ion 𝑑loca ed in posi ion
𝑜(𝑑)(e.g., a ansi s a ion) and o each cus ome 𝑖, he ope a o knows
he eques ed pick-up ime 𝑇𝑃
𝑖, he eques ed a i al ime 𝑇𝐴
𝑖and he
o igin 𝑜(𝑖). We le 𝛥be he maximum wai ing ime (i.e., di e ence
be ween ac ual pick-up ime and eques ed pick-up ime). Simila ly, a
he beginning o he e-op imiza ion phase, deno ed 𝑇, each ehicle
𝑘is loca ed a 𝑜(𝑘)as a esul o p e ious deploymen o eloca ion
decisions. The ehicle is ei he idle in i s loca ion, o a eling be ween
cus ome s o o he s a ion. In addi ion, ehicles migh ini ially ha e
cus ome s on boa d. We deno e 𝑉𝑘 he numbe o cus ome s on boa d
o ehicle 𝑘a he beginning o he e-op imiza ion phase and 𝑇𝑘 he
ea lies a i al ime o he passenge s al eady on boa d ehicle 𝑘.
The ope a o needs o ensu e ha ehicles wi h cus ome s on boa d
e mina e hei jou ney o he s a ion. Con e sely, ehicles wi h no
cus ome s on boa d may be sen o a ebalancing poin o s ay a hei
o igin loca ion 𝑜(𝑘). A se ℛ∶= {1,…, 𝑅}o po en ial ebalancing
poin s in he ope a ing a ea is a ailable. Fo each ebalancing poin
𝑟we le 𝐵𝑟deno e an uppe bound on he numbe o ehicles ha can
be dispa ched o he ebalancing poin .
The ope a o bea s anspo a ion cos s gene a ed by ehicle mo e-
men s. Pa icula ly, we assume a el imes a e known, wi h 𝑇𝑖𝑗 being
he a el ime be ween loca ions 𝑜(𝑖)and 𝑜(𝑗)wi h 𝑖∈𝒦∪𝒩𝑈,
𝑗∈𝒩𝑈∪ℛ∪ {𝑑}and cos 𝐶is bo n o each uni o a el ime.
The ope a o collec s a e enue 𝑃𝑖when picking up cus ome 𝑖, o
𝑖∈𝒩𝐶. No e ha he e enue is collec ed only when picking up new
cus ome s as we assume he e enue o he cus ome s in 𝒩𝑃has been
collec ed du ing p e ious op imiza ion phases. Fu he mo e, 𝐸𝑟deno es
he expec ed e enue collec ed o each ehicle eloca ed o ebalancing
cen e 𝑖∈ℛ. Pa ame e 𝐸𝑖is calcula ed as 
𝑃𝑖−𝐶𝑇𝑖𝑑 , whe e 
𝑃𝑖is he
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
4

J. Ye e al.
expec ed e enue ob ained om dispa ching a ehicle o ebalancing
cen e 𝑖∈ℛ. Expec ed u u e e enues om ebalancing ac i i ies
a e discoun ed using a pa ame e 𝛽 ha deno es he weigh o he
ebalancing ewa d.
The decisions made by he ope a o can be o malized as ollows.
We le 𝑥𝑘
𝑖𝑗 ake alue 1i ehicle 𝑘mo es di ec ly be ween 𝑜(𝑖)and 𝑜(𝑗),
0o he wise, o all 𝑖∈ {𝑘}∪𝒩𝑈, 𝑗 ∈𝒩𝑈∪ℛ∪{𝑑}, 𝑘 ∈𝒦. Fu he mo e,
we le 𝑡𝐴
𝑘deno e he ac ual a i al ime o ehicle 𝑘 o he s a ion, o
𝑘∈𝒦and 𝑡𝑃
𝑖deno e he ac ual pick-up ime o cus ome 𝑖, o 𝑖∈𝒩𝑈.
Thus, we use a 3-index o mula ion o size 𝑂(|𝒩𝐶||𝒦||ℛ|). The
FMRSP is NP-ha d, as i con ains he p ize-collec ing TSP (Balas,1989)
as a special case.
3.2. Ma hema ical model
Ha ing de ined all decision a iables and pa ame e s, we may o -
mula e he p oblem as ollows.
max ∑
𝑘∈𝒦
∑
𝑖∈𝒩𝐶
∑
𝑗∈𝒩𝑈∪{𝑑}
𝑃𝑖𝑥𝑘
𝑖𝑗 −∑
𝑖∈{𝑘}∪𝒩𝑈
∑
𝑗∈𝒩𝑈∪ℛ∪{𝑑}
∑
𝑘∈𝒦
𝐶𝑇𝑖𝑗 𝑥𝑘
𝑖𝑗
+𝛽∑
𝑖∈ℛ
∑
𝑘∈𝒦
𝑥𝑘
𝑘𝑖𝐸𝑖(1a)
s. . ∑
𝑗∈𝒩𝑈∪{𝑑}
∑
𝑘∈𝒦
𝑥𝑘
𝑖𝑗 ≤1 ∀𝑖∈𝒩𝐶
(1b)
∑
𝑗∈𝒩𝑈∪{𝑑}
∑
𝑘∈𝒦
𝑥𝑘
𝑖𝑗 = 1 ∀𝑖∈𝒩𝑃
(1c)
∑
𝑖∈𝒩𝑈∪𝒦
𝑥𝑘
𝑖𝑑 ≤1 ∀𝑘∈𝒦
(1d)
∑
𝑖∈𝒩𝑈∪{𝑘}
𝑥𝑘
𝑖𝑗 =∑
𝑖∈𝒩𝑈∪{𝑑}
𝑥𝑘
𝑗𝑖 ∀𝑗∈𝒩𝑈, 𝑘 ∈𝒦
(1e)
∑
𝑗∈ℛ∪𝒩𝑈∪{𝑑}
𝑥𝑘
𝑘𝑗 =∑
𝑗∈𝒩𝑈∪{𝑘}
∑
𝑖∈ℛ∪{𝑑}
𝑥𝑘
𝑗𝑖 ∀𝑘∈𝒦
(1 )
∑
𝑖∈{𝑘}∪𝒩𝑈
∑
𝑗∈𝒩𝑈
𝑥𝑘
𝑖𝑗 +𝑉𝑘≤𝑄∀𝑘∈𝒦
(1g)
∑
𝑘∈𝒦
𝑥𝑘
𝑘𝑗 ≤𝐵𝑗∀𝑗∈ℛ
(1h)
𝑉𝑘≤𝑄(1 − ∑
𝑗∈ℛ
𝑥𝑘
𝑘𝑗 ) ∀𝑘∈𝒦
(1i)
𝑉𝑘≤𝑄∑
𝑗∈𝒩𝑈∪{𝑑}
𝑥𝑘
𝑘𝑗 ∀𝑘∈𝒦
(1j)
𝑡𝑃
𝑖+𝑇𝑖𝑗 ≤𝑡𝑃
𝑗+𝑇𝐿(1 − ∑
𝑘∈𝒦
𝑥𝑘
𝑖𝑗 ) ∀𝑖, 𝑗 ∈𝒩𝑈
(1k)
𝑇+𝑇𝑘𝑗 ≤𝑡𝑃
𝑗+𝑇𝐿(1 − 𝑥𝑘
𝑘𝑗 ) ∀𝑗∈𝒩𝑈, 𝑘 ∈𝒦
(1l)
𝑡𝑃
𝑖−𝑇𝑃
𝑖≤𝛥∀𝑖, 𝑗 ∈𝒩𝑈
(1m)
𝑡𝐴
𝑘≤𝑇𝐴
𝑖+𝑇𝐿(1 − ∑
𝑗∈𝒩𝑈∪{𝑘}
𝑥𝑘
𝑗𝑖) ∀𝑖∈𝒩𝑈, 𝑘 ∈𝒦
(1n)
𝑡𝐴
𝑘≤𝑇𝑘∀𝑘∈𝒦
(1o)
𝑡𝑃
𝑗+𝑇𝑗𝑑 𝑥𝑘
𝑗𝑑 ≤𝑡𝐴
𝑘+𝑇𝐿(1 − 𝑥𝑘
𝑗𝑑 ) ∀𝑗∈𝒩𝑈, 𝑘 ∈𝒦
(1p)
𝑥𝑘
𝑖𝑗 ∈ {0,1} ∀𝑖∈ {𝑘} ∪ 𝒩𝑈,
𝑗∈𝒩𝑈∪ℛ∪ {𝑑}, 𝑘 ∈𝒦
(1q)
𝑡𝐴
𝑘∈R+∀𝑘∈𝒦
(1 )
𝑡𝑃
𝑖∈R+∀𝑖∈𝒩𝑈
(1s)
Objec i e unc ion (1a) ep esen s he p o i o he ope a o . The
i s e m ep esen s he e enue gene a ed by picking up cus ome s,
he second e m he o al cos bo n o he ehicles mo emen s and,
inally, he hi d e m is he discoun ed expec ed p o i ob ained in he
ebalancing cen e s.
Cons ain s (1b) and (1c) s a e ha new cus ome s may be picked
up a mos once and cus ome s al eady accep ed mus be picked up
exac ly once, espec i ely. Obse e, in (1b) and (1c), ha a e isi ing
a cus ome 𝑖∈𝒩𝐶o 𝑖∈𝒩𝑃, he ehicle can only mo e o ano he
cus ome 𝑖∈𝒩𝑃∪𝒩𝐶o o he s a ion 𝑑. Cons ain s (1d) ensu e
ha ehicles a el o he s a ion a mos once. Cons ain s (1e) s a e
ha whene e a ehicle a i es a a cus ome loca ion, i mus hen
mo e o ano he cus ome o o he s a ion. No ice ha a ehicle can
a i e a a cus ome loca ion 𝑗ei he om ano he cus ome o om
he ehicle’s o iginal loca ion 𝑜(𝑘). We emind he eade ha a iable
𝑥𝑘
𝑘𝑗 mus be unde s ood as ehicle 𝑘mo ing om i s o iginal loca ion
𝑜(𝑘) o he loca ion 𝑜(𝑗)o cus ome 𝑗. Cons ain s (1 ) s a e ha , i a
ehicle depa s om i s o iginal loca ion 𝑜(𝑘), i.e., 𝑥𝑘
𝑘𝑗 = 1 o some 𝑗,
i mus e mina e i s jou ney ei he a he s a ion o a a ebalancing
poin . Also in his case, a iables 𝑥𝑘
𝑘𝑗 mus be unde s ood as he ehicle
mo ing om i s o igin, 𝑜(𝑘), see Sec ion 3.1.
Cons ain s (1g) ensu e ha he capaci y o he ehicles is no ex-
ceeded, while cons ain s (1h) ensu e ha he o al numbe o ehicles
dispa ched o a ebalancing cen e will no exceed he uppe bound on
he ehicles dispa chable a he ebalancing cen e . Cons ain (1i) s a e
ha only emp y ehicles may be dispa ched o ebalancing cen e s. Fo
ins ance, i ehicle 𝑘is dispa ched o one o he ebalancing cen e ,
he igh -hand-side becomes 0, and he cons ain s can only be sa is ied
when 𝑉𝑘is equal o 0. I ehicle 𝑘is no dispa ched o any ebalancing
cen e , he igh -hand-side educes o he capaci y o he ehicle, and
he cons ain holds wi h any alue o 𝑉𝑘. No ice ha he mo emen s
be ween cus ome poin s 𝒩𝑈and ebalancing poin s a e au oma ically
o bidden by he absence o he co esponding 𝑥𝑘
𝑖𝑗 a iables. Cons ain s
(1j) s a e ha he ehicles ha al eady ha e cus ome s on boa d a he
beginning o he pe iod mus be dispa ched (i.e., canno s ay idle). I
𝑉𝑘is s ic ly posi i e, he cons ain o ces he igh -hand-side o be
s ic ly posi i e as well, and hus o dispa ch he ehicle.
Cons ain s (1k) s a e ha i cus ome 𝑗is picked up by ehicle
𝑘immedia ely a e picking up cus ome 𝑖, hen he ac ual picking
up ime o cus ome 𝑖plus he a el ime be ween cus ome 𝑖and 𝑗
mus be less o equal o cus ome 𝑗’s ac ual pick up ime. He e 𝑇𝐿:
=𝑚𝑎𝑥𝑖{𝑇𝐴
𝑖} o 𝑖∈𝒩𝑈is an uppe bound on he eques ed a i al
ime. Simila ly, cons ain s (1l) deno e he pick-up ime o he i s
cus ome s in he ou e. Cons ain s (1m) ensu e ha he di e ence
be ween he ac ual pick up ime and he eques ed pick up ime o he
cus ome does no exceed he maximum wai ing ime 𝛥. Cons ain s
(1n) ensu e ha he ac ual a i al ime o ehicle 𝑘mus be ea lie
han he eques ed a i al ime o any o he cus ome s on boa d o i .
Fo ins ance, i cus ome 𝑖is picked up by ehicle 𝑘, he igh -hand-side
becomes 𝑇𝐴
𝑖en o cing ha he ac ual a i al ime o ehicle 𝑘is be o e
𝑇𝐴
𝑖. Cons ain s (1o) ensu e ha he ac ual a i al ime o ehicle 𝑘
is ea lie han he ea lies eques ed a i al ime 𝑇𝑘o he passenge s
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
5
J. Ye e al.
on boa d a he beginning o he e-op imiza ion phase. Cons ain s
(1p) s a e he ela ionship be ween pick-up ime and a i al ime. Fo
example, i 𝑗is he las cus ome picked up by ehicle 𝑘be o e he
s a ion 𝑥𝑘
𝑗𝑑 akes alue 1, he le -hand-side becomes 𝑡𝑃
𝑗+𝑇𝑗𝑑 , and he
igh -hand-side becomes 𝑡𝐴
𝑘, en o cing ha he ac ual pick-up ime o
cus ome 𝑗plus he a el ime be ween cus ome 𝑗and s a ion be less
han o equal o he ac ual a i al ime o ehicle 𝑘. I 𝑗is no he las
cus ome picked up by he ehicle 𝑘be o e a i e a he s a ion, hen
he le -hand-side becomes 𝑡𝑃
𝑗, he igh -hand-side becomes 𝑡𝐴
𝑘+𝑇𝐿,
which always holds. Finally, cons ain s (1q)–(1s) de ine he domain
o he decision a iables.
An illus a i e example o possible solu ions o he p oblem is
p o ided in Appendix B.
4. Finding ebalancing cen e s
Iden i ying whe e o ebalance in o de o an icipa e demand, and
how many ehicles o send o each ebalancing poin is cu en ly an
open esea ch ques ion. Any such p edic ion model could be used o
eed ebalancing cen e s o model (1). In his sec ion we in oduce a
clus e ing-based me hods o iden i ying ebalancing cen e s. We e e
o he me hod as he K-means Clus e ing (KC) me hod. The me hod
iden i ies bo h he loca ion and demand o he ebalancing cen e s, and
his in u n allows us o de e mine he uppe bound on he numbe o
ehicles dispa chable o he di e en ebalancing cen e s.
Gi en a numbe 𝑘o ebalancing cen e s o ind, he KC me hod
inds ebalancing cen e s by pa i ioning all eques s ecei ed in he
cu en e-op imiza ion phase in o 𝑘=|ℛ|clus e s. Clus e s a e c ea ed
in such a way as o minimize he o al dis ance be ween he poin s
alloca ed o he clus e and he cen oid o he clus e . The cen oids
o he clus e s will hen be used as ebalancing cen e s. The expec ed
demand (numbe o eques s) o he ebalancing cen e s will be se
equal o he numbe o eques s in he co esponding clus e . We le
𝐷𝑟be he demand o ebalancing poin 𝑟∈ℛ.
The a ional behind he clus e ing me hod is he ollowing. Assume
ha he decision make pe o ms equen e-op imiza ions and ha
he demand dis ibu ion changes slow enough. Then he geog aphical
dis ibu ion o demand in he nea u u e is app oxima ely he same
as he cu en demand. Cu en eques s ep esen a sample om his
(unknown) dis ibu ion. Thus, o e many epe i ions one expec s o pu
ebalancing cen e s whe e he e is ac ually mo e demand. We belie e
ou assump ion o equen e-op imiza ions and demand changing
slowe han he e-op imiza ions is easonable in eal-li e. Howe e ,
clea ly, he p edic ion accu acy o he KC me hod is expec ed o all
when ei he (i) he e is no unde lying pa e n in he demand (we
a gue ha any p edic ion me hod would p obably ail in his case)
and (ii) when he demand changes apidly o e-op imiza ions a e no
pe o med su icien ly equen ly. In he compu a ional s udy we assess
bo h cases.
In Sec ion 5we compa e he KC me hod agains wo benchma ks,
namely andom selec ion and no ebalancing. The andom selec ion
me hod (he ea e named RS me hod) consis s o andomly selec ing
|ℛ|poin s in he ope a ing a ea as ebalancing cen e s. To each ebal-
ancing cen e is assigned a demand equal o he numbe o cus ome
eques s o he cu en e-op imiza ion phase wi hin a ce ain dis ance
(e.g., 1km) o he ebalancing cen e . No ebalancing en ails ℛ= ∅.
Fo bo h he KC and RS me hods, he uppe bound 𝐵𝑟o he numbe
ehicles ha can be dispa ched o each ebalancing cen e 𝑟is de ined
as 𝐵𝑟=𝐷𝑟∕
𝑄, whe e 
𝑄deno es he a e age numbe o cus ome on
boa d a ehicle du ing one ip.
5. Nume ical expe imen s
In his sec ion we epo he esul s o ou nume ical expe imen s.
The scope o he expe imen s is o assess, in e ms o p o i s and se ice
a es, wo di e en con igu a ions o he se ice which we e e o as
wi hou ebalancing (woR) and wi h ebalancing (wR). The con igu a ion
woR e e s o he si ua ion whe e he se ice p o ide dispa ches he
ehicles only based on cus ome eques s o he cu en e-op imiza ion
phase. Fo he model wi hou ebalancing, we simpli y ou model
in Sec ion 3by ha ing an emp y se o ebalancing cen e s. In he
con igu a ion wR, he se ice p o ide makes he dispa ching decision
based bo h on cu en cus ome eques s and on p edic ed demand
using ebalancing cen e s. In his case, we es he model wi h wo
di e en me hod o inding ebalancing cen e s. In he i s case, which
we e e o as wRKC, he company use KC o ob ain he loca ion and
demand o he ebalancing cen e s. In he second case, which we e e
o as wRRS, he company uses he RS me hod o ind he loca ions and
demands o he ebalancing cen e s.
Obse e ha he po en ial alue o eloca ion ac i i ies in on-
demand mobili y has been he ocus o o he s udies, such as Ma e al.
(2019b), Jamshidi e al. (2021), Saya shad and Chow (2017), Kash
e al. (2022) and Danassis e al. (2022) o di e en con igu a ions o
he se ice. Pa icula ly, ou wo k sha es simila i ies wi h Saya shad
and Chow (2017) who also explici ly model he decision o he se ice
p o ide as an op imiza ion model. Howe e , wi h espec o Saya shad
and Chow (2017) we conside (i) binding p e iously accep ed eques s,
(ii) cus ome s desi ed a i al imes and (iii) an uppe bound on he
maximum wai ing ime. We belie e ou s udy can p o ides e idences
based on a mo e in ol ed se up o he se ice.
The di e en con igu a ions a e es ed on a se o andom ins ances
in oduced in Sec ion 5.2. All p oblems a e sol ed wi h he Py hon
lib a ies o GUROBI 9.5.0 and a se e equipped wi h In el Co e i5 and
16 GB o RAM.
5.1. Simula ion amewo k
We es ou model in a simula ion amewo k, based on olling-
ho izon op imiza ion, wi h a planning ho izon o one hou . We assume
online e-op imiza ion happens e e y 5minu es. This means ha e e y
simula ion equi es he solu ion o 12 op imiza ion p oblems (1). A
each e-op imiza ion we upda e he s a us o he sys em, and andomly
gene a e (as explained in he nex sec ion) a numbe o new cus ome s.
Pa icula ly,
•A he ini ial op imiza ion phase, say 𝑇= 0, we assume ha he
𝒩𝑃is emp y. This means ha he e is no cus ome whose eques
had al eady been accep ed in a p e ious op imiza ion phase. We
gene a e a numbe o new cus ome s 𝒩𝐶, ebalancing cen e s ℛ,
and ini ial ehicle posi ions (as explained in he nex sec ion) and
sol e he esul ing model (1).
•We hen s ep i e minu es o wa d in ime, say op imiza ion
phase 𝑇= 1, and assume he solu ion o he model o 𝑇=
0, has been implemen ed. This en ails he ehicle ollowed he
ou es de e mined by he p e ious op imiza ion model o i e
minu es, mo ing ei he o cus ome s loca ions o o ebalanc-
ing cen e s. This p o ides hei upda ed loca ion o he new
e-op imiza ion phase. We hen pa i ion he cus ome s o he
p e ious op imiza ion phase in o h ee g oups:
1. The i s g oup con ains hose cus ome s ha had been
assigned o a ehicle bu ha e no ye been picked up in
he i e minu es in e al be ween he wo e-op imiza ions
(i.e., he ou e o he ehicle assigned o he cus ome did
no s op by he cus ome wi hin he i e-minu e in e al
be ween e-op imiza ions). These cus ome s o m he se o
manda o y cus ome s 𝒩𝑃in he new e-op imiza ion phase
and mus be picked up by some ehicle (possibly di e -
en om he one assigned in he p e ious e-op imiza ion
phase).
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
6
J. Ye e al.
Fig. 3. Uni o m and non-uni o m dis ibu ion o cus ome s wi h he s a ion loca ed in he cen e .
2. The second g oup con ains hose cus ome s ha had been
assigned o a ehicle in he p e ious e-op imiza ion phase
and he ou e o he assigned ehicle s opped by he cus-
ome wi hin he i e-minu e in e al be ween
e-op imiza ions. In he new e-op imiza ion phase hese
cus ome s ep esen s occupied sea s (𝑉𝑘) in he ehicles
o which hey we e assigned. The e o e, hese cus ome s
ep esen ul illed eques s and do no appea in 𝒩𝑃in he
new e-op imiza ion phase.
3. The hi d g oup con ains hose cus ome s ha had no been
assigned o a ehicle in he p e ious e-op imiza ion phase.
These ep esen cus ome s whose eques has been ejec ed
and will no show up in he new e-op imiza ion phase.
Obse e, ha in he new e-op imiza ion phase, ehicles may
ind hemsel es in o one o he ollowing si ua ions. (A) The
ehicle is emp y a a gi en posi ion and was on he way o pick-
up cus ome s o o a ebalancing cen e s. (B) The ehicle has
passenge s on boa d a a gi en posi ion and was on he way o
pick-up addi ional cus ome s o o he s a ion. In case (A), in
he new e-op imiza ion phase he ehicles may be assigned o
new cus ome s o o a ebalancing cen e , independen ly o he
decision made in he p e ious e-op imiza ion phase. Tha is, i is
possible ha he ehicle is assigned o a se o cus ome s di e en
om he ones p e iously assigned o he ehicle. In case (B) he
ehicle canno be sen o a ebalancing cen e bu may be as-
signed o new cus ome s o sen di ec ly o he s a ion. Following,
we gene a e new cus ome s 𝒩𝐶 o he new e-op imiza ion phase
and esol e a p oblem (1).
The p ocedu e con inues s epping i e minu es o wa d in ime un il
he end o he one-hou planning ho izon. Thus, we a e able o collec
s a is ics on he pe o mance o he se ice. Pa icula ly, he p o i is
compu ed as ollows. A he end o each e-op imiza ion phase, we
collec he ee o all he cus ome s ha ha e been accep ed (i.e., a
ehicle has been assigned o hem) and picked up (i.e., he ehicle
has a i ed a hei loca ion du ing he i e-minu e in e al be ween
e-op imiza ions) and sub ac he cos o he mo emen s he ehicles
ha e done du ing he i e-minu e in e al be ween e-op imiza ions.
The inal o al p o i is hen he sum o he indi idual p o i s made
du ing he one-hou planning ho izon. The p ocedu e is explained by
he ollowing example.
•Assume ha a 𝑇= 0,𝒩𝑃is emp y and 𝑉𝑘= 0 o all ehicles
𝑘∈ {𝐷1, 𝐷2, 𝐷3}. Tha is, he e is no cus ome whose eques
had al eady been accep ed in a p e ious op imiza ion phase.
We gene a e a numbe (say ou ) o new cus ome s 𝒩𝐶∶=
{𝐶0
1, 𝐶0
2, 𝐶0
3, 𝐶0
4}, ebalancing cen e s ℛ∶= 𝑅0
1, and ini ial ehicle
posi ions 𝑜(𝐷1), 𝑜(𝐷2), 𝑜(𝐷3)and sol e he esul ing model (1).
Assume ha he solu ion de e mines he ollowing ou es o he
h ee ehicles: 𝚁𝚘𝚞𝚝𝚎𝟷0∶= {𝐷1, 𝐶0
1, 𝐶0
3, 𝑑},𝚁𝚘𝚞𝚝𝚎𝟸0=∶ {𝐷2.𝐶0
2, 𝑑},
𝚁𝚘𝚞𝚝𝚎𝟹0∶= {𝐷3, 𝑅0
1}and ha cus ome 𝐶0
4is ejec ed.
•The solu ion compu ed a 𝑇= 0 is implemen ed and he ehicle
ollow he espec i e ou es o i e minu es. This p o ides up-
da ed sys em in o ma ion o op imiza ion phase 𝑇= 1. Tha is,
we upda ed he loca ion o he ehicles {𝑜(𝐷1), 𝑜(𝐷2), 𝑜(𝐷3)}. We
obse e ha ,
1. Fo 𝚁𝚘𝚞𝚝𝚎𝟷0, he ehicle 𝐷1al eady picked up cus ome
𝐶0
1, and is s ill on he way o pickup 𝐶0
3, so we can dele e
𝐶0
1 om he sys em, upda e 𝑉𝐷1= 1 and mo e 𝐶0
3 o
manda o y cus ome se 𝒩𝑃∶= {𝐶0
3}.
2. Fo 𝚁𝚘𝚞𝚝𝚎𝟸0, ehicle 𝐷2al eady picked up cus ome 𝐶0
2
and is s ill on he way o s a ion, so we can dele e 𝐶0
2 om
he sys em and upda e 𝑉𝐷2= 1.
3. Fo 𝚁𝚘𝚞𝚝𝚎𝟹0, ehicle 𝐷3a i ed a he ebalancing cen e
𝑅0
1, hus 𝑉𝐷3= 0.
In he new op imiza ion phase 𝑇= 1, since he ehicles 𝐷1, 𝐷2
al eady ha e cus ome s on boa d, hey canno be sen o a e-
balancing cen e bu may be assigned o new cus ome s o sen
di ec ly o he s a ion. Howe e , ehicle 𝐷3may be assigned o
new cus ome s o o a ebalancing cen e as i is s ill emp y.
Following, we gene a e new cus ome s 𝒩𝐶∶= 𝐶1
1, 𝐶1
2, 𝐶1
3, 𝐶1
4 o
he new e-op imiza ion phase 𝑇= 1 and esol e he p oblem (1).
5.2. Ins ance gene a ion
We gene a e a numbe o a i icial and andomly gene a ed in-
s ances ha mimic eal-li e ope a ing scena ios o he se ice. Pa icu-
la ly, we assume a lee o homogeneous ehicles o capaci y 𝑄= 4. The
posi ion o he ehicles o he i s e-op imiza ion phase is gene a ed
andomly in he business a ea (de ined below) and ini ially ehicles a e
assumed o ha e no passenge on boa d. Fo he e-op imiza ion phases
o he han he i s , he posi ion o he ehicles, and he numbe o
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
7
J. Ye e al.
Fig. 4. Uni o m and non-uni o m dis ibu ion o cus ome s wi h he s a ion loca ed in a co ne .
passenge s on boa d is compu ed as he esul o p e ious op imiza ion
phases.
We conside wo di e en geog aphies o he business a ea. In he
i s geog aphy, depic ed in Fig. 3, he s a ion is loca ed a he cen e o
he business a ea, and he business a ea i sel is ep esen ed by a ci cle
o adius 𝑅= 4 km. In he second geog aphy, see Fig. 4, he s a ion
is loca ed in a co ne and he business a ea is a qua e o a ci cle
o adius o 𝑅= 8 km. The second geog aphy is mean o ep esen
u ban con ex s whe e he demand is concen a ed only on one side o
he s a ion due o, e.g., physical ba ie s such as i e s o ha bo s.
Fo each geog aphy, and o each e-op imiza ion phase, cus ome
eques s a e gene a ed in he ollowing wo di e en scena ios o
demand dis ibu ion. In he i s scena io, e e ed o as he uni o m
demand scena io, pickup loca ions a e andomly sca e ed in he whole
business a ea, see Figs. 3(a) and 4(a). In he second scena io, e e ed
o as he non-uni o m demand scena io, one hi d o he eques s a i e,
andomly, om inside he inne ci cle o adius 𝑅𝐼= 0.6𝑅(whe e 𝑅
is he adius o he ou e ci cle), while he emaining eques s a i e,
andomly, om he ou e po ion o he ci cle, see Figs. 3(b) and 4(b).
We ob ain, in o al, ou con igu a ions namely
1. s a ion in he cen e and uni o m demand (UC ),
2. s a ion in he cen e and non-uni o m demand (NUC ),
3. s a ion in he co ne and uni o m demand (UCn),
4. s a ion in he co ne and non-uni o m demand (NUCn).
Fo each eques , he eques ed pickup ime (𝑇𝑃
𝑖) is andomly gene a ed
uni o mly be ween 0and 3minu es a e he beginning o he planning
ho izon, and he eques ed a i al ime (𝑇𝐴
𝑖) is se as he sum o
eques ed pickup ime, 𝑇𝑃
𝑖, a el ime be ween cus ome 𝑖and he
s a ion 𝑑, and a bu e ime andomly gene a ed be ween 5and 8
minu es. T a el ime 𝑇𝑖𝑗 a e calcula ed using Euclidean dis ances and
assuming an a e age speed o 36 Km/h (Commission and Limousine,
2023). The uni anspo a ion cos 𝐶is se o $11.25/h (English,2008)
and ip e enues 𝑃𝑖a e compu ed using a a e o $2.59 pe Km a eled
plus $0.74 pe minu e a eled, wi h a minimum a e o $8 ollowing
he se ing in INSHUR (2022).
We se he alue o 𝛽 o 0.1 in he objec i e unc ion, unless
o he wise speci ied. Obse e ha 𝛽de e mines he impac o ebal-
ancing mo emen s. High alues will inc ease he po en ial bene i o
ebalancing and migh lead o ejec ing cu en cus ome s while low
alues migh lead he model o p o ide myopic decisions. The impac
o di e en alues o 𝛽will be assessed h ough sensi i i y analysis in
Sec ion 5.5. The expec ed e enue o ebalancing a ehicle o cen e
𝑖∈ℛ,𝐸𝑖, is calcula ed as 
𝑃𝑖−𝐶𝑇𝑖𝑑 , whe e 
𝑃𝑖is he e enue o
dispa ching a ehicle o ebalancing cen e 𝑖∈ℛ, and is calcula ed
as 
𝑃𝑖=𝑄 𝑃 𝐴
𝑖, whe e 𝑃𝐴
𝑖 he a e age e enue o he eques s in he
clus e whe e 𝑖is he cen oid and 𝑄is he capaci y o he ehicles.
𝐶is he uni anspo a ion cos , se as abo e, and 𝑇𝑖𝑑 is he dis ance
be ween ebalancing poin 𝑖and he s a ion. To ob ain he uppe bound
on he numbe o ehicles dispa chable o a ebalancing cen e (𝐵𝑟, see
Sec ion 4) we se he a e age numbe o cus ome s on boa d du ing
one ip o a ehicle 
𝑄equal o hal o he capaci y 𝑄= 4.
Fo each con igu a ion, we gene a e di e en ins ances a ying
in he numbe o ehicles and cus ome s ha appea a each new
e-op imiza ion phase. Pa icula ly, we c ea e ins ance classes named
𝐶|𝒩𝐶|𝑉|𝒦|wi h numbe o cus ome s |𝒩𝐶|∈ {6,7,8}, and num-
be o ehicles, |𝒦|∈ {10,12,14}. As an example, 𝐶8𝑉10 indica es
a class o ins ances wi h 8new cus ome s in each e-op imiza ion
phase and 10 ehicles a ailable o dispa ching o he whole planning
pe iod. Fo each ins ance class we andomly gene a e 3di e en in-
s ances. Obse e, howe e , ha o each ins ance we sol e 12 di e en
op imiza ion p oblems in ou simula ion amewo k.
We se he numbe o ebalancing cen e s |ℛ| o 3in all ins ances
(la e we pe o m sensi i i y analysis wi h espec o his pa ame e .) .
This numbe is ound using he Elbow Me hod (EM) and he Silhoue e
Analysis Me hod (SAM) (Mahend u,2019). Pa icula ly, we use he
ins ances wi h |𝒩𝐶|= 8 as a e e ence case o ind a sui able alue
o 𝑘=|ℛ|. Fi s we andomly gene a e 8cus ome s in he ope a ing
a ea, hen we use he EM app oach o show he pe o mance o he
KC me hod o di e en alues o 𝑘. Fo each 𝑘we conside he Wi hin-
Clus e -Sum o Squa ed E o s (WSS). We hen plo he WSS e sus 𝑘, and
choose he alue o 𝑘 o which he WSS la ens. This poin is e e ed
o as an ‘‘Elbow’’, see Fig. 5(a).
Ne e heless, in some cases, he EM does no gi e p ecise answe s
as i is no always clea o which alue o 𝑘 he change o slope is
signi ican . In such cases, we will use he SAM o make a decision. The
silhoue e sco e is a measu e o how simila a cus ome eques is o
i s own ebalancing clus e compa ed o o he ebalancing clus e s. To
be mo e p ecise, he silhoue e sco e o one cus ome eques 𝑖can be
calcula e as below:
𝑠(𝑖) = 𝑏(𝑖) − 𝑎(𝑖)
max{𝑎(𝑖), 𝑏(𝑖)} (2)
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
8
J. Ye e al.
Fig. 12. Example p oblem in a scena io whe e ebalancing in no pe mi ed.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
15

J. Ye e al.
Fig. 13. Example p oblem in a scena io whe e ebalancing is pe mi ed.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
16
J. Ye e al.
Fig. 14. Illus a ion o capaci y and a i al ime cons ain s.
Table 10
Se ice a e [%] in he simula ions wi h |ℛ|= 4.
C6V10 C6V12 C6V14 C7V10 C7V12 C7V14 C8V10 C8V12 C8V14
NUC
wRKC 91% 98% 98% 95% 97% 97% 93% 96% 98%
wRRS 95% 94% 93% 91% 92% 91% 89% 93% 94%
woR 94% 94% 94% 89% 94% 91% 90% 90% 92%
UC
wRKC 97% 97% 96% 95% 96% 98% 94% 98% 99%
wRRS 92% 94% 95% 92% 93% 94% 92% 94% 94%
woR 91% 95% 94% 92% 95% 95% 91% 96% 92%
NUCn
wRKC 79% 84% 86% 79% 84% 86% 77% 84% 89%
wRRS 59% 62% 77% 56% 63% 65% 62% 57% 72%
woR 63% 66% 72% 48% 60% 62% 47% 48% 57%
UCn
wRKC 86% 87% 87% 81% 88% 87% 82% 87% 90%
wRRS 67% 70% 72% 72% 72% 78% 64% 62% 70%
woR 66% 69% 78% 63% 76% 68% 66% 72% 65%
Table 11
P o i [$] in he simula ions wi h |ℛ|= 5.
C6V10 C6V12 C6V14 C7V10 C7V12 C7V14 C8V10 C8V12 C8V14
NUC
wRKC 55.59 58.84 57.78 68.43 67.63 70.83 76.62 81.41 82.31
wRRS 56.72 55.37 53.75 64.77 68.90 66.49 73.98 79.11 80.38
woR 56.37 56.61 56.42 63.96 67.08 65.72 74.71 77.52 78.71
UC
wRKC 54.50 51.97 56.89 64.16 64.61 63.51 67.93 74.05 72.42
wRRS 53.76 51.60 53.94 61.15 60.48 62.18 67.57 67.84 70.33
woR 50.88 55.03 54.35 61.46 61.68 65.22 66.79 71.78 68.77
NUCn
wRKC 96.28 89.64 97.71 117.68 120.27 128.11 127.05 149.52 148.79
wRRS 73.74 79.37 87.74 86.42 77.28 97.84 91.69 103.02 115.89
woR 71.16 72.65 85.50 64.70 82.34 88.40 73.28 76.91 94.33
UCn
wRKC 90.33 86.50 94.46 101.61 112.41 106.93 114.81 123.93 125.85
wRRS 61.13 84.17 81.85 72.83 78.28 91.78 86.65 88.83 103.16
woR 70.33 69.94 89.82 77.23 94.43 86.60 90.63 106.04 91.04
Table 12
Se ice a e [%] in he simula ions wi h |ℛ|= 5.
C6V10 C6V12 C6V14 C7V10 C7V12 C7V14 C8V10 C8V12 C8V14
NUC
wRKC 93% 99% 96% 94% 95% 97% 89% 95% 96%
wRRS 93% 94% 91% 91% 94% 92% 90% 93% 93%
woR 94% 94% 94% 89% 94% 91% 90% 90% 92%
UC
wRKC 98% 94% 98% 95% 98% 95% 93% 99% 98%
wRRS 94% 94% 97% 95% 93% 94% 92% 90% 95%
woR 91% 95% 94% 92% 95% 95% 91% 96% 92%
NUCn
wRKC 78% 78% 81% 81% 83% 86% 78% 86% 84%
wRRS 63% 68% 75% 61% 59% 70% 59% 63% 69%
woR 63% 66% 72% 48% 60% 62% 47% 48% 57%
UCn
wRKC 81% 75% 82% 81% 87% 83% 77% 82% 85%
wRRS 61% 78% 76% 62% 66% 76% 64% 68% 73%
woR 66% 69% 78% 63% 76% 68% 66% 72% 65%
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
17
J. Ye e al.
Re e ences
Al-Abbasi, Abubak O., Ghosh, A nob, Agga wal, Vanee , 2019. DeepPool: Dis ibu ed
model- ee algo i hm o ide-sha ing using deep ein o cemen lea ning. IEEE
T ans. In ell. T ansp. Sys . 1–14.
Alonso-mo a, Ja ie , Walla , Alex, F azzoli, Emilio, Rus, Daniela, 2018. On-demand
high-capaci y ide-sha ing ia dynamic ip- ehicle assignmen . P oc. Na l. Acad.
Sci. USA 115 (3), E555.
Balas, Egon, 1989. The p ize collec ing a eling salesman p oblem. Ne wo ks 19 (6),
621–636.
Bei igo, B eno A, Negenbo n, Rudy R, Alonso-Mo a, Ja ie , Schul e, F ede ik, 2022.
A business class o au onomous mobili y-on-demand: Modeling se ice quali y
con ac s in dynamic idesha ing sys ems. T ansp. Res. C 136, 103520.
Be beglia, Ge a do, Co deau, Jean F ançois, Lapo e, Gilbe , 2010. Dynamic pickup
and deli e y p oblems. Eu opean J. Ope . Res. 202 (1), 8–15.
Be simas, Dimi is, Jaille , Pa ick, Ma in, Sébas ien, 2019. Online ehicle ou ing:
The edge o op imiza ion in la ge-scale applica ions. Ope . Res. 67 (1), 143–162.
Bian, Zheyong, Liu, Xiang, 2019a. Mechanism design o i s -mile idesha ing based
on pe sonalized equi emen s pa I: Theo e ical analysis in gene alized scena ios.
T ansp. Res. B 120, 147–171.
Bian, Zheyong, Liu, Xiang, 2019b. Mechanism design o i s -mile idesha ing based
on pe sonalized equi emen s pa II: Solu ion algo i hm o la ge-scale p oblems.
T ansp. Res. B 120, 172–192.
Bian, Zheyong, Liu, Xiang, Bai, Yun, 2020. Mechanism design o on-demand i s -mile
idesha ing. T ansp. Res. B 138, 77–117.
Bongio anni, Claudia, Kaspi, Mo , Co deau, Jean-F ancois, Ge oliminis, Nikolas, 2022.
A machine lea ning-d i en wo-phase me aheu is ic o au onomous idesha ing
ope a ions. T ansp. Res. E 165, 102835.
B aeke s, K is, Ramaeke s, Ka ien, Van Nieuwenhuyse, Inneke, 2016. The ehicle
ou ing p oblem: S a e o he a classi ica ion and e iew. Compu . Ind. Eng. 99,
300–313.
B äysy, Olli, Gend eau, Michel, 2005. Vehicle ou ing p oblem wi h ime windows, Pa
I: Rou e cons uc ion and local sea ch algo i hms. T ansp. Sci. 39 (1), 104–118.
Chemla, Daniel, Meunie , F édé ic, Cal o, Robe o Wol le , 2013. Bike sha ing sys ems:
Sol ing he s a ic ebalancing p oblem. Disc e e Op im. 10 (2), 120–146.
Chen, Yiwei, Wang, Hai, 2018. P icing o a las -mile anspo a ion sys em. T ansp.
Res. B 107, 57–69.
Chen, Shukai, Wang, Hua, Meng, Qiang, 2020. Sol ing he i s -mile idesha ing
p oblem using au onomous ehicles. Compu .-Aided Ci . In as uc . Eng. 35 (1),
45–60.
Commission, New Yo k Ci y Taxi, Limousine, 2023. New Yo k Ci y Taxi and Limou-
sine Commission. h ps://www1.nyc.go /si e/ lc/abou / lc- ip- eco d-da a.page.
(Online; Accessed 10 Oc obe 2023).
Co deau, Jean F ançois, Lapo e, Gilbe , 2003. The Dial-a-Ride P oblem (DARP):
Va ian s, modeling issues and algo i hms. 4OR 1 (2), 89–101.
Danassis, Panayio is, Sako a, Ma ija, Filos-Ra sikas, A is, Fal ings, Boi, 2022. Pu ing
idesha ing o he es : E icien and scalable solu ions and he powe o dynamic
ehicle eloca ion. A i . In ell. Re . 55 (7), 5781–5844.
Dan zig, G.B., Ramse , J.H., 1959. The uck dispa ching p oblem. Manage. Sci. 6 (1),
80–91.
El ing, S e en, Ehmke, Jan Fabian, 2021. Po en ial o sha ed axi se ices in u al
a eas–A case s udy. T ansp. Res. P ocedia 52, 661–668.
English, Sandy, 2008. High uel p ices impo e ish new yo k ci y axi d i e s. h ps:
//www.wsws.o g/en/a icles/2008/09/ axi-s04.h ml. (Online; Accessed 10 Oc obe
2022).
Faghih-Imani, Ahmad eza, Hampshi e, Robe , Ma la, La anya, Elu u, Na een, 2017. An
empi ical analysis o bike sha ing usage and ebalancing: E idence om Ba celona
and Se ille. T ansp. Res. A 97, 177–191.
Fagnan , Daniel J., Kockelman, Ka a M., 2018. Dynamic ide-sha ing and lee sizing
o a sys em o sha ed au onomous ehicles in Aus in, Texas. T anspo a ion 45,
143–158.
Folkes ad, Ca l Axel, Hansen, No a, Fage hol , Kje il, Ande sson, Hen ik, Pan uso, Gio-
anni, 2020. Op imal cha ging and eposi ioning o elec ic ehicles in a
ee- loa ing ca sha ing sys em. Compu . Ope . Res. 113, 104771.
Ho, Sin C., Sze o, W.Y., Kuo, Yong-hong Hong, Leung, Janny M.Y.Y., Pe e ing, Ma hew,
Tou, Te ence W.H.H., 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. B 111, 395–421.
Huang, Yan, Bas ani, Fa yen, Jin, Ruoming, Wang, Xiaoyang Sean, 2014. La ge scale
eal ime idesha ing wi h se ice gua an ee on oad ne wo ks. In: P oceedings o
he VLDB Endowmen .
Illgen, S e an, Höck, Michael, 2019. Li e a u e e iew o he ehicle eloca ion p oblem
in one-way ca sha ing ne wo ks. T ansp. Res. B 120, 193–204.
INSHUR, 2022. How much does an Ube d i e make in New Yo k Ci y?. h ps://
inshu .com/blog/how-much-does-an-ube -d i e -make-in-new-yo k-ci y/. (Online;
Accessed 10 Oc obe 2022).
Jamshidi, Helia, Co eia, Gonçalo HA, an Essen, J The esia, Nökel, Klaus, 2021.
Dynamic planning o simul aneous echa ging and eloca ion o sha ed elec ic
axies: A sequen ial MILP app oach. T ansp. Res. C 125, 102933.
Kash, Ian A., Wen, Zhongkai, Zuck, Leno e D., 2022. Dynamic eloca ion in idesha ing
ia ixpoin cons uc ion. In: Cussens, James, Zhang, Kun (Eds.), P oceedings
o he Thi y-Eigh h Con e ence on Unce ain y in A i icial In elligence. In:
P oceedings o Machine Lea ning Resea ch, ol. 180, PMLR, pp. 980–989, URL
h ps://p oceedings.ml .p ess/ 180/kash22a.h ml.
Kuma , Su esh Nanda, Pannee sel am, Ramasamy, 2012. A su ey on he ehicle
ou ing p oblem and i s a ian s. In ell. In . Manage. 04 (03), 66–74.
Li, Xihan, Zhang, Jia, Bian, Jiang, Tong, Yunhai, Liu, Tie-Yan, 2019. A coope a i e
mul i-agen ein o cemen lea ning amewo k o esou ce balancing in com-
plex logis ics ne wo k. In: In e na ional Founda ion o Au onomous Agen s and
Mul iagen Sys ems. AAMAS ’19, pp. 980–988.
Lin, Canhong, Choy, K.L., Ho, G.T.S., Chung, S.H., Lam, H.Y., 2014. Su ey o G een
ehicle ou ing p oblem: Pas and u u e ends. Expe Sys . Appl. 41 (4 PART 1),
1118–1138.
Lin, Kaixiang, Zhao, Renyu, Xu, Zhe, Zhou, Jiayu, 2018. E icien la ge-scale lee
managemen ia mul i-agen deep ein o cemen lea ning. In: P oceedings o he
ACM SIGKDD In e na ional Con e ence on Knowledge Disco e y and Da a Mining.
pp. 1774–1783.
Liu, Junming, Sun, Leilei, Chen, Weiwei, Xiong, Hui, 2016. Rebalancing bike sha ing
sys ems: A mul i-sou ce da a sma op imiza ion. In: P oceedings o he 22nd ACM
SIGKDD In e na ional Con e ence on Knowledge Disco e y and Da a Mining. pp.
1005–1014.
Lokhandwala, Mus a a, Cai, Hua, 2018. Dynamic ide sha ing using adi ional axis
and sha ed au onomous axis: A case s udy o NYC. T ansp. Res. C 97, 45–60.
Lo i, Sepide, Abdelghany, Khaled, 2022. Ride ma ching and ehicle ou ing o
on-demand mobili y se ices. J. Heu is ics 28 (3), 235–258.
Ma, Tai-yu Yu, Rasulkhani, Saeid, Chow, Joseph Y.J. J, Klein, Syl ain, 2019a. A
dynamic idesha ing dispa ch and idle ehicle eposi ioning s a egy wi h in eg a ed
ansi ans e s. T ansp. Res. E 128 (Decembe 2018), 417–442.
Ma, Ruimin, Yao, Li ei, Song, Lijun, Jin, Maozhu, 2019b. A no el algo i hm o
pee - o-pee idesha ing ma ch p oblem. Neu al Compu . Appl. 31 (s1), 247–258.
Mahend u, Khya i, 2019. How o de e mine he op imal K o K-means?.
h ps://medium.com/analy ics- idhya/how- o-de e mine- he-op imal-k- o -k-
means-708505d204eb. (Online; Accessed 10 Oc obe 2022).
Mao, Chao, Liu, Yulin, Shen, Zuo-Jun Max, 2020. Dispa ch o au onomous ehicles o
axi se ices: A deep ein o cemen lea ning app oach. T ansp. Res. C 115, 102626.
Masoud, Neda, Jayak ishnan, R., 2017. A decomposi ion algo i hm o sol e he
mul i-hop Pee - o-Pee ide-ma ching p oblem. T ansp. Res. B 99 (May), 1–29.
Masoud, Neda, Llo e -Ba lle, Roge , Jayak ishnan, R., 2017. Using bila e al ading o
inc ease ide ship and use pe manence in idesha ing sys ems. T ansp. Res. E.
Mou ad, Abood, Puchinge , Jakob, Chu, Chengbin, 2019. A su ey o models and
algo i hms o op imizing sha ed mobili y. T ansp. Res. B 123, 323–346.
No uzoliaee, Mohamadhossein, Zou, Bo, 2022. One- o-many ma ching and sec ion-based
o mula ion o au onomous idesha ing equilib ium. T ansp. Res. B 155, 72–100.
Oso io, Jesus, Lei, Chao, Ouyang, Yan eng, 2021. Op imal ebalancing and on-boa d
cha ging o sha ed elec ic scoo e s. T ansp. Res. B 147, 197–219.
Pan uso, Gio anni, 2022. Exac solu ions o a ca sha ing p icing and eloca ion p oblem
unde unce ain y. Compu . Ope . Res. 144, 105802.
Pa agh, Sophie N., Doe ne , Ka l F., Ha l, Richa d F., 2008. A su ey on pickup and
deli e y p oblems: Pa II: T anspo a ion be ween pickup and deli e y loca ions.
J. Be . 58 (2), 81–117.
P ei e , Ch is ian, Schulz, A ne, 2022. An ALNS algo i hm o he s a ic dial-a- ide
p oblem wi h ide and wai ing ime minimiza ion. OR Spec um 44 (1), 87–119.
Pillac, Vic o , Gend eau, Michel, Gué e , Ch is elle, Medaglia, And és L., 2013. A e iew
o dynamic ehicle ou ing p oblems. Eu opean J. Ope . Res. 225 (1), 1–11.
Qin, Zhiwei, Tang, Xiaocheng, Jiao, Yan, Zhang, Fan, Wang, Chenxi, Li, Qun, 2019.
Deep ein o cemen lea ning o ide-sha ing dispa ching and eposi ioning. In:
IJCAI In e na ional Join Con e ence on A i icial In elligence. 2019-Augus, pp.
6566–6568.
Ri zinge , Ul ike, Puchinge , Jakob, Ha l, Richa d F., 2016. A su ey on dynamic and
s ochas ic ehicle ou ing p oblems. In . J. P od. Res. 54 (1), 215–231.
Ropke, S e an, Co deau, Jean-F ançois F ançois, 2009. B anch and cu and p ice o he
pickup and deli e y p oblem wi h ime windows. T ansp. Sci. 43 (3), 267–286.
San os, Douglas O., Xa ie , Edua do C., 2015. Taxi and ide sha ing: A dynamic
dial-a- ide p oblem wi h money as an incen i e. Expe Sys . Appl. 42 (19),
6728–6737.
Saya shad, Hamid R., Chow, Joseph Y.J., 2017. Non-myopic eloca ion o idle mobili y-
on-demand ehicles as a dynamic loca ion-alloca ion-queueing p oblem. T ansp.
Res. E 106, 60–77.
Shen, Yu, Zhang, Hongmou, Zhao, Jinhua, 2018. In eg a ing sha ed au onomous ehicle
in public anspo a ion sys em: A supply-side simula ion o he i s -mile se ice
in Singapo e. T ansp. Res. A 113, 125–136.
S iglic, Mi ja, Aga z, Niels, Sa elsbe gh, Ma in, G adisa , Mi ko, 2015. The bene i s o
mee ing poin s in ide-sha ing sys ems. T ansp. Res. B 82, 36–53.
S iglic, Mi ja, Aga z, Niels, Sa elsbe gh, Ma in, G adisa , Mi ko, 2018. Enhancing
u ban mobili y: In eg a ing ide-sha ing and public ansi . Compu . Ope . Res. 90,
12–21.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
18
J. Ye e al.
Tang, Xiaocheng, Qin, Zhiwei Tony, Zhang, Fan, Wang, Zhaodong, Xu, Zhe, Ma, Yin ai,
Zhu, Hong u, Ye, Jieping, Labs, A I, Chuxing, Didi, Tang, Xiaocheng, Qin, Zhi-
wei Tony, Zhang, Fan, Wang, Zhaodong, Xu, Zhe, Ma, Yin ai, Zhu, Hong u,
Ye, Jieping, 2019. A deep alue-ne wo k based app oach o mul i-d i e o de
dispa ching. In: P oceedings o he ACM SIGKDD In e na ional Con e ence on
Knowledge Disco e y and Da a Mining. pp. 1780–1790.
Taniguchi, Eiichi, Thompson, Russell G., Yamada, Tadashi, 2014. Recen ends and
inno a ions in modelling ci y logis ics. P ocedia Soc. Beha . Sci. 125, 4–14, URL
h ps://www.sciencedi ec .com/science/a icle/pii/S187704281401489X.
To h, Paolo, Vigo, Daniele, 2002. The Vehicle Rou ing P oblem. SIAM.
Walla , Alex, Van De Zee, Menno, Alonso-Mo a, Ja ie , Rus, Daniela, 2018. Vehicle e-
balancing o mobili y-on-demand sys ems wi h ide-sha ing. In: IEEE In e na ional
Con e ence on In elligen Robo s and Sys ems. pp. 4539–4546.
Wang, Hai, 2019. Rou ing and scheduling o a las -mile anspo a ion sys em. T ansp.
Sci. 53 (1), 131–147.
Wang, Xing, Aga z, Niels, E e a, Alan, 2018. S able ma ching o dynamic ide-sha ing
sys ems. T ansp. Sci. 52 (4), 850–867.
Wen, Jian, Zhao, Jinhua, Jaille , Pa ick, 2018. Rebalancing sha ed mobili y-on-demand
sys ems: A ein o cemen lea ning app oach. In: IEEE Con e ence on In elligen
T anspo a ion Sys ems, P oceedings. ITSC, 2018-Ma ch, (Oc obe ), pp. 220–225.
Xu, Zhe, Li, Zhixin, Guan, Qingwen, Zhang, Dingshui, Li, Qiang, Nan, Junxiao,
Liu, Chunyang, Bian, Wei, Ye, Jieping, 2018. La ge-scale o de dispa ch in on-
demand ide-hailing pla o ms: A lea ning and planning app oach. In: P oceedings
o he 24 h ACM SIGKDD In e na ional Con e ence on Knowledge Disco e y & Da a
Mining. KDD ’18, Associa ion o Compu ing Machine y, New Yo k, NY, USA, pp.
905–913.
Zhao, Meng, Yin, Jia eng, An, Shi, Wang, Jian, Feng, Dejian, 2018. Ridesha ing p oblem
wi h lexible pickup and deli e y loca ions o app-based anspo a ion se ice:
Ma hema ical modeling and decomposi ion me hods. J. Ad . T ansp. 2018.
Zheng, Minyi, Pan uso, Gio anni, 2023. T ading o cos s and se ice a es in a i s -mile
ide-sha ing se ice. T ansp. Res. C 150, 104099.
EURO Jou nal on T anspo a ion and Logis ics 13 (2024) 100132
19