Ba z, Ch is iane; Gönsch, Jochen; Rauhaus, Da ina; He, Siqi
A icle — Published Ve sion
Dynamic p icing wi h (ex a) sea ese a ions unde he
nes ed logi model
OR Spec um
Sugges ed Ci a ion: Ba z, Ch is iane; Gönsch, Jochen; Rauhaus, Da ina; He, Siqi (2025) : Dynamic
p icing wi h (ex a) sea ese a ions unde he nes ed logi model, OR Spec um, ISSN 1436-6304,
Sp inge Be lin Heidelbe g, Be lin/Heidelbe g, Vol. 47, Iss. 4, pp. 1133-1179,
h ps://doi.o g/10.1007/s00291-025-00817-y
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/333239
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:1133–1179
h ps://doi.o g/10.1007/s00291-025-00817-y
ORIGINAL ARTICLE
Dynamic p icing wi h(ex a) sea ese a ions
unde henes ed logi model
Ch is ianeBa z1 · JochenGönsch2· Da inaRauhaus2· SiqiHe1
Recei ed: 16 Ap il 2024 / Accep ed: 15 Ap il 2025 / Published online: 27 May 2025
© The Au ho (s) 2025
Abs ac
We sugges a dynamic p icing model o selling ex a sea s - sea ese a ions o
unoccupied sea s ha p o ide addi ional space alongside egula ese a ions. Such
ex a space icke s sha e he esou ces o he main p oduc and le e age he unused
capaci y, o e ing signi ican e enue-gene a ion oppo uni ies when coaches, ains,
o ai planes equen ly depa wi h emp y sea s. We o mula e a Ma ko decision
p ocess (MDP) ep esen ing he icke sales p oblem o a anspo a ion company
ha sells icke s o a single leg in a single compa men , o e ing h ee op ions:
(1) wi hou sea ese a ion, (2) wi h sea ese a ion, and (3) wi h sea ese a ion
and ex a space. In his amewo k, sea ese a ions a e in eg a ed in o he s a e
space, making he p oblem a special case o he ne wo k dynamic p icing p oblem.
To sol e his p oblem, we d aw om es ablished ne wo k dynamic p icing me h-
ods o de i e uppe bounds and policies o p icing he h ee icke ypes. These
app oaches include de e minis ic app oxima ion, app oxima e linea p og amming,
and a decomposi ion me hod based on sea alues p o ided by he de e minis ic
app oxima ion. Unde he nes ed logi demand model, we demons a e ha he ALP
subp oblem ea u es a con ex objec i e unc ion in ac ions and linea i y in he s a e
componen s, enabling e icien solu ions. An ex ensi e nume ical s udy highligh s
he e iciency o he decomposi ion app oach, which deli e s a supe io e enue-
o- un ime ade-o compa ed o mo e complex me hods. This makes i a p ac ical
choice o eal-wo ld applica ions. Addi ionally, ou esul s quan i y he signi ican
e enue po en ial o o e ing ex a sea s, pa icula ly in low-demand scena ios.
Keywo ds Re enue managemen · Ex a sea s· Emp y sea s· App oxima e dynamic
p og amming· Dynamic p icing· Ancilla y p oduc s· Nes ed logi · Cus ome
choice
Ex ended au ho in o ma ion a ailable on he las page o he a icle
1134
C.Ba z e al.
1 In oduc ion
In he dynamic landscape o e enue managemen (RM), inno a i e p ac ices o en
eme ge in indus y applica ions. This pape p esen s a modeling app oach o add ess
he common p ac ice o selling ex a, unoccupied sea s adjacen o a cus ome ’s
ese ed sea .
Companies like FlixBus, a leading global long-dis ance bus company and pa en
o he US G eyhound, wi h o e 60 million passenge s in 2022 (Flix 2023), ha e
adop ed his p ac ice. They o e passenge s he “T a el neighbou - ee” op ion
o ese e an adjacen sea o hei exclusi e use, hus ensu ing ex a space and
com o du ing hei jou neys (see Fig.1). Gi en he low a e age occupancy a es
in some anspo a ion sec o s using e enue managemen , his app oach seems o
ha e signi ican po en ial. Fo example, he a e age coach occupancy a e in F ance
anged om 29.8 pe cen o 53.8 pe cen be ween 2015 and 2017, acco ding o
S a is a (2022). This issue was u he exace ba ed du ing he COVID-19 pandemic,
which led o a d ama ic decline in a el demand (Dhi al e al. 2022). And on he
demand-side, Mumbowe e al. (2015) shows wha seasoned a ele s know ins inc-
i ely: cus ome s alue ex a space o long-haul a el and a e willing o pay o i
unde ce ain ci cums ances.
Bu ex a sea ese a ion has seen widesp ead implemen a ion in he a ia ion
indus y as well, wi h examples like he “Neighbou -F ee” sea ing p og am in o-
duced by Qan as Ai lines and Eu owings o “Ex a Sea s” by Ai China, All Nip-
pon Ai ways, EL AL, and Tu kish Ai lines. These p og ams allow passenge s o
ensu e an emp y middle sea o mo e con enience o a small ee, compa ed o
he whole icke p ice. This app oach enables ope a o s o capi alize on he sale
o sea s ha migh o he wise emain unsold, he eby inc easing e enue. In addi-
ion, o e ing such an addi ional op ion can expand he ma ke and a ac mo e
cus ome s, as people a e inclined o choose a el op ions ha p io i ize com-
o . The ma ke demand o addi ional space has become e en mo e p onounced
du ing he COVID-19 pandemic, whe e social dis ancing was conside ed a high
Fig. 1 Example om booking p ocess (FlixBus websi e, 28 h Oc obe 2024)
1135
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
p io i y. Howe e , o he bes o ou knowledge, no esea ch exis s on when o
o e and how o p ice hese ex a sea s.
Despi e hese p ominen implemen a ions in indus y p ac ice, academia has
emained ela i ely silen on op imal s a egies o o e ing and p icing ex a
sea s. Ins ead, indus y p ac i ione s seem o o en ely on basic ules o humb.
Ou esea ch aims o b idge his gap by le e aging s a e-o - he-a RM echniques
o in o m indus y p ac ices and shed ligh on op imal p icing s a egies in his
complex ecosys em.
In his pape , we use he example o a bus company like FlixBus o illus a e
ou ideas. Mo e speci ically, we conside he ollowing op imiza ion p oblem o
an expec ed e enue-maximizing i m ha ope a es a coach on a single leg. Sea s
a e speci ic, i.e., cus ome s may ha e p e e ences o speci ic sea s (e.g., i s ow,
le window sea ). As usual in dynamic p icing se ings, he company’s decision
is o adjus i s p oduc s’ p ices h oughou he ini e selling ho izon in o de o
maximize expec ed e enue. Cus ome s a i e sequen ially, obse e he p ices
o all p oduc s, and hen s ochas ically choose a p oduc ype o lea e wi hou
a pu chase. In pa icula , he e a e h ee ypes o p oduc s. (1) Ticke s wi hou
sea ese a ion, whe e cus ome s pick a ee sea when boa ding o a e andomly
assigned one a his ime. (2) Ticke s wi h a sea ese a ion, whe e cus ome s
choose a speci ic sea when booking. We subsequen ly e e o his as (single-)
sea ese a ion. (3) Ticke s wi h an ex a sea ese a ion, whe e cus ome s
choose a speci ic pai o sea s. Only a e he p oduc ype is chosen, he cus-
ome selec s a speci ic sea o a pai o neighbo ing sea s. Since he nes ed logi
(NL) model na u ally desc ibes he hie a chy in he pu chase decisions ega d-
ing p oduc ype and speci ic sea in case o a ese a ion, we assume his model
h oughou . On a mo e echnical le el, he NL is a ac able model ha cap u es
di e en pai wise simila i ies as p oduc s a e a anged in nes s and wo p oduc s
sha ing a common nes a e mo e simila han wo p oduc s in di e en nes s. This
is exac ly wha we ha e he e: o example, o mos cus ome s, a ese a ion o
a ou h ow sea is e y simila o a ese a ion o a i h ow se , bu di e en
om a icke wi hou ese a ion. In ou nume ical s udy, we also conside p e -
e ences o di e en sea ypes, e.g. aisle o window sea . Howe e , he gene al
ideas in oduced he e ca y o e o o he choice models as well.
Ou con ibu ions can be summa ized as ollows:
• No el o mula ion as ne wo k e enue managemen p oblem: We a e he i s ,
o ou knowledge, o ame he p oblem o maximizing expec ed e enue om
selling icke s wi h and wi hou ese a ions ia dynamic p icing as a ne wo k
e enue managemen p oblem. This no el o mula ion allows us o add ess icke
sales in h ee con ex s: wi hou ese a ions, wi h single-sea ese a ions, and
wi h ex a-sea ese a ions.
• Applica ion o es ablished solu ion echniques o ob ain uppe bounds and p ic-
ing heu is ics: We apply h ee es ablished app oaches o de e mine uppe bounds
on expec ed e enue and sugges ela ed p icing heu is ics o he ne wo k e -
enue managemen p oblem:
1136
C.Ba z e al.
• A s a ic de e minis ic p icing p oblem (DPP), p o iding a s aigh o wa d and
compu a ionally e icien pa h owa ds an uppe bound and bid p ices ha can
be used o de e mine a s a ic p icing policy.
• A semi-in ini e linea p og am inspi ed by Ke e al. (2019), based on an
app oxima e linea p og amming (ALP) app oach. We demons a e ha ,
unde a NL choice model, he ow-gene a ion subp oblem can be e o mu-
la ed as a ac able op imiza ion p oblem, whe e he objec i e unc ion is con-
ex in he ac ion and linea in he componen s o he s a e. I s solu ion can
also be used o cons uc a dynamic p icing heu is ic.
• A decomposi ion heu is ic based on bid-p ices ob ained by he DPP o ALP
app oach, sol ing se e al one-dimensional Bellman equa ions, yielding
igh e bounds and ypically be e p icing policies han hei coun e pa s.
• Enhanced decomposi ion heu is ic: Exploi ing he unique s uc u e o ou p ob-
lem, we in oduce a modi ied decomposi ion heu is ic ha ocuses on decompos-
ing only he componen ep esen ing he o al numbe o emaining sea s. This
a ge ed decomposi ion educes complexi y while main aining solu ion quali y.
• Compu a ional compa isons o bounds and p icing policies: We conduc a com-
p ehensi e nume ical s udy o compa e he pe o mance and un ime o he
uppe bounds and se e al p icing policies, including a simula ion-based app oxi-
ma e dynamic p og amming (ADP) policy. The esul s e eal ha ou enhanced
decomposi ion heu is ic seems o p o ide he bes ade-o be ween be ween
igh ness and compu a ional e o bo h wi h espec o he uppe bound as well
as he esul ing p icing.
• Sensi i i y analysis: Las ly, we in es iga e (1) i ou esul s depend on he a ac-
i eness o ex a sea ese a ions and (2) when selling ex a space is bene icial
om a business pe spec i e.
The pape is s uc u ed as ollows: Sec .2 e iews he ela ed li e a u e. In Sec .3,
we p esen he dynamic p og amming model and he cus ome choice model in
de ail. Since he model su e s om he cu se o dimensionali y e en o single-leg
p oblems, Sec .4in oduces h ee uppe bound p oblems. We in oduce dynamic
p icing policies based on hese uppe bound p oblems in Sec .5. Sec ion6 epo s
nume ical esul s and Sec .7 concludes he pape .
2 Li e a u e
In classical dynamic p icing models, a manage owns a ini e in en o y o esou ces
ha pe ish a e a ini e selling ho izon. The p oduc s o e ed a e composed o hese
esou ces. Cus ome s a i e s ochas ically and sequen ially o e ime. Time is o en
disc e ized in o a se o ime pe iods such ha he e is a mos one a i al wi hin a
gi en ime pe iod. Gi en he p ices, cus ome s can decide o buy one o he p oduc s
o e ed o lea e wi hou pu chasing any hing. The objec i e is o ind a se o p ices
o he p oduc s o each ime pe iod and in en o y s a e such ha he expec ed
1137
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
e enue is maximized. Dynamic p icing is widely applied ac oss a a ie y o sec o s,
includinghospi ali y, e ailing, ai a el, andpublic anspo a ion.
The dynamic p icing p oblem was i s desc ibed by Gallego and an Ryzin
(1994), who add ess a scena io wi h one p oduc consuming a single esou ce o e
a ini e con inuous- ime selling ho izon. Demand is s ochas ic and he demand a e
is ime-in a ian and depends only on p ice, which is a con inuous a iable. They
e o mula e i as an in ensi y/demand a e con ol p oblem and ob ain an exac solu-
ion when he selling p obabili y is an exponen ial unc ion o p ice. Building on
his, Gallego and an Ryzin (1997) ex end he model o mul iple p oduc s consum-
ing a se o esou ces. Since he compu a ional complexi y p ohibi i ely inc eases in
he numbe o p oduc s and esou ces, hey p opose wo solu ion heu is ics.
Fo excellen comp ehensi e e iews on dynamic p icing, we e e o he e iew
pape s o den Boe (2015) and Chen and Chen (2015), as well as he books by Tal-
lu i and Van Ryzin (2004) and Gallego and Topaloglu (2019).
A i s glance, ex a sea ese a ions may also seem ela ed o g oup bookings,
see, e.g., Haensel and Koole (2013). While bo h scena ios in ol e he simul aneous
booking o wo o mo e sea s, he e a e impo an di e ences in cus ome choices
and willingness- o-pay conside a ions. In ou se ing, a cus ome can eely choose
whe he o ese e one o wo sea s (i.e., an ex a sea ). By con as , a g oup o wo
will usually ei he pu chase wo sea s o none. Mo eo e , o a g oup o wo, he
willingness o pay o bo h sea s is o en modeled as wice he willingness o pay o
a single sea o a single cus ome . In con as , o ex a sea ese a ions, he will-
ingness o pay o he ex a sea is ypically much lowe han he willingness o pay
o he p ima y sea . Since we do no conside g oup bookings in his pape , we do
no discuss he li e a u e in his a ea in de ail.
In his pape , we dynamically p ice egula icke s, sea ese a ions and ex a
sea s. Since ex a sea s can be iewed as ancilla y p oduc s ha sha e esou ces
wi h he co e p oduc , we discuss li e a u e abou p icing o ancilla y p oduc s
in Sec .2.1. On he o he hand, egula icke s wi hou sea ese a ions could be
iewed as selling lexible p oduc s because he sea ha can ul ill his eques can
be assigned la e . The e o e, we discuss li e a u e discussing p icing o lexible
p oduc s in Sec .2.2. Sec ion2.3 ou lines he nes ed logi model and why i is na -
u ally sui ed o model sea ese a ion choice beha io . Since ou model o mula-
ion su e s om he well-known cu se o dimensionali y, we apply me hods om
app oxima e dynamic p og amming (ADP) o ob ain uppe bounds and heu is ics.
We discuss li e a u e on dynamic p icing models sol ed ia app oxima e linea p o-
g amming (ALP) and decomposi ion me hods in Sec .2.4.
2.1 P icing o ancilla y p oduc s
Sea ese a ions and ex a adjacen sea ese a ions a e o en ca ego ized as ancil-
la y p oduc s in RM, alongside se ices such as in- ligh meals and checked bag-
gage. A simple icke wi hou any sea ese a ion, on he o he hand, is ca ego ized
as he p ima y p oduc . Fo a comp ehensi e e iew o ancilla y p oduc s, we ec-
ommend Ozmec-Ban e al. (2022).
1138
C.Ba z e al.
Howe e , compa ed o in- ligh meals and checked baggage, sea ese a ions a e
cha ac e ized by he ac ha hey ha e a di ec impac on sea capaci y. Exis ing
s udies on dynamic p icing and ancilla y p oduc s ha e p ima ily ocused on ancil-
la y p oduc s ha do no consume he capaci y o he p ima y p oduc . Fo ins ance,
Wilson (2016) discusses a luid model o p icing a p ima y p oduc and mul iple
ancilla y p oduc s which e e mos ly o wa an y, checked baggage, e c., wi h lin-
ea expec ed demand unc ions. Simila ly, Ødegaa d and Wilson (2016) p esen a
dynamic p og am conside ing he p icing o a p ima y p oduc (speci ically a ligh )
along wi h checked baggage ees as an ancilla y p oduc . Demand is s ochas ic and
a ies o e ime. Building on he model o Wilson (2016); Zhao e al. (2021) inco -
po a es a ime-he e ogeneous linea demand unc ion in o he luid model. As hese
s udies ocus on ancilla y p oduc s ha do no ha e he same capaci y cons ain s as
he p ima y p oduc , hey ha e less impac on p icing decisions. To he bes o ou
knowledge, he e is a pauci y o li e a u e on dynamic p icing o ancilla y p oduc s
ha consume capaci y, despi e he widesp ead implemen a ion o such a business
idea in indus y. This gap highligh s he need o u he esea ch in his speci ic
a ea.
2.2 Flexible p oduc s
A lexible p oduc is a menu o wo o mo e al e na i es which he selle chooses
om a e he sale. The concep was in oduced o ne wo k RM by Gallego e al.
(2004) and Gallego and Phillips (2004). Gönsch (2020) p o ides a de ailed in o-
duc ion o he associa ed supply-side lexibili y as well as modeling app oaches
and e iews he wo k o di e en esea ch communi ies. This s eam o esea ch
is ele an because, echnically, a icke wi hou a ese a ion is a lexible p oduc :
I allows he selle o alloca e a designa ed sea a a la e s age. Acco dingly, he
dynamic p og am p esen ed in Sec .3.3 echnically desc ibes a special case o a
RM p oblem wi h a lexible p oduc ha comp ises a lo o al e na i es (all sea s).
Mo eo e , Koch e al. (2017) ha e shown ha e e y se ing wi h a bi a y lexible
p oduc s can be modeled as an equi alen (albei o en e y la ge) s anda d ne wo k
e enue managemen se ing (wi hou lexible p oduc s). Fo ou se ing, his ans-
o ma ion is easy and in ui i e, and we di ec ly s a e he p oblem as a ne wo k e -
enue managemen p oblem in Sec .3.3.
The li e a u e on dynamic p icing wi h lexible p oduc s is sca ce. Sie ag (2017)
ex ends he mul i-p oduc dynamic p icing o mula ion o Gallego and an Ryzin
(1997) o lexible p oduc s wi h a bi a y egula demand unc ions. Howe e , he
ocuses on a de e minis ic model ha se es as an uppe bound on he DP. Analo-
gous o he well-known de e minis ic p icing o mula ion as s a ed e.g. in Tallu i
and Van Ryzin (2004), he s ochas ic demand is eplaced by i s expec ed alues and
he in eg ali y cons ain s a e elaxed. The esul ing solu ion is hen used in wo
heu is ics, a make- o-s ock heu is ic and a make- o-o de heu is ic. Ou nes ed logi
demand model ul ills he equi ed egula i y condi ions s a ed by Sie ag (2017). Bu
since his de e minis ic o mula ion is equi alen o he well-known de e minis ic
1139
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
p icing p oblem o ne wo k e enue managemen in ou case, we do no discuss
de ails o his p oblem o mula ion in he ollowing.
We a e only awa e o one mo e pape dynamically p icing lexible p oduc s: Ce yan
e al. (2018) a e u he away om ou se ing as hey conside eplenishmen decisions
and upg ades in a mul i-pe iod e ail amewo k. They model cus ome choice h ough
alua ions and p opose a wo-s age MDP as well as a heu is ic o sol e he p oblem.
They also include an upg ade ee in hei model o mone ize upg ades.
2.3 The nes ed logi model indynamic p icing
We assume ha cus ome choice can be modeled by a nes ed logi model. The NL
model is an ex ension o he mul inomial logi model (MNL). The MNL, o iginally
p oposed by Luce (1959), has become a well-es ablished choice model in RM o e he
pas 40 yea s, see, e.g., S auss e al. (2018) o an o e iew. I is a simple and lex-
ible choice model wi h o igins in ma ke ing and RM (e.g., Ande son and Xie (2012)).
Bo h NL and MNL models belong o he class o andom u ili y models. These models
assume ha a gi en cus ome n possesses a andom u ili y, deno ed as
un,j
, o each
p oduc j. Among he se o a ailable al e na i es, he chooses he one wi h he high-
es u ili y. The MNL model assumes ha his u ili y consis s o a de e minis ic pa
n,j
and an i.i.d. Gumbel-dis ibu ed noise
𝜖n,j
. In he dynamic p icing se ing,
n,j
ob iously
depends on he p ice o p oduc j, besides o he p oduc cha ac e is ics. The MNL
model has been widely adop ed in dynamic p icing models, howe e , i su e s om he
well-known independence om i ele an al e na i es (IIA) p ope y.
The IIA assump ion s a es ha he a io o he p obabili ies o wo al e na i es does
no depend on any o he al e na i e, bu solely on he u ili ies o hese wo al e na i es.
In ou se ing, IIA implies ha i he numbe o ee sea s ( ha a e a ailable o single-
sea ese a ions) doubles, hen he p obabili y ha a gi en cus ome chooses a single-
sea ese a ion doubles as well. Howe e , his is no in ui i e. Fo mos cus ome s, he
numbe o a ailable sea s only ma ginally inc eases he p obabili y ha any ese a ion
is bough - especially i many sea s a e s ill a ailable.
To o e come IIA’s limi a ion, McFadden (1973) in oduced he NL model. The
NL allows ela ed al e na i es o be g ouped in he same nes and hei Gumbel-
dis ibu ed noises a e no longe independen . Unde he NL, cus ome s i s choose
a nes om se e al gi en nes s and hen p oceed o choose a p oduc wi hin he cho-
sen nes , making each choice along he line acco ding o he MNL. This s uc u e
alle ia es he IIA conce n associa ed wi h MNL.
Li and Huh (2011) apply NL o dynamic p icing and demons a e ha he o al
p o i unc ion exhibi s conca i y. This p ope y holds signi ican implica ions o
ou wo k, con ibu ing o he e ec i eness o ou p oposed heu is ic app oach.
Gallego and Wang (2014) use NL in an oligopolis ic mul i-p oduc dynamic p ic-
ing se ing. They simpli y he p oblem wice by showing ha he so-called adjus ed
ma kup is cons an o all p oduc s and ha he adjus ed nes -le el ma kup is
nes -in a ian .
Li e al. (2015) ex end he pape o Gallego and Wang (2014) by gene alizing
he nes ing s uc u e o mo e han wo s ages. Da is e al. (2017) ans o m a s a ic
1140
C.Ba z e al.
p icing p oblem wi h quali y consis ency cons ain s in o a linea p og am, bu con-
side he decision s ages as pa o a dynamic p og am in some se ings.
2.4 ADP Me hods indynamic p icing
Since ou model can be iewed as a ne wo k p oblem wi h
c+1
esou ces, whe e
esou ces
1, …,c
ep esen indi idual sea s wi h an ini ial capaci y o 1 and he las
esou ce ep esen s he o al numbe o icke s ha can be bough , ou wo k can also
be iewed as a special case o a ne wo k dynamic p icing p oblem wi h nes ed logi
demand.
Common heu is ic app oaches o sol e ne wo k RM p oblems include bo h ALP
as well as decomposi ion-based app oaches. The basic idea in ALP is o e o mula e
he dynamic p og am as an equi alen linea p og am (LP). In his LP, each decision
al e na i e leads o a cons ain and each s a e co esponds o a decision a iable,
which makes he LP p ohibi i ely la ge o sol e. Thus, a s anda d app oach is o
eplace he decision a iables by an app oxima ion consis ing o a ine (basis) unc-
ions. I hen uses ow gene a ion o educ ions o de e mine he pa ame e s o his
a ine app oxima ion. The objec i e alue o his app oxima ed linea p og am hen
p o ides an uppe bound on he op imal expec ed e enue. The op imal solu ion, i.e.
he pa ame e s o en ha e in ui i e in e p e a ions and can be used o cons uc poli-
cies o he con ol p oblem.
The o mal in oduc ion o ALP in o ne wo k RM was pionee ed by Adelman
(2007), who applies i o sol e capaci y con ol p oblems. Ke e al. (2019) ex ended
his amewo k o he dynamic p icing p oblem desc ibed in Gallego and an Ryzin
(1997), whe e ime is disc e e and p icing a iables a e con inuous. They app oxi-
ma e he decision a iables using a ine unc ions, demons a ing ha o an a ine
app oxima ion unde a linea demand unc ion, ALP can be e ec i ely used wi h
column gene a ion.
E en houghKe e al. (2019)do no analyze he sale o ex a adjac en sea s, hei
wo k is closely connec ed o ou wo k since hey discuss a ne wo k dynamic p icing
p oblem wi h gene al demand s uc u e. They de elop a igh e uppe bound o his
ne wo k p icing p oblem and sugges e icien solu ion me hods in he case o linea
demand. In addi ion, hey sugges a decomposi ion ha p o ides an uppe bound.
O he wo k applying decomposi ion me hods o e enue managemen p oblems
includes (Liu and an Ryzin 2008) and Zhang (2011).
3 The (ex a) sea ese a ion andp icing model
In his sec ion, we p esen he ma hema ical model used o in es iga e dynamic p ic-
ing o bo h icke s and (ex a) sea ese a ions. In pa icula , Sec .3.1 in oduces
he se ing and he no a ion. While we will always use bus e minology, ou p o-
posed p oblem o mula ion is qui e gene al and can be used o single-leg ain ides
o ligh s wi hou changes. Sec ion3.2 hen discusses he nes ed logi model used o
1147
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
and
w −1≤w
o all . In addi ion, hey p o e ha (AFF) p o ides a bound ha is a
leas as igh as (DPP), i.e.
V∗≤VAFF ≤VDPP
.
Ke e al. (2019) sugges o sol e (AFF) ia ow gene a ion. Howe e , sol ing
he ow gene a ion algo i hm o (AFF) can be compu a ionally expensi e. This is
because he algo i hm i e a i ely inds he la ges disc epancy be ween he le - and
igh -hand sides o he cons ain s ac oss all s a e-ac ion pai s and ime pe iods..
Using he nes ed logi model, howe e , subp oblems a e ela i ely easy o sol e
since o ixed s a e
(x,y)
he subp oblem is con ex. A ma hema ical o mula ion o
ha subp oblem and p oo o he ollowing heo em can be ound in Appendix B.1.
Theo em1 Fo a gi en s a e
(x,y)∈S
, he subp oblem o a ow-gene a ion algo-
i hm sol ing (AFF) o a gi en ime pe iod is a con ex op imiza ion p oblem in
p
.
Since he subp oblem is a con ex p oblem in
p
and linea in all s a e a iables
xi
and y, he subp oblem can be sol ed using a s aigh o wa d b anch-and-bound
algo i hm.
4.3 A Decomposi ion
The alue unc ion app oxima ion
wi h
i
ep esen ing exogenously gi en ime-independen alues o ese ed sea s
i=1, …,c
ep esen s a dynamic p og amming decomposi ion. Fixing
V0
(y)=
0
o
all y and plugging his in o he Bellman equa ions, we ob ain
whe e we used ha
P(1,y)⊇P(x,y)
o all
x∈{0, 1}c
.
The i e a i e solu ion o (DPD-BE) ia backwa d induc ion only implies he solu-
ion o con ex op imiza ion p oblems o each ime pe iod and sea occupancy le el
y. The esul also p o ides an uppe bound ha is igh e han he bound p o ided by
he de e minis ic p icing p oblem (DPP).
Theo em2 Independen o he choice o
i
,
V∗≤VDPD
. Deno ing he solu ion o
(DPD-BE) wi h alues
i
gi en by he op imal solu ion o (DPP) by
VDPD* =
VT(c)
,
we u he ha e
(APPROX-DPD)
V
(x,y)≈
V (y)+
c
∑
i=1
ixi
,
(DPD-BE)
V
(y)= max
p∈P(1,y)
{
p0
V −1(y)+p1( 1(p)+
V −1(y−1
))
+∑
i
p2,i( 2,i(p)+
V −1(y−1)− i)
+
∑
i
p3,i( 3,i(p)+
V −1(y−2)− i− i∗)
}
,
V∗≤VDPD* ≤VDPP.
1148
C.Ba z e al.
The p oo o Theo em2, highligh ing he connec ion o P oposi ion 5 in Ke e al.
(2019), can be ound in Appendix B.2.
No e ha in ypical ne wo k p icing p oblems, i is unclea which componen o
he s a e space should be modeled by a alue unc ion and which ones should be
assumed linea . In ou special case, howe e , he sea ese a ions only ha e alues
0 and 1, so a linea app oxima ion is no es ic i e. Wha is es ic i e is ha we do
no allow he alue o a sea ese a ion o sea i,
i
, o depend on ime. We discuss
a ime-dependen e sion in Appendix C.
5 P icing policies
The op imal p ices in s a e
(x,y)
a ime a e gi en by he a gumen
maximizing
he igh -hand side o he Bellman equa ion (BE). Subs i u ing
p0=1−p1−p2−p3
and applying Lemma 1, we can e o mula e he Bellman equa ions maximizing o e
he pu chasing p obabili ies
p
and he op imal p obabili ies in s a e
(x,y)
a ime a e gi en by
The abo e op imiza ion p oblem is con ex in
p
as shown in Theo em1. In addi-
ion, he i s e m,
V −1(x,y)
is a cons an ha does no change in
p
and can hence be
d opped when inding he
a g max
. In a inal s ep, we ansla e
p∗
(x,y)
in o op imal
p ices applying Lemma 1 again.
Howe e , his app oach elies on de e mining all alues o he alue unc ion V,
which is compu a ionally in easible due o he la ge s a e space, e en o mode a e
(3)
V
(x,y)=V −1(x,y)+ max
p∈P(x,y)
{
p1
(
1(p)−
[
V −1(x,y)−V −1(x,y−1))
])
+∑
i
p2,i( 2,i(p)−[V −1(x,y)−V −1(x−ei,y−1)])
+
∑
i
p3,i
(
3,i(p)−
[
V −1(x,y)−V −1(x−ei−ei∗,y−2)
])}
(BE-RHS)
p
∗
(x,y) =a gmax
p∈P(x,y)�p1
⎛
⎜⎜⎜⎝
1(p)−�V −1(x,y)) − V −1(x,y−1)�
⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
Value o 1 sea
⎞
⎟⎟⎟⎠
+�
i
p2,i⎛⎜⎜⎜⎝
2,i(p)−�V −1(x,y)−V −1(x−ei,y−1)�
⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
Value o 1 sea and a ese a ion o sea i
⎞⎟⎟⎟⎠
+�
i
p3,i⎛
⎜⎜⎜⎝
3,i(p)−
�
V −1(x,y)−V −1(x−ei−ei∗,y−2)
�
⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
Value o 2 sea s and ese a ions o sea s iand i
∗
⎞
⎟⎟⎟⎠
�
.
1149
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
capaci y le els. This is why, in he ollowing, we discuss a ious p icing heu is ics
o ou p icing p oblem wi h ese a ions and ex a sea s. The co e idea o hese
policies is o es ima e he ue alue unc ions abo e by he app oxima ions p o ided
by ou uppe bound p oblems.
5.1 A policy based on hede e minis ic p icing p oblem
Le
w∗
be he ( ime-independen ) dual alue o he capaci y cons ain o y in
(DPP) and he alues
∗
i
be he co esponding dual alues o he capaci y con-
s ain s o he
xi
s in (DPP). Using hese, we app oxima e he alue o each sea
by
w∗
and he alue o a ese a ion o sea i by
∗
i
. This is equi alen o assuming
V
(x,y)≈
∑i
x
i
∗
i
+w
∗y
and eplacing (BE-RHS) by
We will e e o his s a ic p icing policy as (Policy-DPP). The p ice p o ided by his
policy only depends on he cu en s a e solely o de e mine he se o easible ac ions.
5.2 A policy based on hea ine app oxima ion
Simila ly, a s aigh o wa d app oach o app oxima ing (BE-RHS) is o eplace all
occu ences o he alue unc ion by he a ine app oxima ion (APPROX-AFF) using
pa ame e s gi en by he op imal solu ion o (AFF). Deno ing he op imal alues o
i
s and
w
s in (AFF) as
∗
i,
s and
w∗
s, will e e o he dynamic p icing policy sol ing
o gi en s a e
(x,y)
a ime as (Policy-AFF) in he ollowing. This p icing policy is
now ime-dependen bu s ill only depends on he cu en s a e h ough he de ini ion
o easible ac ions.
5.3 A policy based ondecomposi ions
Simila ly, eplacing he alue unc ions in (BE-RHS) by he decomposi ion
(APPROX-DPD), we ob ain
(Policy-DPP)
p
∗
(x,y) =a gmax
p∈P(x,y)
{
p1
(
1(p)−w∗
)
+
∑
i
p2,i
(
2,i(p)−(w∗+ ∗
i)
)
+
∑
i
p3,i
(
3,i(p)−(2w∗+ ∗
i+ ∗
i∗)
)}
.
(Policy-AFF)
a gmax
p∈P(x,y)
{
p1
(
1(p)−w∗
−1
)
+
∑
i
p2,i
(
2,i(p)−(w∗
−1+ ∗
i, )
)
+
∑
i
p3,i
(
3,i(p)−(2w∗
−1+ ∗
i, + ∗
i∗, )
)}
1150
C.Ba z e al.
Using alue unc ions
V −1(
y
)
p o ided by (DPD-BE) and
i
gi en by he de e -
minis ic p icing p oblem (DPP), we ob ain a p icing policy ha now explici ly
depends on he cu en s a e and ime un il depa u e. This p icing policy is e e ed
o as (Policy-DPD).
6 Nume ical s udy
In ollowing nume ical s udy, we i s (Sec .6.1) compa e he quali y o he uppe
bounds we sugges ed in Sec .4. In Sec .6.2, we hen analyze he pe o mance o
he p icing policies p esen ed in Sec .5. To in es iga e he easons o pe o mance
di e ences, we analyze he p ices se in Sec .6.3. Then, we look a how he esul s
depend on he a ac i eness o p oduc ype 3, i.e. a sea wi h an ex a emp y sea
(Sec .6.4). Finally, in Sec .6.5, we quan i y he business impac o selling ex a
sea s compa ed o no doing so. Appendices C and D p esen a decomposi ion
app oach based on ime-dependen sea alues, as de ined in AFF, along wi h a p ic-
ing policy gene a ed using simula ion-based ADP. E en hough hese policies p o-
ide la ge expec ed e enues, hey a e no discussed in he main ex because hey
a e compu a ionally expensi e and o e li le manage ial insigh .
Th oughou , we conside a bus ha has a o al o c sea s whe e
c∈{8, 16, 24, 32, 40, 48, 56, 64, 72, 80}
. The leng h o he ime ho izon is dependen
on he numbe o sea s and equals
T=2⋅c
. The p oduc wi h index 0 deno es he
no-pu chase al e na i e.
The NL model desc ibed in Sec .3.2 inco po a es h ee se s o cus ome choice
pa ame e s. Quali y indices (
a1,a2,i,a3.i
), ep esen he u ili y associa ed wi h choos-
ing speci ic sea s o p oduc s. Nes simila i ies (
𝜏1,𝜏2,𝜏3
) measu e he deg ee o
simila i y among al e na i es wi hin a gi en choice nes . Finally, p ice sensi i i-
ies (
b1,b2,b3
) cap u e he in luence o p ice on he p obabili y o cus ome choice,
e lec ing how p ice changes a ec decision-making. We assume
a1=0.2
,
𝜏1=1
,
𝜏2=0.4
,
𝜏3=0.6
,
b1=0.2
,
b2=0.4
, and
b3=0.6
, and model di e en cus ome
p e e ences wi h espec o single o double sea ese a ions by a ying he se ing-
speci ic choice beha io pa ame e s
a2,i
and
a3,i
. In pa icula , we dis inguish h ee
se ings:
• HOMOG (homogeneous cus ome p e e ences): Quali y indices a e se o
a2,i=0.4
and
a3,i=0.6
o all sea s i.
(Policy-DPD)
a gmax
p∈P(x,y)
{
p1
(
1(p)−
[
V −1(y)−
V −1(y−1)
])
+∑
i
p2,i( 2,i(p)−[
V −1(y)−
V −1(y−1)+ i])
+
∑
i
p3,i
(
3,i(p)−
[
V −1(y)−
V −1(y−2)+ i+ i∗
])}
1151
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
• AW (p e e ences o aisle and window sea s di e ): Le
Ia
be he se o indices o
aisle sea s and
Iw
he indices o window sea s. We assign quali y indices o win-
dow sea s as
a2,i=0.5
o all
i∈Iw
and o aisle sea s as
a2,i=0.4
o all
i∈Ia
.
Double ese a ions include one aisle and one window sea , and we assign hem
he same quali y index as in he HOMOG se ing:
a3,i=0.6
o all
i
.
• HET (he e ogeneous sea p e e ences): In his se ing, sea p e e ences
inc ease wi h sea numbe , e lec ing a p e e ence o he back o he
coach. Thus, we choose
a2,i=0.39 +0.01i
. Simila o p oduc 2, we use
a3,i=0.585 +0.02
⋅
⌈i∕2⌉
such ha he alue inc eases by 0.02 o e e y sea
pai and he inc emen on wo sea s o p oduc 2 equals he inc emen on hese
sea s o p oduc 3.
To u he explo e he implica ions o di e en ia ed p e e ences, we p esen an addi-
ional se ing in Appendix E whe e only p oduc ype 3 exhibi s a ying sea p e e -
ences. The esul s a e almos he same as in he abo e se ings.
We used CVX 1.1.18 in Py hon 3.8.10 o sol e con ex op imiza ion p oblems
and CPLEX 22.1.1 o linea p og amming p oblems. Fo non-con ex mixed-in ege
p og amming p oblems, we implemen ed a cus om b anch-and-bound algo i hm
based on CVX. All compu a ions we e pe o med on a sys em unning Mic oso
Windows 11 En e p ise S anda d 64-bi , equipped wi h an AMD Ryzen 7 PRO
5850U p ocesso wi h 8 CPU co es and 30.8 GB o RAM. We used common an-
dom numbe s o compa e di e en p icing policies and cus ome p e e ence se ings.
6.1 Compa ison o uppe bounds
In his sec ion, we in es iga e he pe o mance o he uppe bounds discussed in
Sec .4. In pa icula , we conside he ollowing bounds:
• UB DPP: objec i e alue o (DPP) (Sec .4.1).
• UB AFF: objec i e alue o ALP (AFF) (Sec .4.2).
• UB DPD: dynamic p og amming decomposi ion (DPD-BE) (Sec .4.3).
• UB DPD-Benchma k: bid p ice decomposi ion heu is ic in oduced in Ke e al.
(2019)
The benchma k in oduced in Ke e al. (2019) was designed o he gene al ne wo k
p icing p oblem. I s co e idea is he same as he idea p esen ed in (DPD-BE) bu i
compu es bo h
V (y)
and
V (xi)
o all componen s
xi
. The uppe bound, UB DPD-
Benchma k is hen de i ed by aking he minimum o he bounds ob ained om
V (y)
and
V (xi)
. As a consequence, we expec his benchma k o be a leas as good
as ou (DPD-BE) p oblem bu compu a ionally much mo e expensi e,
Figu e3a, c and e show he alues o hese uppe bounds ela i e o UB DPD-
Benchma k o he h ee cus ome choice se ings. Figu e3b, d and show he co e-
sponding un ime necessa y o calcula e hese bounds. Missing alues indica e ha
he un- ime exceeded 50,000s.
1152
C.Ba z e al.
We obse e ha he quali y o he uppe bounds, as well as hei un imes, a e
s ikingly simila ac oss all demand se ings.
Compa ing ou decomposi ion heu is ic wi h i s benchma k, we obse e ha ou
hypo heses a e ue: The alue o UB DPD is iden ical o he benchma k uppe bound UB
DPD-Benchma k in oduced in Ke e al. (2019). This can be in ui i ely explained by he
ac ha , as
xi
only akes bina y alues,
V
(x
i)
can be closely app oxima ed by an a ine
unc ion. By con as ,
V
(y
)
akes inpu
y∈{0, 1, ..., c}
, making i ha de o be app oxi-
ma ed by an a ine unc ion. Nume ical esul s unde pin ha
V
(y
)
ypically p o ides a
igh e uppe bound han he ones p o ided by
V
(x
i)
. So while he solu ion quali y is simi-
la , UB DPD is much as e han UB DPD-Benchma k.
UB DPP is p o ably he weakes bound among he ou . I is unclea a p i-
o y, howe e , how la ge he di e ence is (o i he e e en is one) and how UB
AFF and UB DPD compa e. Ou nume ical esul s show ha UB DPP is always
sligh ly wo se han UB AFF and bo h a e conside ably wo se han bo h UB DPD
and UB DPD-Benchma k. The di e ence dec eases wi h bus size om abou
12% o small busses o 2% o la ge ones.
Compa ing he un imes o ou uppe bound p oblems, UB AFF is he mos
expensi e uppe bound p oblem, exceeding ou 50,000s cu o e en o mode -
a e bus sizes. The solu ion o he semi-in ini e linea p og am UB AFF uses a
ow gene a ion algo i hm ha equi es he solu ion o a b anch-and-bound algo-
i hm o e e y ime pe iod in he selling ho izon o each subp oblem.
The bounds based on he con ex op imiza ion p oblem UB DPP a e much
as e o sol e. Unsu p isingly, UB DPP is as e han he decoposi ion
app oaches, as i s solu ion se es as an ini ial s ep o bo h.
Compa ing he un imes o UB DPD and UB DPD-Benchma k, he compu-
a ion o UB DPD is conside ably sho e ( oughly 50%), especially o la ge
ins ances. This is expec ed since he benchma k heu is ic compu es mul i-
ple uppe bounds and epo s he minimum. Fo a p oblem o bus size c and
ime ho izon T, UB DPD has o sol e cT con ex op imiza ion p oblems and he
benchma k heu is ic 3cT.
In compa ison wi h he o he uppe bounds, UB DPD p o ides a low uppe
bound, and pe o ms he second bes in un ime. Fo a bus wi h 80 sea s, i akes
less han 10,000s o compu e UB DPD. This makes i easy o use in p ac ice.
UB DPP pe o ms he bes in e ms o un ime. Howe e , i also p o ides he
wo s uppe bound due o he simplici y in he s uc u e o his app oach.
6.2 Compa ison o expec ed e enues omp icing policies
Tigh bounds a e o g ea in e es as empi ical s udies and p ac ical expe ience sug-
ges ha models ha gi e igh e bounds o en lead o be e con ols (leading o
highe expec ed e enue), bu he e is no gua an ee, see (Tallu i 2009). Thus, in
he ollowing, we in es iga e he pe o mance o he policies discussed in Sec .5.
In pa icula , we in es iga e he p icing policies (Policy-DPP), (Policy-AFF),
1153
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
(Policy-DPD) and he bid-p ice decomposi ion desc ibed in Ke e al. (2019) as a
benchma k (Policy-DPD-Benchma k), wi h 100 simula ion uns each.
The addi ional un ime o he policies is negligible and compa able o all
policies. Once he uppe bounds a e calcula ed, in each ime pe iod only one
con ex op imiza ion p oblem has o be sol ed o de e mine he p ices o he
cu en s a e.
Figu e4a, b and c show he pe o mances o all p icing policies ela i e o UB
DPD. The p icing policy based on he de e minis ic p icing p oblem, (Policy-DPP),
ends o pe o m wo s , wi h (Policy-AFF) being only sligh ly be e in mos cases.
The gap o he uppe bound a ies be ween 6% and 12% o bo h policies. P icing
ia (Policy-DPD) ends o imp o e expec ed e enue by 1–5 pe cen age poin s (pp)
compa ed o (Policy-DPP), depending on he bus size. Simila e enues a e ob ained
using he benchma k p icing heu is ic (Policy-DPD-Benchma k).
Fig. 3 Uppe bounds o op imal expec ed e enue, 1.00
=
UB DPD and un ime (seconds) necessa y
o calcula e uppe bounds. UB DPD and UB DPD-Benchma k yield iden ical esul s. Missing alues o
la ge bus sizes a e caused by un ime limi iola ions
1154
C.Ba z e al.
6.3 Compa ison o p icing policies
We in oduced he uppe bounds and p icing heu is ics because he cu se o dimen-
sionali y p e en s an exac solu ion in ins ances wi h la ge capaci ies. To disen angle
he e ec s o selling ex a sea s om he e ec s o ou heu is ics, we now ocus on
an ins ance ha can be sol ed exac ly, i.e., wi h a bus size o
c=8
.
In ou dynamic p icing p oblem, p ices o all p oduc s a e de e mined a he
beginning o each ime pe iod depending on he cu en numbe o sea s sold y,
and he ese a ions
x
. To simpli y he exposi ion, we only discuss he homogeneous
sea p e e ence se ing since all p ices o p oduc s o ypes 2 and 3 a e iden ical. In
o he wo ds, o each ,y and
x
, he e is a
p2=p2,i
and a
p3=p3,i
o all i.
Sol ing (BE), we can de e mine he op imal p ices o all h ee p oduc ypes
o each s a e and ime pe iod. Figu e5 shows median p ices o
=1, …, 16
and
y=1, …,8
. Gi en and y, he median p ices o e all possible ese a ion s a es
x
a e displayed. No p ices a e displayed o p oduc ype 3 gi en
y=1
since i equi es
wo uni s o his esou ce. Unsu p isingly, he p ice o a ype 1 p oduc is cheape
han he co esponding ype 2 p oduc , which is cheape han he co esponding ype
3 p oduc . A ype 3 p oduc is almos wice he p ice o a ype 2 p oduc ea ly on,
since he e is no ad an age o selling o a ype 3 cus ome wi h sca ce capaci y. The
di e ences ge much smalle close o depa u e, especially i ex a sea s a e a ail-
able, since he oppo uni y cos o one ex a sea dec eases in ime. Mo eo e , p ices
demons a e he ypical mono one beha io in and y.
No e ha op imal p ices, howe e , do depend no only on and y bu on
x
as well.
Conside , e.g., a bus wi h only wo speci ic sea s le o sell,
y
=
∑i
x
i
=
2
. Only i
he wo emaining sea s a ailable a e adjacen , cus ome s eques ing p oduc ype
3 can s ill be se ed. Since u u e demand is highe in his case, we expec highe
p ices o ype 1 and ype 2 p oduc s. We demons a e his by depic ing he op imal
p ices o p oduc ypes 1, 2 and 3 o all
=1, …, 16
in Fig.6. As expec ed, he
p ices o p oduc ypes 1 and 2 a e highe gi en wo ee adjacen sea s han he
co esponding p oduc s’ p ices in he non-adjacen sea case. Again, p oduc ype 1
is always p iced lowe han p oduc ype 2. I p oduc ype 3 is a ailable, i is e en
mo e expensi e han ype 2. Again, we can see ha ea ly in he booking ho izon,
he p ice o p oduc 3 is almos wice he p ice o p oduc 2 in he case o adjacen
sea s. The p ice di e ence be ween p oduc ypes 2 and 3 dec eases as depa u e
app oaches.
To compa e he pe o mance o ou heu is ics wi h he op imal p icing policy,
Fig. 7 illus a es he p ices ob ained om (Policy-AFF), (Policy-DPP), (Policy-
DPD) and (Policy-DPD-Benchma k) gi en
y
=
∑i
x
i
=
2
. P ices p o ided by he
s a ic p oblem (Policy-DPP) a e cons an o e ime and a e lowe han he p ices
o all o he policies. In con as , he a ine app oxima ion policy (Policy-AFF) sug-
ges s o e ing highe p ices ea ly in he selling ho izon and educing hem only du -
ing he inal ime pe iods, pa icula ly o p oduc ype 3. Bo h (Policy-DPD) and
(Policy-DPD-Benchma k) ecommend s a ing wi h signi ican ly highe p ices and
1155
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
dec easing hem mo e subs an ially o e ime. P ices o p oduc ype 1 wi h a aila-
ble adjacen sea s a e e y simila o (and some imes he same as) p ices o p oduc
Fig. 4 A e age e enue o p icing policies, 1.00
=
UB DPD. Missing alues o la ge bus sizes a e
caused by un ime limi iola ions
1156
C.Ba z e al.
ype 2 wi hou a ailable adjacen sea s o (Policy-DPD) and (Policy-DPD-Bench-
ma k). Al hough he p ice s uc u es o (Policy-DPD) and (Policy DPD-Benchma k)
a e simila , he la e consis en ly ecommends sligh ly highe p ices. When com-
pa ed o he op imal p ices (Fig.6), he p ice cu es p oduced by (Policy-DPD)
and (Policy-DPD-Benchma k) exhibi a compa able shape bu s a a highe p ice
le els.
6.4 Impac o hea ac i eness o p oduc ype 3
To examine he impac o p oduc ype 3 a ac i eness, we sol ed o op imal p ices
ia (BE) in he HOMOG se ing gi en a bus wi h
c=8
sea s a ying he a ac i e-
ness o ex a sea ese a ions,
a3,i=a3∈{0, 0.1, …, 4.9, 5}
o
i=1, …,c
. Fig-
u e8 compa es he mean e enue ob ained applying he p icing policies men ioned
abo e o e 100 simula ions. These esul s a e compa ed o he mean e enue om
applying he op imal policy and he igh es uppe bound, UB DPD.
As expec ed, bo h he uppe bound and he mean e enues inc ease as he a ac-
i eness o p oduc ype 3 ises. This is in ui i e because, o a ixed p ice ec o
p
,
inc easing he alue o
a3
while keeping
a1
and
a2
cons an educes he no-pu chase
p obabili y. We obse e ha (Policy-DPP) and (Policy-AFF) consis en ly pe o m he
Fig. 5 Hea map o median op imal p ices o a ailable sea s o each p oduc ype o e he booking ho i-
zon gi en y
1163
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
li e a u e. In con as , policies based on s a ic p oblems like he de e minis ic p ic-
ing p oblem o he a ine app oxima ion deli e lowe e enues, wi h gaps o a ound
6–12% ela i e o he bes uppe bounds.
The in oduc ion o ex a sea ese a ions (ou p oduc ype 3) shows no able e e-
nue imp o emen s, especially in low-demand scena ios, whe e e enue inc eases by up
o 63.8%. E en in high-demand condi ions, selling ex a sea s p o ides modes bene i s,
ensu ing i s alue ac oss di e en demand le els. Ou sensi i i y analysis modeling
cus ome s who de i e li le ex a u ili y om ex a sea s when he bus is emp y e eals
ha e enue gains diminish wi h inc easing cus ome sensi i i y o bus occupancy bu
emain signi ican , exceeding 8% e en in he mos ad e sa ial cases.
In a nushell, ou indings emphasize he impo ance o adap i e p icing and le e ag-
ing ex a sea ese a ions o maximize e enue unde a ying ma ke condi ions.
To ou knowledge, his is he i s pape discussing a ma hema ical model o dynami-
cally p ice ex a sea s as well as egula icke s and sea ese a ions. As a consequence,
we see ample oppo uni ies o u u e esea ch.
Since each sea is ea ed as an indi idual esou ce, ou p oposed model is highly
lexible and can accommoda e a ious sea ing con igu a ions. I ex a sea s a e s ic ly
assigned o ese a ions (e.g., o pe sonal i ems), he model can be di ec ly applied
wi h mino adjus men s. An in ui i e ex ension would be a business model whe e only
an emp y adjacen sea is gua an eed, bu i s use is es ic ed. Fo ins ance, h ee adja-
cen sea s could be sold as wo ype-3 p oduc s, p o ided he emp y sea is he middle
one. Wi hin ou amewo k, his can be modeled such ha a egula sea ese a ion o
sea i equi es 1 uni o esou ce i, while selling sea i as an emp y sea would equi e
0.5 uni s o esou ce i. Al hough his adjus men in oduces addi ional complexi y o he
a ine app oxima ion—since he
xi
a iables a e no longe bina y—we an icipa e ha
he decomposi ion app oach would s ill pe o m e ec i ely wi h hese modi ica ions.
Empi ical s udies could alida e ou app oaches agains indus y p ac ices, sug-
ges pa ame e es ima es o ou NL choice model, o sugges o he choice models ha
should be conside ed. To acili a e indus y implemen a ion, ou wo k could also be
ex ended o accoun o a small, disc e e se o p ices only. In addi ion, simple heu is-
ics o allow o he analysis o a ne wo k o connec ing legs could be de eloped o
applica ions wi h many s ops, e.g., bus o ail se ices.
In conclusion, we hope ha ou esea ch inspi es mo e wo k on his impo an
indus y p ac ice and pa es he way o complemen a y empi ical esea ch o assis
companies in implemen ing e enue managemen in he ace o low-demand scena ios.
Appendix A: P oo o Lemma 1
We i s show (1). Acco ding o he de ini ions o he NL choice p obabili ies, we ha e
Since
𝜏j
>
0
, his yields
pj( )
p0( )=pj( )
1−
∑
l=1,2,3 pl( )=e𝜏jIj=
⎡
⎢
⎢
⎣�
i∈Nj
eaj,i−bj j,i
⎤
⎥
⎥
⎦
𝜏
j
∀j=
2, 3.
1164
C.Ba z e al.
A he same ime, he de ini ion o
pj,i( )
implies
Mul iplica ion by
∑
k∈N
j
e
a
j,k
−b
j
j,
k
gi es
Subs i u ing
∑
i∈N
j
e
a
j,i
−b
j
j,
i
by (A1) and ea anging e ms yields:
Taking he na u al loga i hm leads o:
Sol ing o
j,i
, we ob ain equa ion (1) o Lemma 1 and can in e p e
j,i
as a
unc ion o
p
:
(A1)
�
i
∈N
j
eaj,i−bj j,i=
�
pj( )
1−
∑
l=1,2,3 pl( )
�
1
𝜏j
∀j=
2, 3.
pi
�
j( )=
p
j,i
( )
pj( )=eaj,i−bj j,i
∑
k∈N
j
eaj,k−bj j,k
∀j=2, 3, i=1, ..., c
.
e
aj,i−bj j,i=
p
j,i
( )
pj( )
∑
i∈N
j
eaj,i−bj j,i∀j=2, 3, i=1, ..., c
.
e
aj,i−bj j,i=pj,i( )
pj( )( )
�
pj( )
1−∑l=1,2,3 pl( )
�
1
𝜏j
=pj,i( )
1−
∑
l=1,2,3 pl( )
�
pj( )
1−
∑
l=1,2,3 pl( )
�
1
𝜏j
−1
∀j=2, 3, i=1, ..., c
.
log �eaj,i−bj j,i�=log
⎛
⎜⎜⎝
pj,i( )
1−∑l=1,2,3 pl( )
�
pj( )
1−∑l=1,2,3 pl( )
�1
𝜏j
−1
⎞
⎟⎟⎠
∀j=2, 3, i=1, ..., c
⇔
aj,i−bj j,i=log �pj,i( )
1−∑l=1,2,3 pl( )�+1−𝜏j
𝜏j
log �pj( )
1−∑l=1,2,3 pl( )�
=log pj,i( )−log �1−�
l=1,2,3
pl( )�
+1−𝜏j
𝜏j�log pj( )−log �1−�
l=1,2,3
pl( )��
∀j=2, 3, i=1, ..., c.
1165
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
The p oo o equa ion (2) can be de i ed along he same lines.
Appendix B: P oo s abou uppe bound p oblems based onalinea
p og am
I is well-known, see e.g. Adelman (2007), ha he ollowing semi-in ini e linea
p og am also p o ides
V∗
No e ha p oblem (LP) has an in ini e numbe o cons ain s and one a iable
o each po en ial s a e in each ime pe iod. To educe he numbe o s a es, he
alue unc ion is o en eplaced by a linea combina ion o so-called basis unc ions,
yielding an app oxima ion. This me hod o app oxima ing he solu ion o a MDP is
o en e e ed o as app oxima e linea p og amming.
B.1: P oo o Theo em1
Using he alue unc ion app oxima ion (APPROX-AFF) in (LP) yields
(Policy-AFF).
Applying he ans o ma ion om Lemma 1, he subp oblem o he co espond-
ing ow gene a ion p oblem is
j,i(p)=aj,i
bj
+1
bj
[
log
(
1−
∑
l=1,2,3
pl
)
−log pj,i
]
+1
bj
1−𝜏j
𝜏j
[
log
(
1−
∑
l=1,2,3
pl
)
−log pj
]
,∀j=2, 3, i=1, ..., c
.
(LP)
V∗=min
V (⋅), =1,…,T
V
T
(1,c)
s. . V (x,y)≥p0( )V −1(x,y)+p1( )( 1+V −1(x,y−1))
+∑
i
p2,i( )( 2,i+V −1(x−𝐞𝐢,y−1)
+∑
i
p3,i( )( 3,i+V −1(x−𝐞𝐢−𝐞𝐢∗,y−2
))
∀ =T, ..., 1, (x,y)∈S , ∈R(x,y)
V
0
(x,y)≥0∀(x,y)∈S
,
1166
C.Ba z e al.
wi h
I he e a e ime pe iods wi h
𝜋 >0
, he op imal objec i e alue o (P1-AFF)
migh be lowe han he co esponding alue o (AFF). Ke e al. (2019) p o e, how-
e e , ha he di e ence will ne e exceed
∑
𝜋
, which can be used in a s opping
c i e ion o o bound
VAFF
and, hus,
V∗
.
We use (AFF-sub) o epea Theo em1 wi h mo e p ecise no a ion: Theo em1 Fo
a gi en s a e
(x,y)∈S
, subp oblem (AFF-sub) is a con ex op imiza ion p oblem.
P oo Fi s , no e ha he easible se o
p
,
P(x,y)
, is linea and hus con ex. In addi-
ion, he only e ms in (AFF-sub) depending on
p
in a non-linea way a e
To p o e ha he op imiza ion p oblem is con ex, i hence su ices o show ha ,
and hence he objec i e unc ion o be minimized, is conca e in
p
.
Explici ly w i ing he dependence o p ice on
p
, (1), in
(p)
yields
The i s wo e ms, p1
a1
b1
and pj,i
a
j,
i
b
j
, a e linea in
p
. To show ha he nex wo
e ms a e conca e, we mimic he p oo o Li and Huh (2011): Le
g(x,y)=x(log x−log(1−y))
. The Hessian ma ix o g(x,y) is:
(AFF-sub)
𝜋
∶= max
(x,y)∈S ,p∈P(x,y)
𝜋 ∶=p1( 1(p)−w −1)+
∑
i
p2,i( 2,i(p)− i, −1−w −1
)
+∑
i
p3,i( 3,i(p)− i, −1− i∗, −1−2w −1)
−𝜃 +𝜃 −1−(w −w −1)y−
∑
i
( i, − i, −1)xj
P
(x,y)=
�
p∈P∶p1≤y,p2,i≤xi,p2,i≤y,
p3,i≤xi,p3,i≤xi∗,p3,i≤
⌊
y∕2
⌋
∀i=1, …,c
�.
(p)=p1 1(p)+
∑
i
p2,i 2,i(p)+
∑
i
p3,i 3,i(p)
.
(p)=p1
a1
b1
+
∑
j=2,3
∑
i
pj,i
aj,i
bj
+p1
(
1
b1
1
𝜏1
[
log
(
1−
∑
j=1,2,3
pj
)
−log p1
])
+∑
j=2,3 ∑
i
pj,i(1
bj[log (1−∑
j=1,2,3
pj)−log pj,i]
+1
bj
1−𝜏j
𝜏j
[
log
(
1−
∑
j=1,2,3
pj
)
−log pj
])
1167
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
We can show ha his Hessian is posi i e semi-de ini e by compu ing (
𝛼,𝛽∈ℝ
):
The e o e, g is con ex. Since an a ine unc ion o a con ex unc ion is s ill con-
ex, he unc ions
g=g(p1,∑ipi)
and
g(
pj,i,
∑i,j
pi,j
)
a e also con ex.
Using he same a gumen o he hi d e m and no icing ha is a unc ion o
−g
and
−g
shows he conca i y o .
◻
B.2: P oo o Theo em2
Plugging
wi h
V0
(y)=
0
o all y in o (LP) yields
The esul ing p oblem hence mi o s he one desc ibed in Ke e al. (2019) and
Zhang and Adelman (2009) and we p o e he esul acco dingly:
V∗≤VDPD
holds because e e y easible solu ion o (DPD) is also easible in
he o iginal p oblem (LP). This inequali y also implies he i s inequali y in he
sequence
V∗≤VDPD* ≤VDPP.
The second inequali y ollows om he ac ha
(DPP) is equi alen o assuming he ime-independen alue unc ion app oxima ion
V (x,y)=𝜃+∑i ixi+wy
, see e.g. Adelman (2007). Using his equi alence, e e y
easible solu ion o (DPP) wi h
i= ∗
i
co esponds o a easible solu ion o (DPD)
choosing
V(y)=𝜃+wy
. As a consequence, he second inequali y holds.
H
g(x,y)=
[1
x
1
1−y
1
1−y
x
(1−y)
2
]
�
𝛼𝛽
�
⋅Hg(x,y)⋅
�
𝛼
𝛽
�
=
�
𝛼
√
x
+𝛽
√
x
1−y
�2
≥
0.
V
(x,y)≈
V (y)+
c
∑
i=1
ixi
,
(DPD)
V
DPD =min
V (⋅), =1,…,T
VT(y)+
c
∑
i=1
i
s. .
V (y)≥&p0( )
V −1(y)+p1( )( 1+
V −1(y−1
))
+∑
i
p2,i( )( 2,i+
V −1(y−1)− i)
+∑
i
p3,i( )( 3,i+
V −1(y−2)− i− i∗, −1)
∀ =T
, ..., 1,
(
x,
y)∈
,
∈
(
x,
y)
.
1168
C.Ba z e al.
Appendix C: Adecomposi ion based on ime‑dependen sea ‑ alues
In his sec ion o he appendix, we in oduce a decomposi ion based on ime-
dependen sea - alues. A sho nume ical s udy shows ha un imes o his heu is ic
a e la ge and ex a bene i s a e small when compa ed o he co esponding decom-
posi ion based uppe bound (DPD-BE) and p icing policy (Policy-DPD).
C.1: The decomposi ion app oach
The alue unc ion app oxima ion
wi h
i,
ep esen ing exogenously gi en alues o a non- ese ed sea i a ime ,
ep esen s ano he dynamic p og amming decomposi ion. In con as o he decom-
posi ion we p esen ed in he main ex , he alues o
may now be ime-dependen .
Fixing
V0
(y)=
0
o all y and plugging his app oxima ion in o (LP) yields
A s aigh o wa d way o sol e (TD-DPD) is ia backwa d induc ion. S a ing
wi h
V0(y)=0
o all y, le ing
X(
y
)={
x
∈{
0, 1
}c�∑i
x
i
≥y
}
, and using p ob-
abili ies as he a iables, he ecu sion is
As in he p e ious sec ion, he maximiza ion o e he igh hand side can be
done ia b anch-and-bound o e he s a e a iables aking ad an age o he con-
ca i y in
(p)
.
V
(x,y)≈
V (y)+
c
∑
i=1
i, xi
,
(TD-DPD)
VDPD =min
V (⋅), =1,…,T
VT(y)+
c
∑
i=1
i,T
s. .
V (y)≥p0( )
V −1(y)+p1( )( 1+
V −1(y−1))
+∑
i
p2,i( )( 2,i+
V −1(y−1)− i, −1)
+∑
i
p3,i( )( 3,i+
V −1(y−2)− i, −1− i∗, −1)
+
∑
i
( i, −1− i, )xi∀ =T, ..., 1, (x,y)∈S , ∈R(x,y)
.
(TD-DPD-BE)
V
(y)= max
x∈X(y),p∈P(x,y)
{
p0
V −1(y)+p1( 1(p)+
V −1(y−1))
+∑
i
p2,i( 2,i(p)+
V −1(y−1)− i, −1)
+
∑
i
p3,i( 3,i(p)+
V −1(y−2)− i, −1− i∗, −1)+
∑
i
( i, −1− i, )xi
}
1169
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
Since we again es ic he shape o he alue unc ion, any easible solu ion
o (TD-DPD) yields an uppe bound o he o iginal p oblem (BE). In addi ion, i
is easy o see ha i we choose
i,
- alues equal o he op imal solu ion o (AFF),
he op imal solu ion o (AFF) is also a easible solu ion in (TD-DPD). So i is
no su p ising ha (TD-DPD) p o ides a igh e bound han (AFF) in his case.
Theo em3 Independen o he choice o
i,
,
V∗≤VDPD
. Deno ing he solu ion o
(TD-DPD) wi h alues
i,
gi en by he op imal solu ion o (AFF) by
VTD-DPD*
, we
u he ha e
P oo
V∗≤VTD-DPD
holds because e e y easible solu ion o (TD-DPD) is also ea-
sible in he o iginal p oblem (LP). This inequali y also implies he i s inequali y in
he sequence
V∗≤VTD-DPD* ≤VAFF ≤VDPP.
The las inequali y o ha sequence is
a di ec consequence o P oposi ion 5 in Ke e al. (2019). The second inequali y ol-
lows om P oposi ion 2 in Zhang and Adelman (2009).
◻
C.2: Nume ical esul s
We compa e he pe o mance o he bound and p icing policy based on (TD-DPD-
BE). Figu e13a– show a compa ison o he un ime and uppe bound wi h hose
ob ained by sol ing (DPD-BE) and (DPP) unde he HOMOG, AW, and HET se -
ings. While he uppe bounds a e iden ical ac oss hese me hods, he un imes o
(TD-DPD-BE) a e signi ican ly longe . No ably, p oblems in ol ing bus sizes o 48
sea s o mo e could no be sol ed wi hin 50,000s and a e he e o e no displayed.
Rega ding he co esponding policy, Fig. 14 compa es he expec ed e enue
achie ed by he p icing policy based on (TD-DPD-BE) wi h (Policy-DPD) and a
simula ion-based app oach (Policy-sbADP), which we in oduce and discuss in
Appendix D. Again, he decomposi ion based on ime-independen sea alues,
(Policy-DPD), p oduces e y simila expec ed e enues as he policy policy based
on (TD-DPD-BE) while being much as e o compu e. In summa y, he addi ional
compu a ional e o does no appea o yield signi ican ly be e esul s.
Appendix D: Simula ion‑based app oxima e dynamic p og amming
In his sec ion o he appendix, we in oduce a p icing policy ob ained by simula-
ion-based ADP. A e a sho li e a u e e iew, we explain he me hod and highligh
ad an ages and disad an ages in a nume ical s udy.
V∗≤VTD-DPD* ≤VAFF ≤VDPP.
1170
C.Ba z e al.
D.1: Rela ed li e a u e
In con as o ALP and decomposi ion me hods based on ALP, simula ion-based
ADP (see, e.g., he ex books by Powell (2007), (2021) and Be sekas (2012)) p o-
ides no heo e ical gua an ees o in ui i e in e p e a ions. Bu i he associa ed
compu a ional bu den is accep ed, a la ge numbe o a bi a ily di icul basis unc-
ions can be chosen o yield e y good app oxima ions and co esponding policies.
Since his app oach is closely connec ed o he a ea o ein o cemen lea ning, we
also men ion pape s a his in e sec ion he e.
Schwind (2007) o mula es a dynamic p icing model o ne wo k RM as a p ice-
con olled esou ce alloca ion p oblem. In pa icula , he conside s an in o ma ion
se ice and in o ma ion p oduc se ing and uses Q-lea ning and empo al-di e ence
Fig. 13 Uppe bounds o op imal expec ed e enue, 1.00
=
UB DPD and un ime (seconds) necessa y
o calcula e uppe bounds. UB DPD, UB TD-DPD, UB TD-DPD-Benchma k, and UB DPD-Benchma k
yield (almos ) iden ical esul s, and a e no dis inguishable in he igu e. Missing alues o la ge bus
sizes a e caused by un ime limi iola ions
1171
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
lea ning as solu ion me hods, which pe o m be e han gene ic algo i hms. Rana
and Oli ei a (2014) lea n demand by a so-called
Q(𝜆)
algo i hm based on Q-lea n-
ing and upda e p ices in eal- ime. Balasho e al. (2021) conside dynamic p icing
o a p oduc a an au oma ic gas s a ion wi h disc e e p ices and compa e se e al
ein o cemen lea ning algo i hms. All h ee pape s sugges algo i hms ha wo k in
a model- ee en i onmen and conside an agg ega ed esou ce capaci y o be sold.
Maes e e al. (2019) use Q-lea ning and neu al ne wo k app oxima ions o
dynamically p ice a single p oduc . Thei ocus lies on ai ness in p icing which is
based on Jain’s index. Raju e al. (2003) conside a single-selle and a wo-selle
se ing in which hey y o lea n a policy by Q-lea ning. Kim e al. (2014) conside
a single-p oduc case in he con ex o sma elec ici y g ids. They use Q-lea ning
wi hou in o ma ion on ansi ion p obabili ies. Fo oo ani e al. (2018) use a Leas
Squa es Tempo al Di e ence algo i hm.
Kas ius and Schlosse (2022) e iew dynamic p icing in compe i i e ma ke s
using ein o cemen lea ning.
Fig. 14 Compa ison o p icing policies o di e en sea con igu a ions
1172
C.Ba z e al.
D.2: Asimula ion‑based ADP dynamic p icing policy
Using ou p oblem knowledge, wo adjacen non- ese ed sea s end o be mo e
aluable han wo simila non- ese ed bu non-adjacen sea s because p oduc 3
can only be sold wi h adjacen sea s. In ui i ely, he quali y o he VFA should
hence imp o e i we include he numbe o a ailable adjacen sea pai s,
(No e ha he di ision by wo a oids coun ing wo adjacen sea s i and
i∗
wice.)
Including such mul iplica i e e ms in ou app oxima e linea p og ams complica es
he esul ing subp oblems and p e en s he solu ion o p oblems o ealis ic size.
Howe e , simula ion-based ADP can ypically p o ide app oxima ions based
on VFAs composed o a la ge numbe o po en ially non-linea basis unc-
ions, hus inc easing he po en ial o p oduce be e policies. Thus, o le e age
he abo e obse a ion and include u he non-linea e ms in he VFA, we use
simula ion-based ADP in addi ion o he a o emen ioned policies ha ely on a
nume ical compu a ion o uppe bound p oblems.
In pa icula , o a gi en pa i ion o he se o sea s
{
1, …,c}=
⋃P
p=1
I
p
in o P
disjoin se s, we conside he ollowing ex ension o (APPROX-AFF):
To see ha his is indeed a gene aliza ion o (APPROX-AFF), choose
P=c,Ip={p}
and le ing
p, =0
o all
p>c
, as well as
w2 =w3 =z2 =z3 =0
o all o eco e (APPROX-AFF). Bu we will conside mo e gene al cases in
he ollowing. To do so, we summa ize he se o coe icien s o a gi en ime in
he ec o
𝜹 =( 1,1,…, 3P, ,w1 ,w2 ,w3 ,z1 ,z2 ,z3 )
.
We app oxima ely sol e (3) by backwa d ADP (BADP) up on using app oxi-
ma ion (D2) in an o line aining phase, simila o he solu ion o he uppe
bound p oblem o he a o emen ioned policies. Mimicking he classical dynamic
p og amming ecu sion, he idea is o go backwa d in ime. Bu ins ead o e alu-
a ing all s a es exac ly a each ime pe iod, only a subse is e alua ed using he
app oxima ion
V −1(
⋅
,
⋅
)
. These alues a e hen used o es ima e he coe icien s
𝜹
o
V
.
La e , o calcula e online he p ices o s a e
(x,y)
in pe iod we use he
app oxima ion
V −1(x,y)
in (BE-RHS) and ob ain he policy (Policy sbADP).
In mo e de ail, ou simula ion-based ADP algo i hm, Algo i hm1, wo ks as
ollows. Fi s , we se he app oxima ion o 0 in
=0
, because no mo e e enue
can be ob ained, e lec ing he bounda y condi ion (see line 1). We hen loop o e
q
=
1
2
∑
i
xi⋅xi∗
.
(D2)
V
(x,y)≈
V (x,y) ∶= 𝜃 +
P
�
p=1
p,
�
i∈Ip
xi+w1 y+z1 q+
P
�
p=1
P+p,
��
i∈Ip
xi
+w2
√
y+z2
√
q+
P
�
p=1
2P+p,
⎛⎜⎜⎝�
i∈Ip
xi
⎞⎟⎟⎠
2
+w3 y2+z3 q2.
1179
Dynamic p icing wi h(ex a) sea ese a ions unde henes ed…
Raju C, Na aha i Y, Ra ikuma K (2003) Rein o cemen lea ning applica ions in dynamic p icing o
e ail ma ke s. In: EEE in e na ional con e ence on e-comme ce, 2003. CEC 2003. IEEE, pp 339–
346. h ps:// doi. o g/ 10. 1109/ COEC. 2003. 12102 69
Rana R, Oli ei a FS (2014) Real- ime dynamic p icing in a non-s a iona y en i onmen using model- ee
ein o cemen lea ning. Omega 47:116–126. h ps:// doi. o g/ 10. 1016/j. omega. 2013. 10. 004
Schwind M (2007) Dynamic p icing and au oma ed esou ce alloca ion o complex in o ma ion se ices:
ein o cemen lea ning and combina o ial auc ions, ol 589. Sp inge , Be lin
Sie ag D (2017) P icing-based e enue managemen o lexible p oduc s on a ne wo k. J Re enue P ic
Manag 16:325–339. h ps:// doi. o g/ 10. 1057/ s41272- 016- 0061-1
S a is a (2022) A e age coach occupancy a e in F ance 2015–2017. h ps:// www. s a i s a. com/ s a i s ics/
11310 45/ a e- occup a ion- coach- ance/
S auss AK, Klein R, S einha d C (2018) A e iew o choice-based e enue managemen : heo y and
me hods. Eu J Ope Res 271(2):375–387. h ps:// doi. o g/ 10. 1016/j. ejo . 2018. 01. 011
Tallu i KT (2009) On bounds o ne wo k e enue managemen . Uni e si a Pompeu Fab a, Ba celona
Tallu i KT, Van Ryzin G (2004) The heo y and p ac ice o e enue managemen , ol 1. Sp inge , New
Yo k
Wilson JG (2016) Join ly op imising p ices o p ima y and mul iple ancilla y p oduc s. IFAC-Pape sOn-
Line 49(12):267–270. h ps:// doi. o g/ 10. 1016/j. i acol. 2016. 07. 615
Zhang D (2011) An imp o ed dynamic p og amming decomposi ion app oach o ne wo k e enue man-
agemen . Manu Se Ope Manag 13(1):35–52
Zhang D, Adelman D (2009) An app oxima e dynamic p og amming app oach o ne wo k e enue man-
agemen wi h cus ome choice. T ansp Sci 43(3):381–394. h ps:// doi. o g/ 10. 1287/ sc. 1090. 0262
Zhao G, Cui Y, Cheng S (2021) Dynamic p icing o ancilla y se ices based on passenge choice beha -
io . J Ai T ansp Manag 94:102058. h ps:// doi. o g/ 10. 1016/j. jai aman. 2021. 102058
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps
and ins i u ional a ilia ions.
Au ho s and A ilia ions
Ch is ianeBa z1 · JochenGönsch2· Da inaRauhaus2· SiqiHe1
* Ch is iane Ba z
[email p o ec ed]
Jochen Gönsch
jochen.goensc[email p o ec ed]
Da ina Rauhaus
da[email p o ec ed]
Siqi He
[email p o ec ed]
1 Chai o Ma hema ics o Business andEconomics, Depa men o Business Adminis a ion,
Uni e si y o Zu ich, Pla ens asse 14, 8032Zu ich, Swi ze land
2 Chai o Se ice Ope a ions, Me ca o School o Managemen , Uni e si y Duisbu g-Essen,
Lo ha s . 65, 47057Duisbu g, Ge many
