公交线路模型.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date公交线路模型公交线路模型公交线路模型摘 要本文解决的是线路选择的问题，我们利用分层处理法，针对转车次数、乘车时间、乘车费用这三个考虑因素，对不同的查询者分别建立了不同的优先级，属于多目标决策的最优化模型。对于问题一：首先我们在转车次数最少的情况下，根据查询者的要求，把查询者分成三种类型：节约时间型、节约费用型和两者兼顾型，然后建立了总的时间模型和费用模型，分别根据三种查询者的要求确定了优先级，针对不同的优先级确定了多目标决策模型，利用Matlab编程求出了6对起始站终到站之间的最佳路线：（以S0087S3676为例）起始站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0087L454上行线S3496L209下行线S36761652对于问题二：我们同样采用层次分析法，对三种类型的查询者分别建立模型，在转车次数最少的前提下，利用Matlab编程求出了6对起始站终到站之间的最佳路线：（以S0087S3676为例）行驶路线中转站地铁编号中转站行驶路线终点站中转站数耗时（分钟）费用（元）步行到D27D27T2D36步行到S3676S36760383对于问题三：在问题二的基础上，考虑步行的可能，假设知道所有站点之间的步行时间，同样我们先建立总的时间模型和费用模型，在转车次数最少的同时，要使得线路需要步行时间最短。关键词：线路选择 多目标决策 层次分析法 优先级 最优化1. 问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。在本文中，为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。我们考虑路线选择的合理性以及查询者的各种不同要求，建立了多目标规划模型。各类查询者的不同需求：根据查询者的不同需求，我们考虑到查询者可能对乘车时间，乘车费用，转车次数等因素比较关注。但是根据实际情况，没有人为了节约时间和节约费用而宁愿多次转车的，所以对于起始站均相同的不同路线，在考虑最佳路线时，我们人为排除转车达三次及三次以上的路线。另外，我们把查询者的需求分成三种类型，一是节约时间型，二是节约费用型，三是两者兼顾型，但是不管查询者的需求是哪种类型，我们必须在考虑转车次数最少的同时，还要考虑其它因素的影响，因此我们对于不同需求的查询者，根据他的要求，将三种因素的优先级定义如下：对于节约时间型，它的优先级为：最先考虑转车次数、其次是时间、最后是费用；对于节约费用型，它的优先级为：最先考虑转车次数、其次是费用、最后是时间；对于两者兼顾型，最先考虑转车次数，时间和费用优先级相同。另外，我们还为这三种类型的查询者分别建立了三个不同的线路查询方式，一是节约时间型线路查询，二是节约费用型线路查询，三是省时省费用型线路查询。本文需解决的问题有：问题一：仅考虑公汽线路最佳路线，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线 （要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 2. 模型的假设与符号说明2.1模型的基本假设相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)2.1其它假设1. 假设最佳路线中转车次数不超过两次；2. 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)；3. 假设各公交运行正常，不会发生堵车现象；4. 假设公交车和地铁都是到站后再停车。2.3符号说明 ：起点站i到终点站j汽车经过的站点个数 ：转乘次数 ：初始车站等待时间 ：相邻公汽站平均行驶时间 ：公汽换乘公汽平均耗时 ：乘客乘第n辆公汽所花费的费用 ：公交计算价格因子 ：乘客乘第n辆公汽所经过的站点A ：表示公汽经过的站点总数a ：表示公汽换乘公汽的次数b ：表示公汽换乘地铁的次数D ：表示地铁经过的站点总数d ：表示地铁换乘地铁的次数e ：表示地铁换乘公汽的次数 ：表示初始站点等待时间 ：相邻公汽站平均行驶时间 ：表示公汽换乘公汽平均耗时 ：表示公汽换乘地铁平均耗时 ：表示相邻地铁站平均行驶时间 ：表示地铁换乘地铁平均耗时 ：表示地铁换乘公汽平均耗时 ：表示公交经过站点的占总站点的比例 ：表示公交经过的站点表示第n辆公交所花费的费用3. 问题分析本文研究的是公交线路选择问题，在选择公交线路时乘客通常会考虑三方面因素：转车次数、乘车时间、乘车费用。不同的查询者有不同的要求， 通过查阅南京市做的一个公交乘客出行心理调查统计（结果如下图）可知：41.16%的乘客在选择出行路径时，首先考虑的是转车次数最少，其次考虑的是时间和费用。因此我们把转车次数作为最主要的影响因素，然后根据不同查询者的要求分别建立节约时间型模型、节约费用型模型和两者兼顾型模型，并把两者兼顾型模型的求解结果作为起始站和终点站均相同时的最佳路线。针对问题一：仅考虑公汽线路最佳路线，先将整条线路中的时间模型和乘车费用模型建立出来，再根据不同查询者的要求分别建立上面所说的三种模型，并根据附录数据，利用我们的模型，求出6对起始站终到站之间的最佳路线。在求解过程中我们把转车次数作为第一考虑因素，也就是说转车次数的优先级最高，对于节约时间型的查询者，他的第二优先级为时间，最后是费用；而对于节约费用型的查询者，他的第二优先级为费用。针对问题二： 我们同时考虑了公汽与地铁线路的相关信息，跟问题一一样，我们先建立总的时间和费用模型，然后对不同查询者的要求分别建立模型，利用Matlab求解不同需求下的最佳模型。针对问题三：考虑到对于较近的公汽站或者地铁站，查询者可以步行，在假设知道所有站点之间的步行时间，我们建立了转车次数最少且线路需要步行时间最短的多目标模型。 4. 数据的处理与分析4.1 公汽线路原始数据的处理与分析由于所给的数据量比较大，而且存储在txt文档中，不方便运用，我们利用Matlab编程，将原始数据转换成元胞数组，其程序见附录一。根据程序结果，我们可以轻松得到有关公汽线路的相关信息：（1）公汽线路总共有520条，公汽站点共有3957个；（2）附录一的程序中，L用来存储L001到L520线路信息，查询L，我们可以轻松得到每条线路的起始站、途径站及终点站点编号，以公交线L086和L111为例：L0861来回1S2365-S1047-S2916-S1045-S0748-S2410-S3633-S0989-S0503-S0437L0861来回2S2365-S1047-S2916-S1045-S0748-S2410-S3633-S0989-S0503-S0437L2622上行S2872-S3562-S2284-S1880-S2065-S2064-S2279-S0700-S1747-S1327-S1842-S0205L2622下行S0205-S1842-S1327-S0700-S2279-S2064-S2065-S1880-S2284-S3562-S28721> L086和L111表示公汽线路编号为；2>“1”表示该线路为单一票价，且票价为1元，“2”表示该线路实行分段计价；3>“上行”下行“”表示该线路是上行（或下行）线路，“来回1”“来回2”表示下行线是上行线原路返回（站点名完全相同）；“环行”表示该公汽线路是环行行驶的；4.2 地铁线路原始数据的处理与分析地铁T1换乘公汽的相关信息：地铁站地铁站可换乘的公交站点地铁站地铁站可换乘的公交站点D01S0567，S0042，S0025D13S2633，S0399，S0401，S0400D02S1487D14S3321，S2535，S2464D03S0303，S0302D15S3329，S2534D04S0566D16S3506，S0167，S0168D05S0436，S0438，S0437，S0435D17S0237，S0239，S0238，S0236，S0540D06S0392，S0394，S0393，S0391D18S0668D07S0386，S0388，S0387，S0385D19S0180，S0181D08S3068，S0617，S0619，S0618，S0616D20S2079，S2933，S1919，S1921，S1920D09S1279D21S0465，S0467，S0466，S0464D10S2057，S0721，S0722，S0720D22S3457D11S0070，S2361，S3721D23S2512D12S0609，S0608地铁T2换乘公汽的相关信息：地铁站地铁站可换乘的公交站点地铁站地铁站可换乘的公交站点D24S0537，S3580D32S0978，S0497，S0498D25S0526，S0528，S0527，S0525D18S0668D26S3045，S0605，S0607D33S1894，S1896，S1895D12S0609，S0608D34S1104，S0576，S0578，S0577D27S0087，S0088，S0086D35S3010，S0583，S0582D28S0855，S0856，S0854，S0857D36S1961，S2817，S0455，S0456D29S0631，S0632，S0630D37S0180，S0181D30S3874，S1426，S1427D38S3262，S0622D31S0211，S0539，S0541，S0540D39S1956，S0289，S02915 问题一的解答仅考虑公汽线路，我们对不同转车次数不同类型的查询者分别求了最佳路线，但对于起始站和终点站均相同的情况，我们以直达路线中两者兼顾型作为该问题的最佳路线。5.1 模型一的建立（针对问题一） 5.1.1 时间费用总模型（1）查询者从起始站出发到达终点站，相邻公汽站平均行驶时间设为，在公汽换乘公汽的过程中会花费一段时间，查询者进入车站后有可能不会马上搭到公汽，在起始站等待时间设为，因此有乘车时间模型：（2）用表示转乘次数，当转乘次数为0，即直达时，乘车费用为所搭公汽的费用；转车次数为1时，乘车费用为前后两辆公汽所收的费用；转车次数为2时，乘车费用为所搭三辆公汽所收的费用之和，则有乘车费用模型：5.1.2 查询者的三种需求模型（1）对于节约时间型查询者，乘车时间、乘车费用、转车次数三种因素的影响优先级为：最先考虑转车次数、然后是时间，则有节约时间型线路查询模型（2）对于节约费用型查询者，乘车时间、乘车费用、转车次数三种因素的影响优先级为：最先考虑转车次数、然后是费用，则有节约费用型线路查询模型 （3）对于两者兼顾型型查询者，乘车时间、乘车费用、转车次数三种因素的影响优先级为：最先考虑转车次数、乘车时间和乘车费用的优先级相同，则有两者兼顾型线路查询模型 5.2 模型一的求解思想：我们先用Matlab将题中所给的数据处理成元胞数组形式，为了不区分环形，沿原路返回、上行和下行线路，我们将520条路线处理成1040条单条路径，根据起始站点和终点站判断是否可以直达。如果可以直达，则直接根据起始站和终点站找到可行的路径。如果不可以直达，则应该考虑转车的情况：当需要一次转车时，依据起始站找出通过起始站的所有路径A，依据终点站找到通过终点站的所有路径B，再用交集操作找到A和B具有的共同站点p，通过并集等集合操作找到所有可行的路径C（C=AB），然后根据可行的路径，将时间和费用计算出来，并比较得出不同要求下的最佳路线。当需要两次转车时，依据起始站找出通过起始站的所有线路集合E，然后找出线路E上所经过的所有站点F，经过站点F的所有线路集合A，接着找出通过终点站的所有线路集合B，再用交集操作找到具有共同站点p, 再通过并集等集合操作找到所有可行的路径D（D=AB），根据可行的路径,将时间费用计算出来，并比较得出不同要求下的最佳路线。5.3 问题一的结果(1)、S3359S1828经过求解我们得出该两公汽站点直接没有直达车，最少转车次数为一次，当转车次数为一次时，共有10条可行线路，对于不同查询者的要求有以下几种线路:1> 节约时间型：（所有可行线路中最短时间为101分钟）起始站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S3359L436下行线S1784L167下行线S182811013S3359L436下行线S1784L217下行线S1828110132> 节约费用型：（所有可行线路中最少费用为3元）起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S3359L436下行线S1784L167下行线S182813101S3359L436下行线S1241L167下行线S182813107S3359L436下行线S1784L217下行线S182813101S3359L436下行线S1241L217下行线S182813107S3359L436下行线S3695L217下行线S182813113S3359L436下行线S2606L217下行线S182813125S3359L469上行线S0727L217下行线S182813137S3359L469上行线S0304L217下行线S182813137S3359L469上行线S3192L217下行线S1828131373> 两者兼顾型 ：(乘车费用为3元且乘车时间为101分钟的路线即为最佳路线)起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S3359L436下行线S1784L167下行线S182813101S3359L436下行线S1784L217下行线S182813101(2)、S1557S0481 经过求解我们得出该两公汽站点直接没有直达车，最少转车次数为2次，共有296条可行线路，对于不同查询者的要求有以下几种线路:1> 节约时间型：（所有可行线路中最短时间为106分钟）起始站行驶路线中转站行驶路线行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S1557L084下行线S1919L189下行线L189下行线S3186L460S048121063S1557L363下行线S919L189下行线L189下行线S3186L460S0481210632> 节约费用型：（所有可行线路中最少费用为3元）296条可行线路中，费用为3元或4元，但所花时间为106分钟到250分钟，转车次数均为2次，所以最佳路线肯定是费用为三元且所花时间为106分钟的线路。3> 两者兼顾型：(乘车费用为3元且乘车时间为106分钟的路线即为最佳路线)起始站行驶路线中转站行驶路线行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S1557L084下行线S1919L189下行线L189下行线S3186L460S048121063S1557L363下行线S919L189下行线L189下行线S3186L460S048121063(3)、S0971S0485 经过求解我们得出该两公汽站点直接没有直达车，最少转车次数为1次，共有12条可行线路，对于不同查询者的要求有以下几种线路:1> 节约时间型：（所有可行线路中最短时间为128分钟）起始站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0971L013下行线S2184L417下行线S0485112832> 节约费用型：（所有可行线路中最少费用为3元）起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S0971L013下行线S2119L395下行线S048513143S0971L013下行线S2184L417下行线S048513128S0971L013下行线S0992L417下行线S048513131S0971L013下行线S2322L417下行线S048513134S0971L013下行线S1770L417下行线S048513134S0971L013下行线S1789L417下行线S048513134S0971L013下行线S2119L417下行线S048513134S0971L119下行线S0872L417下行线S048513149S0971L119下行线S1739L417下行线S0485131493> 两者兼顾型：(乘车费用为3元且乘车时间为128分钟的路线即为最佳路线)起始站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0971L013下行线S2184L417下行线S048511283(4)、S0008S0073 经过求解我们得出该两公汽站点直接没有直达车，最少转车次数为1次，共有81条可行线路，对于不同查询者的要求有以下几种线路:1> 节约时间型：（所有可行线路中最短时间为83分钟）起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S0008L159下行线S2683L058下行线S00731283S0008L159下行线S0291L058下行线S00731283S0008L159下行线S3614L058下行线S00731283S0008L159下行线S0491L058下行线S00731283S0008L159下行线S2559L058下行线S00731383S0008L159下行线S3315L058下行线S00731383S0008L159下行线S2559L464上行线S00731383S0008L159下行线S0400L474上行线S00731283S0008L159下行线S2633L474上行线S00731283S0008L159下行线S3053L474上行线S00731283S0008L355下行线S2263L345上行线S00731283S0008L355下行线S3917L345上行线S00731283S0008L355下行线S2303L345上行线S007312832> 节约费用型：（所有可行线路中最少费用为2元）起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S0008L159下行线S2683L058下行线S00731283S0008L159下行线S0291L058下行线S00731283S0008L159下行线S3614L058下行线S00731283S0008L159下行线S0491L058下行线S00731283S0008L159下行线S0400L474上行线S00731283S0008L159下行线S2633L474上行线S00731283S0008L159下行线S3053L474上行线S00731283S0008L355下行线S2263L345上行线S00731283S0008L355下行线S3917L345上行线S00731283S0008L355下行线S2303L345上行线S00731283S0008L159下行线S3917L011下行线S00731289S0008L355下行线S2303L011下行线S00731289S0008L355下行线S2263L057上行线S00731286S0008L355下行线S3917L057上行线S00731286S0008L355下行线S2302L057上行线S00731286S0008L355下行线S3232L057上行线S007312863> 两者兼顾型：(乘车费用为2元且乘车时间为83分钟的路线即为最佳路线)起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S0008L159下行线S2683L058下行线S00731283S0008L159下行线S0291L058下行线S00731283S0008L159下行线S3614L058下行线S00731283S0008L159下行线S0491L058下行线S00731283S0008L159下行线S0400L474上行线S00731283S0008L159下行线S2633L474上行线S00731283S0008L159下行线S3053L474上行线S00731283S0008L355下行线S2263L345上行线S00731283S0008L355下行线S3917L345上行线S00731283S0008L355下行线S2303L345上行线S00731283(5)、S0148S0485 经过求解我们得出该两公汽站点直接没有直达车，最少转车次数为2次，共有380条可行线路，对于不同查询者的要求有以下几种线路:1> 节约时间型：（所有可行线路中最短时间为115分钟）起始站行驶路线中转站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0148L308上行线S3604L123上行线S2026L469上行线S048521153S0148L308上行线S3604L129上行线S1383L469上行线S048521153S0148L308上行线S3604L129上行线S1381L469上行线S0485211532> 节约费用型：（所有可行线路中最少费用为3元）起始站行驶路线中转站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S0148L024S1487L378S2026L469上行线S048523124S0148L024S1487L378S3359L469上行线S048523124S0148L024S1487L378S2023L469上行线S048523124S0148L024S1487L378S2027L469上行线S048523121S0148L024S1487L427S2027L469上行线S048523121S0148L024S3341L013下行线S0992L417下行线S048523160S0148L308上行线S1716L481S2027L469上行线S048523133S0148L308上行线S0128L427S2027L469上行线S048523124S0148L308上行线S0128L481S2027L469上行线S048523133S0148L308上行线S3604L021下行线S0248L469上行线S048523124S0148L308上行线S3604L021下行线S3776L469上行线S048523130S0148L308上行线S3604L021下行线S1590L469上行线S048523136S0148L308上行线S3604L082上行线S0992L417下行线S048523166S0148L308上行线S3604L123上行线S2026L469上行线S048523115S0148L308上行线S3604L123上行线S3359L469上行线S048523121S0148L308上行线S3604L129上行线S1383L104下行线S048523124S0148L308上行线S3604L129上行线S1383L469上行线S048523115S0148L308上行线S3604L129上行线S1381L104下行线S048523124S0148L308上行线S3604L129上行线S1381L469上行线S048523115S0148L308上行线S3604L129上行线S1321L104下行线S048523127S0148L308上行线S3604L129上行线S1321L469上行线S048523118S0148L308上行线S3604L206下行线S2079L417下行线S048523121S0148L308上行线S3604L454上行线S2840L417下行线S048523118S0148L308上行线S3604L454上行线S1893L104上行线S048523124S0148L308上行线S3604L454上行线S1893L377下行线S048523130S0148L308上行线S3604L454上行线S1893L395下行线S048523124S0148L308上行线S3604L454上行线S0519L469下行线S048523127S0148L308下行线S0345L140下行线S3037L104下行线S0485231303> 两者兼顾型：(乘车费用为2元且乘车时间为115分钟的路线即为最佳路线)起始站行驶路线中转站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0148L308上行线S3604L123上行线S2026L469上行线S048521153S0148L308上行线S3604L129上行线S1383L469上行线S048521153S0148L308上行线S3604L129上行线S1381L469上行线S048521153(6)、S0087S3676经过求解我们得出该两公汽站点直接没有直达车，最少转车次数为1次，共有2条可行线路，对于不同查询者的要求有以下几种线路:1> 节约时间型：（所有可行线路中最短时间为65分钟）起始站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0087L454上行线S3496L209下行线S367616522> 节约费用型：（所有可行线路中费用为均2元） 起始站行驶路线中转站行驶路线终点站转车次数费用（元）耗时（分钟）S0087L454上行线S3496L209下行线S36761265S0087L454上行线S1893L209下行线S367612713> 两者兼顾型：(乘车费用为2元且乘车时间为65分钟的路线即为最佳路线)起始站行驶路线中转站行驶路线终点站转车次数耗时（分钟）费用（元）S0087L454上行线S3496L209下行线S367616526. 问题二的解答对于问题二，我们在问题一的基础上，对于不同的查询者同样先考虑转车次数，然后根据查询者的要求考虑其他因素的影响，建立了三种模型。6.1模型二的建立（针对问题二）6.1.1时间和费用总模型同问题一一样，我们先建立不同的乘车方式所花费的（1）时间模型：（2）费用模型表示第n辆公交所花费的费用6.1.2查询者不同要求的两种模型（1）节约时间型 （2）节约费用型 （3）两者兼顾型 6.2模型二的求解 首先我们由地铁换乘公汽线路的信息可知，地铁T1、T2线可换乘的公汽，然后根据地铁票价及行驶路线，可得到查询者不同需求下的最佳路线。(1)、S3359S1828 从S3