赛题精讲2007高教社杯全国生数学建模竞赛

2007高教社杯大学生数学建模竞赛区评阅编号（由赛区评阅前进行编号赛区评阅记录（可供赛区评阅时使用统一编号（由赛区送交前编号评阅编号（ 评阅前进行编号乘客线路最佳选择问题 本文通过对不同乘坐人群的需求进行分析，得出影响路线选择的三（1（2，最少时间模型（3广进优先的搜索算法，并用7.2进行编程（语句见附录3）求解。后来又46组起始站→终到站之间的最佳路线对模型进行了验证，求得结果（1应的结果（2络问题变成了一个类似于网格线的最短路径问题对三种出行方式的三个因规划模型。最后利用c语言编程对一对起始站→终到站之间的最佳路线问题求：优化模型短路径模型广义公汽虚拟公汽多目标规划模一、问题重1、问题背，第29届奥运会明年8月将在举行，届时将有大量观众到现场奥运 市的线路已达800条以 ，相邻公汽站平均行驶时间(包括停站时间)3相邻地铁站平均行驶时间(包括停站时间)：2.5公汽换乘公汽平均耗时 5分钟(其中步行时间2分钟地铁换乘地铁平均耗时 4分钟(其中步行时间2分钟地铁换乘公汽平均耗时 7分钟(其中步行时间4分钟公汽换乘地铁平均耗时 6分钟(其中步行时间4分钟票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）（见数据文件B2007data.rar）3、要解决的问上述问题是线路选择的模型与算法，具体要求如下 (4)、 (5)、 二、定义和符号si：表示第i个公汽站点，其中iSsii：表示所有公汽站点集lj；表示第jjLljj：表示所有公汽路线集合Tk：表示地铁线路，其中kdn：表示地铁站点，其中nDdnn：表示所有地铁站点集t1：表示相邻公汽平均行使时间t2：表示相邻地铁站平均行使时t3：表示公汽换乘公汽平均耗时t4：表示地铁换乘地铁平均耗时t5：表示地铁换乘公汽平均耗时t6：表示公汽换乘地铁平均耗时三、问题分换车次数，是指乘客在完成一次出行过所换车的次数四、基本假公众出行不借助其他交通工具，只考虑和步行的组五、模型建立与数据预处问题一的模问题分基本模型的建给定起点s0和讫点sd，可行的路径集合为

s0,li1,si1,li2,si2,..lij..,lin,sin,

,i1...k,j TRis0选择路线li1到达si1，换乘li2到达si2，……，最终到达sd，ks0sd总路径数，lij表示第i条路径的第j条路线，ni表示第i条路径的线路个数Si表示第i条路径经过的总站数Pi表示第i条路径的总花费。xi，当走第ixi＝1xi＝0 1、最小换乘次数优化模

kk

(ni1)*

（1） 0第i条路线没有被

kkxi2、最小乘车费用优化模仅考虑路径集合TR中的乘车费用Pi，设0－1变量yij来表示路线lij是sij经过的站点数为mij

kk

P1mij*y

，其中”代表取整运算

20 （2）yij0,1 第i条路线被选取 k0第i条路线没有被kxi13、最小时间优化仅考虑路径集合TR中的时间消耗，设第TRi条路径的时间为Ti，建立目Ti5ni

kk

kkxi模型的改1为例进行分析如下：n01k1 0ii d TR'TR'TR's,l',s',l',s',..l'..,l',s', ,i1... 0ii d TRs选择路线l's'，换乘l'到达s'，……，最终到达s，k i i ss总路径数l'表示第i条路径的第j SiiPii条路xi，当走第ixi＝1xi＝0。最小换乘－最小费用模0－1y'来表示路线l'y' 否则y'＝0；并设在路线l'上 到s'经过的站点数为m'。建立目标函数为

i(j P1P1

ijij*

11i

y'x k0第i条路线没有被选kxi'其中”代表取整运算最小换乘－最小时间模设第TR'i条路径的时间为Ti'

kk

T'i*xix k0第i条路线没有被选kxi'模型的算法实模型1、2、3用基于广进优先的搜索算法进行编程处理步骤如下：1s0sd。步骤2：对总的线路矩阵整体检索，经过初始站点s0的线路存为X(i)(i1,2, )，并将其经过初始站点s0后，可以到达的站点si存入Q。经过目站点sd 线路存为Y(i)(i1,2, siP3：判断S中是否存在wi就是目的站点sdwiX(i入Ｚ。若Ｚ不为空，则线路X(i)即为从s0到站点sd的直达线路。这些线路4P和Q取交集，将满足条件站点的存入Ｗ，若WW中的站点mii,,,|)在Xi)中对应的线路和mi)在Y(i)中对应的线mi)就是其中的中转站。路Xi)mi)Yi)作为备选的目标方案。5Psj2sj它的线路Z(i)(i1,2,3,)和经过站点sj后，线路可以到达的站点的集合R。步骤6：对RP取交集，将满足条件的站点存入Ｗ，若W不为空，则W中的站点si在Z(i)中对应的线路和si在Y(i)中对应的线路就是从sj点到的站点的换乘一次的线路，sisjX(iX(isjZ(isi

步骤7R重复步骤56，可以的得到换乘三次的线路：X(isjZ(isiF(iskY(i，作为备选的目标方案。X(isjZ(isiF(iskE(ist Y(i)步骤10：以上步骤如果没有得到最优的线路方案，则可能有多条线路的；模型的推由于数据量太大，利用运行时间太久，则考虑图论中的最小路径，利用c语言编程来对模型进行优化。4、最短路径模此网络可以抽象成有向赋权图的形式G(S,E,Re,W其中G为网络的有向赋权图；S为网络中所有站点的集合；E为连接相邻两个站点之间路段的集合；Re为经过路段e的线路集合；W为边的非负权值（耗费时间c语言构造标记算法如下：G（V，E其中 cost时间耗费 //地铁线路为2.5公汽线路为3，特殊线路为4，6，7num车次号 //公汽线路为0-10392、搜索换乘次数小于maxnm,max，起始站点为src，目的站点为des定义二维数组其中opt[i][j]表示有车次j到达站点i，所需的最小换乘次数定义二维数组Parent[n+1][m+1]；其中parent[i][j]记录车次j到达站点i的前驱，方便到达目的车站后通过对optFori0toForj0toopt[i][j]INFForj0tom即 pre）st表示当前站点，pre表示到达该站点的车次号，若当前站点为起始站点src，则pre=-1；设P1（st1，pre1）st1=desparent路st1e(st1,d,cost，num)pre1！=num，则new=opt[st1][pre1]+1,否则new=opt[st1][pre1];new<max,则P2（d，num）入队，且记录parent[d][num]的前驱（st1，pre1模型的验下面利用求解始发站－终点站分别为(1)、S3359→S1828 (6) 对于模型1、2、3利用编程（见附录1）求解得到如下最佳路径：由于数据量太大，则在此仅列出“优先换乘兼顾时间”和“优先换乘 线路注释 148→L308上行→302→C→S4003→T1→4021 466 L51上行 开头字母SL× →L308 “L308上行 →302”表示乘公汽上行路线L308到达站点302转乘；“541→C→ 540”表示从站点541 经过地铁站到达站点540，但不乘坐“302→C→ →T130240031、优先换兼顾时（1）终点站12始发S3359→L436（下行）→S1784→L167（下行2始发S3359→L436（下行 始发 终点站最小换乘次 3始发S1557→L84（下行）→S1919→L189（下行）→S3186→L460（下行）→始发 终点站最小换乘次 2始发S0971→L13（下行 （4）8终点站12始发S0008→L159（下行）→S2683 线路22始发 （5）终点站23始发S0148→L308（上行）→S0036 →L156（上行）→S3351→L417（下（6）终点站12始发S0087→L454（上行）S3496→L209（下行2、优先换 兼顾费始发 终点站最小换乘次 费用 耗费时间始发S3359→L436（下行）→S1784 线路22始发S3359→L436（下行 始发 终点站最小换乘次 3始发S1557→L84（下行）→S1919→L189（下行）→S3186→L460（下行）→始发 终点站最小换乘次 2始发S0971→L13（下行）→S0992→L201（上行始发 终点站最小换乘次 2始发S0008→L159（下行）→S2683 线路22始发S0008→L159（下行）→S2559→L464（上行2始发S0008→L159（下行）→S3053→L474（上行2始发S0008→L355（下行）→S2263→L345（上行始发 终点站最小换乘次 3始发S0148→L308（上行）→S0036→L156（上行）→S3351→L417（下行→始发 终点站最小换乘次 2S0087→L454（上行）→S3496→L209（下行乘次数乘车时间乘车费用”表示先搜索换乘次数最小的所有路径，在此范围问题二的求问题分无花费，公汽有单一票制和分段票制之差；两种方式的票价不同；地铁只有转化模L520其上站点也相应的标记成SD01标记为S4001。对于地铁站点和公汽站点有联系的，虚拟出一条公汽路线，且此路线上的公汽不，D01到S0567换乘情况，可以虚拟公汽L523D01、终点站为虚拟公汽的不情况按照单一票制为0处理。T11040，T11041；T21042，各地铁站设为num为一个特定的值k，用以和其他普通边区别。下面利用求解始发站－终点站分别为(1)、 (2)、(3)、S0971→ (4)、S0008→ (5)、S0148→ (6) 利用c优先换乘兼顾时起始 终点站最小换乘次 费用2耗费时间1012S3359→L436（下行 →L217（下行起始 终点站最小换乘次 费用3耗费时间106起始 终点站最小换乘次 费用2耗费时间83起始 终点站最小换乘次 费用2耗费时间83费用2耗费时间83费用2耗费时间83费用2耗费时间83起始 终点站最小换乘次 费用3耗费时间109起始 终点站最小换乘次 费用2耗费时间49问题三的求问题分模型的建 TRTRiTRis0,li1,si1,li2,si2,..lij..,lin,sin,sd,i1...k,j TRis0选择路线li1到达si1，换乘li2到达si2，……，最终到达sd，ks0sd总路径数，lij表示第i条路径的第j条路线，ni表示第i条路径的线路个数，则该的转乘次数qi为ni－1，Si表示第i条路径经过的总数，tiipii0－1yij表示路线lijyij＝1yij＝0；并设在路线lijsij1sij经过的站点数为mijxii条路径时，xi＝1，否则xi＝0

(titqiqpipTi5qi

kkktk

1/S1(tt)2 qikkkqk

1/S1(qq)2 P1mij*yi

20 yijkkkpk

1/S1(pp)2 0第i条路线没有被kkxi其中q0为转乘次数上限根据具体情况可以给它赋不同的值而一般情况下转次数不会超过4次，为了不出现转乘次数均相等的情况，指定q0＝6模型验S3359→S1828，设定乘车费用、乘车时间和换乘次数的权重之比为7327：2：110111：2：710112六、模型的评模型的优本问题的参量很多而且不同工具的参量取值不同，利用开关变量0－1进行处理，既清晰又简明。从问题一、二、三的求解过程说明算法的适用性很好模型的缺七、参考文[1]，数学模型.：高等教育[2]，运筹学及实验.广州：华南理工[3]贾，技术经济学.修订版.长沙：中南工业大学[4]，数学实验讲义及上机指导.长沙：中南大学数学科学与计算技术学[5]，及其在理工课的应用指南.西安：西安电子科技大学，2000八、附附录优先时间（1）始发站 终点站最小时 换乘次数 费用始 →L15下 → → 上 → 下 → →L27环 → → 换乘次 费始 →L15下 → → 上 →L480 →2704 →1784 →L217 （2）最小时 换乘次数 费用始 L84→→→→L91上 903→→始 →L84→→→→L91→903→始 →L84→→→→L91→903→（3）终点站最小时 换乘次数 费用始 971→L13下 → →L27环 → →下 → →L41下 换乘次数 费用始 971→L13下 → →L27环 → →下 → → 下 换乘次数 费用始 971→L13下 → →L27环 → →下 → →L236下 始发站 终点 最小时 始 →→→L17→→上 →525 上 →始发站 终点站最小时 换乘次数 费用始 148→ 上 → → 上 → 下 始发站 终点 最小时 换乘次数 费用 →L21上行 →1427 →L381 →427→L97上行→ 始 →→→→→→4（1）最小时 换乘次数 费用始 →L15下 → → 上 → 下 → →L27环 → → →L15→→→→→→L27（2）→→终点站最小时 始 →L84→→→→L91上行2→903→→→L84→→→→L91→903→→换乘次数 费用始 L84→→→ L91上 903→（3）最小时 始 →L13→→L27→→→→L41→始 →L13下 →L27→→→ →（4） 终点站最小时 换乘次数 费用始 → 下 → →L17环 →604→上 →525→ 上 （5）始发站 终点 最小时 始 →→→→→→始 →→→→→→（6）最小时 换乘次数 费用 →L21上行 →1427 →L381 →427→L97上行→ 始 →L21→→→427→5（1）始 → 下 → → 下 →换乘次数 耗费时间始 → 下 → → 下 →（2）始 →L84→→→ →（3）始 →L13→→→（4） 始 → 下 → →L58下 →换乘次数 耗费时间始 → 下 → → 上 →换乘次数 耗费时间始 → 下 → → 上 →换乘次数 耗费时间始 → 下 → → 上 →始发站 终点站1换乘次数 耗费时间始 148→ 上 → → 上 → 下 →始发站 终点站1始 →→→→6（1）换乘次数 耗费时间始 → 下 → → 下 →换乘次数 耗费时间始 → 下 → → 下 →始发站 终点站1换乘次数 耗费时间始 →L84→→→ →（3）始 →L13→→→（4） 始 → 下 → →L58下 →换乘次数 耗费时间始 → 下 → → 上 →换乘次数 耗费时间始 → 下 → → 上 →始发站 终点站1换乘次数 耗费时间始 148→ 上 → → 上 → 下 →始发站 终点站1换乘次数 耗费时间始 → 上 → → 下 →（2）1优先换乘（1）起始站 终点站最小换 S →→→→S →→→→（2）最小换 3耗费时间 →L84下 → → 下 → （3）971最小换 2耗费时间 971→L13下 →992→ 上 →起始站 终点站最小换 S →→→→S →→→→S →→→L58→S →→→→（5）148最小换 3耗费时间 148→→36下 （6）87终点站最小换 2耗费时间S→→541C540 2优先换乘兼顾费用（1）最小换 2耗费时间 → 下 → → 下 →2耗费时间（2）最小换 3耗费时间 →L84（2）最小换 3耗费时间 →L84 （3）971最小换 2耗费时间→ → 下 → 971→L13下 →992→ 上 →起始站 终点站最小换 S →→→→S →→→→S →→→L58→S →→→→起始站148终点 最小换 3耗费时间 148→ 上 →36→ 下 下 起始站 终点 最小换 S87→→541C540上行2耗费时间 →时 兼顾换→→→36763优先（1）最小时 终点站4费用 →→→→L27S→→→→ L27（2）最小时 终点站3费用 →L84下行 →1919 →L189 →3186L91上行 3费用 →L84下行 →1919 →L189 →3186L91上行 3费用 →L84下行 →1919 →L189 →3186L91上行 971终点站最小时 →L13→→→ →L13→→→（4）8 971→L13下 →（4）8最小时 3费用（5） → 下 →（5）最小时 换乘次数2费用 148→ 上 →302→ 466L51上 2费用 148→L308 →302→C →T1 464L469 2费用 148→L308 →302→C →T1 464L395 （6）起始站 终点站最小时 、1费用 87→L21上 →C→C优先时间（1）起始站 终点站最小时 4费用 →L15下 → → 上 下 L27环 下 4费用S→→→→ L27（2）最小时 终点站3费用S→L84→→→L91上 上 3费用 →L84下行 →1919 →L189 →3186L91上行 3费用L91（3） →L84下L91（3）最小时 3费用 971→L13下 → →L27环 → 3费用 971→L13下 → →L27环 → 下 下 3费用 971→L13下 → →L27环 → （4）8最小时 3费用 → 下 → →L17环 → （5）最小时 →→→C→CL51 →→→C→C换2 148→ →→C→C464 （6）起始站 终点站最小时 1费用 87→L21上行 →1427 →C →T2 优先费用（1）起始站 终点站最小花 1耗费时间 → 下 → → 下 →18281耗费时间 → 下 → → 下 →（2）起始站 终点站最小花 2耗费时间 →L84下行 →1919 →L189 →L84下 → → 上 （3）971最小花 1耗费时间 971→L13下 →992→ 上 （4）→L13下 终点站→→最小花 →→→→ →→→→ →→→L58→1耗费时间 → 下 → → 上 →148终点站最小花 →→→→（6） 最小花 1耗费时间 87→ 上 →541→ 540→ （1）起始站 终点 最小花 1耗费时间 → 下 → → 下 换乘次数 耗费时间S→→→→（2）起始站 终点最小花 换乘次数 耗费时间 →L84→→→ 下 （3）971终点站最小花 1耗费时间 971→L13下 →992→ 上 （4）起始站 终点 最小花 →→→→ →→→→ （5）→ 148终点站→→下 →最小花 4耗费时间 148→L308 →36→L156 起始站 终点 最小花 1耗费时间 87→ 上 →541→ 540→ 2耗费时间 87→ 上 →541→ 540→ 程序forforifstrcmp(a(n,m),'')elseififk==1&strcmp(a(n,m+1),'')elseifk==1&~strcmp(a(n,m+1),'')forifstrcmp(a(n,j),'')forg=1:1:k-ififyy(1,k)=j-forifstrcmp(a(n,j),'')forg=1:1:k-ifstrcmp(a(n,j),p(g))ifyy(1,k)=j-

forx=1:1:qforforifstrcmp(a(n,m),'')elseififk==1&strcmp(a(n,m+1),'')elseifk==1&~strcmp(a(n,m+1),'')forifstrcmp(a(n,j),'')forg=1:1:k-ifstrcmp(a(n,j),d(g))ifforifstrcmp(a(n,j),'')forg=1:1:k-ifstrcmp(a(n,j),d(g))if

forforifstrcmp(a(n,m),'')elseifstrcmp(a(n,m),s2)ifk==1&m==1elseifif~strcmp(a(n,1),'上行')&~strcmp(a(n,1),'下行环行

elseifk~=1&m~=1forj=1:1:m-1forg=1:1:k-ifstrcmp(a(n,j),e(g)) flag==1&~strcmp(a(n,j),'上行')&~strcmp(a(n,j),'下行')&~strcmp(a(n,j),'环行y(1,k)=m-

forj=1:1:m-1forg=1:1:k-ifstrcmp(a(n,j),e(g)) flag==1&~strcmp(a(n,j),'上行')&~strcmp(a(n,j),'下行')&~strcmp(a(n,j),'环行y(1,k)=m-

form=1:1:fforifstrcmp(d(m),e(n))ift<ssifchehao3(1)=a(y(2,n)-

ifchehao2(1)=a(z(2,m)-

ifchehao1(1)=a(yy(2,x)-

elseifif

ifchehao2(i)=a(z(2,m)-

if

C语言程序：#include<iostream>#include<sstream>#include<vector>#include<algorithm>usingnamespacestd;#defineMAXN #defineMAXM1300#defineINF#defineCIS1199struct{intintnum;doublecost;struct{intintvector<PATH>adj[MAXN];intv[MAXN][MAXM];intinttype[MAXN];intTT[MAXN];pair<int,int>parent[MAXN][MAXM];structLINE{vector<pair<int,int>>vp;intcchange;inttime;intvector<LINE>intN,M;N站点数，Mintmaxcost,mincost;voidinit()charline[10000];intnum=0,st;intfor(intstringstreamios(line);stringtt;stringstreamis(line);}stringstreamiis(line);voidback(inta,int}}voidcacl(intsrc,int{doublefor(intelseif(line.vp[i-1].second<4000&&line.vp[i].second>4000)elseif(line.vp[i-1].second>4000&&line.vp[i].second<4000)}else}

}

}for(int}}voidoutput(vector<pair<int,int>>{int{intinta=vp[i].second; %4d %4d",a);elseif(b/2+1==521) %4d",a);elseif(b/2+1==522) %4d{printf("L%3d",b/2+1);cout<<"elseif(TT[b]==1)cout<<"";cout<<"printf("%4d}boolcomp1(LINEl1,LINEreturnl1.time<l2.time;elseif(l1.cchange!=l2.cchange)returnreturn}boolcomp2(LINEl1,LINEreturnl1.cchange<l2.cchange;elseif(l1.cost!=l2.cost)return}

returnboolcomp3(LINEl1,LINEreturnelseif(l1.cchange!=l2.cchange)returnl1.cchange<l2.cchange;}

returnvoidinti,j;} cout<<"换乘次数"<<res[i].cchange}} cout<<"费用"<<res[i].cost}} cout<<"换乘次数"<<res[i].cchange}}intintsrc,des,i,j;{}intf=0,l=1;intkk=0; {intintpre=Q[f].pre;}intk=adj[st].size();{intintpn=adj[st][i].num;doublecost;intcchange;elseif(pn==pre||pn==CIS)}return

（5）C语言程序：#include<iostream>#include<sstream>#include<vector>#include<algorithm>usingnamespacestd;#defineMAXN#defineMAXM1300#defineINF#defineCIS1199struct{intintnum;doublecost;struct{intintvector<PATH>adj[MAXN];intv[MAXN][MAXM];intinttype[MAXN];intTT[MAXN];pair<int,int>parent[MAXN][MAXM];structLINE{vector<pair<int,int>>vp;intcch