2016数学建模停车策略论文

1自动泊车系统数学建模【摘要】随着汽车产业及科技的高速发展，智能驾驶汽车成为了国内外公认的未来汽车重要发展方向之一。而在汽车智能化进程中，自动泊车是一项非常具有挑战性和实用性的技术。自动泊车系统可通过各类传感器获取车位相对汽车的距离，通过控制汽车前轮转角和瞬时速度控制车辆行驶。若考虑系统控制容易性，参考人工倒车入库，当车辆位于与车位垂直的任意位置时，先通过前行或后退到达理想停车起始点后，再确定前进转角和后退转角，使车身与车位在同一直线上后，直接倒车完成入库，即“一进二退”。这种两段式倒车模式提高了泊车过程中车辆行驶的紧凑性，同时减少了泊车行驶空间。考虑奇瑞汽车公司的QQ3，长3550mm，宽1495mm，轴距2340mm，前轮距1295mm，后轮距1260mm，目标车库为小型汽车库标准大小长6m，宽2.8m，车库周围情况如图。关键字：转乘次数广度优先算法查询效率实时系统一问题的重述1)建立模型，按照车辆与车位之间的距离把车辆位置进行分组，给出每一组对应的倒车理想起始点，a=400mm，b=8000mm，c=300mm。2）建立模型，给出由理想起始点到倒车入库的泊车策略，包括车速、前轮转角、后轮行驶距离。二符号说明iL：第i条公汽线路标号,i=1,2…10400,当i520时,iL表示上行公汽路线,当i520时,iL表示与上行路线i520L相对应的下行公汽路线；i,gS：经过第i条公汽路线的第g个公汽站点标号；jT：第j条地铁路线标号,j=1,2；j,hD：经过第j条地铁线路的第h个地铁站点标号；2nLS：转乘n次的路线；kT：选择第k种路线的总时间；kN1：选择第k种路线公汽换乘公汽的换乘次数；kN2：选择第k种路线地铁换乘地铁的换乘次数；kN3：选择第k种路线地铁换乘公汽的换乘次数；kN4：选择第k种路线公汽换乘地铁的换乘次数；k,mW：第k种路线、乘坐第m辆公汽的计费方式，其中：k,mW1表示实行单一票价，k,mW2表示实行分段计价；k,mCL：第k种路线，乘坐第m辆公汽的费用；kC：选择第k种路线的总费用；kmMS，：选择第k种路线，乘坐第m辆公汽需要经过的公汽站个点数；k,nMD：选择第k种路线，乘坐第n路地铁需要经过的地铁站个点数；k,mFS：表示对于第k种路线的第m路公汽的路线是否选择步行，k,mFS为0-1变量，k,mFS0表示不选择步行，k,mFS1表示选择步行；k,nFD：对于第k种路线的第n路地铁的路线是否选择步行，k,nFD为0-1变量，k,nFD0表示不选择步行，k,nFD1表示选择步行；3三模型假设3.2其它假设10、查询者转乘公交的次数不超过两次；11、所有环行公交线路都是双向的；12、地铁线T2也是双向环行的；13、各公交车都运行正常，不会发生堵车现象；14、公交、列车均到站停车四问题的分析对于路线的评价，我们可以分别以总行程时间，总转乘次数，总费用为指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。而最优路线则应是总行程时间最短，总费用最少或总转乘次数最少，或者三者皆有之。之所以这样考虑目标，是因为对于不同年龄阶段的查询者，他们追求的目标会有所不同，比如青年人比较热衷于比赛，因而他们会选择最短时间内到达奥运赛场观看比赛。而中年人则可能较倾向于综合指标最小，即较快、较省，转乘次数又不多。老年人总愿意以最省的方式看到奥运比赛。而对于残疾人士则总转乘次数最少为好。不同的路线查询需求用图4.1表示如下：图4.1公交线路查询目标图经分析，本问题的解决归结为一个求最短路径的问题，但是传统的Dijkstra最短路径算法并不适用于本问题，因为Dijkstra算法采用的存储结构和计算方法难以应付公交线路网络拓扑的复杂性,而且由于执行效率的问题，其很难满足实时系统对时间的严格要求。为此我们在实际求解的过程中，采用了效率高效得广度优先算法，其基本思路是每次搜索指定点，并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空。此方法在后文中有详细说明。五建模前的准备为了后面建模与程序设计的方便，在建立此模型前，我们有必要做一些准备工作。5．1数据的存储由于所给的数据格式不是很规范，我们需要将其处理成我们需要的数据存储格式。从所给文件中读出线路上的站点信息，存入txt文档中，其存储格式为：两行数据，第一行表示上行线上的站点信息，第二行表示下行线的站点信息，其中下行路线标号需要在原标号的基础上加上520，用以区分上行线和下行线。4如果上行线与下行线的站点名不完全相同，那么存储的两行数据相应的不完全相同，以公交线L009为例：L009:373903591477215923772211248224803439192019210180202030272981L529:298130272020018019211920343934402482221123772159147803593739L529为L009所对应的下行线路。如果下行线是上行线原路返回，那么存储的两行数据中的站点信息刚好顺序颠倒，以公交线路L001为例：L001:061919140388034803920429043638853612081935240820391401280710L521:071001283914082035240819361238850436042903920348038819140619如果是环线的情况（如图5.1所示），则可以等效为两条线路:顺时针方向：S1→S2→S3→S4→S1→S2→S3→S4；逆时针方向：S1→S4→S3→S2→S1→S4→S3→S2。经过分析，此两条”单行路线”线路的作用等同于原环形路线图5.1环行线路示意图以环形公交线L158为例，此环形路线存储数据如下：L153:534649235512128121711708112600172158581426435131215121725126042606534649235512128121711708112600172158581426435131215121725126042606L673:534260626042511217121535132648141585172260081117017181212122355649534260626042511217121535132648141585172260081117017181212122355649在这里，L153被看作成上行路线，L673被当成下行路线。这样对于每条公交线路都可以得到两行线路存储信息。六模型的建立与求解6．1模型一的建立该模型针对问题一，仅考虑公汽线路，先找出经过任意两个公汽站点i,gS与5ººig,S最多转乘两次公汽的路线，然后再根据不同查询者的需求搜寻出最优路线。6．1．1公汽路线的数学表示任意两个站点间的路线有多种情况，如果最多允许换乘两次，则换乘路线分别对应图6.1的四种情况。该图中的A、B为出发站和终点站，C、D、E、F为转乘站点。图6.1公汽路线图对于任意两个公汽站点i,gS与ººig,S，经过i,gS的公汽线路表示为iL，有i,giSL；经过ººig,S的公汽线路表示为ºiL，有ºººigi,SL；1）直达的路线0LS（如图6.1（a）所示）表示为：ºº0i1i,gi1i1ig,LSLSL,SL2）转乘一次的路线1LS（如图6.1（b）所示）表示为：ºº1i1i2i,gi1i10i1i2i2i2ig,LS(L,L)SLSLL,LLS;SCLSCL,;且其中：SC为i1L，i2L的一个交点；3）转乘两次的路线2LS（如图6.1（c）所示）表示为：2i1i2i3i,gi1i1i3i3i2i1i2i2ig,LS(L,LL)SLSLL,L),(L,L)(L,L)L11，,；(LS；S通过以上转乘路线的建模过程，可以看出不同转乘次数间可作成迭代关系，进而对更多转乘次数的路线进行求寻。不过考虑到实际情况，转乘次数以不超过2次为佳，所以本文未对转乘三次及三次以上的情形做讨论。6．1．2最优路线模型的建立找出了任意两个公汽站点间的可行路线，就可以对这些路线按不同需求进行选择，找出最优路线了:1）以时间最短作为最优路线的模型：行程时间kT等于乘车时间与转车时间之和。°N11kk,mkm1kkMinT3(MS1)5N1m1,2,,N11;k1,2,,kgggggg（6.1式）6其中，第k路线是以上转乘路线中的一种或几种。2）以转乘次数最少作为最优路线的模型：kMinN1（6.2式）此模型等效为以上转乘路线按直达、转乘一次、两次的优先次序来考虑。3）以费用最少作为最优路线的模型：kk,mmMinCCL（6.3式）其中，k,mk,mk,mk,mk,m1W1W2,202W2,40CL3W2,k,mk,mk,m或0MS21MS40MS（6.4式）6．1．3模型的算法描述针对该问题的优化模型，我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索出最优路线。现将此算法运用到该问题中，结合图6.2叙述如下：（该图中的i,gS、ººig,S、1,1S、2,1S、2,2S表示公汽站点，1L、2L、3L、4L、5L、6L表示公汽线路。其中（a）、（b）、（c）图分别表示了从点i,gS到点ig,S直达、转乘一次、转乘两次的情况）图6.2公交直达、转乘图（1）首先输入需要查询的两个站点i,gS与ººig,S（假设i,gS为起始站，ººig,S为终点站）；（2）搜索出经过i,gS的公汽线路iL（i=1,2,…,m）和经过ººig,S的公汽线路ººiL(ºi=1,2,…，n)，存入数据文件；判断是iL与ºiL是否存在相同路线，若有则站点i,gS与ººig,S之间有直达路线(如图6.2中的1L)，则该路线是换乘次数最少(换乘次数等于0)的路线，若有多条直达路线，则可以在此基础上找出时间最省的路线；这样可以找出所有直达路线，存入数据文件；（3）找出经过i,gS的公汽线路iL(如图6.2中的2L)中的另一站点i1,g1S和经7过ººig,S的公汽线路ººiL中的另一站点ºº11ig,S。判断i1,g1S与ºº11ig,S中是否存在相同的点，若存在(如图6.2中的1,1S)则站点i,gS与ººig,S间有一次换乘的路线(如图6.2中的2L与3L)，该相同点即为换乘站点；这样又找出了一次换乘路线，存入数据文件；（4）再搜索出经过iL(如图6.2中的4L)线路上除了站点i,gS的另一站点i2,g1S(如图6.2中的2,1S)的公汽线路i6L(如图6.2中的6L)，找出公汽线路i6L上的其他站点i2,g2S；判断，如果i2,g2S与经过ººig,S的公汽线路ººiL中的其他站点ºº22ig,S存在相同的点(如图6.2中的2,2S)，则i,gS与ººig,S间有二次换乘的路线(如图6.2中的4L、6L、5L)，该相同点和点i2,g1S是换乘站点；将此二次换乘的路线存入数据文件中；（5）对上述存储的经过两个站点i,gS与ººig,S的不同路线，根据不同模型进行最优路线进行搜索，得出查询者满意的最优路线。6.1.4模型一的求解起始站S3359到终到站S1828的最少费用为3元，最少费用的最优路线（所需时间较短，转乘次数较少的路线）有30条，其中28条路线所需时间为64min，转乘次数为2次，另外两条路线所需时间为101min，转乘次数为1次；起始站S1557到终到站S0481的最少费用为3元，最少费用的最优路线有2条，所需时间为106min，转乘次数为2次；起始站S0971到终到站S0485的最少费用为3元，最少费用的最优路线有3条，其中两条所需时间为106min，转乘次数为2次，另外一条所需时间为128min，转乘次数为1次；起始站S0008到终到站S0073的最少费用为2元，最少费用的最优路线有9条，所需时间为83min，转乘次数为1次；起始站S0148到终到站S0485的最少费用为3元，最少费用