2014暑期数学建模竞赛1

2014全国大学生数学建模竞赛

承诺书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A

我们的参赛报名号为（如果赛区设置报名号的话）：S42034

所属学校（请填写完整的全名）：郑州大学

参赛队员(打印并签名) ：1. 闫亚倩

2. 雷新

3. 孙俊馥

指导教师或指导教师组负责人(打印并签名)：

（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）

日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：

2014全国大学生数学建模竞赛

编号专用页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

评

阅

人

评

分

备

注

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

高新技术开发区公交路线的优化设计

【摘要】

随着郑州市高新技术开发区经济文化的蓬勃发展，一个问题越来越凸显出来——公共交通网络不够完善。因此，我们将实际统计搜索到的数据加以处理，使之成为能够反映现状的数学模型，并对数学模型加以改善，再转化为实际，以做到为解决现实问题所服务。

由问题一，要对公共交通的合理性以及科学性进行评价，首先要了解什么样的公共交通才算是合理的，科学的。经查询，我们选择采用国家公布的《城市道路交通规划设计规范》（GB 50220—95）中的公交线路长度、线网密度、线路重叠度及非直线系数作为评价指标。然后采用主观线性加权得到各项指标的权重。在此基础上建立综合评价函数，将各评价指标先进行规范化，再进行标准化，然后按权重相加，最终得出综合评价函数，当综合评价指标Z≤0.1时，则可认为该区域公交路线是合理的。

对于问题二，为确定一个合理的线网方案，首先要找候选路线，本文先利用k最短路找到候选线路集；然后在候选线路集中选取几条作为一个线网规划方案，以居民出行线路最短建立目标函数，用遗传算法进行求解。

而问题三，与第二问思路相同，但不同的是目标函数。此问综合考虑居民方便和公交公司成本，建立了多目标规划函数，由于多目标函数求解复杂，本文利用线性加权的方法将多目标规划问题化为单目标规划问题。由于国家对公交车线路等方面有一定的规范，此问比第二问多了约束条件，再利用遗传算法进行求解。

问题四是在二三问的基础上进行发展。在考虑未来区域发展对客流出行以及地铁路线对该地区公交路线服务能力影响的情况下重新对该地区的公交路线进行规划研究。一方面，客流方向有所改变，有些需要增加或减少路线；另一方面，在地铁附近，需要减小线网密度，原有的线网密度比规定的要小，所以只要在考虑该区未来发展方向，在此基础行进行增减站点。之后利用k最短路径生成候选路径，再利用遗传算法得到最优解。

【关键字】

公交线路优化指标 k最短路径遗传算法

1

一．问题重述

郑州国家高新技术产业开发区位于郑州市城区西北部，南临西流湖，北接邙山，东与环城快速路相联，西四环穿区而过，距市中心约12公里，南距310国道2公里，北邻连霍高速公路，距新建郑州国际航空港30公里，对外交通条件优越。属暖温带大陆性气候，四季分明，高新区水质、空气质量上乘。建成区面积110平方公里，总人口25万，是河南省、郑州市发展高新技术产业的核心区域。

随着郑州市高新技术开发区经济文化的蓬勃发展，越来越多的居民居住在此。不仅如此，在该区域也区聚集了越来越多的企业、学校和商业网点。

随着该区域的开发，一个问题越来越凸显出来——公共交通网络不够完善。现有的公交路线覆盖范围主要涉及主城区，但郊区的公交路线和数量都较少，无法满足人民群众日益增加的出行要求。鉴于此况，我们现以高新区已建成的区域中某一区域（例如郑州大学附近）为对象，利用数学模型回答下列问题：

1)收集目前相关信息，建立数学模型对公交路线设置的合理性和科学性进行评价；

2)在考虑人口密度、交通路况等基础上，对该区域的公交路线进行合理的规划设计，

以满足居民在该区域内或区域外工作和生活的需要；

3)由于该区域范围较大，因此部分公交路线可能较长，请在考虑公交公司运营成本和

居民出行方便的基础上，重新规划该区域的公交线路；

4)根据郑州地铁发展规划，高新技术开发区会覆盖地铁路线。以地铁路线为依据，考

虑地铁换乘和未来该区域发展，重新对该区域的公交线路进行规划设计。

2

二．问题分析

问题1）的分析：

要对公交路线设置的合理性与科学性进行评价，我们需要知道，公交路线的设置要满足什么样的要求才算合理。经查询和筛选，我们发现，与题意相符合的公交线路的主要评价指标有公交线路长度、线网密度、线路重叠度及非直线系数，我们以这四个指标搜索相关数据，建立数学模型。

问题2）的分析：

在考虑人口密度、交通路况等基础上，对该区域的公交路线进行合理的规划设计，由问题一可知，仅考虑公交路线的标准，该区域现有的公交路线不尽合理，再加上人口密度和交通路况。所以，我们采用出行线路的长度作为目标，选取该区域主要站点，然后根据人口密度和交通状况，得到候选路径，并利用遗传算法进行筛选，得到符合题意和标准的优化后的路线。

问题3）的分析：

根据公交路线长度和公汽运营成本的关系以及考虑到乘客出行方便,我们参考第二问中采用路线长度为目标函数，并利用路线长短和运营成本及出行方便程度的关系，建立多目标优化模型，再加上约束条件，求解出每条路线的最佳路线，使每条公交路线兼顾公汽成本和出行方便的因素。

问题4）的分析：

这一问题是在二三问的基础上加以发展的，在考虑未来区域发展需要重新对该地区的公交路线进行规划研究。分析客流方向的改变以及新型公共交通对此地区的影响，我们认为在第二问的基础上进行增减设点。之后利用k最短路径生成候选路径，再利用遗传算法得到最优解。

三．模型假设

假设1：只考虑大站点，小站点本文不予以考虑。

假设2：公交系统的承载能力理想。

假设3：同一道路各处以及上下行的道路状况相同。

假设4：在重新规划线路的过程中，原站点不变，且原公交线路数不变。

假设5：本文所引用的数据均为真实数据，可采用。

假设6：每条线路上发车频率是一定的，且合理。

四．符号说明

i L表示第i条公交路线长度；S表示该区域面积；

R表示公交线网密度； 表示公交线路重叠度；

3

4 Ti 表示第i 条线路长度； β 表示非直线系数；

Ci 表示公交线路首末站之间的实际距离； Z 表示题一评价综合指标； La 表示图1中各条路径的长度；

五．模型建立与求解

（一）问题一的模型建立与求解

经过对问题一的分析、讨论及数据搜索，我们选择采用国家公布的《城市道路交通规划设计规范》（GB 50220—95）中的公交线路长度、线网密度、线路重叠度及非直线系数作为评价指标。采用主观线性加权得到各项指标的权重。在此基础上建立综合评价函数，将各评价指标先进行规范化，再进行标准化，然后按权重相加，最终得出综合评价函数。

1.1评价指标

1.1.1公交线路长度i L

公交线路长度指任意一条经过该区域的公交线路在区域范围内的实际长度。包括服务区域内公交线路的线路平均长度、最短线路程度和最长线路长度。该指标反映了区域内公交线路长度设置的合理性。按规范要求，平均长度范围应为5~11.5km 。

1.1.2公交线网密度R

公共交通线路网密度：每平方公里城市用地面积上有公共交通线路经过的道路中心线长度，单位为km/km^2，主城区公交线网密度规范要求3~4km/km^2，城市边缘地区公交线网密度规范要求2~2.5km/km^2，本题采用2~2.5km/km^2。

S

Li R ∑= 其中，i L 表示第i 条公交路线长度；

S 表示该区域面积；

1.1.3公交线路重叠度α

公交线路密度是指公共交通线路总长度与线路总长度之比。根据《规范》标准，设0表示不重叠, 1表示完全重叠,它反映了公交线路分布的合理程度,一般不应大于0.5。

5

Li

Ti =

α

其中，Ti 表示第i 条线路长度； i L 表示第i 条公交路线长度 1.1.4非直线系数β

非直线系数是指服务区域内公交线路首末站之间的实际距离与空间直线距离之比。公共交通非直线系数规范要求应不大于1.4。

Li

Ci =

β

其中，Ci 表示公交线路首末站之间的实际距离； i L 表示第i 条公交路线长度；

1.2模型评价

1.2.1现状指标

表一 高新区公交路线具体指标 路 线路长度/km 直线距离/km 非直线系数 重叠长度/km 重叠度 271 5.5 4.9 1.122 4.8 0.873 31 10.1 6.8 1.485 3.6 0.356 315 17.9 12.6 1.421 7.8 0.436 328 8.9 6.5 1.369 8.5 0.955 45 10.1 7.6 1.329 5.3 0.525 56 14.0 10.8 1.296 7.5 0.536 68 7.3 6.3 1.159 7.0 0.959 72 19.6 5.4 3.630 9.2 0.469 76 2.8 2.1 1.333 1.0 0.354 B12 7.8 5.7 1.368 7.0 0.897 总和 104 68.7 61.7 平均值 10.4 6.9 1.551 6.2 0.636

经计算，高新区公交线网密度为1.96km/km^2。

1.2.2现状指标与标准值的比较

6

根据上述4个重要的评价指标，借助收集到的公交车数据和相关信息进行计算，得出的现状值与标准值进行对比：（见下表）

指标名称

现状指标值 标准值 公交线路长度i L （km ）

线路平均长度：10.4 平均长度范围：5--11.5 公交线网密度R

(km/km^2)

1.96 2--

2.5 公交线路重叠度α 最小：0.354 最大：0.959

平均：0.636

≤0.5 非直线系数β

1.55 ≤1.4

1.2.3各项指标归一化处理

1) 公交线路长度归一化处理

由数据可得，所有线路的平均长度处于标准范围5~11.5的中间，也就表明有绝大多数公交线路长度都在标准范围之内。由此，以和的中间值作为标准值，对公交线路长度进行如下归一化处理：假设公交线路的平均长度为l ，那么，

1(511.5)()8.25(11.58.25)(511.5)

l l l l l λ<>??=?--≤≤?? 或

2) 公交线网密度的归一化处理

公交线网密度的标准范围为2~2.5之间，由于公交线网密度不在此范围内，所以，对公交线网密度做如下归一化处理：

()()()?

??≤≤--><=5.22 25.2/25.22 1R R R R R 或）（λ

3) 公交线路重叠度的归一化处理

线路重叠度本身就是0~1之间的数，根据规定，我们可以认为重叠度小于等于0.5的均为合理线路，因此，我们对线路重叠度做如下的归一化处理：

()

() ()()?

?

?

≤

<

≤

≤

=

1

5.0

5.0

5.0-

5.0

α

α

α

α

λ

4)非直线系数的归一化处理

线路非直线系数是实际长度与区域范围内始末站点的直线距离之比，相同的，认为非直线系数小于1.4就是合理的，赋值为0，而线路非直线系数越大，赋值也越大，由此对线路非直线系数β做如下归一化处理：

()

()

()?

?

?

>

≤

=

1.4

1.4

-1

1.4

β

β

β

β

λ

1.2.4综合评价

公交线路的设置重点是为了使居民出行方便，因此，比较公交线路长度、线网密度、线路重叠度及非直线系数，利用主观线性加权的方法，我们得出四个指标的重要度排序为：公交线路长度、非直线系数、线网密度、线路重叠度，赋予他们权值分别为：0.4，0.3，0.2，0.1。

以Z为评价综合指标，则

()()()()α

λ

λ

β

λ

λ1.0

2.0

3.0

4.0+

+

+

=R

l

Z

Z值越小，表示该区域公交线路越合理，其值越大，表示公交线路设置的越不合理。为了准确的对此进行评价，需要对Z值进行处理，以得出其标准范围。假设：当Z≤0.1（可由参考资料数据处理后得到）时，认为该区域公交路线是合理的。经计算，该区域公交路线的综合评价指标值为0.337>0.1，所以该区域公交路线是不合理的。

（二）问题二的模型建立与求解

在考虑人口密度、交通路况等基础上，对该区域的公交路线进行合理的规划设计，由问题一可知，考虑公交路线的标准，再加上人口密度和交通路况，该区域现有的公交路线不尽合理。所以，我们以路线长度为目标函数，使其最短。

2.1选取站点

我们选取该区域主要站点并编号，得下图：

（以该区域实际地图取主要站点得以下图1 线路图网）

7

8

该区域实际地图

图1 路线图网

2.2候选路径的生成：

我们利用K最短路生成候选路径。它的思想是：从原始点到顶点j的第K条最短路是由原始点到顶点i（i是j的相邻顶点，最短路从i指向j）的第K条最短路加上i到j 的一段弧。我们利用此思想结合路况和人口密度生成了候选线路集如下：

路径编号路径

1 1—21—7—8—24

2 1—9—10—11—19—15—18

3 1—21—7—8—12—19—15—18

4 22—13—14—15—11—18

5 22—13—16—11—17—18

6 22—13—14—15—19—12—8—24

7 23—3—4—20—8—24

8 23—3—4—20—8—12—19—15—18

9 23—10—14—17—18

10 23—3—4—20—7—11—19—15—18

11 22—13—9—1—21—7—8—24

可利用遗传算法进行筛选，然后找出最优路线，以优化原有路线。

（三）问题三的模型建立与求解

该问题是在问题二的基础上，增加了公交公司的运营成本这一条件，所以在问题二的基础上考虑运营成本，而运营成本又与线路长度密切相关，因此，建立的目标函数应当有约束进行限制。

3.1定义数据

1) 各条线路的长度

根据图1中的路线标注可以计算出各条路径的长度La

2) 各条线路的首末站间的直线距离

在百度地图中确定首末站点间的直线距离Da

3.2模型的建立

3.2.1目标函数

此问要考虑到公交成本，我们让公交总线路尽量短：

9

10 ∑=n

a L Min 1a (1)

避免部分路线过长，我们让公交线路长度的方差尽可能小，

21___∑=??? ??-n a La La Min (2)

（1）与（2）构成问题3的目标函数，目标函数如下：

()???

?????-+∑∑==211n a n

a La

La La Min ζμ

3.2.2约束条件

根据《规范》公交线路长应控制在5km~11.5km ；

非直线系数应不大于1.4；

线网密度应在2~2.5km/km^2。

5 ≤ L ≤ 11.5

L/D ≤ 1.4

2 ≤ L/S ≤ 2.5

将目标函数与约束条件综合，利用matlab 来求解。

（四）问题四的模型建立与求解

在考虑未来区域发展对客流出行的影响，和地铁路线对该地区公交路线服务能力影响的情况下重新对该地区的公交路线进行规划研究。一方面，客流方向有所改变，有些路线需要增加或减少路线；另一方面，在地铁附近，需要减小线网密度，原有的线网密度比规定的要小，所以只要在考虑该区未来发展方向，在此基础行进行设点。之后利用k 最短路径生成候选路径，再利用遗传算法得到最优解。

六．模型的评价

模型的优点：

1.利用k最短路径生成候选路径，再利用遗传算法得到最优解。

2. 在设站点时一些站点进行了简化，如科学大道上有很多站，但我们只取了比较主要的几个点，可以连接其他线路的站点，使规划变得简单，在确定好路线后可以在此基础上添加站点。

3. 把多目标问题进行加权，变为更简单的单目标问题。

4. 该模型的算法可以广泛应用于各种规划问题，比较具有普遍性。

模型的缺陷：

1. 模型所需数据不宜寻找。

2. 模型所得的结果不够完善。

七．参考文献

[1] 百度地图网址：13b8c256844769eae009edc3/

[2] 郑州公交信息网址：13b8c256844769eae009edc3/

[3] 尹峰李枫，《公共交通服务水平的模糊评价》，上海铁道大学运输管理工程，上海，2000

[4] 姜启源谢金星，《数学模型》，高等教育出版社，北京，2004

[5] 韩中庚，《数学建模方法及其应用》，高等教育出版社，北京，2006

[6] 刘好德杨晓光，《基于改进遗传算法的公交线网优化设计研究》，计算机工程与应用，2007

11

本文来源：https://www.bwwdw.com/article/e4fl.html