公交线路优化

A—B
33路
0
52
1
A—C
68路
0
46
1
A—D
52路
0
36
1
A—E
14路
0
36
1
B—C
57路
0
35
1.5
B—D
33路
0
38
1
B—E
70路
0
56
1
C—D
39路→53路
1
68
2
C—E
25路
0
44
1
D—E
69路
0
56
1.5
表格3 任意两站之间的最佳路线
3、计算优化后可行方案的数量
根据“排列组合”的知识我们知道，遍历四个目的地再回到出发点的可行方案共有
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：河南科技大学
参赛队员(打印并签名)：1.许光辉
2.李贵涛
3.蔡亚娟
（1）换乘次数：乘客从出发地到目的地过程中所乘车的次数。
（2）消耗时间：乘客乘坐公交车所消耗的时间。
（3）出行费用：乘客从出发点地到目的地过程中所需要的费用。
（4）所需要的步行时间：乘客在换乘时所需要的步行时间。
（5）司机的服务态度和公交的舒适度：这些因素在该问题中不作定量分析。
从现实生活中可知，以上几个因素存在相关性，因此可以对上述因素对比后作出简化。比如“换乘次数”与“所需要的步行时间”具有一定的正相关性。
3、司机的驾驶技术、服务态度及公交车的舒适度等因素对乘客选择公交车次没有影响。
4、洛阳市乘客的心理调查结果与南京市无明显差异。
5、该乘客在各个目的地停留时间与乘坐公交时间的和小于一天。
6、所有公交线路均双向。
四、符号定义及说明
序号
符号
说明
1
A
洛阳火车站
2
B
洛阳市政府
3
C
河南科技大学新校区
4
D
洛阳师范学院
2、需要解决的问题
问题一：从洛阳市火车站出发顺序经过洛阳市政府、河科大新校区、洛阳师院、上海市场步行街，并回到洛阳火车站的可行乘车方案。
问题二：从洛阳市火车站出发遍历洛阳市政府、河科大新校区、洛阳师院、上海市场步行街，并回到洛阳火车站的可行乘车方案。
问题三：从洛阳市火车站出发以顺序和遍历两种方式经过洛阳市政府、河科大新校区、洛阳师院、上海市场步行街，并回到洛阳火车站的最佳乘车方案。
图5
将决策问题分为3个层次：目标层O，准则层C，方案层P
目标层是O最佳乘车方案
准则层有三个因素：C1换车次数、C1时间、C1费用。
其各自权重系数分别为 、 、 ；从5.3.2的分析可知， =0.45、 =0.35、 =0.2。
方案层为24条路线，从P1（路线1）到P24（路线24）。
现在我们再对各个影响因素作详细分析：我们取换乘次数最少、总费用最低、总时间最短分别为各个方面的100分，然后采用数理统计的方法，对落入不同区间的数值赋予分值。赋值原则如下表所示：
二、问题分析
本题目是一个公交出行最优路径选择问题，我们首先应该清楚各个目的地之间的公交线路情况，因此需要登录“洛阳公交网”查询、收集和整理相关数据信息（具体数据信息见附录）。
问题一已经给出确定的出行路线，我们只要知道相邻两个目的地之间的车次情况既可以作答。
问题二要求遍历四个目的地，我们可以先用“控制变量法”筛选出任意相邻的两个目的地的最佳车次，然后根据“排列组合”的知识确定达到各个目的地的先后顺序，最终确定乘坐公交的可行方案。
1、问题一最优方案的确定
我们由5.2.2可知，通过“控制变量法”可得各个目的地之间的最佳车次。我们可以利用该结果对问题一进行简化，进而得到问题一的最优乘车方案。如右图2所示：
2、影响因素的权重分析及调整
从5.1.1的分析可知，影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间、出行费用。那么这几个因素在乘客心中的重要性如何分布呢？这就有必要对洛阳市的公交乘客进行心理调查，然后对数据进行统计处理和分析。考虑到这次模拟训练时间紧迫，我们在此参考南京市做的一个公交乘客出行心理调查结果。其结果如图3。
问题三需要求解出前两个问题的最优乘车方案，为此我们需要建立一个科学、合理的公交线路评价方法，然后定量分析出各种乘车方案的优劣。
三、基本假设
1、公交车不受载客人数、天气等因素影响，能保持匀速行驶，平均速度12.76公里/小时。
2、不考虑公交车在行驶过程中因等待红灯、堵车等客观条件对消耗时间的影响，相邻两公交车的间隔时间为：5分钟。
1
36
68
35
56
36
231
6
16
A-D-C-E-B-A
1
36
68
44
56
52
256
5.5
17
A-D-E-B-C-A
0
36
56
56
35
35
218
6
18
A-D-E-C-B-A
0
36
56
44
35
52
223
6
19
A-E-B-C-D-A
1
36
56
35
68
36
231
6
20
A-E-B-D-C-A
1
36
56
38
68
5
E
上海市场步行街
6
第i个因素在最终评分中所占的权重
7
X
考虑换乘因素后所得的分数
8
Y
考虑时间因素后所得的分数
9
Z
考虑费用因素后所得的分数
10
M
考虑所有因素后最终的得分
五、模型建立及求解
（一）问题一的模型建立及求解
1、对影响乘客选择车次、路线的因素作定性分析
通常公交乘客出行时，主要考虑以下几个主要因素：换乘次数、消耗时间、出行费用、所需要的步行时间、司机的服务态度和公交车的舒适程度等。下面对影响因素作如下解释：
10
A-C-D-E-B-A
1
46
68
56
56
52
278
6
11
A-C-E-B-D-A
0
46
44
56
38
36
220
5
12
A-C-E-D-B-A
0
46
56
56
38
52
248
5.5
13
A-D-B-C-E-A
0
36
38
35
44
36
189
5.5
14
A-D-B-E-C-A
0
36
38
56
44
46
220
5
15
A-D-C-B-E-A
时间/分钟
费用/元
A—B
33路
0
52
1
62路→26路
1
50
2.5
68路→26路
1
52
2
A—C
68路
0
46
1
46路→34路
1
62
2.5
A—D
52路
0
36
1
81路
0
36
1.5
33路
0
37
1
A—E
14路
0
36
1
103路
0
45
1
11路
0
47
1
50路
0
47
1
12路→19路
1
52
2
B—C
57路
0
35
1.5
70路→25路
种
4、依据以上的结论，得到可行的遍历方案。如下表所示：
序号
线路
换乘次数
中途时间/分钟
总时间
总费用
1
A-B-C-D-E-A
1
52
35
68
56
36
247
6.5
2
A-B-C-E-D-A
O
52
35
44
56
36
223
6
3
A-B-D-C-E-A
1
52
38
68
44
36
238
5.5
4
A-B-D-E-C-A
0
52
38
表格5换乘赋值原则
换乘次数
分值
0
100
1
60
表格6 时间赋值原则
时间区间
分数
（185，195］
100
（195，205］
95
（205，215］
2010高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
综上所述，影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间、出行费用。所以，我们应着重做好对以上三方面数据的收集和整理。
2、整理A—B—C—D—E—A中相邻两个目的地之间的车次情况：
乘车区间
路线序号
乘坐公交
换乘次数/次
时间/分钟
费用/元
A—B
1
33路
0
52
1
2
62路→26路
1
50
2.5
3
68路→26路
图2
换乘最少
41.16%
时间最短
30.93%
费用最低
18.61%
其他因素
9.30%
图3
由于时间原因，我们对不同路线中的“其他”类因素暂时不能做出准确的定量评价，因此我们对前三类因素的比重做出调整，使其权重系数和为1。调整后的结果如下：
换乘最少
45%
时间最短
35%
费用最低
20%
图4
3、建立评价方法的层次分析模型
1
48
2
70路→68路
1
48
2
33路→39路
1
54
2
B—D
33路
0
38
1
29路→58路
1Baidu Nhomakorabea
46
3
70路→58路
1
47
2.5
B—E
70路
0
56
1
29路
0
52
1.5
C—D
39路→53路
1
68
2
39路→69路
1
68
2.5
68路→69路
1
76
2.5
C—E
25路
0
44
1
63路→68路
1
56
2.5
63路→25路
1
问题三的中顺序经过这几个站点的最佳乘车路线是:
火车站 市政府 科大新区 洛阳师院 上海市场 火车站
遍历经过这几个站点的最佳乘车路线是:
火车站 海市场步行街 河科大新区 洛阳市政府 洛阳师院 火车站(正序逆序皆可)
【关键词】线路优化；乘客心理调查；控制变量法；遍历；目标规划；层次分析法； LINGO
一、问题重述
56
44
46
236
5.5
5
A-B-E-C-D-A
1
52
56
44
68
36
256
5.5
6
A-B-E-D-C-A
1
52
56
56
68
46
278
6
7
A-C-B-D-E-A
0
46
35
38
56
36
211
6
8
A-C-B-E-D-A
0
46
56
56
56
36
250
6
9
A-C-D-B-E-A
1
46
68
56
56
36
262
5.5
15
103路
0
45
1
16
11路
0
47
1
17
50路
0
47
1
18
12路→19路
1
52
2
表格1 顺序经过各站点车次资料汇总
3、依据上述数据，建立相应的数学模型，如图1所示：
图1顺序经过各站点路线
（二）问题二的模型建立及求解
1、整理A、B、C、D、E中任意两个目的地之间的车次情况：
乘车区间
乘坐公交
换乘次数/次
指导教师或指导教师组负责人(打印并签名)：
日期：2010年8月18日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2010河南科技大学数学建模选拔赛
A题 公交车线路优化设计
摘要
本文旨在研究公交线路优化设计问题，寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案。
首先，我们依据“公交乘客心理调查结果”，明确影响乘客选择车次、路线的主要因素有三个：换乘次数、乘车时间和出行费用，确定各自所占的权重。之后登陆“洛阳公交网”全面收集和整理这三个影响因素的具体数据。
50
2.5
D—E
69路
0
56
1.5
61路→50路
1
65
2
61路→103路
1
64
2
表格2 任意两站点间路线
2、用“控制变量法”初次筛选出任意两个目的地之间的最优车次
因为在任意的两个目的地之间都存在不同的车次供乘客选择，为了使该问题的模型简化，我们决定采用“控制变量法”对任意两个目的地之间的车次进行筛选。依次控制“换乘次数”、“乘车时间”、“出行费用”三个因素中的两个，通过比较另外一个因素得出两个目的地之间的最佳乘车车次。我们得到的筛选结果如下：
1、问题背景
21世纪的中国快速发展，交通事业也应承而上。中国人民先后告别了马车与草鞋，再见了单车与驾车，还有的为了社会的可持续发展，放弃了私家汽车，公共交通如日中天地发展起来，成为交通网络的重要组成部分。现代的洛阳，亦是如此。而随着公共交通的快速发展，这张交通网络也正变得错综复杂。面对着如此复杂密集的交通网络，如何从中寻找出一条或多条快速、经济、方便的从出发点到目的地的最优乘车或换乘方案，成为公共交通系统中最关键而又最基本的问题。
1
52
2
B—C
4
57路
0
35
1.5
5
70路→25路
1
48
2
6
70路→68路
1
48
2
7
33路→39路
1
54
2
C—D
8
39路→53路
1
68
2
9
39路→69路
1
68
2.5
10
68路→69路
1
76
2.5
D—E
11
69路
0
56
1.5
12
61路→50路
1
65
2
13
61路→103路
1
64
2
E—A
14
14路
0
36
1
46
244
5.5
21
A-E-C-D-B-A
1
36
44
68
38
52
238
5.5
22
A-E-C-B-D-A
0
36
44
35
38
36
189
5.5
23
A-E-D-C-B-A
1
36
56
68
35
52
247
6.5
24
A-E-D-B-C-A
0
36
56
38
35
46
211
6
表格4 遍历各站点的所有可选路线
（三）问题三的模型建立及求解
对于问题一，已经给出确定的乘车路线，直接找出两目的地的车次依次乘车。结果见论文第4页图1。
对于问题二，我们先用“控制变量法”初次筛选出任意两个目的地之间的最优车次，然后运用排列组合的方法确定遍历四个目的地再回到出发点的可行方案共有 种。结果见论文第6页表格4。
对于问题三，我们先利用“控制变量法”对任意两个目的地间的车次情况进行优化，筛选出任意两个目的地之间的最佳乘车方案。然后又在问题一、二的基础上通过对权重的设定和调整，将多目标规划问题转化为单一目标规划问题，利用“层次分析法”建立对各条线路进行评价的数学模型，最后用LINGO编程求解出最优乘车方案。