《轨道交通路网末班车合理售票算法的研究与应用》由会员分享，可在线阅读，更多相关《轨道交通路网末班车合理售票算法的研究与应用（72页珍藏版）》请在金锄头文库上搜索。
1、1 9 S 3 8 3 4学校代号：1 0 2 5 5学号：2 0 7 0 7 2 3轨道交通路网末班车合理售票算法的研究与应用S t u d ya I l dA p p l i c a t i o no fa nA l g o r i t l l mo fS e l l i l l gT i c k e t si l lR e a s o nf o rL a s tT r a i n so nR a i lT r a n s i tN e 觚o r k学科专业：计算机软件与理论作者：彭益兵指导教师：苏厚勤答辩日期：2 0 1 0 年1 月15 日东华大学计算机科学与技术学院C o H e g
2、 eo fC o m p u t e rS c i e n c ea n dT e c h n o l o g yD o n g h u aU n i V e r s i t y，厂-山j学位论文作者签名：彰凝日期：加I o 年月山I； 本学位论文属于不保密学位论文作者签名：鸟盗丧日期：弦f 年f 月I g 日指导教师签名：刁，厚日期：，护年7 月，口日一_J间没有市轨交网的规模越来越大，换乘路径的走向将变得错综复杂，类似不能换乘末班车的情况将变得更加频繁。为解决城市轨交网晚间末班车换乘可达预知问题，本文提出关于解决晚间末班车换乘可达合理售票的技术思路，设计和实现了晚间末班车多条最佳可达路径的
3、求解算法。通过该算法可以预知晚间末班车可达路径，从而有效支持城市轨道交通晚间末班车的自动和半自动售票机合理售票。本文作者的主要研究工作如下：1 ) 针对上海当前实际运营轨交路网的拓扑结构，参与研究了信息无损的简化建模方法，并通过编程实现其邻接链表数据结构的存储，便于计算机处理；2 ) 研究和分析了晚间末班车时刻表的特征，针对并线共站和坏线晚间回库末班车的走向提出相应的处理方法；3 ) 在简化建模基础上，基于最短路径及其背离路径思想，研究和实现了搜索次短和次次短路径的算法；4 ) 通过回代，求得非简化建模中各站点对及其与简化建模中站点之间的多条最佳路径；5 ) 通过触模屏方式展现了本文研究成果，
4、并给出该成果在自动售票机上的应用方案。基于本文的研究成果，作者设计和实现了上海轨道交通晚间末班车可达最佳多路径查询系统。该系统在2 0 0 9 年上海国际工业博览会上获得全国高校优秀展品三等奖。关键字：城市轨交网，简化建模，自动售检票系统，站内换乘，末班车，背离路径，最佳多路径搜索算法ln e r c h a I l g e di no n es t a t i o n W i t ht 1 1 eg r o w i n gs c a l eo fc i t yr a j lt r a i n s i tn e t w o r 玉【，l e臼e n do f 仃锄s f 打p a m sw i
5、 l lb e c o m e cc o m p l i c a t i o nm o r e 锄l dm o r e ，t h es i m i l a rS i t u a t i o nw i l lb e c o m em o r e 行e q u e I l c e T bs o l V e 圮r e a c h a b l ep r e d i c t i n gp r o b l 锄a b o u tl 嬲t 勃r a i no fc i t yr a i l 仃j m s i tI l e l 、7 l ，o r ki nI l i 曲tw h e I lp a s s e I
6、 I g e r si n t e r c h 锄g e d ，at e c l l I l i c a li d e aa b o u tm es o l u t i o no fr e a c h a b l es e l l i n gt i c k e ti nr c a S o no f1 a S t 仃a i ni nn i 曲th 髂b e 饥p r o p o s e d ，锄das o l V i n ga 1 9 0 r i t l l mf o r t h eo p t i m a lr c a c h a b l em u l t i p a t h so fl a S
7、 t 砌n si nn i g h ti sd e s i 印e d 觚di m p l e m e n t e d 1 1 1 er e a c h a b l em u l t i p a t I lo fl 船tt r a i ni nn i g h tc 觚b ep f c d i c t e db ym ea l g o r i m m ，m e r e f o r s e l l i n gt i c k e t si nr e 嬲o no fl 觞tt r a i ni nI l i g h to fr a i l 胁s i tf 如mt i c k c tV e l l d o
8、 rm a c l l i n e 趾ds 锄i - a u t o m a t i ct i c k e tv e n d i n gm a c l l i n ec 觚b ee 仃e c t i V e l ys u p p o r t e d T h ep r i m 叫r c s e a r c h 、阳r ko fa u m o ri nt l l i st l l e s i si s 嬲t h ef o l l o w i n g s ：1 ) F o rt h et o p 0 1 0 9 ys 仃u c t u r eo fS h a I l 曲a ic i t yr a i
9、 l 仃a 1 1 s i tn e t 、) l ，o r ka tp r e s 锄t ，硼l o ro f “st h e s i sp 枷c i p a t e di nt h es t u d yo fa l li n f o 咖a t i o nn o n - l o s i n gs i I n p l i 6 e dm o d e l i n gm e t h o d ，a n dh 雒p r o 黟a I T l l I l c dt oa c m e V ei t sd a t as 缸1 l c 觚eo ft h ea 由a c e l l c yl i s t ，s o
10、t h a ti ti se 嬲i l yt ob ep r o c e s s c db yc o m p u t e r 2 ) R e s 伽c ho na n da I l a l y z et h ef e a n 鹏so ft l l el 嬲t 仃a i nt i m es c h e d u l e ci nn i 出，t h eC o r r c s p o n d i n gp r o c e s s 印p r o a c hh 舔b e c I lp r o p o s e df o rt h et e n d so ft l l el a s t 砌ni nl l i
11、咖o nc y c l el i n e 孤ds h a r e dl i n ew i t l lc o m m o ns t a t i o l l so fg o i n gb a c kg a r a g e 3 ) B a S e do nm es i m p l i f i e dm o d e l i n ga n dt h ei d e ao fm es h o r t e s tp a t ha l l dd e V i a t i o np a t l l s ，t 1 1 ea l g o r i m mf o rs e a r c h i n g2 t l Ip a m
12、a 1 1 d3 mp a t hh 嬲b e e ns t u d i e d 砒l dU17F轨道交通路网末班车合理售票算法的研究与应用i m p l e I n e n t e d 4 ) T h em u l t i p a m sa r es o l V e db yr 印l a c i n go fd i 脓既tl i 蝴k e y l 鼯ss t a t i o np a i r s觚db e 研e e I lk e y l e s ss t a t i o na n dk c ys t a i o np a i rb a s e do n l es i m p l i f i
13、e dm o d e l i n g 5 ) T h es t u d yr 懿u l th 勰b 嘲ls h o w e dt I l r o u g ht o u c hs c r c e 玛趾dn l ea p p l i c a t i o ns o l u t i o nh 嬲b e e l la l s o 百V 饥m a tc 趾b eu s c df o rt i c k e tV d o rm a c h i n e s B 嬲o do nm es t u d i e dr e s u l to f l i s l e s i s ，觚o p t i m a lr c a c
14、 h a b l em u l t i - p a t l lq u e r i n gs y s t e mf o rl 嬲t 的i ni I lI l i g h to fS h a l l g l l a ir a i lh 孤s i th 嬲b e 饥d e s i 印e da n di m p l e I l l e n t e db ym ea u t h o r ，a I l di ti sa w a r d e dm et l l i r dp r i z eo fn a t i o n a lu l l i V e 瑙i t yo u t s t a I l d i n gd
15、 i s p l a yi t e mo n2 0 0 9S h 趾g l l a iI n t 锄a t i o n a lI n d u s t r i a lE x p o s i t i o n P e l l gY i - b i n g ( C 锄p u t e rS o f l w a r e 姐dT h e o r y )S u p e i s e db yS 坠丛Q 坠：碰壁K e yw o r d s ：c i 锣r a i l 位m s i tn e t 刚溅s i I I l p l i 丘e dm o d e l i n 岛卸幢锄a t i cf a r ec o l l e c t i o ns y s t e m ，i n t e r e h 锄g ei ns t a t i o n ，1 a S t 臼面n ；d e v i a t e dp a m ，o p t i I n a lm u l t i p a t hs 翩r c ha l g o r i l I I lI I IJ_2 3 本章小结1 2第3 章图论相关知识。1 33 1 图的相关定义1 33 2 图的存储结构。1 43 3 本章小结18第4 章最佳多路径搜索算法的研究与实现1 94 1 最短路径搜索算法
