考虑随机行驶时间和车辆协同的公交时刻表设计方法研究

摘要

随着社会经济快速发展和城镇化进程加快，居民出行需求和机动车拥有量急剧增加导致了城市交通拥堵。交通拥堵已成为很多城市面临的严峻问题。提高公交系统运营效率和服务质量是缓解交通拥堵的关键举措。一个有效的公交系统不仅节省运营成本，还能吸引更多的私家车出行者转向公交方式出行。公交系统的有效性在很大程度上取决于公交规划过程。公交规划过程是一个复杂且多阶段的决策问题，它一般包含线网规划、时刻表设计、车辆调度和驾驶员调度。因为整个规划过程涉及很多决策变量，且每个子问题都是NP-hard问题，可依次按顺序求解各个子问题，从而获得整个问题的解。公交时刻表设计是整个规划过程中最为复杂和关键的子问题，决策线路各车次的发车时间，这不仅关系着公交服务质量，还影响着接下来车辆调度和驾驶员调度这些子问题的求解。因此，研究公交时刻表设计方法来获得高质量的时刻表至关重要。在实际运营环境中，车辆行驶时间具有不确定性。为提高服务的可靠性，需要在时刻表设计中考虑不确定的车辆行驶时间。另外，现有的公交网络不可能提供给乘客点对点的服务，乘客在不同线路间换乘是普遍的现象，为减少乘客换乘等待时间，设计时刻表时要使得不同线路的车辆协同达到换乘站点，方便乘客换乘。 作为国家创新研究群体科学基金(71021061)和中央高校基本科研业务费资助项目(N090204001)的重要组成部分，本论文以公交企业对公交规划与运营管理的大框架为研究背景，在对公交规划过程中各子问题详细描述和公交时刻表设计优化方法研究综述的基础上，采用运筹学理论深入研究了不同场景下的公交时刻表设计问题，这些场景包括随机车辆行驶时间和运营策略比较分析、超时行驶费用和驻站策略、不固定发车间隔、时刻表中加入松弛时间和多目标。本论文的创新工作主要体现在以下五个方面: (1)考虑实际运营环境中车辆行驶时间的不确定性，研究了随机行驶时间情况下的公交线路时刻表设计问题和不同运行策略比较分析。以车辆到站准点偏差期望值最小为目标，构建了公交线路时刻表设计的一般期望值模型。基于该模型，构建了四个分别嵌入不同运营策略（无运营策略、驾驶员调整车速策略、驻站策略和集成驾驶员调整车速和驻站的策略）的期望值模型。驾驶员调整车速策略就是激励驾驶员根据车辆到达当前站点的准点情况，尽量调整下一路段的行驶速度;驻站策略就是确保的实际离站时间不能早于计划发车时间，晚点的车辆服务完乘客上下车后立即离站。由于这些模型包含期望值项和非线性约束，采用Monte Carlo仿真和不等式约束方法将期望值模型转化为线性优化模型，然后利用优化器CPLEX求解。通过算例计算，比较分析了不同策略对时刻表设计的影响。结果表明，相对于其他运行策略，驻站策略能极大地提辆到站准点率。最后，分析了不同运营策略的适用场景。 (2)由于车辆行驶时间的不确定性，车辆常会超时行驶。在这种情况下，一方面公交公司要额外支付驾驶员的加班费用;另一方面，造成车辆晚点到达终点站，使得车辆不能准时执行返回车次，从而形成恶性延时循环。从系统费用的角度，构建了考虑超时行驶费用和驻站策略的公交线路时刻表设计模型。该模型考虑了运营者对车辆晚点到站或超时行驶的费用的主观偏好。通过一个实际算例对模型中的参数进行了灵敏度分析。结果表明，车辆行驶时间的不确定性将极大地增加公交系统的运营成本，且系统总成本是随机行驶时间方差的凸函数。 (3)由于均匀发车间隔的时刻表无法满足不断变化的乘客需求，将导致车辆的载客量不均衡;为减少乘客换乘等待时间，考虑同时决策整个公交网络各线路的时刻表。研究了不均匀发车间隔下的公交网络时刻表协同设计问题。使用数学不等式精确地描述了乘客的换乘等待时间，构建了以乘客总换乘等待时间最小为优化目标的混合整数规划模型，分析了可行解的空间结构和计算复杂性，并证明了该问题是NP-hard问题。基于模型特征的分析，设计了缩减求解空间的预处理方法，然后采用分支定界算法对预处理后的模型进行求解。通过计算不同算例，验证了求解方法和模型的有效性。 (4)由于车辆行驶时间的不确定性，车辆不能严格按照计划的时刻到达换乘站点，这将导致乘客可能完全错过计划的换乘车次。研究了考虑加入松弛时间的公交网络时刻表协同设计问题。构建了求解该问题的随机混合整数优化模型，该模型考虑了车辆行驶时间的不确定性和松弛时间。分析了模型特征和计算复杂性，并证明其是一个NP-hard问题;设计了求解该模型的嵌入局部搜索的改进遗传算法。通过计算一个实际算例，与确定性模型相比，该模型得到的时刻表能减少乘客等待时间费用达9.5％。当车上乘客与换乘乘客的数目之比小于10时，提出的模型是有效的。最后，通过计算不同规模的算例，进一步验证了模型和求解算法的有效性。结果表明，在不确定的运营环境下，将松弛时间加入时刻表中能降低乘客换乘的失败率，从而提高时刻表的可靠性使换乘乘客受益。 (5)公交网络时刻表设计问题涉及多个目标，且这些目标相互冲突。设计一个全新的时刻表会对原有时刻表和乘客原有出行计划产生影响。研究了多目标公交网络时刻表协同设计问题。该问题考虑了对发车间隔敏感的乘客需求、不均匀发车间隔、服务规则性、灵活的协同换乘方式和原始时刻表。考虑决策者调整现有时刻表以使更多的乘客受益于平滑换乘服务，同时又担忧调整后的时刻表将打乱不换乘乘客已习惯的出行计划。为权衡受益于平滑换乘的总乘客数目和偏离现有发车时间的最大值，提出了求解该问题的多目标混合整数优化模型。分析了该多目标公交网络时刻表协同设计问题的可行解空间和计算复杂性，证明了该问题是NP-hard，且它的帕累托最优前沿是非凸的。因此，设计了基于非支配排序的多目标进化算法。实验表明，与枚举算法相比较，该算法能够在合理的时间内获得高质量的帕累托最优解集。

目录

声明

摘要

第一章 绪论

1．1问题背景及研究工作的意义

1．2研究目标与研究内容

1．2．1研究目标

1．2．2研究内容

1．3研究的技术路线

1．4主要研究成果

1．5参加的科研项目

第二章公交时刻表设计问题的研究综述

2．1公交规划过程的基本要素

2．2公交规划过程相关问题的概述

2．3公交时刻表构成要素

2．3．1发车间隔方针

2．3．2发车时间的灵活性

2．3．3车辆行驶时间特征

2．3．4协同换乘方式

2．3．5时刻表设计问题的目标

2．4公交时刻表设计问题的研究综述

2．4．1公交线路日'-IN表设计综述

2．4．2公交网络时刻表协同设计综述

2．4．3现有研究的不足

2．5本章小结

第三章随机行驶时间下公交时刻表设计中不同运行策略比较分析

3．1引言

3．2随机行驶时间下公交时刻表设计

3．3随机行驶时间下公交时刻表设计的一般模型

3．3．1符号定义

3．3．2随机行驶时间下公交时刻表设计的问题描述

3．3．3嵌入不同运行策略的随机行驶时间下公交时刻表设计模型

3．3．4不同运行策略的数学描述

3．4基于Monte Carlo仿真的求解方法

3．5考虑超时行驶费用和驻站策略的公交时刻表设计模型

3．6实验算例与结果分析

3．6．1算例设计

3．6．2基于Monte Carlo仿真方法的收敛性

3．6．3不同运行策略对总时刻表偏差的影响

3．6．4不同运行策略对松弛时间的影响

3．6．5不同运行策略对线路计划行驶时间的影响

3．6．6参数灵敏度分析

3．7本章小结

第四章考虑不均匀发车间隔的公交时刻表协同设计优化方法

4．1引言

4．2考虑不均匀发车间隔的公交时刻表协同设计的数学模型

4．2．1问题描述

4．2．2符号定义

4．2．3车辆协同方式的定义

4．2．4换乘等待时间的数学描述

4．2．5数学模型

4．3模型分析

4．3．1计算复杂性分析

4．3．2可行解的空间特征

4．3．3求解模型的预处理方法

4．4实验算例与结果分析

4．4．1算例设计

4．4．2实验与结果分析

4．5本章小结

第五章考虑加入松弛时间的公交时刻表协同设计优化方法

5．1引言

5．2考虑加入松弛时间的公交时刻表协同设计的数学模型

5．2．1问题的描述与假设

5．2．2符号定义

5．2．3车辆在换乘站点的发车时间

5．2．4不同类型乘客的等待时间

5．2．5随机混合整数规划模型

5．3模型分析和计算复杂性

5．3．1模型特征

5．3．2计算复杂性

5．4嵌入局部搜索的改进遗传算法设计

5．4．1遗传算法简介

5．4．2染色体编码

5．4．3初始种群的生成

5．4．4适值函数

5．4．5交叉操作

5．4．6变异操作

5．4．7精英保留策略

5．4．8局部搜索策略

5．4．9嵌入局部搜索的遗传算法总体实现过程

5．5实验算例与结果分析

5．5．1小规模算例与求解结果

5．5．2针对小规模算例模型的有效性分析

5．5．3不同类型乘客数对模型有效性的影响

5．5．4针对不同规模算例模型的有效性分析

5．5．5求解算法的性能分析

5．6本章小结

第六章多目标公交时刻表协同设计：模型，复杂性和方法

6．1问题背景

6．2多目标优化问题求解算法概述

6．3多目标公交时刻表协同设计的数学模型

6．3．1问题描述与假设

6．3．2符号定义

6．3．3数学模型

6．4模型特征和计算复杂性

6．4．1模型特征

6．4．2计算复杂性

6．4．3帕累托前沿

6．5基于NSGA-Ⅱ的求解算法设计

6．5．1 NSGA-Ⅱ算法描述

6．5．2染色体编码

6．5．3解的评价与选择

6．5．4交叉

6．5．5变异

6．5．6父代与后代种群合并

6．5．7基于NSGA-Ⅱ的算法流程

6．6实验算例

6．6．1算例与参数设计

6．6．2针对小规模算例算法的性能分析

6．6．3针对实际公交网络算法的性能分析

6．6．4发车间隔偏移量对帕累托解的影响

6．7本章小结

7．1论文工作总结

7．2未来研究展望

参考文献

致谢

攻读博士期间发表和录用的论文