《2022年数学建模-全国一等推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年数学建模-全国一等推荐 .pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、公交线路的选择摘要本文研究了只考虑公汽、考虑公汽与地铁以及同时考虑公汽、地铁与步行三种情况下的公交线路的选择问题，针对三种选择偏好（较快捷、较经济以及换乘次数最少），分别给出最佳路线选择的模型和算法。我们还对不同算法进行了对比评价，对交通工具的不同选择范围下的时间和用费指标进行了比较。对问题一，建立了目标优化、分层网络和双向完全图三个模型。根据三种偏好，多目标规划问题被转化为了三个单目标的规划问题；分层网络模型同时给出时间边权图和费用边权图，在不同的偏好下，对两个边权图求最短路的顺序不同，并分别给出了求解最佳方案的算法，最短路由动态规划实现；双向完全图同时定义时间边权和费用边权值，不同的偏好以
2、不同的标准同步初始化两种边权值，对得到的有权双向完全图用DIJKSTRA 算法即可以得到最优解。求解过程中，我们将换乘次数限制在4 次以内，在三种偏好下，对不同的换乘次数，先分别求出局部最优方案，再从中全局选出最佳方案；对问题二，我们充分发掘了他与模型一的共性，类似地建立了目标优化和双向完全图两个模型，并给出了加入对地铁的考虑后，目标优化模型中初始可行方案集的确定算法和双向完全图模型中边权的初始化算法。通过从局部到全局的相同的算法思路，可以求出各种偏好下的最佳方案，最优化算法也在文中给出；对问题三，我们建立了双向完全图模型，给出了不同偏好下，双向完全图的时间权值和费用权值的确定方法和最佳方案的
3、确定算法。对问题一和问题二结果的分析发现，加入对地铁的考虑对偏好为较快捷的乘客，时间指标改善比较明显，而对偏好为较经济的乘客，费用指标的改善不明显。关键词：多目标优化，分层优化，分层网络模型，双向完全图名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 24 页 -21、问题的分析本题要求给出公交线路选择的一般的模型与算法，并能给出两点之间的最佳路径，但是最佳线路是相对，不同的乘客对最佳线路的预期是不一样的。偏向线路较快捷的乘客会认为时间最短，费用尽量小的线路方案是最佳的；对偏向于较经济的乘客来说，费用最小，时间尽量短的线路方案是最佳；而希望换乘次数最小的乘客，则将换乘次数最为评价方
4、案优劣的第一准则。因此，不管交通方式的选择范围如何，我们都应该建立能够针对不同乘客类型给出各自的最佳方案的数学模型和方法。方案一，我们可以建立面向一般的统一的多目标规划模型，然后再针对乘客的三种主要的偏好，将该多目标规划问题化为三个相应的单目标问题，并分别给出最优解。方案二，很自然的想法，公交站点之间通过线路连接，从起始点往下，可以到达的站点是一个树型的分布，换乘次数增加一次，树就多一层，而且让最后一层的叶子节点汇入到终点。这样就可以建立一个分层的网络模型，利用动态规划算法求解。在换乘次数比较小的条件下，该模型是可以接受的。方案三，考虑到公交站点和线路的情况与双向完全图的情况的相似性，我们可以
5、建立一个双向完全图，对完全图同时定义时间边权和费用边权，在不同的偏好下采用不同的边权定义和求解算法。偏好较快捷的情况下，以最小的时间来确定时间边权和对应的费用边权，然后求时间边权在起止点之间的最短路，进而以费用尽量小为标准进一步的选优；偏好较经济的情况下，以最小的时间来确定时间边权和对应的费用边权，然后求费用边权在起止点之间的最短路，进而以时间尽量短为标准进一步的选优；而且该方案可以很容易的推广到问题二的情况，只需对与地铁站相连的站点之间的边权进行修改即可。对于问题三，任意两个公汽站点之间的步行时间已知，对任意一个站点，其可选择的下一步方案将增加1alln-种，alln是公汽站点的总数，这是方
6、案集的一个相当大的扩充，从而基于集合选优的多目标规划模型和基于方案生长树的分层网络模型在实现上将会变得不可能。但是双向完全图模型可以通过对比、过滤的方法进行权值的修改，使模型能够用于问题三这种复杂的情况。2、模型假设与符号约定2.1 模型假设1）公汽、地铁线路信息描述的含义相同，且乘客到达终点站后乘客必须下车；2）所有公交的上下行线当作不同的线路来处理；3)乘客查询的起止站点都是公汽站点，而不可能是地铁站；4）乘客换乘次数一般不超过3 次，超过 3 次乘客会选择其他交通方式；5）乘客在查询的同时给出较快捷，较经济或换乘次数最少的选择偏好；6）在问题一中，假设乘客不选择跨站换乘；问题二中，乘客只
7、通过地铁站跨站换乘；问题三种，乘客可以通过地铁站或这通过公汽站之间的步行；2.2 主要符号约定L：,1,.,iLr il=为所有公交汽车线路的集合；名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 24 页 -3S：S,1,.,jsjm=为公交站点的集合；1ct：公汽换乘公汽的平均耗时，原问题中设定为15ct=；2ct：地铁换地铁的平均耗时，原问题中设定为24ct=；3ct：地铁换公汽的平均耗时，原问题中设定为37ct=；4ct：公汽换地铁的平均耗时，原问题中设定为46ct=；5ct：通过公汽换乘的平均耗时，应为343cctt+（3 为等车时间）；1dt：相邻公汽站之间的行驶时间，
8、设定为13dt=；2dt：相邻地铁站之间的行驶时间，设定为22.5dt=；iM：为换乘i次公汽时的可行方案的集合；（其他符号在使用时说明）3、模型的建立与求解3.1 问题一仅在公汽体系中选择，要求给出最佳方案的选择算法。通常来讲，乘客对公交的换乘次数是比较看重的，为了方便进一步的方案选择，我们先以线路换乘次数为依据，分情况对线路选择方案进行局部优化，对不同的换乘次数i，分别求出其最佳选择，在根据乘客的偏好情况（较快捷，较经济，换乘次数最少）进行进一步的方案选择，即采取先局部，后全局的优化顺序。现有的公交查询系统的情况表明，乘客换乘的次数一般不超过三次，这也符合人们的心理状况。因此，模型在时间上
9、是可行的。3.1.1模型一（目标规划模型）对于不同的换乘次数i，起点为0e，终点为1ie+，建立多目标优化模型()MODMi3.1.1-1 ()MODMi模型的建立()1111iicdijMinTittNj+=?+?()11,iijjjMinCc ln+=.st(),iiiiE L NM名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 24 页 -4()011,.,iiEe ee+=()11,.,iiLll+=()11,.,iiNnn+=这是换乘次数为i时的一个多目标方案选择优化问题。根据乘客的偏好，我们分情况采取不同的优化方案。（1.）较快捷如果乘客要求提供较快捷的方案，我们对(
10、)MODMi采取分层优化的办法，将时间最短作为第一优化目标，在时间最短的条件下，以费用最小为第二目标。第一层优化：()1111iicdijMinTittNj+=?+?.st(),iiiiE L NM()011,.,iiEe ee+=()11,.,iiLll+=()11,.,iiNnn+=第一层优化的解可能不唯一，第一层最优解的集合表示为1iM?第二层优化：()11,iijjjMinCc ln+=.st()1,iiiiE L NM?()011,.,iiEe ee+=()11,.,iiLll+=()11,.,iiNnn+=经过两层优化，求出了换乘次数为i时，时间最短，费用尽量小的选择方案集2iM?
11、；当然，该优化问题也有可能无解，则表明在起始点之间不存在换乘i次的名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 24 页 -5公汽。换乘次数不超过3 次，对1,2,3i=分别求解出选择方案集2iM?，其中时间最短的方案记为最终的选择方案iM?（2.）较经济若果乘客要求方案较经济，则与较快捷的情况相似，也是建立双层的优化模型，只是将原()MODMi问题中的两个目标的优化顺序进行交换第一层优化：()11,iijjjMinCc ln+=.st()1,iiiiE L NM?()011,.,iiEe ee+=()11,.,iiLll+=()11,.,iiNnn+=第一层优化的解可能不唯一
12、，第一层最优解的集合表示为1iM?()1111iicdijMinTittNj+=?+?.st(),iiiiE L NM()011,.,iiEe ee+=()11,.,iiLll+=()11,.,iiNnn+=经过两层优化，求出了换乘次数为i时，费用量小，时间尽量短的选择方案集2iM?；当然，该优化问题也有可能无解，则表明在起始点之间不存在换乘i次的公汽。换乘次数不超过3 次，对1,2,3i=分别求解出选择方案集2iM?，其中时间最短的方案记为最终的选择方案iM?。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 24 页 -6（3.）换乘次数最小乘客要求换乘次数最小，从而采取对最小
13、的i值下解上述()MODMi模型，此时可以让乘客有二级目标（较快捷或较经济）。第一层优化：Mini.stiM?该层最优解为i?第二层为()MODM i?如果乘客的二级目标为较快捷，转入（1.）（表格）如果乘客的二级目标为叫经济，转入（2.）3.1.1-2 方案集(),iiiiME L N=的确定()011,.,iiEe ee+=是公汽站点的向量，1,.,iee是依次换乘公汽的i个站点；()11,.,iiLll+=是从0e换乘i次到达1ie+的某种方案下依次经过公汽线路的向量；()11,.,iiNnn+=是该方案沿线经过的基段（同一线路上相邻两站点间为一个基段）数的向量，1jn-是相邻换乘点1j
14、e-和je之间的站点数目（不包括1je-和je）；定义函数变量,k(,)0ksK l ss?=?是线路l 上的第站，不是线路l 上的站点为处理方便，当il为环行路线时，我们将其相同的起点站和终点站当作两个不同的站点处理，这不会影响最后的结果。从而，()()|,0,L slK l slL=表示通过s的所有线路的集合；()1212,|(,)(,)0,s sl K l sK l slL=G表示站点12ss和之间直达线路的集合；换乘的次数为i次，起点为0e，终点为1ie+，具体算法如下：在差集01,iSe e+中搜索出所有满足1,.,1ji?=+有1(,)(,)0,1,.,1jjjjK leK lej
15、i-=+的 一 组 互 异 的 站 点名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 24 页 -71,.,iee，则 表 明 存 在 换 乘i次 的 可 行 方 案，记 为()011,.,iiEe ee+=，()11,.,iiLll+=以及()11,.,iiNnn+=，其中1(,)(,)jjjjjnK leK le-=-。将所有可行的方案记录下来，构成换乘i次的可行方案集合(),iiiiME L N=。3.1.1-3 时间指标iT和费用指标iC的确定方案(),iiiiE L NM，有乘车时间为()1111iicdijTittNj+=?+?乘车费用为()11,iijjjCc ln
16、+=费用函数(),jjc ln为公汽线路jl上经过jn个基段（同一线路上相邻两站点间为一个基段）的费用。设 路段函数()1,0rrr?=?路为分段计价，路为单一票制分段计价函数()1,1202xp x?=?，21x403,x40则费用函数为()()()(),11jjjjjc lnllp n=-?+3.1.2模型二（分层网络模型）模型一建立了一般的精确的最优化模型，但是基于集合的搜索时间复杂度是很高的，特别是当i比较大的时候。因此我们考虑利用网络算法的高效的特点，建立相应的网络模型，时间和费用的最小化问题可以转为求解时间网络和费用网络的最短路问题。如图所示，构造换乘次数为i次时的有向图,iiiG
17、E L=，iE是起始点以及换乘站点的集合，iL是换乘线路的集合。以换乘两次的情况为例说明有向图的构造方法，其他情况类似。给定了起止点0e和1ie+，以起始公汽站点0e为母节点，以所有0e能够直达的站点1ke为第 1 级子节点，同理以第1 级子节点1ke为母节点，所有1ke能够直达名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 24 页 -8的站点2ke组成第 2 级子节点，所有第2 级子节点均向终点连边，由此可得费用有向图和时间有向图，两个有向图的节点是一致的。（a）费用有向图的边12,jjlee=，n为线路l上12jjee和两个站点之间的站点数，l的边权()c l为相应的费用如
18、果最后一级子节点与终点之间无直达线路，则()c l=+；否则，如果线路l为单一票制，则()1c l=如果线路l分段计价，则()1,1202nc ln?=?，21403,n40（b）时间有向图的边12,jjlee=，n为线路l上12jjee和两个站点之间的站点数，l的边权()t l为耗费的时间如果1je为起始站点，即10jee=，则()13dt ltn=+?，其中 3 表示起始站点等车的 3 分钟，1dt是相邻公汽站间的行驶时间；如果2je为终点站，即21jiee+=，则()13,dtnt l+?=?+?第二级站点到终点有直达线路第二级站点到终点没有直达线路如果1je不是起止点，则()11cdt
19、 lttn=+?，1ct为换乘公汽耗时，1dt相邻公汽站间的平均行车时间。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 24 页 -9G1.利动态规划算法能够较高效率地求解有向图的最短路。（1）较快捷对于换乘次数0,1,2,3i=，分别对iG实施以下算法Step1：对时间有向图求最短路，并将非最短路线从图中删去，得到残余有向图；Step2：对残余有向图对应的费用有向图求最短路，将非最短路从残余有向图中删去，剩下的有向图即是所有最优选择方案集iM?。得到的iM是换乘次数为i是时间最短，费用尽量小的方案的集合从求出的四个局部最优选择方案中，找出时间指标最小的方案集iM?，即为该种偏
20、好下的最优方案。（2）较经济对于换乘次数0,1,2,3i=，分别对iG实施以下算法Step1：对费用有向图求最短路，并将非最短路线从图中删去，得到残余有向图；Step2：对残余有向图对应的时间有向图求最短路，将非最短路从残余有向图中删去，剩下的有向图即是所有最优选择方案集iM。得到的iM是换乘次数为i是费用最少，时间尽量短的方案的集合从求出的四个局部最优选择方案，找出费用指标最小的方案集iM?，即为该种情名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 24 页 -10况下的最优方案。（3）换乘次数最小Step1：0i=，iM=?Step2：搜索有向图iG中是否存在从起点到终点的有
21、限权的通路如果没有，1ii=+，转 Step2；否则，转 Step3；Step3：根据乘客的二级目标分情况处理如果二级目标为较快捷，对iG先求时间最短路，删除不是时间最短的路径，再对残余有向图求费用最小，得到最优方案；如果二级目标为较经济，对iG先求费用最小，删除不是费用最小的路径，再对残余有向图求时间最短路，得到最优方案；3.1.3模型三（双向完全图模型）构造双向完全图,GS L=，其中S,1,.,jsjm=是全体公汽站点的集合（在问题一种考虑为公汽站点的集合），(,)|&,ijijijLls ssss sS=，从 而任 意两 个不 同的 站点之 间 都 有两 条方 向 相 反的 有向边，双
22、 向完 全图,GS L=的时间边权为()t l，相应的费用边权()c l。不同的偏好对双向完全图定义边权的方法不同：（1）较快捷定义,()mmijijttsst lss?=?+?是所有到的直达路线的最小时间，和之间没有直达的线路,(),ijijccssc lss?=?+?是 和间直达时间最小时相应的费用和之间没有直达的线路限制换乘次数为不超过3 次，则表明起点和终点之间由不超过4 条时间边权有限的边连接起来，求出连接的边的时间边权之和最小的路的集合，然后在此集合内选出费用边权之和最小的路径，即为所求的最优路径，是该条件下的选择方案。这里用到了图论中的最短路算法。（2）较经济名师资料总结-精品资
23、料欢迎下载-名师精心整理-第 10 页，共 24 页 -11定义,(),ijijccssc lss?=?+?是 和间直达的最小费用和之间没有直达的线路,()mmijijttsst lss?=?+?是 与间直达费用最小时相应的时间，和之间没有直达的线路限制换乘次数为不超过3 次，则表明起点和终点之间由不超过4 条时间边权有限的边连接起来，求出连接的边的费用边权之和最小的路的集合，然后在此集合内选出时间边权之和最小的路径，即为所求的最优路径，是该条件下的选择方案。（3）换乘次数最小若二级目标为较快捷，则采用（1）的处理方法，只是要求换乘次数最少，所以应该让连接起点和终点的边权有限的边尽量少，并在此
24、条件下求最短时间的路径。若二级目标为较经济，则采用（2）的处理方法，并让连接起点和终点的边权有限的边尽量少，并在此条件下求最小费用的路径。3.2 问题二问题二要求同时考虑公汽和地铁，因此站点集S和线路集L的元素会增加，而且由于临近地铁的各个公汽站点可以通过地铁站换乘，因此在可行方案集的确定上会有所不同，但是在可行方案集确定后，方案选择的方法是相似的。3.2.1模型四（集合搜索模型）对于不同的换乘次数i，建立多目标优化模型()MODMi()MODMi模型的建立11iiijMinTTt+=11iijjMinCCc+=.st(),iiiiiE L T CM()011,.,iiEe ee+=()11,
25、.,iiLll+=()11,.,iiTtt+=名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 24 页 -12()11,.,iiCcc+=这是换乘次数为i时的一个多目标方案选择优化问题。根据乘客的偏好，我们分较快捷，较经济，和换乘次数最少三种情况采取不同的优化方案。按照乘客的偏好，采用类似与问题一中的处理方法，将多目标问题化为不同的分层优化模型，只是将约束条件相应改变即可。但是，方案集合(),iiiiiME L T C=和指标的确定方法是不同的：3.2.1-2 方案集(),T,iiiiiME LC=，iTT和jCC的确定()011,.,iiEe ee+=是换乘公交站点的向量，1
26、,.,iee是依次换乘公交的i个站点；()11,.,iiLll+=是从0e换乘i次到达1ie+的某种方案下依次经过公汽线路的向量；11T(,.,)iitt+=是所用时间的向量，jt是经过线路jl从1je-到je所用的时间；11C(,.,)iicc+=是所花费用的向量，jc是经过jl从1je-到je的车票费用；从定义函数,kDk(,)Dk0kskK l ss?=?l 是公汽线路，是公汽线路 l 上的第站,l 是地铁线路，s是地铁站-k,l 是地铁线路,s 是与地铁站相连的公汽站点，不是线路 l 上的站点为处理方便，当il为环行路线时，我们将其相同的起始站点当作两个不同的站点处理，这不会影响最后的
27、结果。换乘的次数为i次，起点为0e，终点为1ie+，具体算法如下：1,.,1ji?=+，在差集01,iSe e+中搜索出所互异的站点组合1,.,iee，使得相邻的节点满足以下几种情况之一：（1）1(,)(,)0jjjjK leK l e-（乘公汽）此时111113,djjjdjcjtnettnte-?+?=?+?jj为起点,n 为经过站点数非起点,n 为经过站点数()()()11jjjjcllp n=-?+名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 24 页 -13其中()1,0rrr?=?路为分段计价，路为单一票制分段计价函数()1,1202xp x?=?，21x403,
28、x40（2）1(,)(,)0jjjjK leK l e-=（公汽站点到地铁站点）此时，4jctt=0jc=（4）1(,)(,)0jjjjK leK le-=（地铁站点到公汽站点）此时，3jctt=0jc=所有满足这些条件的方案集为可行方案的集合(),T,iiiiiME LC=进而时间指标和费用指标分别为：时间指标11iiijTTt+=费用指标11iijjCCc+=3.2.2模型五（双向完全图模型）由于乘客的起点和终点只可能是公汽站点，因此地铁站可以只作为中间的转移节点，用于对原图中节点之间的边权进行修改，而不用将地铁站点加入有向图中。构造双向完全图,GS L=，其中S,1,.,jsjm=是全体
29、公汽站点的集名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 24 页 -14合，(,)|&,ijijijLls ssss sS=，从而任意两个不同的站点之间都有两条方向相反的有向边，双向完全图,GS L=的时间边权为()t l，相应的费用边权()c l。对应乘客的不同偏好，双向完全图边权的定义方法不同：（1）较快捷（a）先不考虑地铁站以及通过地铁站的换乘，利用与问题一相同方法处理权值，得到与问题一中模型三的边权完全一样的有向图。定义权值为,()mmijijttsst lss?=?+?是公汽站到的所有直达路线的最小时间，和之间没有直达的线路起始站的 3 分钟的等候时间也是要考虑的
30、；,(),ijijccssc lss?=?+?是 和间直达时间最小时的费用和之间没有直达的线路（b）加入对地铁以及通过地铁换乘的考虑，修改与地铁站相连的公汽站点之间的边权，含有不与地铁站相连的站点不可能通过地铁直达，因此边权不会改变。边权修改方案如下：（1.1）如果ijss和均与同一个地铁站点相连，则555(),()(),()ccct lt ltt lttt l?=?（时间相等时，默认乘客偏好坐车）费用边权55(),()()0,()ccc lt ltc ltt l?=?（1.2）如果ijss和与不同地铁站点相连，则(),()(),()mmmt lt ltt lttt l?=?，其中mt是坐地铁
31、时的最短时间费用边权(),()()3,()mmc lt ltc ltt l?=?（c）求解算法通过（a）（b）得到修改后的有向图，在修改后的有向图上实施以下算法：名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 24 页 -15Step1：由 DIJKSTRA 算法求通过边数不大于4（即换乘不超过3 次）的时间边权图的最短路；Step2：在 Step1中得到的最短路中，搜索出费用边权和最小的路径，即为该偏好下的最优方案。（2）较经济方法与较快捷下的方法基本一致，只是在进行图的权值确定和修改时，不是以时间最小为依据，而是改为以费用最小为依据，在方案搜索时先求费用最短路，然后再从其中
32、选出时间较短的最为最终方案。在此，不赘述。（3）换乘次数最小若二级目标为较快捷，则采用（1）的处理方法，只是要求换乘次数最少，所以应该让连接起点和终点的边权有限的边尽量少，并在此条件下求最短时间的路径。若二级目标为较经济，则采用（2）的处理方法，并让连接起点和终点的边权有限的边尽量少，并在此条件下求最小费用的路径。3.3问题三任意两个站点之间的步行时间已知，允许乘客通过步行实现站间的转移，对于偏好快捷的乘客，我们可以利用问题二的双向完全图，通过对比修改时间权值进行求解，直接给出时间最短的线路选择方案；但是对于偏好较经济的乘客，由于步行的费用为0，单纯利用费用最小为目标的方法得到的方案会走极端，
33、即全部步行实现，这显然不是我们想要的结果，因此我们需要乘客提供进一步的个人要求信息才能给出最佳的线路选择方案，在这里我们假设偏好较经济的乘客还会同时给出能够接受的单次最长步行时间a这一决策信息。该问题从本质上来讲和问题二没有太大的区别，只是站点之间的联系更多了，每个站点处的选择更多了，均可以通过建立目标规划模型、分层网络模型以及来双向完全图模型来刻画，但是前两者的时间复杂度会几何级数地增加，实际应用上没有太大意义；只有双向完全图模型能够通过适应性的改进而适于作为这一问题的数学模型。3.3.1 模型六（双向完全图模型）构造双向完全图,GS L=，其中S,1,.,jsjm=是全体公汽站点的集合，(
34、,)|&,ijijijLls ssss sS=，从而任意两个不同的站点之间都有两条方向相反的有向边，双向完全图,GS L=的时间边权为()t l，相应的费用边权()c l。（1）较快捷（a）先不考虑地铁站以及通过地铁站的换乘，利用与问题一相同方法处理权值，名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 24 页 -16得到与问题一中模型三的边权完全一样的有向图。定义权值为,()mmijijttsst lss?=?+?是公汽站到的所有直达路线的最小时间，和之间没有直达的线路起始站的 3 分钟的等候时间也是要考虑的；,(),ijijccssc lss?=?+?是 和间直达时间最小时
35、对应的费用和之间没有直达的线路（b）加入对地铁以及通过地铁换乘的考虑，修改与地铁站相连的公汽站点之间的边权，含有不与地铁站相连的站点不可能通过地铁直达，因此边权不会改变。与地铁站相连的公汽站点之间的边权的具体修改方案如下：（1.1）如果ijss和与同一个地铁站点相连，则555(),()(),()ccct lt ltt lttt l?=?（时间相等是，默认乘客偏好坐车）费用边权55(),()()0,()ccc lt ltc ltt l?=?（1.2）如果ijss和与同不同地铁站点相连，则(),()(),()mmmt lt ltt lttt l?=?，其中mt是坐地铁时的最短时间费用边权(),()
36、()3,()mmc lt ltc ltt l?=?（c）任意两个站点ijss和之间的步行时间(),ijs s已知，乘客可以选择步行在站点之间转移，因此有可能通过步行使时间更短，需要对完全图的权值进行第二次修改。修改算法如下：对于所有的有向边(,)ijls s=如果()(),ijs st l则()(),ijt ls s=且()0c l=；否则(,)ijls s=的边权不改变。名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 24 页 -17（d）对修改后的双向完全图实施以下算法：Step1：由 DIJKSTRA 算法求通过变数不大于4 的时间边权图的最短路；Step2：在 Step
37、1中得到的最短路中，搜索出费用边权和最小的路径，即为该偏好下的最优方案。（2）较经济（a）先不考虑地铁站以及通过地铁站的换乘，利用与问题一相同方法处理权值，得到与问题一中模型三的边权完全一样的有向图。定义,(),ijijccssc lss?=?+?是 和间直达的最小费用和之间没有直达的线路,()mmijijttsst lss?=?+?是 与间直达费用最小时的时间，和之间没有直达的线路（b）加入对地铁以及通过地铁换乘的考虑，修改与地铁站相连的公汽站点之间的边权，含有不与地铁站相连的站点不可能通过地铁直达，因此边权不会改变。第一步边权修改方案如下：（1.1）如果ijss和与同一个地铁站点相连，则(
38、)0c l=（经过地铁站不用支付地铁费用）时间边权5()ct lt=（经过地铁站换站的时间）（1.2）如果ijss和与同不同地铁站点相连，则(),()3()3,3()c lc lc lc l?=?，其中3是乘坐地铁支付的地铁票价时间边权(),()3(),3()mt lc lt ltc l?=?，其中mt是坐地铁从ijss到的最短时间（c）任意两个站点ijss和之间的步行时间(),ijs s已知，乘客可以选择步行在站点之间转移，但是乘客能够接受的步行时间为a。两个站点之间的步行时间超过a时，不能通过步行在这两个站点之间转移，否则由于乘客的偏好是较经济，应该选择费用为0 的走路方案，需要对完全图的
39、权值进行第二次修改。修改算法如下：对于所有的有向边(,)ijls s=名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 24 页 -18如果(),ijas sL484/L324-S1746-L485-S1784-L217/L167-S1828 （/表示或）（2）较经济，费用为3 元S3359-L469/L87-S304-L217/L45-S1828（3）换乘次数最小，换1 次S3359-L436-S1784-L217/L167-S1828（较快捷为二级目标）S3359-L469/L87-S304-L217/L45-S1828（较经济为二级目标）A2、起止点为（6）S87-S367
40、6（1）较快捷，耗时为49 分钟S87-L454/L206/L21-S88-L231-S427-L426/L97-S3676（2）较经济，费用为2 S87-L36-S1893-L30-S3676（3）换乘次数最少,为 1 次S87-L454-S3496-L209-S3676（二级目标为较快捷）S87-L36-S1893-L30-SL3676（二级目标为较经济）（B）问题二的最优方案（以1 和 6 两组起始点为例，完整的结果间【附件1】）B1、起止点为（1）S3359S1828（1）较快捷，耗时为67 分钟S3359-L484/L324-S1746-L485-S1784-L217/L167-S1
41、828 （/表示或）（2）较经济，费用为3 元S3359-L484-S3697/S3727/S1746-L485-S1784-L167/L217/L218/L219-S1828（3）换乘次数最小，换1 次S3359-L436-S1784-L217/L167-S1828（较快捷为二级目标）名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 24 页 -19S3359-L469/L87-S304-L217/L45-S1828（较经济为二级目标）B2、起止点为（6）S87-S3676（1）较快捷，耗时为34 分钟S87-D24-D36-S3993（2）较经济，费用为2 S87-S88-L
42、231-S427-S3676（3）换乘次数最少,为 0 次（通过地铁）S87-D27-T2-D-S3676（二级目标为较快捷）S87-D27-T2-D-S3676 （二级目标为较经济）4.2 解的评价说明较快捷的方案给出了换乘次数在三次以内的时间最短，费用尽量小的方案；较经济的方案给出费用最小，时间尽量短的方案；换乘次数最小的方案以据二级目标的不同，分别给出了换乘次数最小、时间尽量短和换乘次数最小、费用尽量小的方案。起止点为 S3359S1828的情况下，换乘次数为1，2，3 次的最短时间分别为 104，67，72，从而我们应该选择全局最优的换乘2 次，最短时间 67 对应的方案中，费用最小的
43、方案为S3359-L484/L324-S1746-L485-S1784-L217/L167-S1828 即为在较快捷偏好下的最佳方案。换乘次数为 1，2，3 次的最小费用分别为3、3、4，从费用最小的方案中选出时间最短的方案为S3359-L469/L87-S304-L217/L45-S1828，为较经济条件下的最优方案。不存在换乘次数为 0 的方案，因此之间在换乘次数为1 的方案中依据二级目标的不同搜索得到换乘次数最小偏好下的最佳方案。起止点为 S87-S3676在问题一下的解的情况与S3359S1828 基本一致，但是在问题二中，两者的最优解出现了较大的差异，起止点组 1 的方案、时间指标、
44、费用指标都没有太大的变化，而起止点组 6 的方案、时间指标、费用指标都有较大的变化，特别是时间指标，这是因为起止点组1（S3359S1828）与地铁站比较远，在问题二中并不选择地铁交通方式，因此解基本与不考虑地铁的问题一种的情况比较一致。但是起止组六的起点和终点都与地铁站相连，这样的话地铁对他的影响会比较大，时间指标也可以得到较大的优化。这也说明，不同的站点对是否考虑地铁因素的敏感度是不一样的，时间上比较靠近地铁站的站点比较容易受到地铁因素的影响。模型结果分析对于偏好为较快捷的乘客，可以得到问题一和问题二下的最短时间；而对于偏好为较经济的乘客，可以得到问题一和问题二下的最小费用。问题一和问题下
45、最短时间和最小费用的对比图如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 24 页 -20123456020406080100120起止点组最短时间问题一问题二G.2 问题一和问题二最短时间的对比图12345600.511.522.533.54起止点组最小费用问题一问题二G3 问题一和问题二最小费用的对比图由对比图可以发现，是否考虑地铁对最短时间有较大的影响，但六组起止点的最小费用均不因是否考虑地铁而改变。可见，是否考虑地铁，对与偏好为较快捷的乘客有较大意义，对偏好为较经济的乘客没有太大的改善意义，这是由地铁较快的速度和比较昂贵的价格的特点决定的，可见模型的结果与现实比较
46、相符。5、模型评价与改进5.1 模型评价模型一和模型四是目标规划模型，分别解决问题一和问题二，目标规划模型表述清晰，容易理解，能够很好地体现乘客的偏好，但是对于较大的换乘次数，时间复杂度太大；模型二是多层网络模型，结构清晰，容易理解，能够利用动态算法较高效率地对名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 24 页 -21问题一进行求解，但是无法拓展到问题二，因为层次结构无法保证，而且层数较大是空间和时间的复杂度也不容忽视。模型三和模型五是双向完全图模型，分别针对问题一和问题二，模型的可拓展性强，时间复杂度和空间复杂度都很低，而且能够拓展到问题三，缺点是模型的结构不是很清晰，
47、不易理解，而且权值的确定比较烦琐。5.2 模型的改进方向北京交通的流量大，容易出现交通拥堵的情况，乘客显然不愿意面对堵车，交通查询系统如果能够帮助乘客尽量避免堵车，将是一个很受欢迎的功能，以上提出的模型都是静态的模型，无法合理的规避交通拥堵。事实上，各个路段的交通运行状况是可以实时得到的，结合这些信息，我们可以将堵车的路段作为过滤条件，上述个算法中的方案集进行过滤，或者是对有向图的边权进行修正。这无疑是一个很好的改进方向，但是对算法的实时性要求将更高。参考文献：1 姜启源，谢金星等,数学模型,北京：高等教育出版社，2003 2 韩中庚,数学建模方法及其应用,北京：高等教育出版社，2005 3
48、卢开澄，卢华明.图论及其应用.第2 版.北京:清华大学出版社，2005 4 王成等，DVD租赁问题的模型设计及求解，工程数学，22卷第 7 期：92-100，2005 名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 24 页 -22【附件 1】六组不同的起点和终点条件下的最优方案问题一的最优解如下：1、起止点 S3359S1828（1）较快捷的方案，耗时为67 分钟S3359-L484/L324-S1746-L485-S1784-L217/L167-S1828 （/表示或）（2）较经济，费用为3 元S3359-L469/L87-S304-L217/L45-S1828（3）换乘次
49、数最小，换1 次S3359-L436-S1784-L217/L167-S1828（二级目标为较快捷）S3359-L469/L87-S304-L217/L45-S1828（二级目标为较经济）2、起止点 S1557-S481（1）较快捷，耗时为102 分钟S1557-L363/L84-S1919-L189-S3186-L317/L91-S902-L516/L460/L447/L312/L254-S481（2）较经济，耗费为3 元S1557-L363/L84-S1919-L417-S902-L254/L312/L447/L460/L516-S481（3）换乘次数最小，2 次S1557-L363/L8
50、4-S1919-L189-S3186-L460-S481（二级目标为较快捷）S1557-L363/L84-S55-L348-S2361-L312-S481 （二级目标为较经济）3、起止点 S971-S485（1）较快捷的方案，耗时为106 分钟S971-L13-S2517-L290-S2159-L469-S485（2）较经济的方案，费用为3 S971-L13/L94/L119-S1520-L485/L27-S516-L104/L469-S485 或 S971-L119-S872-L417-S485（3）换乘次数最少，为2 次 S971-L13-S2184-L417-S485（二级目标为较快捷）