年优秀建模2007b题乘公交看奥运

从实际情况出发，建立起不同的最佳路线选择模型，并结合题中所给的线路数据利Mathematica最优解；而且结合原理图给出了求解Un(n1,2C最少两种，分别给出约束条件，进而在集合Un(n1,2中筛选出满足相应需求的最Dijkstra换乘次 算 混合出行模 最佳路问题重 模型假 符号说 问题分 模型建 模型求 （一）可以选乘 线路集合Un的求解方 模型评 优点分 缺点分 模型扩 问题三的回 问题分 模型假 模型建 模型求 模型评 参考文 附 问题重近年来，市系统有了很大的发展，越来越多的人选择乘坐公共交通工具（简称，包括公汽和地铁等）出行；由于线路数量的增多，人们也面临多条线路的选择问题。针对市场需求，某公司欲开发一个线路选择的自主查模型假同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费符号说 i的公汽站点(i1

SstartSi|i1,SendSi|i1, j的地铁站点j1, x的公汽线路(x1, 已看作一条特殊公汽线路的地铁线路（将T1和T2当作一条线路处理 所有公汽线路的集合LLx|x1 换乘n(n1,

可选乘车线路集合中第k种换乘方 (k1,2...520且LinekUsum 相邻公汽站平均行驶时间（包括停站时间 相邻地铁站平均行驶时间（包括停站时间nS,K 在第k种换乘方案中乘坐公汽一次所经过的公汽站总站数（首站不算在内）nD,K 在第k种换乘方案中乘坐地铁一次所经过的公汽站总站数（首站不算在内）nSS,K 在第k种换乘方案中公汽换乘公汽的次数nDD,K在第k种换乘方案中地铁换乘地铁的次数nSD,K 在第k种换乘方案中公汽换乘地铁的次数nDS,K 在第k种换乘方案中地铁换乘公汽的次数 CS公汽单一票价 问题分模型建由模型分析可知，如果从求取乘客需要换乘次数n的角度出发，当任意给出一对起始站Sstart和终到站SendLMathematica实现，找到每个换乘次数n和其所对应的可选乘车线路集合Un(n1,2...)Un(n1,2的范围中讨论各种需求的情况，最终给出满足各种换乘次数n且满足其他在换乘次数n和其相应可选乘车集合Un已求的前提下，我们把乘车人群的需求分模型一（公汽系统换乘模型LinetGetU,T

T Linek

nSS,KtSnSStSS1．函数GetU,T 在可选乘车线路总集合Usum中，选取到达时间为T的线t

GetU,C

C

SS

hCSC

h

or

0nh s

Chh Lineh 21nh h

1．函数GetU,C 在可选乘车线路总集合Usum中，选取总费用为C的线 S3．3．S

第h

SSLsect分段计价的公汽线路集合由于公汽换乘nSS,K次，所以共乘了nSS,K1模型二（系统换乘模型t

GetU,T T Linek

nS,KtSnD,KtDnSD,KtSDnSS,KtSSnDS,KtDSnDD,KtDDLinecGetU,C CMin sgn C

h

D, D h Lineh orLineh 0nh s

Chh

21n

h

sgnx

xx

sgnxxnD,K0地铁所用的车费3元（单一票价）；当xnD,K0sgnnD,KCD0模型求（一）可以选乘的线路集合 的求解方给出起始站Sstart和终到站Send之后，按照换乘次数n讨论，然后根据不同的n选择恰当的算法，利用Mathematica编程实现，在所有公汽线路集合LLx|x1,2,...520中，找出每个n对应的所有可以选乘 线路集合Un（解n和Un1。现给出不同n情况下的具体算法：1）.当n0LLx|x1,2,...520SstartSend同时位于同LxLx；原理如下图：2）.当n11（1）找到所有包含Sstart的公汽线路LxLx中Sstart之后的站点记为集合Ax 同理找到所有包含Send的公汽线Ly，并Ly中Send之前的站点极为集合Ay第一次乘坐的公汽，Ly为第二次乘坐的公汽；原理如下图：3）.当n22然后将Ax中任意一站看作新的

ASxS

AxAy中是否有可以直达的线路，如果有，就说明Sstart和Send之与上述n2n1，可求得n3时的集合U3，依此类推，最终可求得每个n对应的所有可以选乘的线路集合Un，n n ； ；kn k （二）目标函数的求解然后在所得的可选乘车线路集合Un(n1,2...)中，找出Un和

nminMinUn

Usum 从而在Un和

线路； 线路 Min 线路 如果再将在 和 中所得的MinTn或MinCn分别进行比较，又可以得到截至 同时满足时间或费用要求的最佳线路，即得到了满足在换乘次数不超过n的前提下，时间最少或费用最少的最佳路线，这里称之为全局最优解BestMinTkBestMinCk;nMinn

nMinnMin

线路 或n或Min

最佳路线 线路BestMinTkBestMinCk。当然，随着n的增大，所得可以选乘的线路集合Un中元素个数也随之增大，求解复杂程度也随之增大。结合实际3次的人群是较小的人群，所以这里取n2。模型一（公汽系统换乘模型（1）S3359-最佳线路（时间：101；费用L436L16711L217最佳线路（时间：64；费用下,L352下,L336L4852下L485L485（2）S1557-最佳线路（时间：106，费用L084L189L4602L363（3）S0971-最佳线路（时间：128；费用L0131最佳线路（时间：103；费用L013L290L4692（4）S0008-最佳线路（时间：83；费用L463L0571L355L345L159L058L464L474最佳线路（时间：67；费用L043L290L3452（5）S0148-最佳线路（时间：106；费用2L308L156L41722（6）S0087-最佳线路（时间：65；费用L454L2091最佳线路（时间：46；费用L021L231L0972L021L462L206L097L206L462L454L097L454L462模型二（系统换乘模型LLx|x12,...520的搜索；LLx|x12,...520中，用模型一的求解方法，同样可以求得模型二中的可以选乘的线路集合Un，进而结（1）S3359-线路（时间：84.5；费用L015L0413（2）S1557-线路（时间：116.5；费用L084L5162（3）S0971-线路（时间：96；费用L094L0512L104L395L450L469L119L051L104L395L450L469（4）S0008-线路（时间：53.5；费用L200L1033（5）S0148-线路（时间：87.5；费用L24L0512L104L395L450L469（6）S0087-线路（时间：20；费用0模型评优点分Mathematica对站点集合的搜索；LLx|x1,2,...520共同构成一个新的集合，再利缺点分nn大，算法的求解复杂度也越发的大，当n超过3时，求解可以选乘的线路集合Un的模型扩所以我们的模型不仅仅局限于解决系统中最佳路线选择问题，还可以推广到与各种问题三的回问题分行时间不能太久，在这里假设限制最大的步行时间为t。由于有了步行的机动性，大模型假

到Send的步行时间小于t的站点S的集合（包括Send）F(S1S2)步行从S1到S2Lx(S1S2)乘直达车从S1到S2模型建F(Sstart,S)Lx(S,Send (先步行再乘车 在满足SSet1且S与Send之间有直 车的情况下S为离

SLineL ，S)F(S, )(先乘车再步行)...............在满足SSet2且start S

车的情况下S为离

其它情模型求步1：判断Sstart到Send之间是否可以乘车直达)否则，转步2；相应取非空的Set1