公交转车问题.pptVIP

公交转车问题 南京邮电大学理学院杨振华制作 yangzhenhua@njupt.edu.cn 公交转车问题 针对市场需求，某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。 公交：指公共交通工具 ，包括公共汽车与地铁。 公交转车问题 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线 (1)S3359→S1828 (2)S1557→S0481 (3)S0971→S0485 (4)S0008→S0073 (5)S0148→S0485 (6)S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。 公汽线路信息 公汽运行方式 （1）环形 （2）上下行（有可能上下行路线一致） 公汽收费方式 （1）分段计价 （2）单一票制1元 公汽线路信息 文件列出了520条公汽线路，下面是其中的一条： L001 分段计价。 S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710 该线路是分段计价，且上下行路线一致的。 地铁线路信息 T1 票价3元，本线路使用，并可换乘T2。 D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21-D22-D23 T2 票价3元，本线路使用，并可换乘T1。 环行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24 地铁T1线换乘公汽信息 D01：S0567，S0042，S0025 D02：S1487 D03：S0303，S0302 D04：S0566 D05：S0436，S0438，S0437，S0435 D06：S0392，S0394，S0393，S0391 D07：S0386，S0388，S0387，S0385 D08：S3068，S0617，S0619，S0618，S0616 D09：S1279 D10：S2057，S0721，S0722，S0720 D11：S0070，S2361，S3721 D12：S0609，S0608 D13：S2633，S0399，S0401，S0400 D14：S3321，S2535，S2464 D15：S3329，S2534 D16：S3506，S0167，S0168 D17：S0237，S0239，S0238，S0236，S0540 D18：S0668 D19：S0180，S0181 D20：S2079，S2933，S1919，S1921，S1920 D21：S0465，S0467，S0466，S0464 D22：S3457 D23：S2512 地铁T2线换乘公汽信息 D24：S0537，S3580 D25：S0526，S0528，S0527，S0525 D26：S3045，S0605，S0607 D12：S0609，S0608 D27：S0087，S0088，S0086 D28：S0855，S0856，S0854，S0857 D29：S0631，S0632，S0630 D30：S3874，S1426，S1427 D31：S0211，S0539，S0541，S0540 D32：S0978，S0497，S0498 D18：S0668 D33：S1894，S1896，S1895 D34：S1104，S0576，S0578，S0577 D35：S3010，S0583，S0582 D36：S3676，S0427，S0061，S0060 D37：S1961，S2817，S0455，S0