Depósi o de in es igación de la Uni e sidad de Se illa
h ps://idus.us.es/
“This is an Accep ed Manusc ip o an a icle published by Else ie in Omega on 2020,
a ailable a : h ps://doi.o g/10.1016/j.omega.2019.102165.”
.”
An op imiza ion model o line planning and ime abling in
au oma ed u ban me o subway ne wo ks. A case s udy.?
V´ıc o Blancoa, Edua do Condeb, Yolanda Hinojosac, Jus o Pue ob
aIEMa h-GR, Uni e sidad de G anada.
bDep. S a is ics & OR, Uni e sidad de Se illa.
cDep. Applied Economics I, Uni e sidad de Se illa.
Abs ac
In his pape we p esen a Mixed In ege Linea P og amming model ha we de eloped as pa
o a pilo s udy eques ed by he R&D company Me olab R
,?? in o de o design ools o
inding solu ions o line planning and ime able si ua ions in au oma ed u ban me o subway
ne wo ks. Ou model inco po a es impo an ac o s in public anspo a ion sys ems om bo h,
a cos -o ien ed and a passenge -o ien ed pe spec i e, as ime-dependen demands, in e change
s a ions, sho - u ns and echnical ea u es o he ains in use. The incoming lows o passenge s
a e modeled by means o piecewise linea demand unc ions which a e pa ame e ized in e ms
o a i al a es and bulk a i als. Decisions abou equencies, ain capaci ies, sho - u ning
and ime ables o a gi en planning ho izon a e join ly in eg a ed o be op imized in ou model.
Finally, a no el ma heu is ic app oach is p oposed o sol e he p oblem. The esul s o ex ensi e
compu a ional expe imen s a e epo ed o show i s applicabili y and e ec i eness o handle
eal-wo ld subway ne wo ks.
Keywo ds: Line planning, sho - u ns, ime abling, Mixed In ege Linea P og amming,
Ma heu is ic.
1. In oduc ion
In his pape , we p opose a model o line planning and ime abling on gene al u ban sub-
way anspo a ion sys ems. This s udy was o igina ed by a eal-wo ld p oblem p oposed by
Me olab R
, a F ench R&D company, dealing wi h he line planning and ime abling o ains o
exis ing subway ne wo ks. I was a pilo expe ience o au oma ize he decision making p ocess,
a he ac ical and ope a ional le el, o a small sec ion o he Pa is subway ne wo k.
The de elopmen o lexible ools o con ol, au oma ically, a anspo a ion sys em, in o de
o imp o e i s se ice quali y, may ha e conside able impac in i s e iciency and use ulness. The
pe cep ion, om he cus ome ’s poin o iew, o he quali y o a public anspo a ion sys-
em is highly dependen o i s eliabili y, com o abili y and e ec i eness, when compa ing wi h
al e na i e anspo a ion means. I jus poo -quali y connec ions a e o e ed o he quali y-
p ice ela ionship does no ul il he passenge s’ expec a ions, hey may decide o use a di e en
?The au ho s we e pa ially suppo ed by he p ojec s FQM-5849 (Jun a de Andaluc´ıa FEDER), MTM2016-
74983-C2-1-R (MINECO, Spain) and con ac 1853/0257 (Soci´e ´e Me olab R
, Se ice Con ˆole de Ges ion).
??Soci´e ´e Me olab R
, Se ice Con ˆole de Ges ion, egis e ed on he Pa is T ade and Companies Regis e unde
he numbe 532 684 685 RCS Pa is, wi h i s egis e ed o ice a 117/119 Quai de Valmy - 75010 PARIS - FRANCE
Email add esses: [email p o ec ed] (V´ıc o Blanco), [email p o ec ed] (Edua do Conde), [email p o ec ed]
(Yolanda Hinojosa), [email p o ec ed] (Jus o Pue o)
P ep in submi ed o Omega: The In e na ional Jou nal o Managemen Science No embe 17, 2019
anspo a ion mode. The e o e, one o he key objec i es when designing and managing a pub-
lic anspo a ion sys em, besides in as uc u e cons ain s, ope a ional limi a ions o budge
conside a ions, mus be i s se ice quali y [16].
The exis ing li e a u e on line planning is e y ex ensi e (see e.g., [14, 16, 34] and he e e -
ences he ein), including di e en models which can be classi ied acco ding o he decisions co -
e ed (de e mina ion o ain ou es, equency se ing, o bo h), in as uc u e and ope a ional
aspec s, objec i e unc ions and he way in which passenge s’ decisions a e aken in o accoun in
he decision making p ocess. Fo ins ance, in [16], line planning models a e classi ied wi h espec
o hei objec i e unc ions in o models wi h cos -o ien ed o wi h passenge -o ien ed objec i e
unc ions. Ou model will conside bo h poin s o iew in an a emp o ind an equilib ium
be ween hese con lic ing objec i es which, as men ioned in [18], is an impo an challenge in a
public anspo a ion sys em.
Howe e , building an e ec i e model is much mo e complex han selec ing he app op ia e
na u e o he objec i e unc ion. The co ec delimi a ions o he conside ed ea u es in he
con ex o he anspo a ion sys em o in he se o cus ome s se ed by his sys em is a e y
impo an phase in he ac ual modeling. O en, an ini ial line planning mus be e-enginee ed
mo i a ed by changes on cos ume s’ lows induced by changes in passenge s’ ou e choices, [16].
This gi es ise o a bile el op imiza ion p oblem wi h a line planning p oblem on he uppe le el
and a passenge ’s ou e choice p oblem on he lowe le el. Mo eo e , he exis ence o se e al
decision-make s is no he only di icul y o his p oblem. The e exis unce ain ies in he numbe
o passenge s ha mus be se ed (demands), in he o igin-des ina ion pai s ha cus ome s wan
o go ac oss o in he imes needed o co e he ne wo k links due, o ins ance, o machine ailu es
o o he inciden s. In his si ua ion i seems ha d o in eg a e all hese elemen s in a sui able
op imiza ion model.
Usually, some simpli ica ions mus be assumed in o de o ob ain ope a ional solu ions o
ealis ic si ua ions. The use ulness o he model will be s ongly condi ioned by hese assump-
ions. Ha ing a alid model o a wide ange o scena ios migh be a lo y a ge bu one wo h
aiming o . The esul ing app oxima ion can be seen no only as a model o op imize he ex-
is ing esou ces in a gi en anspo a ion sys em bu also as a wha -i ool o make a ional
decisions. Fo ins ance, i can be used o check he implemen a ion o possible modi ica ions in
he s uc u e o he exis ing ne wo k (adding s a ions, new connec ions, . . . ) o in he condi ions
(demand a ia ion, se ice dis up ions, . . . ) unde which he anspo a ion sys em is wo king
a p esen .
Line planning is only one o he planning p ocess’s s ages. Indeed, ollowing [14, 30, 35], he
planning p ocess in public anspo a ion includes se e al phases ha usually a e sequen ially
execu ed in he ollowing o de :
1. ne wo k design, whe e he s a ions, links and ou es o he lines a e es ablished,
2. line planning, speci ying he equency and he capaci y o he ehicles used in each line
(line concep , [16]),
3. ime abling, de ining he a i al/depa u e imes and
4. scheduling, in which ehicles and/o c ews a e planned.
The i s phase, namely ne wo k design, is done a he s a egic le el and implies a high cos (see
e.g., [3]). Mo eo e , he emaining s eps in ol e decisions a he ac ical and ope a ional le els
which a e condi ioned by ha design. Thus, i seems app op ia e o assess di e en designs by
means o a wha -i analysis based on he e iciency o he sys em unde a gi en scena io. In ha
case, a e ini ializing wi h a easonable design, he p ocedu e could op imize he e iciency o he
anspo a ion sys em using ac ical/ope a ional decisions. This may e eal possible weaknesses
o he cu en design and, a e ixing some o hem, will gi e ise o a new design. The p ocess
could be epea ed un il a comp omise anspo a ion design is ound.
2
In addi ion o he li e a u e on line planning commen ed abo e, one may also ind a ich
li e a u e on ime abling and scheduling (see e.g. [1, 8, 9, 26, 36] o ime abling models and
[7, 10, 11, 13, 37] o scheduling models). Time abling models a e usually classi ied acco ding
o he capaci y o he anspo a ion sys em o he equi emen s o passenge s. Rega ding o
he scheduling li e a u e, models can be classi ied in o single and mul iple depo amewo ks [4].
Besides, we can ind pe iodic and ime-dependen ime abling and scheduling models and many
o he a ian s depending on he conside ed cons ain s (see [5, 15, 21, 22, 27, 40, 41]). Con-
side able e o has also been made o analyze he p ac ical e ec s o he di e en elemen s o
ea u es co e ed by hese models. Fo ins ance, as men ioned in [31], pe iodic ime ables easily
allow passenge s o emembe he exac depa u e imes a s a ions bu , in gene al, hey a e no
ully sensi i e o ime- a ying passenge demands, which could esul in long wai ing imes and
educed se ice eliabili y, pa icula ly unde i egula o e -sa u a ed condi ions.
Once he amewo k o he anspo a ion sys em has been delimi ed, he esul ing model
should be op imized. Howe e , as poin ed ou in [35], going h ough he abo e-men ioned s ages
o he planning p ocess in a sequen ial way, o en leads jus o subop imal solu ions. Recen
esea ch (see [17, 18, 25, 32, 35]) is inc easingly o ien ed owa ds in eg a ed planning in which
wo o e en mo e o hese planning s ages a e simul aneously add essed. These in eg a ed op i-
miza ion models a e equen ly supe io o hose op imizing sequen ially he conside ed s ages,
as i has been ecognized in he li e a u e (see e.g., [35] and he e e ences he ein).
In his pape we p opose a new in eg a ed model in which line planning and ime abling a e
simul aneously op imized using a combina ion o cos - and passenge -o ien ed objec i e unc ion.
Acco ding o he pilo p oposal by Me olab R
, a el and dwell imes a e assumed o be ixed.
The same assump ion has been used p e iously in he li e a u e (see e.g. [33]). In ou model,
ime-dependency on demands is conside ed in addi ion o wo o he elemen s ha , as a as
we know, ha e only been add essed sepa a ely in he li e a u e: sho - u ns and in e change
s a ions.
Sho - u ning is a ac ical decision o which some ains can pe o m sho cycles in o de o
inc ease equency in speci ic sec ions o a line. In gene al, due o hei analy ical complexi y, he
app oaches o manage sho - u nings in he con ex o ailways planning a e based on pa icula
cases and he e a e no gene al models ha can be applied wi hou modi ica ions o e e y si u-
a ion [6]. Besides, mos o he li e a u e analyzing sho - u ning in a ailway con ex is limi ed
o a single wo-way ansi line [6, 12, 29, 38]. Ou model inco po a es decisions conce ning he
ac i a ion o sho - u ns simul aneously in se e al lines o he ne wo k.
On he o he hand, in e change o ans e s a ions a e sha ed by se e al lines in he sys em
allowing passenge s o change om one o ano he line. Pape s dealing wi h in e change s a ions
(see e.g., [20, 23, 39]) usually aim o minimizing he o al ans e wai ing ime o passenge s by
synch onizing ain a i al imes a ans e s a ions. We will manage he e he e ec i e lows o
passenge s a he in e change s a ions and compu e he co esponding e ec s bo h in he quali y
o he se ice and in echnical cons ain s, as hose ela ed o he capaci ies o he ains.
The inal aim is o model a eal sys em, inspi ed by one ini ially p oposed by Me olab R
, using
i s mo e ele an ea u es whils i s compu a ional ac abili y is p ese ed. This is an impo an
challenge aking in o accoun he combina o ial, s ochas ic, mul ile el and mul iobjec i e na u e
o he p oblem. The esul ing ou come is a Mixed In ege Linea P og amming model, which can
be sol ed using o - he-shel op imiza ion sol e s, bu only o limi ed sizes. Fo la ge sizes we
p opose a ma heu is ic app oach in which he sys em is decoupled in o di e en lines. A e wa d,
each subsys em is op imized indi idually bu including in he inpu da a he lows o passenge s
gene a ed a e op imizing o he lines. The p ocess is epea ed like in a block coo dina e descen
p ocedu e (see e.g., [2]) un il a gi en s oping ule is e i ied.
The emainde o his pape is o ganized as ollows. Sec ion 2 deals wi h a de ailed desc ip ion
3
o he op imiza ion p oblem and i s main elemen s. In Sec ion 3 we p esen he Ma hema ical
P og amming o mula ion o he p oblem. The demand unc ion modelling how he low o
passenge s en e ing in o ce ain s a ions o a line changes acco ding o he e ec s o he o he
lines o due o ex e nal ac o s is de ailed in Sec ion 4. The use ulness o he p oposed model is
illus a ed in Sec ion 5 wi h a case s udy using eal da a on a sec ion o he Pa is subway p o ided
by Me olab R
. Ou ma heu is ic app oach is p oposed in Sec ion 6 and he co esponding
compu a ional esul s, including i s compa ison wi h he exac me hod, a e epo ed in Sec ion
7 using se e al ne wo k opologies adap ed om he li e a u e. The pape ends wi h a sec ion
whe e some conclusions and u u e ex ensions o he model a e ou lined.
2. P oblem desc ip ion
Le us assume ha he echnical ea u es o a public anspo a ion ne wo k, which is a pa
o a complex unde g ound ain sys em, a e known. Ou goal is o model he p oblem o how
o ope a e di e en me o lines on his ne wo k acco ding o a se o echnical equi emen s
and a gi en s uc u e o he demand eques ing o his se ice. Suppose ha a se o ou es
o he po en ial lines (lines pool) and a se o in e change s a ions a e speci ied. Fu he mo e,
some o he ac o s in ol ed in he sys em pe o mance such as passenge lows, se o possible
ain capaci ies, maximum numbe o allowed ips in a gi en line du ing he planning ho izon,
demand luc ua ion (e.g., ush/o -peak hou s) o dwell imes, amongs o he s, a e assumed o
be also a ailable. The goal is o model such a sys em using i s mo e ele an ea u es whils i s
compu a ional ac abili y is p ese ed. In he desc ip ion o ou app oach we will conside h ee
main blocks: inpu da a, easible ac ions and assessmen o a pa icula solu ion oge he wi h
some addi ional speci ica ions o ou model.
2.1. Inpu da a
In addi ion o he inpu ne wo k, including he opological ou e map and he in e change
s a ions, he main block o inpu da a co esponds o he passenge low amongs he conside ed
se o s a ions. Ob iously, he numbe o passenge s awai ing in a speci ic s a ion o he nex
ain which connec s o a gi en des ina ion is a s ochas ic p ocess. Fu he mo e, he s ochas ic
p ocesses co esponding o he se o conside ed s a ions a e in e dependen due o he low
ela ionships amongs he s a ions which, in addi ion, may change o e ime. In ou model, gi en
ha we deal wi h a hea ily conges ed subway line, hese s ochas ic p ocesses will be eplaced by
a e age a es o he numbe o passenge s. The dynamic dependence o hese p ocesses on ime
should be p ese ed in some way in he op imiza ion model since i is one o he ele an elemen s
in o de o ob ain ealis ic ope a ing solu ions. We will do i h ough a unc ion measu ing he
in ensi y o he demand.
In ou amewo k, we assume ha wo main si ua ions a ec o he passenge s lows: an-
si ions be ween s a ions o lines and a i al o ex e nal demand unc ions. The i s one e e s
o he beha iou o he passenge s wi h espec o he mobili y pa e n. These da a ix an as-
signmen o he des ina ion o he passenge s ca ching a ain in a gi en s a ion, wha is known
in he li e a u e as line planning wi h ou e assignmen , [16]. The al e na i e app oach o line
planning wi h ou e choice seems o be mo e app op ia e jus in hose anspo a ion sys ems
wi h high densi y o connec ions (wi h al e na i e pa hs be ween wo gi en loca ions) and low
ip equency. Howe e , his is no he case in ou model since hese wo ea u es a ely appea
in unde g ound ain sys ems.
We will use an O igin-Des ina ion (OD)-ma ix pe line ha ing as en ies he p opo ions o
passenge s mo ing be ween pai s o s a ions o he line and also a se o alues quan i ying he
p opo ion o passenge s which wan o change om one me o line o ano he in each one o he
4

ans e s a ions. These p opo ions may be conside ed as es ima ions o he p obabili ies wi h
which a passenge mo es h ough he ne wo k and could be dependen on he dynamic na u e
o he anspo a ion sys em. Following [35], in o de o model he passenge s’ lows, OD-da a
gi es ise o mo e ealis ic applica ions han hose based on a ic loads since he pa hs ollowed
by passenge s depend s ongly on he line concep . As obse ed by se e al au ho s ([16, 35]),
he op imiza ion models de i ed om he managemen o OD-da a a e o en ha de o be sol ed
nume ically, and hus, app oxima ed ad-hoc algo i hms need o be used o deal wi h p oblems
o ealis ic sizes.
The second concep , he a i al o ex e nal demand unc ions, e e s o he in ensi y o use
o he anspo a ion ne wo k. The ex e nal demand models he incoming low o passenge s
en e ing o he sys em om ou side du ing he planning ho izon. These unc ions de e mine he
ela i e impo ance, in he o e all planning cos , o he s a ions used o access he sys em and
i may change depending on ime. Also, ush hou s a gi en ime pe iods, i egula wea he
condi ions, o he celeb a ion o e en s a ce ain places close o s a ions may p o oke inc easing
o dec easing o he incoming low o passenge s aken in o accoun in ou model.
These ex e nal demand unc ions, oge he wi h he OD-da a co esponding o mo emen s
be ween pai s o s a ions and he p opo ions o ans e passenge s, gi e ise o a model ha ing
ime-dependen passenge lows. Time-dependen lows a e an app op ia e ea u e o a ealis ic
app oach o a ic planning and, as poin ed ou in [35], a p esen , he e is no much esea ch
li e a u e co e ing in eg a ed op imiza ion planning models unde hese condi ions.
2.2. Feasible ac ions
In ou model, he line concep design is speci ied by choosing he ope a ing equencies and
he ain capaci ies o each line conside ed in he lines pool. Fu he mo e, ou line concep
design allows sho - u ning in some lines, i.e., he possibili y o ac i a ing, o some o all he
ains, and a ce ain ime pe iods, sho cycles, in o de o inc ease he equency in speci ic
(consecu i e) s a ions su e ing om in ensi e demand. This si ua ion is ypical in lines which
connec dis an esiden ial a eas wi h he ci y cen e o economic cen e s.
In he in eg a ed planning model, he line concep design is op imized oge he wi h hei
co esponding ime able. Bo h elemen s de ine he easible solu ions o he p oblem once a se
o echnical cons ain s, in ol ing passenge lows and lea ing/a i al imes, is speci ied.
The line concep design will be he main sou ce o disc e e decision a iables o he o mula-
ion o ou p oblem. As, o ins ance, he selec ion among a ini e se o capaci ies o he ains.
On he con a y, he ac ual numbe o ips o a gi en line will be modeled using a ini e se o
eplicas o con inuous a iables co esponding o po en ial ime ables. On he basis o hese de-
cision a iables a numbe o addi ional auxilia y a iables will be conside ed in he op imiza ion
model in o de o con ol he imes in which di e en e en s happen a each s a ion du ing he
planning ho izon. In ou model, unlike mos o he app oaches de i ing op imal ime ables in
anspo a ion sys ems, he depa u e imes a e no disc e ized and he pe iod o ime elapsing
be ween consecu i e ain depa u es is no cons ained o be cons an . Thus, i p o ides mo e
lexible decisions as well as ime ables sensi i e o he changeable condi ions in he passenge s’s
low du ing he planning ho izon, u ning ou , in gene al, in an ape iodic ime abling.
Di e en ain speeds a e no aken in o accoun in ou line concep design because he
pilo p oposal by Me olab R
only conside ed cons an and ixed speeds be ween each pai o
consecu i e s a ions. Ne e heless, con inuous a iables modeling he speed o a ain be ween
wo consecu i e s a ions could be easily added o ou model as explained in Rema k 1.
5
2.3. Assessing a planning solu ion
As commen ed abo e, due o he mul i-objec i e na u e o he p oblem, one o he mos
di icul modeling issues is ha o assessing a easible solu ion (line concep + ime able). Main e-
nance/ope a ional planning cos s a e usually easy o handle as a pa o he objec i e unc ion.
Howe e , in o de o conside also he passenge -o ien ed na u e o he objec i e, he cos in-
duced by he quali y o he se ice p o ided by he sys em should be included in he objec i e
unc ion. This will be inco po a ed in o he model quan i ying he cos o unme (non-se ed) de-
mand, ha is, passenge s who canno ake a ain due o lack o capaci y. Non-se ed passenge s
con ibu e a gi en amoun , in e ms o cos s, due o hei con idence loss in he anspo a ion
sys em, hei balking a e o a combina ion o hese wo and some o he ac o s. Ob iously, cal-
ib a ing hese cos s is no an easy ask, bu i may be pa ially handled by managing a ini e se
o cos es ima es and sol ing he p oblem o each one o hem in o de o e alua e he in luence
o hese ha d- o-calib a e pa ame e s in he p oposed solu ion.
2.4. Speci ica ions o ou model
In he ollowing we lis he assump ions ha a e imposed o de i e a sui able Ma hema ical
P og amming o mula ion o ou model.
Planning ho izon:Ou model conside s a con inuous ime in e al in which all he e en s
mus s a and decisions occu . The ange o his in e al depends on he da a collec ion
accu acy and wi h-in-day a iabili y o he demand changes. This planning ho izon is ixed
a p io i bu , as men ioned in Rema k 2, ou model allows o join wo consecu i e planning
ho izons by passing da a abou numbe s o passenge s and a i al/depa u e imes ob ained
om an op imal solu ion on a gi en planning pe iod as inpu da a o he nex one.
One di ec ion ips:We assume ha each line in he pool ope a es only in one di ec ion,
om a gi en line-heade s a ion o he inal one. Usual ound- ip lines a e modeled as
wo symme ic lines by in e changing he o de o he s a ions. A ip consis s in making
he comple e walk along all he o de ed s a ions o a gi en line, om he head o he inal
s a ion. Thus, a physical ound- ip s a ing and ending a he same s a ion will be gi en
by wo lines sha ing he s a ions bu in he opposi e o de .
Sho - u ns:We conside ha speci ic sec ions o consecu i e s a ions in ce ain lines a e al-
lowed o be ac i a ed in some o he ips.
In e change s a ions:We conside ha he lines in he lines pool may sha e common in e -
change s a ions whe e some o he passenge s change o line o go o hei inal des ina ion.
T ain capaci ies:The model assumes ha a ini e se o admissible capaci ies o he ains
ope a ing a line is gi en.
Sa e y in e al:A minimum sa e y headway be ween consecu i e ips in any line is es ab-
lished.
Maximum numbe o ips:We assume, w.l.o.g., ha he maximum numbe o possible ips
in each line is gi en be o ehand. No e ha an uppe bound o his maximum numbe can
be ob ained aking in o accoun he ange o he planning ho izon and he sa e y in e al.
In ou o mula ion, we eso o a se o decision a iables con olling he ime in which
di e en e en s happen. These a iables mus be eplica ed as many imes as he maximum
numbe o ips, al hough only some o hose ip- a iables a e ac i a ed and hen ep esen
ac ual ips. Hence, he size o he o mula ion s ongly depends on his maximum numbe .
6
Figu e 1: Rep esen a ion o a sample ne wo k in ou amewo k.
The idea is o conside ha he po en ially a iable numbe o ips o he line concep is
ixed o he maximum numbe al hough, in ac , some o hem a e eally ake ips. This
ick will ease he ask o building cons ain s o ensu e non-o e lapping e en s and he
sa e y in e al be ween consecu i e ips in he s a ions o a gi en line.
Piecewise linea cumula i e incoming demand:We model he accumula ed numbe o pas-
senge s a i ing o each s a ion up o a gi en ins an du ing he planning ho izon by he
so-called demand unc ion. Wi h his unc ion we manage a iable a i al a es du ing he
planning ho izon and bulk a i als due o special e en s, like o ins ance he end o a oo -
ball ma ch in a close loca ion, he a i al o passenge s coming om ano he anspo a ion
mean o , in he in e change s a ions, he a i al o passenge s coming om ano he line o
he subway ne wo k. As p oposed by Me olab R
 o i s pilo expe ience, we conside ha
his unc ion is a piecewise linea unc ion o ime ( u he de ails a e gi en in Sec ion 4).
Figu e 1 illus a es some o he conside ed ea u es o he ne wo ks unde s udy. The e, we
ep esen by ci cles o squa es he nodes co esponding o he s a ions o wo subway lines. An
in e change s a ion common o wo lines is ma ked wi h a black squa e. We ha e also included
a possible sho - u n in he ho izon al line co e ing a se o ou consecu i e squa ed s a ions
(d awn as a dashed line in he pic u e).
3. Ma hema ical P og amming Fo mula ion
In his sec ion we p o ide a Ma hema ical P og amming o mula ion o he p oblem de-
sc ibed in Sec ion 2. Fi s o all, we a e gi en an inpu ne wo k, like he one depic ed in Figu e
1, including he opological ou e map and he s a ions, some o hem being in e change s a ions
and he lines pool Lde ined o e his ne wo k. In addi ion, sho - u ning decisions a e allowed
in some lines o he lines pool. These decisions always conce n a se o gi en consecu i e s a ions
o hose lines. In wha ollows and when no con usion is possible, we will e e o bo h, he se
o consecu i e s a ions and he ip conce ned by a sho - u ning decision as a sho - u n. On
he o he hand, ips h ough he ull-leng h lines will be e e ed as whole ips. In o de o
in oduce he model we s a by de ining he se o pa ame e s desc ibing he emainde o he
inpu da a as well as he decision a iables used o iden i y a easible solu ion.
3.1. Pa ame e s
The inpu pa ame e s o ou model a e he ollowing:
7
•[0, T]: Planning ho izon in which ains s a hei jou neys a a gi en head o line s a ion.
No e ha a ain may s a i s las jou ney on [0, T ] while i s las s op may occu in a
ime ins an > T . The eade may no e ha hese in e als a e ela i e o he ac ual
s a ing and inal ime o each line, al hough o he sake o p esen a ion all o hem ha e
been aken equal.
•L: Se o lines in he ne wo k (lines pool). As men ioned abo e, ound- ip lines a e consid-
e ed as wo di e en lines sha ing he s a ions bu a e sed in opposi e di ec ions ( igo -
ously speaking, he s a ions ep esen pla o ms o he co esponding line). Each one o he
lines is assumed o be desc ibed by i s node s a ions and i s di ec ed connec ions be ween
consecu i e s a ions. Addi ionally we will deno e by LS he se o lines con aining a sho -
u n and by LNS he emainde ( hose in which none o i s p ope subse s o s a ions can
be ac i a ed as sho - u ns). Clea ly, L=LS ∪LNS.
•N`={1, . . . , n`}: Se o labels indexing he s a ions o line `∈L. S a ions a e assumed o be
o de ed in i s a elling di ec ion. Obse e ha i he lines `and `0co espond o he same
ound- ip line bu a e sed in opposi e di ec ions hey ha e he same numbe o s a ions
(n`=n`0) and s a ion i∈` ep esen s he opposi e pla o m o s a ion n`0−i+ 1 ∈`0.
Addi ionally, o each line `∈LS we will deno e by S` he se o s a ions in he (unique)
sho - u n, being 1S` he i s s a ion o he sho - u n and nS` he las one.
In o de o p esen a clea e Ma hema ical P og amming model, we will also deno e om
now on by S=n(i, `) : i∈N`, ` ∈LNSo∪n(i, `) : i∈N` S`, ` ∈LSo, i.e., hose s a ions
which a e no pa o he a ailable sho - u ns.
•d`
i: Dis ance (measu ed as a el ime) be ween he s a ions iand i+ 1 o line `∈L. Recall,
as men ioned in Sec ion 2, ha we assume ha he speed o he ains ope a ing be ween
consecu i e s a ion iand i+ 1 is ixed, and hus, his dis ance is ip independen .
•e`
i: Dwell ime o any ain a s a ion io line `be o e lea ing o s a ion i+ 1. This alue
ep esen s a minimum sa e y headway o pe o m di e en ope a ions as o ins ance he
unload/load o passenge s om/ o he ain o he main enance o he ain in ha s a ion,
amongs o he s. Fo ease o p esen a ion, we also conside ha he dwell imes a e ip
independen .
• 17→1S`: Dis ance (measu ed as a el ime plus dwell ime a he las and in e media e
s a ions) be ween he head o line s a ion and he i s s a ion o he sho - u n o line
`∈LS. No e ha , his pa ame e is gi en by he ollowing exp ession:
17→1S`=
1S`−1
X
=1
(d`
+e`
+1).(T1S)
•IS`: Minimum sa e y ime in e al be ween consecu i e ips in a gi en line `∈L.
•K`={1,...,¯
k`}: Se o labels indexing he ips in line `∈L. I is wo h no ing ha he
exac numbe o ips in a line is a decision o he line planning p ocess and which is no
known be o ehand. In ac , some ips will no be ac ually used on he planning. We will
e e o hem as ake ips. No e also ha he maximum numbe o possible ips in he
line `∈Lcan always be uppe bounded by T
IS`+1. Typically he alue ¯
k`will be smalle
han his bound and should be es ima ed on he basis o he echnical speci ica ions o he
ne wo k.
8
3.4. Modelling Cons ain s
In wha ollows we desc ibe he cons ain s linking he a iables and pa ame e s in ou model.
They ha e been classi ied in ou main blocks: capaci y cons ain s, ime con ol cons ain s, low
con ol cons ain s and passenge su plus cons ain s.
•Capaci ies and ue/ ake ips:
X
q∈Q
y1`
q= 1, ` ∈LNS, (C1 −1)
X
q∈Q
yk`
q≤1,1< k < ¯
k`, ` ∈L, (C1 −2)
X
q∈Q
yk``
q= 1, ` ∈L, (C1 −3)
yk`
q≤yk`
Sq, q ∈Q, k ∈K`, ` ∈LS, (C1 −4)
X
q∈Q
y1`
q+X
q∈Q
y1`
Sq ≥1, ` ∈LS, (C1 −5)
X
q∈Q
yκ``
q=X
q∈Q
y1`
Sq −X
q∈Q
y1`
q, ` ∈LS, (C1 −6)
X
q∈Q
yk`
Sq ≤1, k ∈K`, ` ∈LS, (C1 −7)
whe e κ`=h 17→1Sl
IS`i+ 1, i.e. he numbe o sho - u n ips o line `∈LS which i wi hin
he pe iod o ime aken by a ain o go om he head o line o he i s s a ion o he
sho - u n.
When sho - u ns a e no allowed o a line, he app op ia e de ini ion o he capaci y
a iables is ensu ed by cons ain s (C1 −1)–(C1 −3). They en o ce ha exac ly one o he
allowed capaci ies is chosen o he i s and he las ip and a mos one o he es o
hem. Fake ( esp. ue) ips a e iden i ied by ips wi h capaci ies equal o ( esp. g ea e
han) ze o. Thus, cons ain s (C1 −1) and (C1 −3) de e mine ha he i s and he las
ip o each line a e ue ips. We will see la e ha his pe mi s he ac ual ains o
be scheduled om he beginning o he end o he planning ho izon, p o iding he use s a
comple e se ice du ing ha ime in e al. No e ha cons ain s (C1 −2) and (C1 −3) a e
also alid o lines allowing sho - u ns and hen, when sho - u ns a e allowed o a line,
he app op ia e de ini ion o he capaci y a iables is wa an ed by cons ain s (C1 −2)–
(C1 −7). Cons ain s (C1 −4) indica e ha when a whole ip is a ue ip, i is also
a ue ip o he sho - u n s a ions. Cons ain s (C1 −5) ix ha he i s ip (being
ei he , a whole ip o a sho - u n) is a ue ip. Cons ain s (C1 −6) o ce ip κ` o be
a ue whole ip ( esp. a ake ip) i he i s ip is a sho - u n ( esp. i he i s ip is
a whole ip). These cons ain s, oge he wi h (C1 −5) a e he equi alen o (C1 −1) o
lines wi h sho - u ns, and hey ensu e ha a eal ain is scheduled om he beginning o
he planning ho izon. Finally, cons ain s (C1 −7) assu e ha a mos one o he allowed
capaci ies is chosen o any ip o a line allowing sho - u ns.
•Time con ol:
15

1`
1= 0, ` ∈L, (C2 −1)
k`
1=T, ` ∈L, (C2 −2)
κ``
1≤T
1−X
q∈Q
y1`
Sq +X
q∈Q
y1`
q
, ` ∈LS, (C2 −3)
IS 
X
q∈Q
yk`
q
≤ k`
i− (k−1)`
i,
k= 2, . . . , k`,(i, `)∈ S wi h k6=κ`i `∈LS, (C2 −4)
k`
i− (k−1)`
i≤T
X
q∈Q
yk`
q
, k = 2, . . . , k`,(i, `)∈ S (C2 −5)
IS 
X
q∈Q
yk`
Sq
≤ k`
i− (k−1)`
i, i ∈S`, k = 2, . . . , k`, ` ∈LS, (C2 −6)
k`
i− (k−1)`
i≤(T+ 17→1Sl)
X
q∈Q
yk`
Sq
, i ∈S`, k = 2, . . . , k`, ` ∈LS, (C2 −7)
− 17→1Sl
1−X
q∈Q`
yk`
q
≤wk`, k ∈K`, ` ∈LS, (C2 −8)
wk` ≤(T+ 17→1Sl)
1−X
q∈Q`
yk`
q
, k ∈K`, ` ∈LS, (C2 −9)
Cons ain s (C2 −1) and (C2 −2) s a e ha he i s and he las ip o each line should
exac ly s a a he i s s a ion o he comple e line a ins an ime 0 and T, espec i ely.
I he line does no con ain a sho - u n, hese cons ain s oge he wi h (C1 −1) and
(C1 −3) ensu e ha he e a e ains a eling he line du ing he whole planning ho izon.
I he line con ains sho - u ns, ecall ha cons ain s (C1 −5) pe mi he i s ip o be a
sho - u n ip. In his case, cons ain s (C2 −3) oge he wi h cons ain s (C1 −6) o ce
ip κ` o be a ue whole ip s a ing a ime 0 a he head o he line.
Cons ain s (C2 −4) ensu e ha he a i al imes be ween consecu i e ains sa is y he
sa e y headway in e al. Cons ain s (C2 −5) o ce a ake ip o ope a e on he line a he
same ime as he p e ious ue ip. Fo lines allowing sho - u ns cons ain s (C2 −4)–
(C2 −7) ep esen he same as he abo e bu aking in o accoun ha in his case he ip
can be ei he , a whole ip o a sho - u n.
Obse e ha in (C2 −4) i `∈LS he case k=κ`is excluded. The eason is ha
cons ain s (C1 −6) o ce ip κ` o be a ue whole ip i and only i he i s ip (k= 1)
is a sho - u n and, in his case, cons ain s (C2 −3) ensu e ha ip κ`s a s a he head
o he line s a ion a ime 0, and hen, i is he i s whole ip. Finally, cons ain s (C2 −8)
and (C2 −9) ix he uppe and lowe bounds on he alues o a iables wkl when he k- h
ip is a sho - u n, en o cing ha his a iable is 0 i he ip is a whole ip.
16
•Flow con ol:
k`
i+
i−1
X
=1
k`


n`
X
j=i+1
p`
j
≤X
q∈Q
qyk`
q, k ∈K`, i ∈N`, ` ∈L, (C3 −1)
gk`
i+
i−1
X
=1S`
gk`


nS`
X
j=i+1
p`
j
≤X
q∈Q
q(yk`
Sq −yk`
q), k ∈K`, i ∈S` {nS`}, ` ∈LS, (C3 −2)
1`
i≤D`
i( 1`
i), i ∈N`, ` ∈L, (C3 −3)
kl
i≤D`
i( k`
i)−D`
i( (k−1)`
i) + αh(k−1)`
i, k = 2, . . . , k`, i ∈N`, ` ∈L, (C3 −4)
g1`
i≤D`
i( 1`
i), i ∈S` {nS`}, ` ∈LS, (C3 −5)
gk`
i≤D`
i( k`
i)−D`
i( (k−1)`
i)+αh(k−1)`
i, k = 2, . . . , k`, i ∈S` {nS`}, ` ∈LS.
(C3 −6)
The low o passenge s ca ching a gi en ain is de e mined by he capaci y o he ain
and he mobili y pa e n o people. Hence, he e ec i e capaci y o he ains a i ing
o a gi en s a ion depends o he passenge s ha caugh he ain in p e ious s a ions o
his same ip and whose des ina ion is a subsequen s a ion o he line. Such an e ec i e
capaci y is wa an ed, depending on he case (sho - u n allowed o no ), by cons ain s
(C3 −1) and (C3 −2). Wi h cons ain s (C3 −3) ( esp. (C3 −4)) we ensu e ha he low
o passenge s cap u ed a a gi en s a ion by a ain ha co e s he i s ip ( esp. he
k- h ip o k > 1) is a mos he demand o passenge s accumula ed a s a ion isince
he beginning o he planning ho izon ( esp. since he ins an in which he p e ious ain
depa ed om ha s a ion plus he passenge s ha we e no able o ge on he p e ious
ain because o lack o capaci y and wai o he nex one). Cons ain s (C3 −5) and
(C3 −6) a e he analogous ones o sho - u n ips.
•Passenge su plus:
In o de o compu e only he su plus o passenge s o a ue ip, we use he se o semi-
con inuous a iables xk`
i:
xk`
i=hk`
i×Pq∈Qyk`
qi (i, l)∈So (i=nS`,`∈LS),
hk`
i×Pq∈Qyk`
Sq i i∈S` {nS`},`∈LS,
which can be linea ized as ollows:
xk`
i≥hk`
i−M`
i
1−X
q∈Q`
yk`
q
,(i, l)∈ S o (i=nS`,`∈LS),(C4 −1)
xk`
i≥hk`
i−M`
i
1−X
q∈Q`
yk`
Sq
, i ∈S` {nS`}, ` ∈LS, (C4 −2)
being M`
ia la ge enough cons an bounding he su plus o passenge s a any s a ion io
line `∈L.
17
3.5. A compac Ma hema ica P og amming o mula ion
Acco ding o he decision a iables, he objec i e unc ion and he cons ain s desc ibed
abo e, he ollowing Ma hema ical P og amming o mula ion is alid o ou line planning and
ime abling model:
min X
`∈L
COST(`)
s. . (C1),(C2),(C3) and (C4),
0≤ k`
1≤T, k ∈K`, ` ∈L,
k`
i≥0, k ∈K`, i ∈N`, ` ∈L, (P)
gk`
i≥0, k ∈K`, i ∈S` {nS`}, ` ∈LS,
wk` ∈R, k ∈K`, ` ∈LS,
xk`
i≥0, k ∈K`, i ∈N`, ` ∈L,
yk`
q∈ {0,1}, k ∈K`, q ∈Q, ` ∈L,
yk`
Sq∈ {0,1}, k ∈K`, q ∈Q, ` ∈LS.
Obse e ha al hough he abo e o mula ion seems o be sepa able by lines in L, he lines a e
linked h ough he demand unc ions D`
i( ) (cons ain s (C3 −3)-(C3 −6)) which ep esen he
accumula ed low o passenge s awai ing o a ain a a gi en s a ion io line l∈La ime
ins an . As we will desc ibe in Sec ion 4, such a low is a ec ed no only by he line `bu also
by o he lines h ough passenge s changing o lines a ans e s a ions. This unc ion in oduces
new a iables and non linea cons ain s in o he abo e o mula ion.
Se e al ex ensions may be easily accommoda ed wi hin he abo e model as highligh ed in he
ollowing ema ks:
Rema k 1. In ou model he speed o ains is conside ed o be cons an du ing he whole jou -
ney. Howe e , one can easily modi y exp essions (T1S),(T −1) and (T −2) using a iables
k`
i>0 o decide he speed o he ain du ing a ip ko line `be ween s a ions iand i+ 1. Fo
ins ance, le ρibe he physical dis ance be ween s a ions iand i+ 1 and le ωk`
i ep esen he
in e se o he speed, i.e., ωk`
i=1
k`
i
, hen one could eplace he a el imes d`
iby ρi×ωk`
iin
exp essions (T1S),(T −1) and (T −2). By adding o he objec i e unc ion a cos assessing
he esou ce consump ion due o speed changes one can ha e a mo e gene al model p ese ing he
s uc u e o he one s a ed abo e. Simila modi ica ions can be also conside ed by enabling he
model o decide abou a iable dwell imes a any s a ion.
Rema k 2. The model allows us o join wo consecu i e planning ho izons by passing da a abou
numbe s o passenge s and a i al/depa u e imes ob ained om an op imal solu ion on he i s
planning pe iod as inpu da a o he second one, and so on. In pa icula , he passenge s ha
may emain a s a ion io line `∈La he end o he i s planning ho izon can be conside ed
as passenge s a s a ion i o use line `a he beginning o he second planning ho izon, and so
on. This in o ma ion has o be inco po a ed in o de o compu e he demand unc ion, as we will
see in he nex sec ion.
4. The Demand unc ion
One o he main goals o ou model is o inco po a e, in he design o he line planning and
ime abling o an exis ing ne wo k, in o ma ion abou he low o passenge s mo ing h ough he
18
ne wo k du ing he planning ho izon. Clea ly, he low o passenge s a i ing o a gi en s a ion
is a andom a iable. Thus, we will inco po a e o he model an es ima ion o i s a e age alue.
In o de o model he numbe o passenge s en e ing o he anspo a ion sys em h ough
a gi en s a ion o a ixed line, we use he so-called demand unc ion, which maps a a gi en
ins an he accumula ed numbe o passenge s wan ing o ca ch a ain a his s a ion ( om
he beginning o he planning ho izon). He e, he es ima ion p ocess should be ca e ully done in
o de o cap u e he essen ial beha iou o he demands se ed by he sys em.
Di e en shapes o he unc ion a e possible wi hin his amewo k o app oxima e he
demand. The choice o such a shape is a c ucial s ep in he modeling p ocess since one has o ind
an equilib ium be ween ob aining accu a e es ima ions and p o iding manageable ma hema ical
p og amming o mula ions. Once again, mo i a ed by ou pilo expe ience wi h Me olab R
, we
use a piecewise linea app oxima ion whose slope is ixed o any gi en s a ion i∈N`, bu whose
b eakpoin s and discon inui ies may change acco ding o he low induced by ex e nal block o
a i als and by he es o he lines. Fo a gi en line `∈Land a s a ion i∈N`, we es ima e he
demand unc ion as ollows:
D`
i( ) = β`
0i+β`
i +JE
i` ( ) + X
`06=`,`03i
JI
i``0( ),(D)
o ∈[0,b
T`], wi h b
T`=T+Pn`−1
=1 (d`
+e`
+1), i.e., he maximum ime in which he ain can
each he las s a ion o he line, and whe e:
β`
0iis he numbe o passenge s awai ing a ain o line `∈Lin he s a ion i∈N`a he
beginning o he planning ho izon.
β`
iis he a e age a e o passenge s a i ing o he s a ion i∈N`o line `∈Lby uni o ime.
JE
i` ( ) is he sum o he ex e nal block o a i als o passenge s up o he ins an o he s a ion
i∈N`o line `∈L.
JI
i``0( ) is he sum o he block a i als o passenge s up o he ins an o he s a ion i∈N`o
line `∈L om line `0∈L.
In wha ollows we will e e o [0,b
T`] as he ex ended planning ho izon o line `. Thus, he
demand unc ion a a gi en ime ins an in s a ion i∈N`o line `∈L, consis s o h ee pa s.
The i s one is a linea pa , in which, om an ini ial numbe o passenge s, β`
0i, he numbe
inc eases by a a e β`
i. Howe e , such a base es ima ion may be modi ied ei he by ex e nal
block o a i als (second pa ), JE
i` ( ), o by passenge s coming om o he in e ac ing lines a
in e change s a ions ( hi d pa ), JI
i``0( ).
As can be seen, in he o mula ion (P), he demand unc ion D`
i( ) is used exclusi ely o
access lows in he se o ins an s = k`
i o i∈Nl, ` ∈Land k∈K`. Each o he ime
ins an s in which he demand unc ion needs o be e alua ed induces some se s o inequali ies
and a iables as hose desc ibed in subsec ions 4.1 and 4.2 ( o ex e nal and in e nal a i als).
4.1. Ex e nal A i als: JE
We conside ha we a e gi en bo h a se o b eakpoin s ep esen ing ime ins an s when he
block o a i als occu and he amoun s o passenge s en e ing o he sys em a hese ins an s o
each s a ion i∈N`. Tha is, we assume ha a se o so ed ins an s sei`
1<· · · < sei`
ei` as well
as discon inui y low jumps associa ed o each o hose ins an s Ψi`
1,...,Ψi`
ei` a e known, i.e.,
a block a i al o Ψi`
is assumed a ime ins an sei`
, o = 1, . . . , ei`. The ex e nal a i als
ep esen block o a i als o passenge s o ins ance, due o he end o a oo ball ma ch in a place
19
close o one o ou s a ions. Fo he sake o eadabili y and wi hou loss o gene ali y, we will
assume ha sei`
0= 0, sei`
ei`+1 =b
T`, and Ψi`
0= Ψi`
ei`+1 = 0, i.e., he i s and las ime ins an s
o ex e nal a i als coincide wi h he beginning and he end o he ex ended planning ho izon,
and he discon inui y jumps a hose ins an s a e null. Gi en a ime ins an ∈[0,b
T`], we use
he ollowing se o bina y a iables o de e mine whe he belongs o he in e al [sei`
, sei`
+1)
o = 0, . . . , ei`:
δE
i`( ) = 1 i ∈[sei`
, sei`
+1),
0 o he wise, i∈N`, ` ∈L.
No e ha wi h hese se ings, he accumula ed discon inui y low jumps o ex e nal a i als o
a s a ion i∈N`o line `∈Lcan be modeled using he ollowing cons ain s
JE
i` ( ) =
ei`
X
=0

X
0≤
Ψ`
i 0
δE
i`( ), i ∈N`, ` ∈L,
sei`
δE
i`( )≤ < sei`
+1δE
i`( ) + b
T`(1 −δE
i`( )), = 0, . . . , ei`, i ∈N`, ` ∈L,
ei`
X
=0
δE
i`( ) = 1, i ∈N`, ` ∈L,
δE
i`( )∈ {0,1} = 0, . . . , ei`, i ∈N`, ` ∈L.
(DE)
The eade may obse e ha he i s cons ain allows us o app op ia ely de ine JEby
accumula ing he low jumps p e ious o a gi en ins an . The second se o cons ain s pe mi s
o de e mine he in e als in which lies and he hi d cons ain ensu es ha only one o hese
in e als is iden i ied o each .
4.2. In e nal A i als
The main di e ence be ween in e nal and ex e nal block o a i als is ha in he la e ,
he b eakpoin s and he discon inui y low jumps a e known, while o in e nal a i als, his
in o ma ion depends on he decision a iables o he p oblem. Recall ha in e nal block o
a i als occu when passenge s ge o a ain in an in e change s a ion o ans e o ano he
line. Thus, he ime ins an s o hose a i als a e pa o he decision p oblem. The e o e, we
need o s a e a se o equa ions showing he exis ing ela ionships be ween he decision a iables
and he b eakpoin s and jumps in he low o passenge s hey p o oke.
In wha ollows we desc ibe he modeling issues conce ning he b eakpoin imes and low
jumps o in e nal a i als.
•B eakpoin imes a line `∈L.
No e ha he ins an s, sii``0
, in which an in e nal low jump occu s by he a i als o ains
coming om line `0∈L o an in e change s a ion i∈N`∩N`0can be compu ed in e ms
o he ime `0
ias:
sii``0
= `0
i−e `0
i, = 1,...,¯
k`0
ha is, he ime ins an in which he - h ip o line `0∈Ldepa s o he nex s a ion
( `0
i) minus he wai ing ime a he s a ion i∈N`0(e `0
i), ha is, he ins an s in which he
ains a i e o he in e change s a ion o line `0∈L.
20

•Discon inui y low jumps a line `∈Lcoming om line `0∈L.
The olume o he in e nal block o a i als o an in e change s a ion can be de i ed om
he passenge lows con olled by ou decision a iables. To compu e i we will also need
a se o alues quan i ying he p opo ion o passenge s which wan o change om one
me o line o ano he one in all he in e change s a ions. Le τ``0
ibe he p opo ion o he
passenge s ha ge o a ain in an in e change s a ion i∈N`∩N`0o he line `0∈L o
change o line `∈L. Thus, he low jump a an ins an sii``0
o ∈K`0, ` ∈L, i ∈N`is
gi en by
Φ``0
i =











τ``0
iX
j<i
p`0
ji `0
ji (i, `0)∈ S
τ``0
i
X
j<i
p`0
ji `0
j+X
j<i;j∈S`0
p`0
jig `0
j
i i∈S`0, `0∈LS
Le SI
i``0=nsii``0
0,· · · , sii``0
¯
k`0+1obe he se o so ed b eakpoin imes a a gi en in e change
s a ion i∈N`∩N`0o line `∈Lcaused by line `0∈L. In o de o make clea e he o mula ion,
we will assume, w.l.o.g., ha sii``0
0= 0, sii``0
¯
k`0+1 =b
T`, and Φ``0
i0= Φ``0
i¯
k`0+1 = 0, i.e., he i s and
las ime ins an s o in e nal a i als coincide wi h he beginning and he end o he ex ended
planning ho izon, and he low jumps a hose imes a e null.
Now, we a e eady o model he in e nal low jumps induced by line `0∈Lon o he s a ion
i∈N`∩N`0o he line `. We p oceed analogously as in he ex e nal a i als bu inco po a ing a
se o bina y a iables (δI) o iden i y in which ime in e al be ween wo consecu i e b eakpoin s
a gi en ins an belongs o:
JI
i``0( ) =
¯
k`0
X
=0

X
0≤
Φ``0
i 0
δI
i``0( ), i ∈N`∩N`0, ` ∈L, `0∈L,
sii``0
δI
i``0( )≤ < sii``0
+1δI
i``0( ) + b
T`(1 −δI
i``0( )), = 0,...,¯
k`0, i ∈N`∩N`0, ` ∈L, `0∈L,
¯
k`0
X
=0
δI
i``0( )=1, i ∈N`∩N`0,`∈L, `0∈L,
δI
i``0( )∈ {0,1} = 0,...,¯
k`0, i ∈N`∩N`0, ` ∈L, `0∈L.
(DI)
No e ha he wo i s se s o he abo e inequali ies a e nonlinea since Φ,SIand δIa e decision
a iables o ou p oblem. Ne e heless, hey can be linea ized using McCo mick en elopes [28].
As men ioned abo e, he demand unc ion D`
i( ) is only applied o a ce ain ( ini e) se o ime
ins an s. Then, i can be inco po a ed in o he model by adding he a iables Dk`
i≡D`
i( k`
i),
δEand δI, as well as hei co esponding cons ain s in (DE) and (DI). We also include in he
model (P) he ollowing wo se s o alid inequali ies:
δE
i`( k+1`
i)≤
X
0=0
δE
0i`( k`
i), k ∈K`, , = 0, . . . , ei`, i ∈N`, ` ∈L,
δI
i``0( k+1`
i)≤
X
0=0
δI
0i``0( k`
i), k ∈K`, = 0,...,¯
k`0, i ∈N`∩N`0, ` ∈L, `0∈L.
21
The abo e inequali ies ensu e ha ip k+ 1 goes h ough s a ion ia e ip k. Al hough hese
inequali ies a e edundan wi h he es o he cons ain s in he model, hey conside ably imp o e
he pe o mance o he sol e o e he b anch-and-bound ee induced by he ma hema ical
p og amming model.
5. Case s udy: The Me olab R
pilo expe ience
We illus a e he pe o mance o he Mixed In ege Linea P og amming (MILP) model in-
oduced in Sec ion 3 oge he wi h he demand unc ion desc ibed in Sec ion 4 wi h a simpli ied
e sion o he ne wo k o ou pilo expe ience o Me olab R
.
Conside he simple ne wo k example depic ed in Figu e 2. This ne wo k has a simila
opology o he one p o ided by Me olab R
 o calib a e ou model in he pilo expe ience. I
ep esen s a small sec ion o he Pa is subway ne wo k.
12 3 4 5
1’
2’
4’
5’
31 2 3
2
3
2
2
Figu e 2: Ne wo k o Case s udy 5.
The ne wo k consis s o wo bidi ec ional lines(1-2-3-4-5 and 1’-2’-3-4’-5’), each o hem wi h
i e s a ions and sha ing one o hem (s a ion 3) which ac s as an in e change s a ion. Bo h lines
allow sho - u ns on he planning. The edges o he lines which ake pa o he sho - u n o
each line a e ma ked wi h dashed lines (2 −3−4 o one o he lines and 20−3−40 o he
o he ). The a el ime be ween consecu i e s a ions is w i en nex o each edge o he ne wo k.
The dwell imes a e ixed o 30 seconds o s a ions di e en om he head and he inal ones
(e`
i-pa ame e s). Also he minimum sa e y ime be ween consecu i e ips is 2 minu es (IS`-
pa ame e ). Hence, using ou no a ion |L|= 4 ( wo lines, bu each o hem in wo di ec ions),
|LS|= 4 and |LNS|= 0. The lines will be numbe ed om 1 o 4, whe e 1 and 2 co espond
wi h he ho izon al line, le – igh and igh –le , espec i ely, and lines 3 and 4 a e iden i ied
wi h he e ical line, up–down and down–up, espec i ely. The se o a ailable capaci ies o
he ains a e 800 and 1600 passenge s.
Fo illus a ion pu poses, we conside a planning ho izon o T= 20 minu es ( om 7:30 o
7:50), and a maximum numbe o ips ¯
k`= 7 o he ho izon al lines and ¯
k`= 10 o he e ical
lines. We assume ha all he passenge s ha canno ge on a ain because i is ull awai o he
nex ain (α= 1) and ha he uni a y penal y o pe sis ing passenge s is ixed o µ1= 0.1875
(excep o he las ip in which we ix i o 10 ×µ1= 1.875 o a oid a high excess o passenge s
22
a he end o he planning ho izon). This choice o he µ1-pa ame e causes ha he excess o
passenge s is equal o 0 a he end o he planning ho izon. We also assume ha 40% o he
passenge s ha ge -o a s a ion 3 in e change o he o he lines (τ-pa ame e ).
The O-D ma ix and ewa ds pe passenge a e de ailed in Tables 3 and 4, espec i ely.
p`
ij 1 2 3 4 5 p`
ij 1’ 2’ 3 4’ 5’
10 0.40 0.35 0.20 0 1’ 0 0.40 0.35 0.20 0
20.40 0 0.60 0.35 0 2’ 0.40 0 0.60 0.35 0
30.35 0.6 0 0.95 0 30.35 0.60 0 0.95 0
40.20 0.35 0.95 0 1 4’ 0.20 0.35 0.95 0 1
50.05 0.05 0.05 1 0 5’ 0.05 0.05 0.05 1 0
Table 3: O-D ma ix o Case s udy 5: Lines 1-2 (le ) and 3-4 ( igh ).
γ`
ij 12345 γ`
ij 1’ 2’ 3 4’ 5’
10 0.3 0.4 0.6 1 1’ 0 0.2 0.5 0.7 1
20.3 0 0.1 0.3 1 2’ 0.2 0 0.3 0.5 1
30.5 0.2 0 0.2 1 30.4 0.2 0 0.2 0
40.6 0.3 0.1 0 0 4’ 0.7 0.5 0.3 0 0
50.9 0.6 0.4 0.3 0 5’ 0.9 0.7 0.5 0.2 0
Table 4: Rewa ds o Case s udy 5: Lines 1-2 (le ) and 3-4 ( igh ).
Fo he demand unc ion, we conside he a i al a es o passenge s pe minu e and he
ini ial numbe o passenge s a each s a ion o each line de ailed in Table 5.
Lines
`= 1 `= 2
S a ions (i) 1 2 3 4 5 5 4 3 2 1
β`
0i50 50 50 50 0 50 50 50 50 0
β`
i10 100 120 90 0 10 160 180 150 0
`= 3 `= 4
S a ions (i) 1’ 2’ 3 4’ 5’ 5’ 4’ 3 2’ 1’
β`
0i50 50 50 50 50 50 50 50 50 50
β`
i10 150 170 160 0 10 100 180 150 0
Table 5: Coe icien s o he Demand unc ions o Case s udy 5.
Ou model was coded in Py hon 3.6, and sol ed using Gu obi 8.0 [19] in a Mac OSX wi h
an In el Co e i7 p ocesso a 3300 MHz and 16GB o RAM, using he de aul pa ame e s o he
Gu obi op imize .
The ime abling o he i s line is p o ided in Table A.8 o he Appendix. This able allows
he in e es ed eade o see how he solu ion o he ma hema ical p og amming model can be
u ned in o a eal ime abling o a gi en se o lines. The epo ed solu ion was ob ained a e
12 hou s unning ime wi h a MIP GAP o 1.51%.
The depa ing imes o each ue ip o all he lines om each o he s a ions a e de ailed
in Figu e 3. The ho izon al axis is he ime ho izon, while he e ical axis ep esen spa ial
23
leng hs (s a ions). We also epo o e each o he i ine a ies, hei op imal capaci ies. No e
ha he op imal numbe o ips o line 1 is 5, o line 2 is 6, o line 3 is 8 and o line 4 is 7.
Sho es i ine a ies unning only o e a subse o s a ions a e sho - u ns. One can obse e ha
he ime di e ence be ween consecu i e ips is no cons an , as expec ed om he asymme y
o he lines and he ans e o passenge s be ween hem a di e en ime ins an s. Then, as
men ioned be o e, we deal wi h an ape iodic ime abling.
Figu e 3: Time ables o he di e en ips o each line o he Case s udy o Sec ion 5.
Fu he mo e, wi h he solu ion ob ained, he es ima ed demands a he depa ing imes o
each one o he ips a he in e change s a ion a e d awn in Figu e 4. Obse e ha in ha
pic u e we d aw in he ho izon al axis, he depa ing imes o such an in e change s a ion a he
di e en ips. In he e ical axis we depic he accumula ed demand a hose ime ins an s.
No e ha he jumps in he demand induced by passenge s ha in e change o ha line occu
du ing he whole ime in e al be ween depa ing imes o he in e change s a ion, bu we only
accoun o he accumula ed amoun when he new ain depa s.
Figu e 4: Accumula ed Demands ob ained o he Case s udy o Sec ion 5.
A summa y o he cos s and ewa ds ob ained o he epo ed solu ion is gi en in Table 6.
Since an agg ega ed unc ion o he cos s is minimized in ou model, he nega i e o e all cos
ob ained (−11404.88) can be seen as a posi i e global ewa d o he op imal planning.
P oblem (P) depends on he demand ha occu in each line and on he co ela ion be ween
lines induced by in e changing s a ions. Fo ha eason, o ha e an exac model he demands by
lines mus be conside ed as a iables and hence, he p oblem ha conside s all he lines a he
same ime becomes e y ha d by ob ious easons. Among hem, he p oblem is a Mixed In ege
P og amming P og am whose con inuous elaxa ion is nei he con ex no conca e because o he
bilinea cons ain s in (DI); and in addi ion, he numbe o a iables inc eases conside ably wi h
24
[15] Y. Gao, L. K oon, L. Yang, and Z. Gao. Th ee-s age op imiza ion me hod o he p oblem
o scheduling addi ional ains on a high-speed ail co ido . Omega, 80:175–191, 2018.
[16] M. Goe igk and M. Schmid . Line planning wi h use -op imal ou e choice. Eu opean
Jou nal o Ope a ional Resea ch, 259(2):424–436, 2017.
[17] M. Goe igk and A. Sch¨obel. Imp o ing he modulo simplex algo i hm o la ge-scale pe iodic
ime abling. Compu e s & Ope a ions Resea ch, 40(5):1363–1370, 2013.
[18] V. Guihai e and J.-K. Hao. T ansi ne wo k design and scheduling: A global e iew. T ans-
po a ion Resea ch Pa A: Policy and P ac ice, 42(10):1251–1273, 2008.
[19] Gu obi Op imiza ion. Gu obi op imize e e ence manual e sion 8.0, 2018.
[20] M. Heida i, S.M. Hosseini-Mo lagh, and N. Nikoo. A subway planning bi-objec i e mul i-
pe iod op imiza ion model in eg a ing ime abling and ehicle scheduling: a case s udy o
Teh an. T anspo a ion, 2018.
[21] L. Kang, J. Wu, H. Sun, X. Zhu, and B. Wang. A p ac ical model o las ain escheduling
wi h ain delay in u ban ailway ansi ne wo ks. Omega, 50:29–42, 2015.
[22] L. Kang, X. Zhu, H. Sun, J. Wu, Z. Gao, and B. Hu. Las ain ime abling op imiza ion
and bus b idging se ice managemen in u ban ailway ansi ne wo ks. Omega, 84:31–44,
2019.
[23] L. Kanga, X. Zhua, H. Suna, J. Puchinge c, M. Ru hmai e, and B. Hu . Modeling he i s
ain ime abling p oblem wi h minimal missed ains and synch oniza ion ime di e ences
in subway ne wo ks. T anspo a ion Resea ch Pa B, 93:17–36, 2016.
[24] G. Lapo e, J.A. Mesa, F.A. O ega, and F. Pe ea. Planning apid ansi ne wo ks. Socio-
Economic Planning Sciences, 45:95–104, 2011.
[25] G. Lapo e, F.A. O ega, M.A. Pozo, and J. Pue o. Mul i-objec i e in eg a ion o ime a-
bles, ehicle schedules and use ou ings in a ansi ne wo k. T anspo a ion Resea ch Pa
B, 98:94–112, 2017.
[26] Y. Lee and C.Y. Chen. A heu is ic o he ain pa hing and ime abling p oblem. T ans-
po a ion Resea ch Pa B, 43:837–851, 2009.
[27] R. Liu, S. Li, and L. Yang. Collabo a i e op imiza ion o me o ain scheduling and ain
connec ions combined wi h passenge low con ol s a egy. Omega, 90, 2020.
[28] G.P. McCo mick. Compu abili y o global solu ions o ac o able noncon ex p og ams: Pa
I. Con ex unde es ima ing p oblems. Ma hema ical P og amming, 10, 147–175, 1976.
[29] J.A. Mesa, F.A. O ega, and M.A. Pozo. E ec i e alloca ion o lee equencies by educing
in e media e s ops and sho u ning in ansi sys ems. In R.K. Ahuja, R.H. M¨oh ing,
and C.D. Za oliagis, edi o s, Robus and Online La ge-Scale Op imiza ion, Lec u e No es in
Compu e Science, Vol. 5868, pages 293–309. Sp inge -Ve lag, Be lin Heidelbe g, 2009.
[30] M. Michaelis and A. Sch¨obel. In eg a ing line planning, ime abling, and ehicle scheduling:
A cus ome -o ien ed heu is ic. Public T anspo , 1(3):211–232, 2009.
[31] H. Niu, X. Zhou, and R. Gao. T ain scheduling o minimizing passenge wai ing ime wi h
ime-dependen demand and skip-s op pa e ns: Nonlinea in ege p og amming models
wi h linea cons ain s. T anspo a ion Resea ch Pa B, 76:117–135, 2015.
31

[32] F. O ega, M.A. Pozo, and J. Pue o. On-line ime able escheduling in a ansi line.
T anspo a ion Science, 52(5):1035–1296, 2018.
[33] J. P¨a zold, and A. Sch¨obel. A ma ching app oach o pe iodic ime abling. In 16 h Wo k-
shop on Algo i hmic App oaches o T anspo a ion Modelling, Op imiza ion, and Sys ems
(ATMOS 2016). Schloss Dags uhl-Leibniz-Zen um ue In o ma ik, 2016.
[34] A. Sch¨obel. Line planning in public anspo a ion: Models and me hods. OR Spec um,
34:491–510, 2012.
[35] A. Sch¨obel. An eigenmodel o i e a i e line planning, ime abling and ehicle scheduling in
public anspo a ion. T anspo a ion Resea ch Pa C: Eme ging Technologies, 74:348–365,
2017.
[36] L. Sun, J.G. Jin, D.H. Lee, K.W. Axhausen, and A. E a h. Demand-d i en ime able design
o me o se ices. T anspo a ion Resea ch Pa C, 46:284–299, 2014.
[37] S. Tekin, S. K¨o eci, M.M. Aydin, and M.S. Yildi im. T ip op imiza ion o public ans-
po a ion sys ems wi h linea goal p og amming (lgp) me hod. Sigma Jou nal o Enginee ing
and Na u al Sciences, 36(4):921–933, 2018.
[38] W. Wee awa and K. Chumkad. A new ope a ions app oach o Bangkok me o g een line
using sho u n ope a ion pa e ns. Jou nal o Rail T anspo Planning and Managemen ,
8:207–219, 2018.
[39] R.C.W. Wong, T.W.Y. Yuen, K.W. Fung, and J.M.Y. Leung. Op imizing ime able syn-
ch oniza ion o ail mass ansi . T anspo a ion Science, 42(1):57–69, 2008.
[40] L. Yang, J. Qi, S. Li, and Y. Gao. Collabo a i e op imiza ion o ain scheduling and ain
s op planning on high-speed ailways. Omega, 64:57–76, 2016.
[41] C. Zhang, Y. Gao, L. Yang, U. Kuma , and Z. Gao. In eg a ed op imiza ion o ain
scheduling and main enance planning on high-speed ailway co ido s. Omega, 87:86–104,
2019.
32
Appendix A. Resul s o he i s line o he Case s udy (Sec ion 5)
In Table A.8, we de ail o each ip, k(indica ing wi h S’ hose ips which a e sho - u ns),
i s op imal capaci y, he depa ing imes o each ain o each line (DepTime), and also he low
es ima ions a each o he s ages: he numbe o passenge s ha ge -o he ain (Ge -O ),
he numbe o passenge s ha ge -on he ain ( k`
i o whole ips o gk`
i o sho - u ns), he
excess o passenge s (hk`
i), he passenge s su plus o ue ips (xk`
i) and he ac ual load o he
ain Load.
33
k: Capaci y iDepTime Ge -O k`
i(gk`
i)hk`
ixk`
iLoad
1: 800
1 07:30:00 0.00 50.00 0.00 0.00 50.00
2 07:33:30 20.00 400.00 0.00 0.00 430.00
3 07:35:00 257.50 627.50 101.50 101.50 800.00
4 07:37:30 746.13 725.00 0.00 0.00 778.88
5 07:40:30 778.88 0.00 0.00 0.00 0.00
2S: 1600
2 07:39:34 0.00 606.94 0.00 0.00 606.94
3 07:41:04 364.17 1231.59 0.00 0.00 1474.36
4 07:43:34 1474.36 0.00 638.18 0.00 0.00
3: 0
1 07:30:00 0.00 0.00 0.00 0.00 0.00
2 07:39:34 0.00 0.00 0.00 0.00 0.00
3 07:41:04 0.00 0.00 0.00 0.00 0.00
4 07:43:34 0.00 0.00 638.18 0.00 0.00
5 07:40:30 0.00 0.00 0.00 0.00 0.00
4S: 800
2 07:43:12 0.00 364.02 0.00 0.00 364.02
3 07:44:42 218.41 603.05 0.00 0.00 748.66
4 07:47:12 748.66 0.00 1014.15 0.00 0.00
5: 0
1 07:30:00 0.00 0.00 0.00 0.00 0.00
2 07:43:12 0.00 0.00 0.00 0.00 0.00
3 07:44:42 0.00 0.00 0.00 0.00 0.00
4 07:47:12 0.00 0.00 1014.15 0.00 0.00
5 07:40:30 0.00 0.00 0.00 0.00 0.00
6: 1600
1 07:46:15 0.00 162.60 0.00 0.00 162.60
2 07:49:45 65.04 655.05 0.00 0.00 752.61
3 07:51:15 449.94 1297.33 0.00 0.00 1600.00
4 07:53:45 1494.25 1494.25 109.44 109.44 1600.00
5 07:56:45 1600.00 0.00 0.00 0.00 0.00
7: 800
1 07:50:00 0.00 37.40 0.00 0.00 37.40
2 07:53:30 14.96 373.99 0.00 0.00 396.43
3 07:55:00 237.48 641.05 0.00 0.00 800.00
4 07:57:30 747.38 446.03 0.00 0.00 498.65
5 08:00:30 498.65 0.00 0.00 0.00 0.00
Table A.8: Resul s o he i s line o he Case s udy 5. T ips 3 and 5 a e ake ips ( hey ha e ze o capaci y),
being 5 he op imal numbe o ips o his case s udy. Two o hem (2S and 4S) a e sho - u ns, while he
emainde a e whole ips. As s a ed, ake ips ope a e on he line a he same ime as he p e ious ue ip. Fo
ins ance, ip 3 depa s om s a ion 1, which doesn’ belong o he sho - u n, a he same ime ha he p e ious
ue whole ip (1) and om s a ion 2, which belongs o he sho - u n, a he same ime ha he p e ious ue
ip o his s a ion (2S).
34