《中南大学校内赛论文a乘坐公交车优化方案设计》由会员分享，可在线阅读，更多相关《中南大学校内赛论文a乘坐公交车优化方案设计（22页珍藏版）》请在金锄头文库上搜索。
1、乘坐公交车优化方案设计 摘要本文根据不同乘客的需求，建立以不同需求为目标的优化模型。 问题一，由于乘车路线已定，考虑快速、经济、方便的目的，本文选取对应的路程、乘车费用、乘车次数三个因素，首先分别建立仅考虑路程最短、乘车次数最少和乘车费用最少的单目标最优模型。为避免考虑单一因素的片面性，然后综合考虑路程、乘车次数和乘车费用采用层次分析方法确立综合权重函数，将多个目标线性组合为以P为目标函数的多目标线性组合优化模型，用广度优先算法求解。问题二，为了求出从起始点遍历每个目的点然后回到起始点的最优路径，可以将每个目的点抽象为节点，运用图论观点建立公交网络有向图，本文分别采用乘车路程、乘车次数、乘车费
2、用和综合权重函数为不同权值，将问题转化为TSP模型，采用模拟退火法求解模型。问题三，根据问题一、二给出的模型，从可行性方案中选出最优乘车方案。基于乘客的不同需求，设计出不同的乘车方案。再综合考虑乘车路程、乘车次数、乘车费用等因素以综合权重函数为权值所得到的方案具有广泛的适应性，可满足大部分乘客需求。本文得出问题一的最佳方案为：长沙火车站长沙市政府中南新校区黄兴路步行街长沙火车站,总权值为1.7384（总路程39.7公里，总乘车次数6，总乘车费用8元）。问题二的最佳方案为：长沙火车站黄兴路步行街中南新校区长沙市政府长沙火车站,总权值为1.5206（总路程37.7公里，总乘车次数5，总乘车费用8元
3、）。实际中对某一位乘客来说，人们往往根据最影响自己的主导因素，选择自己的乘车方案，此时但目标优化模型简单易行，但不如多目标线性组合优化模型考虑全面。多目标线性组合优化模型中，综合权重函数的确定因人而异，需分别确定权重系数，考虑全面，但计算量大。两种模型各有优劣。实际中，乘客选择乘车方案时，还要考虑更多因素，如选择始出发车次避免拥挤，或沿途看风景及换乘时步行时间等因素，可以考虑这些因素以完善模型。关键字：单目标优化 多目标线性组合优化 广度优先搜索 模拟退火法1、问题重述公共交通作为长沙市交通网络中的重要组成部分，由于公共交通对资源的高效利用，使得通过大力发展公共交通，实行公交优先成为缓解日趋严
4、重的道路交通紧张状况的必然选择。面对迅速发展和不断更新的长沙市公共交通网，如何根据长沙市居民和外地游客的需要研究出公交出行路径优化算法，寻找并提供一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案，是公共交通系统中最基本最关键的问题。 一公务人员从长沙火车站（五一路火车站）下车在一天时间内到如下地点：长沙市政府、中南大学新校区、黄兴路步行街办事，并回到长沙火车站（五一路火车站）。将解决如下问题：1设计按如下顺序：长沙火车站、长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型；2设计从长沙火车站出发遍历如下
5、地点：长沙市政府、中南大学新校区、黄兴路步行街，并回到长沙火车站（五一路火车站）完成事务的乘坐公交车的可行方案，并给出相应的数学模型；3给出上述两种情况下的最优乘车方案。2、问题分析本题主要考虑三种因素，研究任意两目的点之间公交线路选择问题。联系长沙实际公交情况，出于乘客乘车快速、经济和方便的目的，本文考虑了任意两目的地之间路程、乘车次数、乘车费用等，按照乘客对不同因素的重视程度，设计出可行的乘车方案和最优乘车方案。问题一所给乘客乘车顺序已定，查询长沙任意两目的地之间乘车方案信息，包括乘车距离，乘车次数和乘车费用，在已知的乘车顺序的情况下，分别考虑乘车距离最短、乘车次数最少、乘车费用最少设计三
6、种可行方案。由于实际中有的乘客会综合考虑三种因素，考虑单个因素建立的前面三种方案难免片面。本文考虑乘客三种因素注重程度不同，建立三种因素权重不同的多目标线性组合优化模型。三种因素相互关联，故通过层次分析的方法确定各因素的权重系数。又三种因素不具可比性，通过标准化处理化成定量目标。然后采用广度优先搜索算法求解。 问题二，为了求出从起始点遍历每个目的点然后回到起始点的最优路径，可以将每个目的点抽象为节点，将公交线路抽象为连接各目的点的有向边，建立公交网络有向图，根据乘客出行侧重的因素不同，本文考虑乘车路程、乘车次数和乘车费用为权值建立三个TSP模型。再综合考虑三因素选择乘车方案，建立综合三个因素确
7、定权值的TSP模型，该权值为乘车路程、乘车次数和乘车费用三个目标组合的优化值。考虑对三因素的考虑的不同程度根据层次分析的方法赋予权重系数，将问题转化为在综合目标函数赋权有向图中的寻找最优路径的问题。然后采用模拟退火算法求解。3、问题假设3.1 假设所有公车发车间隔时间相等，每个公交站点人流量相当，每次换乘时间相等。3.2 乘客换乘公交站点不变，中间无步行。3.3 假设所有公车无性能差别，在公交线路上相对稳定，行驶速度相同，不存在堵塞等情况的影响。4、变量说明表示目的地且表示任意两目的地之间乘车方案，表示目的地的路程，（公里）；表示第个乘车阶段采用乘车方案的的路程（公里）；表示目的地的乘车次数；
8、表示第个乘车阶段采用乘车方案的乘车次数；表示目的地的乘车费用（元）；表示第个乘车阶段采用乘车方案的乘车次数；表示目的地无量纲，为该乘车方案路程、乘车次数和乘车费用的函数；表示路程、乘车次数、乘车费用三种因素对应的权重系数；其它符号在具体模型中说明。5、模型建立5.1问题一 单目标优化和多目标线性组合优化模型根据长沙公交查询网，任何两目的地之间可查出给定乘车方案，每种乘车方案包括路程、乘车次数和每路公交乘车费用三项基本信息。但在一些较小的城市，相关公交查询系统建立尚不完善。在公交网站查询不到两目的地之间的线路信息，为使模型建立具有普遍性，本文假设只知道公交线路所经过的站点、路线上相邻站点的距离、
9、经过每一个站点的路线三种信息。当已知乘客到达各目的地的顺序，分别建立仅考虑路程最短、乘车次数最少或乘车费用最少的单目标最优模型和综合考虑路程、乘车次数和乘车费用的多目标线性组合优化模型。模型求解采用广度优先搜索算法。5.1.1模型一 总路程最短 根据给定顺序，分个阶段乘车，每个阶段相互独立，设为乘车阶段，分别表示，n个乘车阶段，目标函数： (1)决策变量： 约束条件： 5.1.2 模型二 总乘车次数最少 (2)目标函数： 决策变量： 约束条件： 5.1.3 模型三 乘车总费用最少 (3)目标函数： 决策变量： 约束条件： 5.1.4模型四 多目标线性组合优化模型 根据乘客乘车需求，每个乘车阶段
10、独立，要对每种乘车方案的进行优化，首先确定优化目标。根据问题分析的结果，采用乘车方案的乘车路程、乘车次数和乘车费用三项目标作为优化的准则，建立“最优乘车方案”的多目标线性组合优化模型。由于各目标不具可比性，通过数据的标准化处理和层次分析的方法确定各目标权重系数来量化各因素的重要性。（1）目标优化数据标准化处理乘车路程在假设了各公交行驶速度相同等的前提下，乘车路程越短即乘车时间越短,对于希望指标值越小越好，得到各公交方案m总乘车路程的标准化值 (4)即为各乘车方案m路程的标准化值，其中为所有中的最大值，为所有中的最小值。乘车次数实际生活中，出行者的乘车次数越少越好。在乘车次数较小时，出行者对乘车
11、次数的敏感程度随着乘车次数的增加而增长不大；但当乘车次数增加到一定值后，该敏感程度随着乘车次数的增加而快速增长，并迅速接近极限值；之后，该敏感程度随乘车次数的增加而增长缓慢，并逐步靠近极限值。根据这一基本事实，我们取近似的偏大型柯西分布作为隶属函数 (5)来对乘车次数的数据进行标准化处理。其中、为待定常数，为函数的分界点。根据实际情况：这里取=1；乘车次数为2的标准化值为0.3，即，表示出行者在自己的出行线路上乘车两次是可接受的；乘车次数为4时的标准化值为1，即，表示乘车4次对出行者来说就不可以接受了。于是，可以求得，故 (6)经计算得到各乘车次数的隶属度（如图1），即各乘车次数的标准化值。图
12、1 各乘车次数的隶属度乘车费用对出行者而言，乘车总费用越少越好，且可将现实中乘车总费用与线路最佳程度的关系简化为线性关系，采用线性型功效系数评分法对乘车总费用的数据进行标准化处理。记为乘车方案m的乘车总费用，它与所包含公交线路的数量、类型以及各线路的长度与计费方式等有关。同理，对于仍希望指标值越小越好，故令其中为所有中的最大值得，为所有中的最小值。所以，对所有的，对应有 (7)即为各公交方案m乘车费用的标准化值。（2）各目标权重系数的确定1确定权重的方法有很多，这里考虑到选择一种乘车方案m后，其乘车路程、乘车次数和乘车费用是相关联的，故引用层次分析法的方法来确定各目标的权重。实现过程如下： 建
13、立成对比较矩阵；这里我们根据Satty的1-9尺度给出成对比较矩阵A，第一行表示乘车路程，第二行表示乘车次数，第三行表示乘车费用。 (8) 一致性检验；矩阵A的最大特征值.一致性指标：.一致性比率：，其中. 求权重向量如下：a.将A的每一列归一化得b.对按行求和得c.将归一化，=即为近似特征向量d.计算，作为最大特征根的近似值通过matlab编程计算我们得到权重向量如下：W=0.5815,0.3090,0.1095，满足一致性要求。所以得到。每个人对各个指标的敏感程度不同，在选择乘车方案时，需要根据各个乘客的不同关注因素生成不同比较矩阵，用特征向量法来计算指标的权重。为了计算方便，本文取w=
14、0.5815,0.3090,0.1095来计算。当权重系数改变时，得到的最优结果可能不同。(3) 建立综合权重函数根据上文的计算结果，综合三个目标，可以确定线路方案最优化的综合权重函数: (9) 决策变量： 这样，建立多目标线性组合优化模型。线路方案的“最优化程度”就可以用量化后的综合权重值p确定，p值越小，所选方案的最优化程度越高。5.2 问题2 TSP模型 为了求出从起始点遍历每个目的点然后回到起始点的最优路径，可以将每个目的点抽象为节点，将公交线路抽象为连接各目的点的有向边，建立公交网络有向图，边上的权值反映乘车路程、乘车次数和乘车费用等信息，根据乘客出行侧重的因素不同，本文考虑乘车路程、乘车次数和乘车费用为权值建立三个TSP模型。再综合考虑三因素选择乘车方案，建立综合三个因
