乘坐公交车优化方案设计

-1-乘坐公交车优化方案设计摘要在现实的生产活动中，最短路径的问题得到广泛的应用，比如印制电路板的钻孔路线方案、连锁店的货物配送路线，以及防控作战中火力单元的部署优化和空袭目标分配优化等，都可以转化为求最短路径，以实现成本最小、利润最优的目标。而公交线路的选择则是最基本、日常生活中最为常见的最优路径问题，本文从最基本的公交路线选择谈起，进而将其转为著名的货郎担问题（TSP问题）进行分析解决。一般来说，公交路线的选择主要考虑其快速、经济和方便的问题。由于公交车车费低廉，在本文的研究中不予考虑，而对于其方便程度和花费时间长短的问题，本文选择路程的长短来量化，在一系列合理假设的前提下，将公交路线的选择问题转为求解最短路径问题。对于事先已规定了顺序的最短路径问题，可直接利用图论的有关方法进行求解。如模型一，将长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街看作四个点，先将其简化为求任意两点之间的最短路径问题，然后将其连接起来，便可得最短路径，本文得到模型一的最短路径为长沙火车站（168）市委长沙市政府毛泽东文学院（903）望月湖小区（804）后湖中南大学新校区（202）阜埠河路牛耳教育南阳街口黄兴路步行街司门口（112）长沙火车站，其中为标明公交线路的为步行。对于事先并未规定顺序的最短路径问题，即可将其转为TSP问题，如模型二，本文采取C-W节约算法求解该问题，C-W节约算法是一种启发式算法，对于n较大的TSP问题能够有效的解决，得到最短路径为长沙火车站长沙市政府中南大学新校区黄兴路步行街长沙火车站。最短路径的选择问题具有很重要的理论和实际意义。图论只能解决事先已规定了顺序的最短路径选择问题，对于TSP问题，则无能为力；而C-W节约算法则能有效的解决TSP问题，但其迭代效果有时并不显著，还需要进一步的研究和讨论；本文在模型的推广部分利用改进的遗传算法进一步分析和解决TSP问题。-2-1.问题重述一公务人员从长沙火车站（五一路火车站）下车在一天时间内到如下地点：长沙市政府、中南大学新校区、黄兴路步行街办事，并回到长沙火车站（五一路火车站）。问题1.设计按如下顺序：长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型然后求解；问题2.设计从长沙火车站出发遍历如下地点：长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型然后求解。2.问题假设1、在公交线路上所有车辆都能正常通行，不考虑诸如堵车、交通事故等意外情况；2、公交车在公路上行驶速度处处相等；3、为了方便的原则，换乘次数越少越好（有特殊情况亦可例外）；4、由于乘坐公交车车费低廉，乘客不考虑价格因素；5、不考虑公交车在各站的停车时间，即乘客上下车均在瞬间完成；6、从距目的地最近的公交站点步行到目的地的路程忽略不计；7、往返路程相等。3.规定说明将长沙火车站定为地点1，长沙市政府定为地点2，中南大学新校区定为地点3，黄兴路步行街定为地点4，地点5亦为长沙火车站。4.问题分析对于第一个问题，由于路线已经指定，只需考虑从每一个上一站到对应下一站的最佳线路。而这里的最佳线路的汇总，即模型的目标。目标函数的选择有很多种，但在上述假设的前提下，本题的目标函数显然则化为最短行驶路程。对于第二个问题，不考虑顺序，要求遍历每一个目标地点，最后回到出发点，是典型的运筹学中的“货郎担问题”，即带权的哈密尔顿回路问题。为使模型化简，已经假设从距目的地最近的公交站点步行到目的地的路程忽略不计，由此可以得到每两个地点之间的行驶路程，画出网络图，就可以按照C-W节约算法解决问题。-3-5.模型的建立与求解问题一模型一的建立：定义总路程为L，地点i到地点1i的路程为iL，则总路程41iiLL。由于iL之间相互独立，目标函数41min()min()iiLL。若地点i到地点1i的最小换乘次数为k，换乘次数为k的路线有n种，各个路线的路程分别记为(1)(2)(),,,niiiLLL，记(1)(2)()()min()min(,,)nmiiiiiLLLLL，即第m个路线为最佳路线。()miL被分为1k段，每一段分别为,1,,1jLjk，则1()1kmijjLL。按照jL乘车，即为问题一的求解。模型的一求解：根据网上公交线路的数据，任意两点之间只考虑直达或换乘一次的方案，这一点是合理的，一般来说考虑方便程度，换乘两次以上就显得相当麻烦，一般乘客都会放弃这种选择。这时可得两点的可选方案如图1所示。图1可选方案利用网上长沙公交查询，地点1到地点2可以直达，即换乘次数为0，而换乘次数为0的路线有两条：第一条，从长沙火车站乘坐168路公交车，在市委下车，步行至长沙市政府（步行路程忽略不计），路程为11.19公里；第二条，从长沙火车站步行至蓉园路口，乘坐302路公交车，在市政府下车，路程为12.79公里。11.1912.79，所以，1min()11.19L，选择第一条路线。-4-地点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公里，在长沙火车站下车即可。综上，最终得到的最佳路线如下：长沙火车站168市委长沙市政府毛泽东文学院903望月湖小区804后湖中南大学新校区阜埠河路202牛耳教育南阳街口黄兴路步行街司门口112长沙火车站。其中，箭头上未标明公交线路的为步行，黑体字为各目标地点。其路线图见图2：图2路线图-5-模型评价优点：此模型所运用的方法浅显易懂，同时又能把问题描述得很清晰，用它解决问题时操作简便。缺点：过于简单，不能很好的解决复杂的问题。问题二模型二的建立：这是一个带权的哈密尔顿回路问题，这个回路中有四个目的地，把每个目的地看成一个点，即长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街，首先需要知道每两点之间的距离，记第i个点与第j个点的距离为ijL，由假设7知ijjiLL。为使模型简化，已经假设步行路程忽略不计，由问题一可得，1211.19L，238.46L，346.92L，143.45L，另外由问题一的方法同理可得，1310.99L，2410.54L。以第一个点长沙火车站为基点，将基点与其他各点连接，构成子回路11(2,3,4)jj，这样就得到了具有3=4-1条子回路的图（这时尚未形成哈密尔顿回路），即初始旅行图，如图3所示。图3初始旅行图-6-乘客按此线路所经过的路程总和等于4122jjLL。若连接点i和点j(,1)ij，即使乘客走弧(,)ij时（这时当然就不再经过弧(,1)i和(1,)j），所引起的路程节约值(,)Sij可计算如下：111111(,)22()ijijijijijSijLLLLLLLL（1）对不同的点对(,)ij，(,)sij越大，乘客通过弧(,)ij所节约的路程越多，因而应优先将这段弧插入到旅行线路中去。在具体应用上述方法时，可按以下迭代步骤进行。（1）选取地点1为基点，将基点与其他各点连接，得到3=4-1条子回路11(2,3,4)jj。（2）对不违背限制条件的所有可连接点对(,)ij计算节约值（,ij不为基点）11(,)ijijSijLLL（2）（3）将所有(,)Sij按其值由大到小排列。（4）按(,)Sij的上述顺序，逐个考察其端点i和j，若满足以下条件，就将弧(,)ij插入到旅行线路中。其条件是：①点i和点j不在一条线路上；②点i和点j均与基点相邻。（5）返回步骤（4），直到考察完所以可插入弧(,)ij为止。通过以上迭代步骤，可使问题的解逐步得到改善，最后达到满意解或最优解。模型二的求解：已经算得各点之间的路程ijL，现将结果列入下表1中。由于假设ijjiLL，可以看到该表中各元素的值以主对角线为对称。取地点1为基点，构成初始旅行线路图，如上图3。再用式（2）计算将弧(,)ij(,1)ij插入到线路中时引起的路程节约值，并按节约值由大到小的顺序将它们填入表2中。-7-表1各点距离表至从地点1地点2地点3地点4地点1011.1910.993.45地点211.1908.4610.54地点310.998.4606.92地点43.4510.546.920表2节约值表序号弧节约值1(2,3)13.722(3,4)7.523(2,4)4.1依节约值从大到小的次序，对每条弧加以考察，看是否应将其插入线路中去。若将其插入，就要对线路作相应的改变。整个过程示于表3中。表3线路选择序号弧线路节约值0121，131，1411(2,3)1231，14113.722(3,4)123417.52当插入弧(3,4)后，线路已包含所有要到达的点，算法终止。所以，用该方法得到的最终线路是：12341如图4所示：-8-图4最终线路图即：长沙火车站长沙市政府中南大学新校区黄兴路步行街长沙火车站。该线路的总长度1213142()((2,3)(3,4))LLLLSS2(11.1910.993.45)(13.727.52)30.02模型评价优点：这是一种启发式的算法，即使是不具有良性结构的实际问题也可以解决。与传统的方法相比，它不需要偏离事实，勉强使用某种标准模型，只需建立基本符合问题实际情况的非标准模型即可。这时，分析人员可以运用自己的感知和洞察力，去发现和构想可用于解决该问题的思路和途径，如此体现了人的主观能动作用和创造力，解决问题的方法比较灵活。它还有以下几个优点：（1）计算步骤简单，易于实施。（2）不需要高深和复杂的理论知识，因而可由未经高级训练的人员实现。（3）与应用优化方法相比，常可以减少大量的计算工作量，从而显著节约开支和节省时间。（4）易于将定量分析与定性分析相结合。缺点：运用此模型可以得到满意解，但不一定能得到最优解。-9-6.模型的推广对于从长沙火车站出发遍历如下地点：长沙市政府、中南大学新校区、黄兴路步行街，最后回到长沙火车站的问题，将其简化，一般来说公交车的价钱不会太高，且乘客们在乘车过程中一般只会考虑其方便程度和时间问题，所以我们假设在乘车过程中乘客只考虑路程，不考虑金钱。这样，便可以将其推广至著名的货郎担问题（即TSP问题）：一个售货员从某一城市出发，访问n个城市各一次且仅一次，然后回到原城市，问他走什么样的路线才能使走过的总路程最短。TSP问题是组合优化问题中最典型的问题之一，并且是一个NP难题，TSP问题展示了组合优化的所有方面，它已经成为并将继续成为测试新算法的标准问题[2]，如模拟退火、禁忌搜索、神经网络以及进化方法等都用TSP来测试。很多实际问题可以转化为TSP问题，如印制电路板的钻孔路线方案、连锁店的货物配送路线，以及防空作战中火力单元的部署优化和空袭目标分配优化等，所以解决TSP问题有很重要的理论和实际意义。本文对第二个问题采用的C-W节约算法对于n较小的TSP问题可以有效的解决，但对n较大的问题，我们