乘公交,看奥运.doc

乘公交，看奥运摘要本文研究了交通网络中的多目标道路寻优问题。首先对影响路线选择的因素进行分析，确定了三个目标函数：换乘次数最少、乘车时间最短、乘车花费最少。根据不同乘客的偏好，分别建立了偏向时间型和偏向金钱型的多目标函数，并确定相关的约束条件，最后利用MATLAB软件进行求解，得出不同类型乘客的最佳乘坐路线的选择。针对问题一，在只有公交路线的情况下，对公交线路进行一个抽象，建立不同偏好乘客的多目标规划模型，并确定换车次数的约束条件，利用MATLAB软件进行求解，最后得到对于不同偏好乘客其最佳路线的选取一样，即为：转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用线路1267L484S3697L485S1784L1673线路22109L363S1919L189S3186L4603线路32109L13S1609L140S2654L4963线路4270L198S1691L290S2184L3453线路52109L308S3604L129S1381L4693线路6249L21S88L231S427L972针对问题二，在问题一的基础上同时考虑地铁线路，将地铁站点与其周围的公汽站点作为抽象站点进行处理，同样的，我们建立了不同偏好乘客的多目标规划模型，并确定换车次数的约束条件，利用MATLAB软件进行求解，最后得到对于不同偏好乘客的最佳乘坐路线为： 偏好金钱的乘客的最佳乘车方案转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用线路1267L484S3697L485S1784L1673线路22109L84D20L189S3186L4603线路31131L13S2184L417_3线路4183L159D13L474_2线路52109L308S36L156S2210L4173线路6033L2311 偏好时间的乘客的最佳乘车方案转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用线路1267L484S3697L485S1784L1673线路22109L84D20L189S3186L4603线路3299L94D1T1D21L515线路4258L150D30T2D25L1035线路5290.5L24D2T1D21L515线路6030T33针对问题三，将步行范围等效为问题二中的抽象站点，建立多目标优化模型，解决了任意两点间的线路选择问题，并利用线路一进行检验。关键词：1问题重述问题的背景： 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。本文需要解决的问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2模型的假设与符号说明2.1 模型的假设假设1：所给公汽、地铁线路数据来源准确、可信、稳定。假设2：公共交通工具（包括公汽、地铁等）票价稳定，不因其它外在因素的动而变动。假设3：车站不重名。假设4：不出现车辆故障和道路交通事故。假设5：公交车准点到达，不考虑红绿灯等待的时间。 假设6：在时间相等的情况下，我们认为花费最少的线路为最佳线路假设7：在花费相等的情况下，我们认为时间最短的线路为最佳线路2.2 符号说明符号符号说明汽车站点是否在同一条线路上站点和站点是否步行地铁站和地铁站是否在同一条线路上汽车站点和地铁站点是否在同一条线路上地铁站点和汽车站点是否在同一条线路上相邻公汽站平均行驶时间相邻地铁站平均行驶时间第个站点是否为到的起始站站点到站点的乘车费用乘一次地铁需要的费用汽车站到汽车站之间经过的总站数地铁站到地铁站之间经过的总站数某一站点某一线路站点是否是线路上的某一站公汽换乘公汽的平均耗时地铁换乘地铁的平均耗时地铁换乘公汽的平均耗时公汽换乘地铁的平均耗时相邻两站之间步行的平均耗时3.问题分析此题研究的是选择最佳公交线路的数学建模问题，在三种不同的情况下，研究任意两个站点之间的线路选择。联系生活的实际，考虑公众乘坐公共交通工具的需求，确定最佳的乘车路线。针对问题一：在只考虑公汽线路的情况下，首先根据题目所给的公交线路信息数据，对每条线路进行抽象处理和分类。然后根据公众乘车的考虑因素：转乘次数、坐车时间和花费，确定目标函数，建立最优化模型确定任意两个站点之间的最佳路线。针对问题二：在问题一的基础上同时考虑地铁线路，可以将每个地铁站点相邻的汽车站点等效为同一站点，将地铁路线等效为单向行驶的公交线路，等效为环型的公交线路，然后依照问题一中所建立的模型进行求解。针对问题三：在上述两个问题的基础上增加考虑步行时间，根据公交和地铁站点的实际分别情况，有时会出现步行小段距离再转车使得公众能够更加节省时间和转车的次数，研究在这样一种情况下的出行方案具有实际意义。4数据处理4.1 公交线路的抽象公交线路在抽象的公交网络中可以抽象成连接各结点的有向边。根据实际情况可以分为以下三类：1. 完全的双同线路公交车在这两个端点之间双向行车，两个方向上路线是相同的，经过同样的站点序列和街道序列，因而可以抽象成由一条双向边连接的各站点，如图1所示：ADECB图12. 单向环形线路这种线路的行车路线是单向环形的，可以抽象成一各单向的环，如图2所示：图23. 音体分路段是单行线的线路。根据实际情况这种线路可以抽象为部分路段时单向的，部分路段是双向的，如图3所示：AA4A3A2B图34.2 地铁线路的抽象我们将与地铁相邻的各个公交站点抽象为同一站点，如下图4所示：地铁站汽车站抽象站点图44.3 公交乘客出行心理调查结果分析在研究公交最优路径的算法时，首先要了解公交乘客出行时所考虑的因素，通过对公交乘客的出行心理、行为的调查研究来确定模型的优化目标和约束条件是必要的。根据1999年，南京市针对换乘次数、出行耗时和出行距离做了一个公交乘客出行心理调查。调查的统计结果，如图5所示。从图中可看出公交乘客在选择出行方案时考虑最多的是换乘次数最少，其次是考虑时间最短和距离最短。也就是说，换乘次数最少是绝大多数乘客都放在第一位考虑的，在换乘次数已经确定的情况下，由于乘客的偏好不一样，会出现偏向时间型和偏向金钱型两种类型的乘客。图55问题一的求解针对问题一，我们建立多目标优化模型。5.1多目标优化模型的建立5.1.1 目标函数的确定结合实际情况，以公众的需求因素来确定目标函数，换乘的次数是所用乘客都要考虑的问题，在换乘次数确定的情况下，由于不同的人的偏好不同，我们将乘客分为两种类型：偏向时间型、偏向金钱型，根据不同乘客的偏好确定不同的目标函数。目标一：换乘次数最少换乘的次数等于从起点到终点站所经过的总站点数减1，所以换乘次数最少的目标函数为：其中 ：目标二：行程的总时间最短行程的总时间包括两个方面：公汽在路上的行驶时间和公汽换乘公汽所花费的时间。（1） 公汽的行驶时间公汽的行驶时间为公汽经过的总站数乘以相邻公汽站的平均行驶时间，即为：（2） 公汽换乘公汽的时间由题设已知，公汽之间换乘平均耗时为，所以公汽之间换乘所用的时间为：（3） 综合可得行程的总时间最短的目标函数为：目标三：行程的总花费最少由题设可知公汽的票价分为单一票价和分段计价两种，而且站数多少的不同会导致票价上的差异，具体的情况如下所示：所以行程总花费最少的目标函数为：5.1.2 约束条件的确定考虑实际情况，换乘的次数应该有一个上限，否则不具有实际意义，即：5.1.3 综合可得，我们建立的多目标优化模型为： 5.2 问题一的求解5.2.1 换乘次数的确定（1）不换乘，即有直达车到达目的地我们设作为起点，作为终点。假设：，它表示经过站点的线路到所有的所有站点的集合若 ，则说明由起点到达终点由直达的公交车，即不需要转乘。（2）换乘一次若，说明需要转乘，求，即经过点的所有公交线路上的所有由到点的集合；，即经过所有点的所有公交线路上的所有由到点的集合，判断是否为空集，若，则返回交集中的每个站点，即为起始点和终站点的一次换乘站点，即此时需要换乘一次即可。（3） 换乘两次和两次以上AB若同时满足和，则至少需要换乘两次，若能够在和分别找出两个站点和，使得 ，形成如图4所示的线路图5则最终通过两次换乘到达目的地；若找不到和，则通过类似的寻找方法进行换乘。5.2.2 算法步骤Step 1：输入乘车的起始站A和终点站B；Step 2：搜索所有的线路，设经过起始站点的A的线路的集合为L(A)，经过终点站B的线路集合为L(B)；Step 3：判断L(A)与L(B)是否有交集L(AB)，若有，说明A、B之间有直达线路，输出结果并计算出所花费的时间和所用的花费，否则进行Step 4；Step 4：搜索各线路的站点，设经过起始站点A的所有公交线路中在A之后的站点的集合为S(A)，经过目的站点的所有公交线路中在B之前的站点的集合为S(B)；Step 5：判断S(A)和S(B)是否有交集S(AB)，若有，说明站点A到B可以通过一次转车到达，交集中的点即为转车的站点，输出结果并分别计算出所花费的时间和所用的花费，否则进行Step 6；Step 6：分别搜索S(A)和S(B)中的站点，类似Step 2中的方式寻找两集合中是否有直达的两站点，若有说明站点A、B可以通过两次转车到达，其中即为转车的站点，输出结果并分别计算出所花费的时间和所用的花费，否则进行Step 7；Step 7：分别搜索S(A)和S(B)中的站点，寻找两集合中是否有通过一次转车到达的两站点，若有假设的转车站点为，说明站点A、B可以通过三次转车到达，其中即为转车站点，输出结果并分别计算出所花费的时间和所用的花费，否则进行Step 8；Step 8：在不大于上界Q次转车的情况下找到可行的路径，输出结果并分别计算出所花费的时间和所用的花费。5.2.3 寻找最佳线路利用MATLAB软件找出起始站到终点站的所有路线集合，对任意的求其所花费的时间和费用，进行比较，分别找出所用时间和所用花费最少的线路，即为最佳线路。最终通过上述算法我们得到的出行方案如下所示：表5.1 S3359到S1828部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用1104L436S1784L16731104L436S1784L2173267L484S3697L485S1784L1673267L324S2027L485S1784L2173表5.2 S1557到S0481部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用2109L363S1919L189S3186L46032115L84S1919L417S2424L2543表5.3 S1557到S0481部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用1131L13S2184L417_32109L13S1609L140S2654L4963表5.4 S0008到S0073部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用186L355S2263L345_2270L198S1691L290S2184L3453表5.5 S0148到S0485部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用2112L308S36L156S2482L41732109L308S3604L129S1381L4693表5.6 S0087到S3676部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用168L454S3496L2092249L21S88L231S427L972表5.7 六条路线的最优乘车方法转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用(1)267L484S3697L485S1784L1673(2)2109L363S1919L189S3186L4603(3)2109L13S1609L140S2654L4963(4)270L198S1691L290S2184L3453(5)2109L308S3604L129S1381L4693(6)249L21S88L231S427L9725.3 问题一的结果分析分析上面表5.1到表5.6中从转乘次数，所花费的总时间和总费用对出行线路进行了一个刻画。乘客可以根据自身的偏好选取合适的线路，偏好时间型的乘客可以选取花费时间最短的线路，偏好金钱的乘客可以选取总费用最短的线路。例如如S3359到S1828出行方案，发现转乘一次与转乘两次的花费相同，而转乘一次的时间为104分钟，转乘两次的时间为67分钟，故建议乘客乘坐转乘两次的路线。例如S1557到S0481出行方案，发现所有线路的转乘次数都为两次，乘车的花费也都相等，在这种情况下，我们建议乘客选取时间最短的线路作为最佳线路。最后我们得出最优的乘车路线且对于偏好金钱型与偏好时间型结果都相同。如表5.7所示。6问题二的求解6.1 模型的建立问题二与问题一类似，在问题一的基础上增加考虑了地铁线路，我们将与地铁相邻的各个公交站点抽象为同一个站点，将两条地铁线路和分别抽象为一条单向的和一条环形的公交线路，而由题设可知，地铁之间换乘的耗时和费用都会发生改变，在这种情况下，相对于问题一的多目标优化模型，其目标函数会发生相应的改变。6.1.1 目标函数的确定目标一：换乘次数最少在问题一的基础上引入了抽象站点，所以换乘的总次数最少的目标函数为：其中 ： 目标二：行程的总时间最短行程的总时间包括两个方面：公汽和地铁在路上的行驶时间和公汽、地铁之间相互换乘所花费的时间。（1） 公汽和地铁的行驶时间由题设已知，公汽行驶的时间为公汽在行驶过程中经过的站点总数乘以相邻公汽站的平均行驶时间，地铁行驶的时间为地铁在行驶过程中经过的站点总数乘以相邻地铁站的平均行驶时间，即为：（2） 公汽换乘公汽的时间由题设已知，公汽之间换乘平均耗时为，所以公汽之间换乘所用的时间为：（3） 地铁换乘地铁的时间由题设已知，地铁之间换乘平均耗时为，所以地铁之间换乘所用的时间为：（4） 公汽换乘地铁的时间由题设已知，公汽换乘地铁的平均耗时为，所以公汽换乘地铁的所用的时间为：（5） 地铁换乘公汽的时间由题设已知，地铁换乘公汽的平均耗时为，所以地铁换乘公汽的所用的时间为：（6） 综合可得行程的总时间最短的目标函数为：目标三：行程的总花费最少由题设可知公汽的票价分为单一票价和分段计价两种，而且站数多少的不同会导致票价上的差异，地铁票价是确定的，具体的情况如下所示：乘坐公汽的总花费为：其中：乘坐地铁的总花费为:汽车换乘地铁时，需要购票一张，而地铁之间的换乘无需购票，所以乘坐地铁的总花费为：综上可得行程总花费最少的目标函数为：6.1.2 约束条件的确定与问题一类似，以换乘次数的上限作为约束条件，即：6.1.3 综上所述，我们建立的多目标优化模型为： 6.2 问题二的求解与问题一中模型的算法一样，我们利用matlab软件进行求解，对题中所给的六条线路的出行方案进行列表说明，如下所示：表6.1 S3359到S1828部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用1104L436S1784L16731104L436S1784L2173267L484S3697L485S1784L1673267L324S2027L485S1784L2173表6.2 S1557到S0481部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用2109L84D20L189S3186L46032109L363D20L189S3186L4603表6.3 S1557到S0481部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用1131L13S2184L417_3299L94D1T1D21L515表6.4 S0008到S0073部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用183L159D13L474_2258L150D30T2D25L1035表6.5 S0148到S0485部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用290.5L24D2T1D21L5152109L308S36L156S2210L4173表6.6 S0087到S3676部分出行方案列表转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用030T33033L2311表6.7 偏好金钱的乘客的最佳乘车方案转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用267L484S3697L485S1784L16732109L84D20L189S3186L46031131L13S2184L417_3183L159D13L474_22109L308S36L156S2210L4173033L2311表6.8 偏好时间的乘客的最佳乘车方案转乘总时间车辆1转乘点1车辆2转乘点2车辆3总费用267L484S3697L485S1784L16732109L84D20L189S3186L4603299L94D1T1D21L515258L150D30T2D25L1035290.5L24D2T1D21L515030T336.3 问题二的结果分析通过对表6.1到表6.6进行分析，我们发现在引入了地铁以后所花费的总时间都会减少，对于偏向时间的乘客而言，选择乘坐地铁能够更满足他们的要求。但是我们也发现，绝大多数路线的花费都增加了，对于偏向金钱的顾客而言，选择乘坐地铁线路不符合他们的心理，所以对于偏向金钱的乘客而言，不要乘坐包含地铁的线路。最后我们我们根据不同乘客的不同喜好得出对于不同喜好乘客的最佳乘坐路线，即为表6.7和表6.8的结果。7问题三的求解7.1 模型的建立问题三与问题二类似，在问题二中，地铁站为其所在线路周围各个站点提供了一个中转连接的作用，而问题三中所给的步行这样一种方式与地铁站有着同样的。根据实际情况，步行时间存在一个上限，以乘客所在的站点为中心，以步行时间的上限为半径，找出在我们所限定范围内的所有站点，将这些站点抽象为一个特殊的站点，与问题二中地铁与其临近站点所形成的抽象站点类似，我们用下图进行抽象的刻画：步行抽象站点车站 7.1.1 目标函数的确定目标一：换乘次数最少在问题一的基础上引入了抽象站点，所以换乘的总次数最少的目标函数为：其中 ： 目标二：行程的总时间最短行程的总时间包括两个方面：公汽和地铁在路上的行驶时间和公汽、地铁之间相互换乘所花费的时间。（1） 公汽和地铁的行驶时间由题设已知，公汽行驶的时间为公汽在行驶过程中经过的站点总数乘以相邻公汽站的平均行驶时间，地铁行驶的时间为地铁在行驶过程中经过的站点总数乘以相邻地铁站的平均行驶时间，即为：（2） 公汽换乘公汽的时间由题设已知，公汽之间换乘平均耗时为，所以公汽之间换乘所用的时间为：（3） 地铁换乘地铁的时间由题设已知，地铁之间换乘平均耗时为，所以地铁之间换乘所用的时间为：（4） 公汽换乘地铁的时间由题设已知，公汽换乘地铁的平均耗时为，所以公汽换乘地铁的所用的时间为：（5） 地铁换乘公汽的时间由题设已知，地铁换乘公汽的平均耗时为，所以地铁换乘公汽的所用的时间为：（6） 步行时间步行的总时间应该等于相邻两站之间步行的平均时间乘以步行的站数，即为：（7） 综合可得行程的总时间最短的目标函数为：目标三：行程的总花费最少与问题二中的类似，行程的总花费最少的目标函数为：7.1.2 约束条件的确定（1） 换乘次数的上限与问题二类似，以换乘次数的上限的约束条件为：（2） 步行时间的上限根据现实生活，每个人的步行的时间有个上限，我们设为，所以步行时间为上限的约束条件为：7.1.3 综上所述，我们建立的多目标优化模型为： 7.2 问题三的求解我们将线路1与线路6代入模型检验有以下结果：转乘总时间车辆1转乘点1车辆2转乘点2车辆3步行总费用线路1199L436S1784L1671站2线路6267L324S2027L485S1784L217037.3 问题三结果的分析通过结果与问题一和问题二中结果的比较，发现步行确实能够在一定范围内乘车的总时间和乘车费用，与实际生活的要求相符合。8.模型的评价和推广8.1 模型的评价：优点：（1）模型对题中所给的数据进行了有效的处理，并根据要求得到了满意的结果。（2）模型提出了合理的假设使得问题的解决更加符合现实中的公交线路乘车问题。（3）模型提供的算法代码具有一定的人性化查询效果，对时间和花费的分别考虑能够满足不同顾客的需求，具有一定的现实应用性。（4）模型利用合理的假设将满足条件的车站转化为抽象车站，使得原本复杂的问题简单化，减少了问题的复杂性。缺点：（1）题中的公路网络中的站点过多，本文提供的模型在解决的过程中时间复杂度较大。（2）文中仅分别考虑时间偏好度的顾客和金钱偏好度的乘客，没有估计到现实中可能存在的更加复杂的需求的顾客。（3）由于信息量的不足没有考虑到现实的生活中乘客更多的要求，例如对观光线路的需求8.2 模型的推广本模型不仅可以由于公交线路的选择，还可以用于旅游观光线路的选择，推销员推销线路的选项，电路的铺设等实际经济和工程问题。参考文献1薛定宇，陈阳泉，高等应用数学问题的MATLAB求解，北京：清华大学出版社，2008年10月第2版2董霖，MATLAB使用详解，北京：科学出版社，2008年8月第1版3王丽，李文权，公共交通系统最佳路径算法，东南大学学报，第34卷：第三期，2004年3月4苏爱华，施法中，公交网络换成问题的一种实现，工程图学学报，2005年第4期附录clear all %5201000 up_line=zeros(520,100);% down_line=zeros(520,100);% % fid=fopen(d:1.12 .txt,r);% line_num=1; while line_num=0 & A(1,1)0&up_line(i,col)0&up_line(i,col-1)3958&up_line(i,col)0&down_line(i,col)0&down_line(i,col-1)3958&down_line(i,col)0 t=t+1; end end re(1,i)=t;endmax=1;t=1;for i=1:3957 if re(1,i)9 i; t=t+1; endendtmaxre_dec=zeros(3957,max);%max=16for i=1:3957 tt=1; for j=1:3957 k=relation_matrix(i,j); if k0 re_dec(i,tt)=j; tt=tt+1; end endendfid=fopen(d:line.m,w);A1=zeros(1,15);A2=zeros(1,15);A3=zeros(1,15);A4=zeros(1,15);disp(-);disp();begin_s=input();%,:0end_s=input();%tt=1;for i=1:520 for j=1:100if up_line(i,j)=begin_s fprintf(fid,%d ,i); A1(tt)=i; tt=tt+1;end endendfprintf(fid,n)