2007优秀的数学建模论文 最佳路径选择方案的优化模型.doc

最佳路径选择方案的优化模型摘 要：本文对乘公交、看奥运这一实际问题进行了深入的研究，首先对公交乘客进行了心理分析，得出影响乘客出行的三个主要因素分别为：换乘次数、出行时间、出行费用，通过调查研究，得出换乘次数最少是乘客出行考虑的最主要因素，其次是出行时间和出行费用。然后利用公交乘客的出行过程抽象为站点线路的交替转换的思想，建立了站点线路序列模型，从而确定了出行者对路线的所有选择方案。针对问题一：仅考虑公汽的情况下，以换乘次数最少为第一目标、出行时间为第二目标建立了优化模型一，再以换乘次数最少为第一目标、出行费用为第二目标建立了优化模型二，从而满足了两类不同乘客的需求。并依靠站点线路序列模型采用图论中计算方法，分别得到了公交乘客的最少换乘次数，所经过的站点，出行时间、出行费用以及相应的算法。针对问题二：在问题一的基础上再考虑地铁线路，建立了对应的两组优化模型，并推导出相应的改进算法。针对问题三：在问题一、二的基础上，考虑出行者可以通过步行到达相邻的公交站点的情况，同样建立了两组相应的优化模型，并给出了相应的计算方法。然后利用基于换乘次数最少的最优路径改进算法思想，借助MATLAB软件编程分别对问题一和二进行了求解，得到的结果见模型的求解（正文第21、22页）。最后对所求得的结果进行了对比分析和检验，根据各参数的变化关系，进行了灵敏性分析，本模型主要抓住了乘客的心理需求，实用性强，具有较强的现实意义。关键词：站点线路序列 最优路径改进算法 公交一、问题的提出1.1基本情况我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择（包括不同线路上的换乘交通工具的路径选择等）问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。1.2基本参数设定：1）相邻公汽站平均行驶时间(包括停站时间)： 3分钟；2）相邻地铁站平均行驶时间(包括停站时间)：2.5分钟；3）公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)；4）地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；5）地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)；6）公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；7）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元； 2140站：2元； 40站以上：3元。地铁票价：3元（无论地铁线路间是否换乘）。注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。1.3相关信息（详见附件）【附件1】公汽和地铁线路信息数据文件格式说明；【附件1.1】公汽线路及相关信息；【附件1.2】地铁线路及相关信息；【附件2】地铁换乘公汽信息数据文件格式说明；【附件2.1】地铁T1线换乘公汽信息；【附件2.2】地铁T2线换乘公汽信息。1.4需解决的问题为了设计这样一个公交线路选择的自助查询计算机系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，以满足查询者的各种不同需求。进而需要解决如下问题：问题一、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附件中的相关数据，利用所得到的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676问题二、同时考虑公汽与地铁线路，解决以上问题。问题三、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、基本假设2.1出行者对公交线路的选择是理性的且能够顺利正常的到达目的地。2.2出行者在所经过的站点中，不允许两次经过相同的站点。2.3公交与地铁换乘距离固定，换乘步行时间为常数。2.4同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费。2.5出行者换乘时，不受人群拥挤、交通堵塞等现象的影响且均能乘到相应线路的公汽或地铁。2.6出行者换乘交通工具时的平均耗时包括出行者到站的等待时间和换乘的步行时间；2.7公汽线路上的单一制票价为1元，分段计价的票价为：020个站：1元；2140站：2元；40站以上：3元；地铁票价：3元（无论地铁线路间是否换乘）。2.8附件所给数据准确无误。（注：本文中针对相应问题的假设将在后文中陆续给出）三、问题分析与模型建立观看2008年8月在北京举行的奥运会是我国人民翘首企盼的盛事，届时将会有大量的观众需要到现场观看奥运比赛，公交也将成为主要的交通工具，因此观看比赛的首要问题应当是解决每位观众如何去的路线问题。本文需要设计乘客对路线的选择方案，在探讨选择公交线路的数学模型和最优路径算法时，有必要先了解公交乘客出行时所考虑的因素，通过对公交乘客出行心理、行为的研究来确定模型的优化目标和约束条件。3.1对公交乘客的心理研究通常乘客出行时，主要考虑以下几个主要因素1：“换乘次数”、“出行经历的总站数”、“出行耗时”、“出行费用”、“存在的步行时间”等。就乘客本身而言，公交乘客出行更多考虑的是出行的方便性和舒适性，下面就影响公交乘客出行的各因素进行具体分析，不妨将以上影响因素作如下归纳解释：(1)换乘次数：出行者完成一次从出发点到终点出行过程中所换车的次数。(2)出行经历的总站数：由起点到终点所经历的站点总数。(3)出行耗时：出行者在一次乘公交出行过程中所用的总时间。(4)出行费用：出行者在完成一次由起点到达目的地过程中所花的车费。(5)存在的步行时间：出行者由起点到终点所有步行时间的总和。从实际生活可知，上述几个因素是相互关联，相互影响的，因此影响乘客出行的因素可以通过对比后进行简化。比如“换乘次数”与“出行费用”和“存在的步行时间”都具有一定的正相关性，一般说来，当乘客的换乘次数越多，出行费用将更高，通过换乘而步行的时间也就越多，这在单一的公汽票价上最容易体现与费用的相关性；“出行经历的总站数”与“出行耗时”也具有一定的正相关性，尤其是不需要经过换乘就能到达的目的地。而“换乘次数”与“出行经历的总站数”在一般情况下，将不会存在绝对的相关性。因此，可认为“换乘次数”和“出行耗时”是影响出行者的两个独立的因素，经研究表明多数的公交乘客希望换乘次数最少，况且公交公司对公交线路的设计也是尽量减少乘客的平均换乘次数2；而且公交乘客出行时还受到行李、地理位置等客观因素的影响，这样更不希望有较多的换乘。其次对于看奥运非常心切的出行者来讲，出行耗时对他们也许是比较关键的。在此当给出供乘客选择的公交路线也应当尽可能的满足公交乘客的需求，那么什么样的出行路线又是出行者最需要的呢？这除了对个别的公交乘客进行心理分析得到不同的需求结果之外，还应当使得众多的公交乘客在选择上得到满意，为权衡这两方面的独立因素，有必要对看奥运的公交乘客进行心理调查，介于竞赛期间的时间关系本文对出行看奥运的出行者的心理调查就不作单独的深入研究，现参考在南京市做的一个公交乘客出行心里调查统计结果1，该调查主要对3个因素做了统计：换成次数，出行距离，出行耗时。其记录结果如下图（图3-2）所示：图3-2 公交乘客出行心理分析图从图中统计的心理分析结果可以看出，有的出行者在选择出行路径时，首先考虑的是换乘次数最少，其次考虑的是时间最短。在实际生活中，出行者往往受到行李、地理位置、天气等诸多因素的影响，选择最少换乘次数的公交路线往往能最大限度地解决某些因出行带来的麻烦，并且从一条线路换乘到另一条线路是费时又费力的，这也是大多数公交乘客希望换乘最少而与实际生活调查相吻合的主要原因。因此公交乘客在选择最优路线时应当是以换乘次数最少为第一目标。另外，对于一个以出行看奥运为目的的出行者来说，达到目的地的出行总费用远不足以作为主要因素。并且出行费用受换乘次数的影响较显著，当不考虑地铁、较多站数的分段计价线路的公汽是不会有多大影响的，因此这不比作为主要目标加以考虑。综上所述，可以以换乘次数最少为第一目标，以选择乘车所用时间最少为第二目标建立相应的线路选择的优化模型。但对这些目标函数和约束条件的具体考证和检验还需要进一步挖掘附件中的相关信息。3.2分析附件中的主要相关信息3.2.1直观统计结果作为需要乘坐公交工具去看奥运的行者来说，了解乘车路线的相关信息同样是最重要的；由EXCEL软件统计【附件1.1】和【附件1.2】中的公交线路系统数据，得到如下信息：（1） 该公交系统共有公汽线路520条。其中票价信息为分段计价的线路283条，单一票制1元的线路237条；上下行路径不同的线路409条，上下行路径相同的线路89条，环行线路22条。（2） 该公交系统共有公汽站点3957个。（3） 该公交系统共有地铁线路2条。其中直行线路1条，环行线路1条；（4） 该公交系统共有地铁站点39个。3.2.2信息处理对于上述统计的直观信息，结合本文1.2节基本参数设定中的票价信息，结合上述第（1）条统计结果中的分段计价线路进行综合考虑，可得：在分段计价路线中，共有27条的公汽站点数不超过20，有148条的公汽站点数在2140之间，公汽站点数超过40的线路有108条。因此，从单独的计算角度来考虑，可以将分段计价中站数不超过20的线路归为单一票制1元的线路，因此上述信息（1）可修正为：票价信息为单一票制1元的线路264条；在分段计价的路线中，共有256条，其中有148条的公汽站点数在2140之间，公汽站点数超过40的线路有108条。从上述处理结果可以看到，在公汽的运行系统中“出行费用”的增长将胜过换乘次数的增长，其原因是出行者在乘坐分段计价的公汽线路时，将可能被多耗费用，所以将费用计算出来共乘客参考也是有必要的。为给出行者提供乘车路程，考虑到22条环行路线中，存在一定数量的单一票价制线路，因此还需要计算出所经历的相应站点总数。同样，当条件对步行时间给予强调时，步行时间应是为不便于步行的公交乘客所参考的。为进一步简化问题，同时也便于统一变量所表示的含义。不妨对附件中的相关信息进行如下符号约定：公汽站点:；表示出行者选择第条公交线路所经过的第个站点。公汽站点集:公汽线路:；表示出行者选择第条公交线路所乘坐的第辆公交工具。公汽线路集:地铁站点:；表示出行者选择第条公交线路所经过的第个站点。地铁站点集:地铁线路:；表示出行者选择第条公交线路所乘坐的第辆公交工具。地铁线路集:从上述信息可知，分析公交乘客的心理而得到出行者对路线选择目标的重要性是至关重要的，但还不能完全解决此类问题。可见要直接建立一个全面的，能快速选择任意两站点之间最优乘车路线的模型是比较困难的。同时就是能得到具体的出行线路，也还必须依赖于具体的公交行车路线和大范围的公交站点。根据解决问题的时应当采取化繁为简，先易后难的原则，本文在此不妨对所研究的问题进行重难点分析以得到相应的建模思路。3.3重点、难点分析与建模思路首先，对公交系统中乘客给出的任意一对起始站终到站，如何确定其最优乘车方案是本文讨论的中心。所谓乘车方案即可看着是一个站点、线路的交替序列1，该序列说明从起点出发乘坐何种路线，途中如何换乘，直至到达终到站。因此，从前文的分析可以看出，建立站点、线路的交替序列1模型是分析公交线路选择问题的关键和出发点，也是本文所有问题讨论的基础。其次，在站点上放置一个便于乘客查询到达目的地的理想乘车方案的计算机系统，必须让计算机收集到本站到其他任意一站的路径与换乘信息，因此单独设计这样的算法是相当困难的，而且算法的精度要求也比较高。对本文附件中的公交系统中所列的3957个公汽站点和39个地铁站点来说，直接要得到所有任意两站点之间的最优公交路径的计算量是相当大的。当面对这样一个密集的交通网络来说，对路线的选择主要是将面临一个类问题4，根据类问题的处理特点，可以用某种主次改进的方法来求解。由于每次改进中的计算量都是多项式界的，改进的次数也是多项式界的。目前已找到具有这种特性的算法，如椭球算法，卡马卡算法，但都相当复杂。因此要满足出行者的路线需求，则有必要对目标进行归类筛选，以降低不必要的选择、计算与搜索。不妨采用改进的广度优先搜索算法，基于改进次数为多项式界的算法理论，本文选择从某次乘公交的起点和终点的两端进行同时搜索，在满足换乘次数最少的条件下寻找不同线路中的共同站点或不同站点之间的相同线路，并计算其总路线的中的乘车时间和站点数。3.4预备知识据问题提出的相关信息可知，本文所要解决的根本问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑，以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。由附件中的统计信息可以知道，任意一个公交站点都不是孤立的，即连接任意两公交站点之间的公交路径都是存在的。当然这样的路径可能只有一条，也可能有多条，不妨记出行者所选择出行的起始站为，终到站为，从到的所有路径的集合也不妨记为，其中第条路径为。进一步分析和考虑出行者乘公交的具体情况，一个出行者的出行可简单描述为如下路径（图3-1）：起始站中转站1乘第1节公交离开公交结束选乘初次车出发中转站2中转站3选择路线乘第2节公交第1次换乘终到站乘第3节公交第2次换乘中转站Ni乘第Ni+1节公交第Ni次换乘图3-1 出行者选乘公交路径规律分析示意图注：图中表示某出行者的换乘次数从图中内容也可以反应，出行者出行乘公交的路径可看着是站点、车次、站点、车次的交替进行，直至到达终到站。为区别前后的车次或站点，使得前后排列的站点与车次都有一定的顺序，不妨设出行者选择第条路径时，所乘坐的第节公交工具为，第个换乘站点（中转站）记为，由于出行者不能在同一站点上出现两次，即各不相同，特别地令，；于是可以得到从到的所有路径集中的第条路径为：因此将所有路径集在一起，可得：由此而来，对任何一个出行者来说，只要知道他的出行起始站和终到站之后，便可以在路径集中找到他最需要的出行路线，据此可以得到站点线路交替序列的一般模型。3.4.1站点线路交替序列模型通过前文的逐步分析，设出行者仅通过公汽及换乘从起始点到达终到点，出行者选择第条线路上的第次乘车的公交线为，经过的第个站点为，则该条选择线路上的站点线路交替序列为：其中站点线路交替序列表示从起始点选择线路，换乘到达，最终到达的第种路径。不妨将所有的站点线路交替序列集在一起，可得到相应的从起始站到达终到站的公交线路选择集，即：可见本模型对路线的选择范围确定了界限，这样也明确了寻求最优线路的讨论范围，即搜索的路径（公交线路）和节点（公交站点）都是相互关联的。3.4.2多目标优化函数的提出通过前文对公交乘客的心理分析，已经得到设计出以换乘次数最少为第一目标，以出行时间最短为第二目标所建立的数学模型是比较合理的，因此这需要提出一个针对该种情况下的多目标函数。设出行者选择第条路线时的换乘次数为；出行者选择第条路线时所消耗的总时间为；则在有序约束集中，选择在满足换乘次数最少的情况下的出行时间最短的目标函数为：在这里，是指一个目标优先的二元目标函数集，即首先满足达到目标后，再使得达到目标的最优方案集。相应地，表示出行者选择第条路线时的有序路径集当然对所得的目标函数还必须赋予一定的函数性质，否则该目标函数将不会有任何实际意义。根据以上分析，可知应当满足：同理，可将上述原理作一般性推广，如当需要建立以换乘次数最少为第一目标，出行所消耗的时间为第二目标，所支付的公交费用为第三目标时的目标函数，可表示为：其中，表示出行者选择第条公交线路从起始站到达终到站所应当支付的所有费用。注：在本文中，后面所用到的上述目标优化函数，不作特别说明，都默认为分别具有相应的函数性质。3.5针对问题一的分析与建模在问题一中，要求仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型。根据前文对公交乘客的出行心理分析，以选择换乘次数最少为第一目标，以选择乘车所用时间最少为第二目标可得到相应的目标函数，而具体的约束条件则需要另外求得。对于换乘次数，联系被选择线路上的站点线路交替序列的元素个数可以表示出来；站点总数则采用给同一线路上的站点排序的方法也可以求到，由于只考虑了公汽之间的换乘，则出行时间只与换乘次数和所历站数有关；对于出行费用则在换乘次数的基础上，引入分段计价的加价函数也可求得。3.5.1模型1：公汽路线选择的通用模型在问题的分析中，我们已经初步地得到了寻求线路最优的双目标函数选择的优化模型，现归纳如下：目标函数：若以换乘次数最少为第一目标，以选择乘车所用时间最少为第二目标可得总体的目标函数，约束条件：（1）当选择总目标取最小时，而换乘次数和乘车所用时间也都同样在要求最少，因此与是正相关的；即，（2）同样与也是正相关的，即：（3）由于在优先选择权上，按相应条件，在目标函数中，应优于，即：；很明显，上述优化函数满足多目标优化的条件，因此可转化为多目标求解。单由上述模型提供的总目标选择，还不能全面地选择出相应的全程公交线路；因此，需要进一步对目标函数中的相关子目标进行细化和计算。同时考虑该最优目标下的约束条件应是强约束的，而出行者所乘坐公交时的换乘次数与出行者乘公交所用时间不存在明显的相关性，因此这需要将两方面进行独立考虑，根据前文的分析与叙述已经知道，需要在满足取最小值时，再进行其它变量的确定与计算，才能选择到相应的目标。即需要在可行域中进行优先性的条件搜索。（1）换乘次数不妨设表示有序集中的元素的个数，为便于区别，现标记，于是换乘次数的计算公式可简单归纳为：（2）所通过的总站数设非环行线路上的两个站点和在沿着公交工具行进方向上的站数按照正整数从小到大的排序分别为和，其中仍然记；，于是由附件中的相关统计结果可知：当线路为环行线路时，设该环行路线上的总站数为，为上的任意一站，分别为公交工具在沿着行进方向上的最后一站和前一站，于是可标记；所以出行者乘坐线路的公交所经过的站点数目为：所以，出行者途经的总站数为共条行车路线上车站数的总和，即（3）出行者所用时间由于在只有公汽交通的线路中，仅存在公汽线路之间的换乘消耗时间和在公汽上的运行时间，于是由问题中的参数设定可以得到：相邻公汽站平均行驶时间(包括停站时间)： 3分钟；公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)；不妨设出行者选择第条线路从起始站到达终到站所耗的平均总时间为，换乘一次所耗的平均时间为=5分钟，相邻两站点之间乘车的平均时间为=3分钟。则有（4）乘车总费用由问题中的参数设定容易知道，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响，在附件统计信息已经得到，公汽线路上的单一制票价为1元，分段计价的票价标准为出行者通过本线路020个站：1元；2140站：2元；40站以上：3元。不妨令公汽的单一票价为，出行者在所选择的出行线路中所应支付的车旅费为，所乘同一公交线路上的最高收费为，分段计价时加价的最少站数为，于是有：其中表示取不超过的最大整数，参数：（元），（元），.综上所述，根据不同目标因素的优先性可建立不同的线路选择方案模型；当然针对不同的出行者的选择要求，将会有更多的选择方案的模型，但是无论优选目标顺序如何变化，它们的基本约束条件都是相同的，不妨记问题一中的约束条件集为，则有：（1）以换乘次数最少为第一目标，乘车所用时间最少为第二目标所建立的模型为：（2）以换乘次数最少为第一目标，乘车总费用最少为第二目标所建立的模型为：其中，基本约束条件集为：为了使出行者在乘坐公交的过程中，达到最少换乘次数，而只与出行者在某一公交体系中的初始站、终到站、公交线路、公交站点有关。因此可以考虑以换乘次数从小到大的排除选优搜索法进行求解计算。3.5针对问题二的分析与建模考虑地铁与公汽并行时的公交系统时，出行者的选择将变得更加灵活，其主要变化的因素有：（1）地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少。（2）地铁与公汽之间进行换乘时，由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多，而且位于与地铁换乘的公汽站点还可以通过本地铁站进行免费耗时换乘到下一个公汽站。综上所述，不妨将跨公交站的步行也同样看着是一条步行公交线路，不过该条公交线路具有免费耗时的特点。同问题一中的解决方案可建立相应的数学模型。3.5.1地铁公汽型公交线路选择模型当并入地铁公汽的交通网络时，增加地铁站与其周围的公汽站之间的步行线连接转换后，本问题可转化为问题一中的模型求解，同样有出行者通过公汽换乘、地铁换乘、公汽与地铁之间的换乘后从起始站到达终到站的可行路径集为：其中的属性将被扩大，它将表示公汽、地铁、步行这三类交通路线中的某一类交通路线；而的含义与问题一中的含义相同，仍表示公交站点或地铁站点。（1）换乘次数与途经总站数同样设路径的换乘次数为途经总站数为，同问题一对，仍然有：（2）出行者乘公交所用时间在地铁公汽的公交系统中，出行者将会表现在公汽运行耗时，地铁运行耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时。为简化变量，考虑出行者的异站步行也纳入到公交线的行列中，则所消耗的时间可归结为：交通工具运行耗时，交通线路换乘耗时两类。根据基本参数设定的类型，不妨设出行者从起始站到达终到站所用的总时间为，从公交站点乘线路公交工具到达公交站点所消耗的时间（包括相邻两站点间的停站时间）为：，由线路的公交工具换乘到线路的公交工具所消耗的时间为： ，由基本参数设定的信息可得：其中（3）乘车总费用在问题二的讨论中，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响，而在本问题中，有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，同样根据问题一中，对乘公交所支付费用的讨论思想，仍然令乘坐公汽的单一票价为，出行者在所选择的出行线路中所应支付的车旅费为，所乘同一公交线路上的最高收费（含地铁收费）为，分段计价时加价的最少站数为，于是有：其中表示取不超过的最大整数；参数：（元），（元），.综上所述，同样采用问题一中对目标函数和约束条件的处理，仍然根据不同目标因素的优先性可建立不同的线路选择方案模型；它们仍具有相同的约束条件集，不妨记问题二中的约束条件集为，则（1）以换乘次数最少为第一目标，乘车所用时间最少为第二目标所建立的模型为：（2）以换乘次数最少为第一目标，乘车总费用最少为第二目标所建立的模型为：其中，上述模型中的基本约束条件为：3.6针对问题三的分析与建模考虑到出行者在步行时，所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过，由问题三的条件可知，步行时所经过的两站点之间的步行时间是一个已知值。据实际情况，假设步行者步行在相邻两公汽站所用时间平均是公汽经过这两站（包括停站时间）所用时间的倍，则由基本参数设定可知，步行者通过这样两站点所用的平均时间为分钟，于是将行人步行所经过的线路也纳入到公交线路中，其特点是费时费力但选择灵活，路途捷近。3.6.1步行地铁公汽型公交线路选择模型设出行者以步行、乘公交、换乘等任意的出行方式从初始站到达终到站的可行路径集为：，其中，上式中的、都与问题二中、的含义分别相同，（1）换乘次数、途经总站数设该路径的换乘次数为途经总站数为，仍然有（2）出行者乘公交所用时间在步行地铁公汽的公交系统中，出行者将会出现公汽运行耗时，地铁运行耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时，公交站点之间的步行耗时。同样考虑出行者的异站步行纳入到公交线的行列中来简化变量，则所耗时间仍然可分为：交通工具运行耗时（包括步行耗时），交通线路换乘耗时两类。同样设出行者从起始站到达终到站所用的总时间为，从公交站点乘线路公交工具到达公交站点所消耗的时间（包括相邻两站点间的停站时间）为：，由线路的公交工具换乘到线路的公交工具所消耗的时间为： ，则由基本参数设定的信息可得：其中为公汽行进时是出行者步行时的平均倍率。（3）乘车总费用在问题三的讨论中，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响，而在本问题中，有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，步行的出行者在步行的公交站点线路上也不需要支付公交费用，同样由问题一中对乘公交所支付的费用的讨论思想，同样令乘坐公汽的单一票价为，出行者在所选择的出行线路中所应支付的车旅费为，所乘同一公交线路上的最高收费（含地铁收费）为，分段计价时加价的最少站数为，于是有：其中表示取不超过的最大整数，在本题中；综上所述，同样采用问题一中对目标函数和约束条件的处理，仍然根据不同目标因素的优先性可建立不同的线路选择方案模型；但是无论优选目标顺序如何变化，它们的基本约束条件仍然是相同的，因此设问题三中的约束条件集为，则（1）以换乘次数最少为第一目标，乘车所用时间最少为第二目标所建立的模型为：（2）以换乘次数最少为第一目标，乘车总费用最少为第二目标所建立的模型为：其中，基本约束条件集为：从上面的模型可以看出，要得到公交乘客的具体乘车路线，还必须对上述三个问题的模型进行求解，其中在可行域中可根据目标函数的优先性，对进行有目的的搜索和筛选，方可得到解答，计算详细步骤及算法思想见模型求解。四、模型求解4.1.基于换乘次数最少的最优路径搜索改进算法54.1.1换乘方案的选择：根据人们的出行习惯6，在选择从A站到B站的行车路线时，首先考虑是否有经过A站直接到达B站的车，如果有，马上会选择直达车（如图4-1（a），如果存在不只一条的直达线路，在考虑所走路线的远近，选择距离最近的乘车方案；如果没有直达车，就会考虑换一次车的方案：即经过A站的车与经过B站的车是否有公共站点C。如果有，则可在公共站点C处转车到达站点B（如图4-1（b）；如果没有换一次车的方案，则又要考虑乘坐经过A点的车到某一站C下车，经过C站点的车与经过B站点的车是否有公共站点D，如果有，就到公共站点D转车，两次转车可到达站点B（如图4-1（c）；如果没有，则需要转乘三次或三次以上才可到达目的地（如图4-1（d）。在上述情况中如果存在不止一种的选择方案，则在考虑乘车距离，选择路程最短的乘车方案。(d)换乘多次车的情况图4-1 公交线路换乘方案示意图(a)直达的情况(b)换乘一次车的情况ABCBA(c)换乘两次车的的情况ABCDABCD4.1.2.算法设计分析对上面换乘方案选择的分析，我们可以发现只有当不同线路之间具有公共站点时才能够进行转车，这样计算出来的结果有时并不符合实际情况，比如在实际出行时只需换乘两次便可到达目的地，但计算出来的结果缺需要换乘三次或四次。出现这种情况的愿意是忽视了现实生活中人们步行小段距离在转车的现象。具体地说，人们在转车时，并不是下车后直接在下车的站点处转车，往往需要步行一小段距离到附近的站点去转车。人们选择这种方式通常可以减少换乘次数，而且这种换车方式也是由站点的分布情况所决定的。参考文献7已详细分析了紧邻站点的分布情况。紧邻是一个半定量的距离概念，用以描述公交站点空间位置上的距离关系，通常是根据人们的行为习惯和平均公交路段长度来决定的。紧邻站点的存在使得人们在选择换乘路线时多了一个考虑方案，就是如果在某一站点下车后没有直接换乘的车次，还可以考虑附近的站点是否有换乘车次。根据这种思想，本文对上面的算法进行了改进，即在换乘时，加入对紧邻站点的判断和分析。这种算法更加符合站点的分布情况以及人们出行时的实际选择情况。从前面的公交乘客出行心里调查统计表可以看出，换乘次数最少是公交乘客出行时考虑的第一重要因素，所以就以换乘次数最少作为最优路径算法的第一约束目标，而出行耗时则是公交乘客考虑的第二重要因素，所以将其作为最优路径算法的第二约束目标。4.1.3.算法的设计思想及步骤（）算法的设计思想该算法的基本思想为5，分别从起点A、终点B出发，通过比较公交网络上各车站的可换乘车站，追索A到B的可能路径，然后比较各可能路径的换乘次数、所用的时间来确定最佳选择的路径。设表示乘客在换车时步行距离的最大心里承受值，它时一个人为干预的经验值，与公交站点间的平均时间成线性相关。对于站点与站点之间的紧邻关系，可以用一个不等式来表示：。根据参考文献9所提供的资料表明，在上海都市的公交网络上，换3次车即乘坐4条线路的公交车，方可到达目的地的情况都是很少发生的。所以根据北京市公交线路的实际情况，本文认为三次以内的转车是比较合理的，超过三次的转车情况在这里不予考虑。（）算法的设计步骤（1）输入乘车的起始站点及目的站点；（2）求经过站点A的所有线路集和经过站点B的所有线路集；（3）判断=吗？ 如果有，则找到了从站点到站点的直达线路即，输出结果，结束运算，如果没有则进行下一步。（4）求线路上的站点以及线路上的站点；（5）判断是否存在相同站点，即=，或者存在紧邻站点，即满足；如果满足=，则线路，即为一次转车的线路，即为转车站点且换车时不用更换站点；如果满足但满足，则线路，即为一次专车线路，即为转车站点但换车时要步行到紧邻站点。如果没有，再执行下面步骤。（6）求经过的线路集，经过的线路集；（7）判断=吗？如果有，则线路，为两次换车的线路，换车站点为和，输出结果，结束运算；如果没有则执行下面步骤。（8）求线路上的站点和线路上的站点；（9）判断是否存在相同站点，即=，或者存在相邻站点，即满足；如果满足=，则线路，即为三次转车的线路，即为转车站点，且换车时不用更换站点；如果满足但满足，则在站点专车时要步行到紧邻站点。 在上述情况中，满足条件的线路可能不止一种，这时在计算每种方案的换乘次数和所用时间，取在换乘系数最少的前提下，所用的时间最短的乘车方案为最终结果输出。其算法流程图5见附录图(附-1)4.2求解结果根据算法思想及所提供的算法步骤，运用Matlbe软件编程计算，所得求解结果为：4.2.1针对问题一中所给六对站点的最佳路径的计算结果如下：（1）第一条路线：S3359S1828出行的最佳路径为：由出发点S3359乘坐L0436路公交车，到达S3500站点，换乘L0167路公交车，到达目的地S1828站点。整个过程，换乘次数：1（次）；出行耗时：101（分钟）；途经总站数：32（个）；花费金额：3（元）。（2）第二条路线：S1557S0481出行的最佳路径为:由出发点S1557乘坐L0363路公交车，到达S1919站点，换乘L0417路公交车，到达站点S2424，然后换乘L0516路公交车到达目的地S0481站点。整个过程，换乘次数：2（次）；出行耗时：109（分钟）；途经总站数：33（个）；花费金额：3（元）。（3）第三条路线：S0971S0485出行的最佳路径为:由出发点S0971乘坐L0013路公交车，到达S2184站点，然后换乘L0417路公交车到达目的地S0485。整个过程，换乘次数：1（次），出行耗时：128（分钟）；途经总站数：41（个）；花费金额：3（元）。（4）第四条路线：S0008S0073出行的最佳路径为:由出发点S0008乘坐L0463路公交车，到达S2083站点，然后换乘L0057路公交车到达目的地S0073。整个过程，换乘次数：1（次）；出行耗时：80（分钟）；途经总站数：25（个）；花费金额：2（元）。（5）第五条路线：S0148S0485出行的最佳路径为：由出发点S0148乘坐L0308路公交车，到达S0036站点，换乘L0156路公交车到达S2210站点，然后换乘L0417路公交车到达目的地S0485。整个过程，换乘次数：2（次）；出行耗时：103（分钟）；途经总站数：31（个）；花费金额：3（元）。（6）第六条路线：S0087S3676出行的最佳路径为：由出发点S0087乘坐L0454路公交车，到达S3496站点，然后换成L0209路公交车到达目的地S3676。整个过程，换乘次数：1（次）；出行耗时：65（分钟）；途经总站数：65（个）；花费金额：2（元）。4.2.2针对问题二最佳路径的选择计算结果如下：当同时考虑公交与地铁的情况下，相对问题一，除了第六条路线S0087S3676有更优的路径选择外，其余五条路径均无明显变化。第六条线路：S0087S3676出行的最佳路径为：由出发点S0087进入地铁站D27，乘坐T02路地铁到达D36站点出站，然后到达目的地S3676公交站点。整个过程中，换乘次数：0（次）；出行耗时：40.5（分钟）；途经总站数：11（个）；花费金额：3（元）。4.2.2针对问题三寻求最佳路径的方案.针对本问我们给出了出行者选择最佳乘车路线的多目标优化模型及与起相匹配的算法。由于问题中所有站点之间的步行时间作为符号常量给出，所以在本文中我们不能对其进行求解，但实际生活中该符号常量可通过重复试验测出其平均值，即可将其当作已知常数。所以，当考虑公汽、地铁及在站点之间采取必要的步行措施时，我们同样可以通过本问中所提供的多目标优化模型及算法求出出行者欲从起始站到达终点站所需要选择的最佳（换乘次数最少且耗时最短）路径及相应花费的票价总金额。五、结果分析与检验在上述所求解的结果中，可以发现，所得到的六组路径，都是没有直接通达的车次，即至少需要换乘一次，其结果统计归纳如下：路径中转站换乘次数历经站数出行时间出行费用(1)、S3359S1828S3500132101分钟3元(2)、S1557S0481S1919,S2424233109分钟3元(3)、S0971S0485S2184141128分钟3元(4)、S0008S0073S208312580分钟2元(5)、S0148S0485S0036,S2210231103分钟3元(6)S0087S3676D27,D3601140.5分钟3元S3496,16565分钟2元可见在这组交通路线中，增加交通工具的公交线路，不一定能改变出行者的交通路线，当然，离在新交通工具站点附近的站点出行的乘客受到的影响则比较大如第（6）对站点。根据上表中各参数的变化关系，可见增加换乘次数，可以明显地减少站点总数，而对时间和费用的影响不大。因此本模型在考虑换乘次数上比较稳定。六、模型评价及推广6.1模型的评价本文分析了公交与地铁交通网络相互配合的交通特点，建立了以换乘次数最少为第一目标，以选择最少乘车所用时间（或途经站数）为第二目标的最佳乘车路径选择模型，并在此模型的基础上设计了广度优先搜索算法。在模型的建立过程中，考虑到影响乘车者选择乘车方案的因素很多，如换乘次数，乘车时间，乘车费用等因素，所以不能简单的将本文中的最佳路径选择问题抽象为最短路问题8。在算法的设计过程中，由于传统的交通网络最短路径查询6通常需要先求出发地和目的地之间的最短路径，然后在考虑这个路径上的换乘方案。这可能导致换乘的次数过多而使乘车的时间和费用增加，这不符合人们的乘车习惯。而基于乘车换乘次数最少的查询算法是一种较为符合实际的算法，符合人们的心里要求3；另外，传统的交通网络最短路径查询算法在计算转乘方案时往往忽视了人们在换车时可能步行一段距离到转乘点，而以紧邻站点来表示这种转乘的情况既能符合实际又能较为有效地解决中途换乘的问题。6.1.1模型的具体优、缺点分析：优点：1.分析具有逻辑性。首先，在模型的建立过程中采取了逐层推进的方法，使其有较强的逻辑性；同时，对必要的结论加以证明，使模型的建立更有根据性。其次对模型的求解结果进行了灵敏度分析，这对出行者在最佳路径的选择方面具有一定的实际参考价值。2.实用性强。因本文所提出的算法是通过计算机程序来实现求解的，所以本文中的模型和算法均可通过计算机编译，将其转化为计算机应用系统。只要出行者从计算机输入起点站与终点站即可得知应选择的最佳乘车路径及相应的票价总金额。这将使模型及算法具有很强的实用性。3.容易推广。本文的1，2，3问题中所建立模型的最大优点是设计了与模型相匹配的求解算法（广度优先搜索算法），这使问题的解决可通过计算机搜索的方法找出所有可共选择路径中的最佳路径。本模型的建立过程及算法的设计思想同样可以应用到解决其它方面的类似问题，有较强的推广价值。缺点：1.本模型在建立过程中的影响因素较多，为使问题简单化，仅研究了影响出行者选择乘车路线的主要因素，忽略了次要因素，所以使模型在实际的应用过程中会产生一定的误差。2.由于题中所给参数均为简化问题而做的假设，而未必与实际数据完全吻合，这将给模型在推广方面带来一定的局限性。 6.1.2模型及算法的改进（1）模型功能的完善。本模型仅实现了城市公交，地铁网络最佳路径的查询目的，对于人们想了解的城市公交，地铁其它方面的信息未能提供。所以将本模型的功能进一步扩充，完善成一个城市公交，地铁网路的综合查询模型将是下一步改进的方向。（2）最优路径算法的改进。本文提出的算法仅讨论了基于换乘数最少的前提下，使乘车时间最短的最佳乘车路径选择问题。这种算法虽然符合实际但仍存在不足之处：首先，算法的效率随换乘次数的增加而急剧下降，特别是需要搜索紧邻站点时。其次，算法中只考虑了换乘次数，乘车时间，途径的站点数等几个因素，但对于现实生活中影响乘车方案的其它因素，如道路阻塞程度、公共汽车发车间隔、公共汽车舒适程度等因素都未加以考虑。基于以上影响因素，增强本算法的功能性将是下一步所需要改进完善的。6.1.3.数据动态更新和实时查询的实现。本文所研究和实现的的查询系统是一个静态的系统，数据如果发生了变更，就可能需要对其重新进行预处理，如城市公交线路的新增、改线及原来定义的属性信息扩展等。因此本查询系统还需要在系统功能上进一步改进完善以适应数据的动态更新及在动态更新的基础上实现实时查询。6.2模型的推广本文通过对出行者的心里调查，参考文献1，得出了出行者乘交通工具时首先考虑的时途中换乘的次数最少，在此基础上使所花费的时间最短。针对此条件，我们列出了以换乘次数最少为前提，满足从出发点到达终点所花费时间最短的交通网络模型，并根据建立模型的思想，设计了相应的算法。另外，本模型填补了传统的最短路法的局限性，相应算法在应用的过程中也具有一定的广泛性和灵活性。尤其在情况较为复杂的一些道路交通网络模型中具有较好的推广性。如在客运路径的选择，最短路径选择方面都具有良好的推广性。七、参考文献1杨新苗、王炜、马文腾，基于GIS的公交乘客出行路径选择模型J，东南大学学报（自然科学版），30（6）：87-88，2000年。2韩传峰、胡志伟，城市公交路网性能评估的网络图方法J，系统工程，21（3）：58-61，2003.3赵巧霞、马志强、张发，以最小换乘次数和站数为目标的公交出行算法J，计算机应用，24（12）：136-137，2004年。4杨启帆、方道元，数学建模M，杭州：浙江大学出版社，188-189，1999年5王建林，基于换乘次数最少的城市公交网络最优路径算法J，浙江交通职业技术学院院报，25（5）：673-676，2000.6陈萧枫、蔡秀云、唐德强，最短路径算法分析及其在公交查询的应用J,工程图学学报，(3)：20-24，2001.7赵玲，基于MAPINFO的城市公交信息查询系统的设计与实现D,中南大学硕士论文，2003.8 严寒冰、刘迎春，基于GIS的城市道路网最短路径算法探讨J,计算机学报，23（2）：211-215，2000.9陈家治，ARC/INFO路径寻找功能的扩展：双向比较追索法J,上海师范大学学报（自然科学版），（3）：78-83,2003.附录