乘坐公交车优化方案设计

乘坐公交车优化方案设计摘要在现实的生产活动中，最短路径的问题得到广泛的应用，比如印制电路板的钻孔路线方案、连锁店的货物配送路线，以及防控作战中火力单元的部署优化和空袭目标分配优化等，都可以转化为求最短路径，以实现成本最小、利润最优的目标。而公交线路的选择则是最基本、日常生活中最为常见的最优路径问题，本文从最基本的公交路线选择谈起，进而将其转为著名的货郎担问题（TSP问题）进行分析解决。一般来说，公交路线的选择主要考虑其快速、经济和方便的问题。由于公交车车费低廉，在本文的研究中不予考虑，而对于其方便程度和花费时间长短的问题，本文选择路程的长短来量化，在一系列合理假设的前提下，将公交路线的选择问题转为求解最短路径问题。对于事先已规定了顺序的最短路径问题，可直接利用图论的有关方法进行求解。如模型一，将长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街看作四个点，先将其简化为求任意两点之间的最短路径问题，然后将其连接起来，便可得最短路径，本文得到模型一的最短路径为长沙火车站（168）t市委t长沙市政府t毛泽东文学院（903）t望月湖小区（804）t后湖t中南大学新校区（202）t阜埠河路t牛耳教育南阳街口t黄兴路步行街t司门口（112）t长沙火车站，其中为标明公交线路的为步行。对于事先并未规定顺序的最短路径问题，即可将其转为TSP问题，如模型二，本文采取C-W节约算法求解该问题，C-W节约算法是一种启发式算法，对于n较大的TSP问题能够有效的解决，得到最短路径为长沙火车站t长沙市政府t中南大学新校区t黄兴路步行街t长沙火车站。最短路径的选择问题具有很重要的理论和实际意义。图论只能解决事先已规定了顺序的最短路径选择问题，对于TSP问题，则无能为力；而C-W节约算法则能有效的解决TSP问题，但其迭代效果有时并不显著，还需要进一步的研究和讨论；本文在模型的推广部分利用改进的遗传算法进一步分析和解决TSP问题。问题重述一公务人员从长沙火车站（五一路火车站）下车在一天时间内到如下地点：长沙市政府、中南大学新校区、黄兴路步行街办事，并回到长沙火车站（五一路火车站）。问题1.设计按如下顺序：长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型然后求解；问题2.设计从长沙火车站出发遍历如下地点：长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型然后求解。问题假设1、 在公交线路上所有车辆都能正常通行，不考虑诸如堵车、交通事故等意外情况；2、 公交车在公路上行驶速度处处相等；3、 为了方便的原则，换乘次数越少越好（有特殊情况亦可例外）；4、 由于乘坐公交车车费低廉，乘客不考虑价格因素；5、 不考虑公交车在各站的停车时间，即乘客上下车均在瞬间完成；6、 从距目的地最近的公交站点步行到目的地的路程忽略不计；7、 往返路程相等。规定说明将长沙火车站定为地点1，长沙市政府定为地点2,中南大学新校区定为地点3,黄兴路步行街定为地点4,地点5亦为长沙火车站。问题分析对于第一个问题，由于路线已经指定，只需考虑从每一个上一站到对应下一站的最佳线路。而这里的最佳线路的汇总，即模型的目标。目标函数的选择有很多种，但在上述假设的前提下，本题的目标函数显然则化为最短行驶路程。对于第二个问题，不考虑顺序，要求遍历每一个目标地点，最后回到出发点，是典型的运筹学中的“货郎担问题”，即带权的哈密尔顿回路问题。为使模型化简，已经假设从距目的地最近的公交站点步行到目的地的路程忽略不计，由此可以得到每两个地点之间的行驶路程，画出网络图，就可以按照C-W节约算法解决问题。模型的建立与求解问题一模型一的建立:定义总路程为L，地点i到地点i+1的路程为L 则总路程L=£L。由于Li=1之间相互独立，目标函数min(L)=£min(L)。若地点i到地点i+1的最小换乘次i=1数为k，换乘次数为k的路线有〃种，各个路线的路程分别记为L⑴,L(2),...,L(n)，ii i十己min(L)=min(L⑴，L⑵，…L(n))=L(m)，即第m个路线为最佳路线。L(m)被分为i ii i i ik+1段，每一段分别为L,j=1,...,k+1，^UL(m)=Z1L。按照L乘车，即为问J=1题一的求解。模型的一求解：根据网上公交线路的数据，任意两点之间只考虑直达或换乘一次的方案，这一点是合理的，一般来说考虑方便程度，换乘两次以上就显得相当麻烦，一般乘客都会放弃这种选择。这时可得两点的可选方案如图1所示。图1可选方案利用网上长沙公交查询，地点1到地点2可以直达，即换乘次数为0，而换乘次数为0的路线有两条：第一条，从长沙火车站乘坐168路公交车，在市委下车，步行全长沙市政府(步行路程忽略不计)，路程为11.19公里；第二条，从长沙火车站步行全蓉园路口，乘坐302路公交车，在市政府下车，路程为12.79公里。11.19<12.79，所以，min(L)=11.19，选择第一条路线。地点2到地点3,没有直达，至少换乘一次，换乘一次的路线有十条（在此不一一列举，具体路线见附录1），其中路程最短的为第一条，8.46公里：从长沙市政府步行至毛泽东文学院，乘坐903区间，在望月湖小区下车，然后乘坐804路公交车，在后湖下车，步行至中南大学新校区。地点3到地点4,在中南大学新校区的附近的站点有两个：后湖和阜埠河路。从后湖出发，可视为假设3的例外情况，因为乘坐804直达的路程为12.58公里，而乘坐63路公交车在新民学会旧址下车，再乘坐旅3路公交车在五一广场下车步行至黄兴路步行街的总路程仅为6.75公里，这两种路线相比，第二种换乘路线更佳；而从阜埠河路出发，可以直达，路程最短的为乘坐202路，在牛耳教育南阳街口下，步行至黄兴路步行街，路程为6.92公里。从后湖的换乘路线与从阜埠河直达的路线相比，路程差不多，当然是直达更佳。地点4到地点5,可以直达，路程最短的为从司门口乘坐112路公交车，为3.45公里，在长沙火车站下车即可。综上，最终得到的最佳路线如下：长沙火车站——市委—_＞长沙市政府＞毛泽东文学院——望月湖小区——后湖—_＞中南大学新校区—_＞阜埠河路——-牛耳教育南阳街口——＞黄兴路步行街——＞司门口——-长沙火车站。其中，箭头上未标明公交线路的为步行，黑体字为各目标地点。其路线图见图2：模型评价优点：此模型所运用的方法浅显易懂，同时又能把问题描述得很清晰，用它解决问题时操作简便。缺点：过于简单，不能很好的解决复杂的问题。问题二模型二的建立：这是一个带权的哈密尔顿回路问题，这个回路中有四个目的地，把每个目的地看成一个点，即长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街，首先需要知道每两点之间的距离，记第/个点与第j个点的距离为L，由假设7ij知L=L。为使模型简化，已经假设步行路程忽略不计，由问题一可得，L=11.19，L=8.46，L=6.92，L=3.45，另外由问题一的方法同理可得，L=10.99，L=10.54。以第一个点长沙火车站为基点，将基点与其他各点连接，构成子回路1-j-1(j=2,3,4，)这样就得到了具有3=4-1条子回路的图(这时尚未形成哈密尔顿回路)，即初始旅行图，如图3所示。图3 初始旅行图乘客按此线路所经过的路程总和等于L=2勇L1。若连接点z•和点jj=2(九j71)，即使乘客走弧(九j)时(这时当然就不再经过弧(•,1)和(1,j)),所引起的路程节约值S(•,j)可计算如下：S(•,j)=2L+2L-(L+L+L)=L+L-L (】)1• 1j 1•1j • H1j•对不同的点对(•,j)，s(•,j)越大，乘客通过弧(•,j)所节约的路程越多，因而应优先将这段弧插入到旅行线路中去。在具体应用上述方法时，可按以下迭代步骤进行。选取地点1为基点，将基点与其他各点连接，得到3=4-1条子回路1rjr1(j=2,3,4)。对不违背限制条件的所有可连接点对(九j)计算节约值(/,j不为基点)S(i,j)=L+L-L (2)将所有S(i,j)按其值由大到小排列。按s(i,j)的上述顺序，逐个考察其端点i和j，若满足以下条件，就将弧(i,j)插入到旅行线路中。其条件是：点i和点j不在一条线路上；点i和点j均与基点相邻。返回步骤(4)，直到考察完所以可插入弧(i,j)为止。通过以上迭代步骤，可使问题的解逐步得到改善，最后达到满意解或最优解。模型二的求解：已经算得各点之间的路程L，现将结果列入下表1中。由于假设L=L，可以看到该表中各元素的值以主对角线为对称。取地点1为基点，构成初始旅行线路图，如上图3。再用式(2)计算将弧(i,j)(i,j71)插入到线路中时引起的路程节约值，并按节约值由大到小的顺序将它们填入表2中。

表1各点距离表\全从地点1地点2地点3地点4地点1011.1910.993.45地点211.1908.4610.54地点310.998.4606.92地点43.4510.546.920表2节约值表依节约值从大到小的次序，对每条弧加以考察，看是否应将其插入线路中去。若将其插入，就要对线路作相应的改变。整个过程示于表3中。表3线路选择序号弧线路节约值01—2—1，1—3—1，1—4—11(2,3)1—2—3—1，1—4—113.722(3,4)1—2—3—4—17.52当插入弧（3,4）后，线路已包含所有要到达的点，算法终止。所以，用该方法得到的最终线路是：1T2T3T4T1如图4所示：图4 最终线路图即：长沙火车站-长沙市政府-中南大学新校区-黄兴路步行街-长沙火车站。该线路的总长度L=2x(L+L+L)-(S(2,3)+S(3,4))=2x(11.19+10.99+3.45)—(13.72+7.52)模型评价优点：这是一种启发式的算法，即使是不具有良性结构的实际问题也可以解决。与传统的方法相比，它不需要偏离事实，勉强使用某种标准模型，只需建立基本符合问题实际情况的非标准模型即可。这时，分析人员可以运用自己的感知和洞察力，去发现和构想可用于解决该问题的思路和途径，如此体现了人的主观能动作用和创造力，解决问题的方法比较灵活。它还有以下几个优点：计算步骤简单，易于实施。不需要高深和复杂的理论知识，因而可由未经高级训练的人员实现。与应用优化方法相比，常可以减少大量的计算工作量，从而显著节约开支和节省时间。易于将定量分析与定性分析相结合。缺点：运用此模型可以得到满意解，但不一定能得到最优解。6.模型的推广对于从长沙火车站出发遍历如下地点：长沙市政府、中南大学新校区、黄兴路步行街，最后回到长沙火车站的问题，将其简化，一般来说公交车的价钱不会太高，且乘客们在乘车过程中一般只会考虑其方便程度和时间问题，所以我们假设在乘车过程中乘客只考虑路程，不考虑金钱。这样，便可以将其推广全著名的货郎担问题（即TSP问题）：一个售货员从某一城市出发，访问n个城市各一次且仅一次，然后回到原城市，问他走什么样的路线才能使走过的总路程最短。TSP问题是组合优化问题中最典型的问题之一，并且是一个NP难题，TSP问题展示了组合优化的所有方面，它已经成为并将继续成为测试新算法的标准问题［2］，如模拟退火、禁忌搜索、神经网络以及进化方法等都用TSP来测试。彳艮多实际问题可以转化为TSP问题，如印制电路板的钻孔路线方案、连锁店的货物配送路线，以及防空作战中火力单元的部署优化和空袭目标分配优化等，所以解决TSP问题有很重要的理论和实际意义。本文对第二个问题采用的C-W节约算法对于n较小的TSP问题可以有效的解决，但对n较大的问题，我们采用遗传算法来进行分析。遗传算法解决TSP问题中一个难解决的问题是如何较快地找到最优解。为了保证遗传算法的全局收敛性，就要维持解群体中个体的多样性，避免有效基因的丢失。一、基本遗传算法1.1基本遗传算法的原理遗传算法（GA）是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、具有广泛适应性的搜索方法。GA搜索结合了达尔文适者生存和随机信息交换的思想，前者消除了解中不适应因素，后者利用了原有解中已知的知识，从而有力地加快了搜索过程。与传统搜索算法不同，遗传算法从一组随机产生的初始群（称为群体）开始搜索过程，群体中的每个个体是问题的一个解（称为染色体），这些染色体在后续迭代中不断进化（称为遗传）。遗传算法主要通过交叉、变异、选择运算实现。遗传算法对求解问题本身一无所知，它需要的仅仅是对算法所产生的每个染色体进行评价，并基于适就度值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式生成若干个求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群，再继续进化，这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。1.2基本遗传算法的求解步骤基本遗传算法的求解步骤如下：（1） 初始化种群；（2） 计算种群中每个个体的适应度值；（3） 按由个体适应度值所决定的某个规则选择将进入下一代的个体;（4） 按概率pc进行交叉操作；

按概率pm进行变异操作；若没有满足某种停止条件，则转到步骤(2),否则转到(7)；输出种群中适应度值最优的染色体作为问题的满意解或最优解。算法停止条件最简单的有如下两种：一是完成了预先给定的遗传代数则停止；二是种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。二、改进遗传算法在求解TSP问题上的应用2.1TSP问题简述旅行商问题(TSP)的数学描述是：给定n个城市的集合C={c1，c2,…，cn}，设％是城市ci和城市cj之间的距离，寻找一条经过所有城市(每个城市只能经过一次)的最短路径，使l=乂d「取最小值。i=12.2改进遗传算法设计及其在求解TSP问题上的应用2.2.1编码方案对城市采用顺序编码的方法，即染色体中每个元素代表一个城市的编号。例如染色体Si(2，3，1，5，4，7，6，8，9)代表了对9个城市进行编码过的染色体，它意味着从城市2出发，依次经过城市3,1，5,4,7,6,8,9最后回到出发城市2的一条路径。2.2.2适应度函数初始种群根据编码规则随机产生N个个体，将个体基因型解码为个体表现型，然后计算出个体的路径长度1(s)，记为li,贝UN-11(s)N-11(s)=£d+d.i=1个体s^的适应度定义为:1(s)j=1—i (s)j(4)「「0l<s)=<［门xmax(1)一1v ii〈小xmax(/) i=1,2,„,M (5)1<门xmax(1)式中：n为适应度系数；max(1)为本代个体的最大巡回距离。通过修改n可以调整选择压力，n=1时，最差个体适应度为0；当n<1时，对于l>nxmax(l)的个体s，其适应度等于0，在选择操作时将被淘汰。当n>1时，所有个体均有可能被复制到下一代。n越小选择压力越大，收敛速度也就越快，但是过大的选择压力容易导致算法早熟，通常取0.9<n<1.5。2.2.3选择算子为了使种群具有多样性，使算法收敛于全局最优解，该本文采用两种方法产生新一代种群，然后进行交叉和变异操作。一种是掺杂算子，其基本思想是在每代中随机产生m个新个体参与选择、交叉、变异操作。掺杂浓度为掺杂个体量与种群规模之比p,p一般就小于10%。m=Int(Nxp) (6)另一种是采用轮盘赌的方法从父代随机选择出N-Int(Nx(1-p))个个体进入新一代种群。每个个体被选中的概率为：p(s)=堂匚 (7)'寸f(s)jj=1轮盘赌方法的选择策略是首先随机产生一个随机数00，如果切p(s)<q<Zp(s)，则个体i+1被选入新种群。i 0 ik=1 k=1利用这两种方法产生新的种群，即保留了较优个体，又引入了新个体，使新的种群更具有多样性，这就扩大了求解空间，使算法收敛于全局最优解成为可2.2.4杂交算子杂交算子采用顺序交叉的方法，即随机产生两个整数c1和c2,c1和c2取值范围介于1和n之间。对两位置的中间数据进行交叉操作，如n=9,c1=2,c2=7,交叉前个体s和s是：s:42|67981|35s:47|36192|58交叉后是：s':42|36192|35:47167981158可以看出，交叉后同一个个体中出现了重复的城市，为了避免这个问题，提出了一种解决方案，即从S^中删除S.的cl和c2之间的城市编号，然后将S^中剩余的城市编号从s^的c2后边的位置开始填充，当填充到右边界时再从1位置开始填充；s.进行相似的操作，最终得到的新个体如下所示：S〃：85136192147S〃：251679811432.2.5基于近邻选择策略的变异算子近邻选择规则为：首先根据n个城市的坐标文件建立坐标系统对n个城市进行定位，并计算出两两城市之间的距离，形成一个nXn的距离矩阵A；对A的每一列按城市距离由小到大进行排序，并将排序后的城市距离用城市编号代替；最后删除最后一行（因为预设城市i到城市i之间的距离为无穷大，即不可达，所以排序后肯定在最后位置），形成一个（n-1）Xn的距离索引矩阵B。这样矩阵B中的第i列从第一行至第（n-1）行就是距城市i由近及远的城市编号排列。变异算子采用单位变异操作。首先产生一个随机数m1，指定D为常量，D是与某个城市i最近的D城市，可以从矩阵B的第i列取前D行即可，m1和D的取值范围是1与n之间;然后随机产生一个介于1与D之间的一个随机数m2,将m2置于个体s』勺m1之后从而产生新的个体。2.2.6精英策略因为选择策略是按轮盘赌方法和掺杂算子产生的，可能不会选中最优个体，而选择最差个体，所以为了保存成果，每一代经过选择、交叉和变异操作后都用最优个体代替最差个体，这就是精英策略，这样就可以保证改进的遗传算法具有全局收敛性，能够收敛于全局最优解。2.2.7改进遗传算法描述改进遗传算法描述如下：（1）设定遗传参数和常量D，计算距离索引矩阵B，随机生成种群P={s「S2,,Sj（2） 根据式（2）计算初始群体中个体的适应度值。（3） 根据设定的掺杂参数〃，按式（4）计算出要产生的掺杂个体数目，随机生成这些掺杂个体；按轮盘赌方法根据式（5）选择其他个体组成新的种群。（4） 根据设定的参数〃，进行交叉操作。（5） 根据设定的参数p，按照2.2.5的方法进行变异操作。（6） 利用精英策略，用本代最优个体替换最差个体。（7） 更新群体，用新种群替换父代种群。（8） 如果达到最大遗传代数或连续20代最优解没有发生变化则算法中止，输出最短路径及最短路径对应的染色体。否则转（2）。7.结论综上所述，本文对日常生活中最为常见的公交线路的选择问题进行了全面的分析和有效的解决。本文在对乘客进行公交线路的选择问题上进行了一系列合理假设的前提上，将其转化为最优路径的选择问题。而对事先已规定了顺序的最短路径选择，运用图论的有关知识予以解决，这里可进一步将其简化为任意两点间的最短路，然后将所有地点串连起来便可得到全局的最短路径。就本文研究的从长沙火车站出发，依次经过长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站的公交线路选择问题，运用图论的有关方法得到其最优路径选择：长沙火车站—市委—_＞长沙市政府—_＞毛泽东文学院—『望月湖小区—『后湖—_＞中南大学新校区—_＞阜埠河路—『牛耳教育南阳街口__＞黄兴路步行街—_＞司门口—j长沙火车站。对于事先已给出具体顺序的最短路径选择问题，在实际生活中的应用是屡见不鲜的，有些生产活动，必须以前一步骤的完成作为前提。而对于事先并未给出具体顺序，从基点出发，经过任意一点一次且仅一次，最后回到基点的问题，即著名的货郎担问题，本文采取C-W节约算法对其进行分析和讨论，并得到了公交线路的最短路径：长沙火车站T长沙市政府T中南大学新校区T黄兴路步行街T长沙火车站。图论的有关方法可以有效的解决事先已规定顺序的最短路径的选择问题，但对于地点较多的问题，使用起来会比较麻烦。而C-W节约算法是一种启发式算法，启发式算法对于解决TSP问题来说是很有帮助的，但也存在一些缺陷，对于其的应用，还有待进一步研究。遗传算法解决TSP问题中一个难解决的问题是如何较快地找到最优解，相对C-W算法能够有效的加快迭代速度。参考文献【1】胡运权，运筹学教程（第三版），北京：清华大学出版社，2007.4【2】蓝晓玲、周永权、韦修喜，求解TSP问题的社会演化算法，计算机工程与应用，2009年第26期【3】陶利民、郭俊恩，改进遗传算法在求解TSP问题上的应用研究，计算机工程与应用，2009年第33期附录公交线路：长沙火车站T长沙市政府线路1：长沙火车站乘坐168路在市委下车步行至长沙市政府路程：11.19公里线路2：长沙火车站步行全蓉园路口乘坐302路在市政府下车步行全长沙市政府路程：12.79公里线路3：长沙火车站乘坐118路在溁银桥下车乘坐903路区间在毛泽东文学院下车步行全长沙市政府路程：9.69公里线路4：长沙火车站乘坐117路在溁湾镇新外滩下车乘坐903路在毛泽东文学院下车步行全长沙市政府路程：9.71公里线路5：长沙火车站乘坐118路在望月湖下车乘坐903路在毛泽东文学院下车步行全长沙市政府路程：9.7公里长沙市政府t中南大学新校区线路1：长沙市政府步行至毛泽东文学院乘坐903路区间在望月湖小区下车乘坐804路在后湖下车步行至中南大学新校区路程：8.46公里线路2：长沙市政府步行至毛泽东文学院乘坐903路区间在溁湾镇下车步行全市四医院乘坐63路在后湖下车步行至中南大学新校区路程：9.23公里线路3：长沙市政府步行至毛泽东文学院乘坐903路区间在高叶塘溁湾路下车步行至高叶塘总站乘坐152路在后湖下车步行至中南大学新校区路程：10.21公里线路4：长沙市政府步行全市政府南乘坐903路在望月湖小区下车乘坐804路在后湖下车步行至中南大学新校区路程：9.2公里线路5：长沙市政府步行全市委乘坐168路在银盆岭