An optimization model for line planning and timetabling in automated urban metro subway networks. A case study

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