论文部分内容阅读
摘 要：针对公交乘客对出行舒适度的要求，在考虑动态需求的环境下，提出了乘客满意度出行函数。通过分析不同的拥挤现象，建立了非线性优化模型，同时设计遗传算法对所建模型进行求解。最后，通过算例验证了模型与算法的实效性。
关键词：乘客满意度；动态需求
一、引言
随着我国社会经济的快速发展、城市规模的不断扩大，城市交通拥堵现象日趋严重。优先发展城市公共交通是解决城市交通问题的主要出路，所以提高公交系统对乘客的吸引力便成为迫在眉睫的问题，而这个吸引力的体现就是公交系统的服务水平，而公交时刻表就是衡量服务水平最直接的指标之一。
对公交时刻表的研究已有许多文献，[1]根据线路断面乘客量给出了时刻表设计的方法；Palma以乘客总延误时间为目标研究理想状态下的时刻表。[2]基于西安市的公交客流调查数据，讨论了四种不同情况下发车的间隔。这四种情况分别为：在客流需求给定的情况下，可以提供发车间隔来满足乘客出行；当车辆的数量有限的情况下，也相应的改变发车间隔，提高服务质量；若在相邻时段内，发车间隔的确定应采用平滑法；发车时刻表的确定，应考虑不同的时间采用不同的发车间隔。[3]通过对公交列车化现象的分析，以公交运营成本最小和乘客收益最大为目标建立模型，确定最小发车间隔。并利用算例验证模型了模型的可行，结果表明：最小间隔的确定必须满足车辆在运行时不能串行的同时也要满足乘客的利益。
在考虑公交的运行随机性的方面，[4]考虑在实际运营中乘客需求具有随机性，固定需求下优化的公交时刻表不适应运营的要求，随机需求下的期望值模型忽略了不利可能事件对运营的负面影响，针对此情况研究随机需求下公交时刻表设计的鲁棒性优化。[5]针对需求随机变动条件下公交运营设计的综合优化问题，首先将公交运行情况抽象到三维网络中，给出公交车辆运营服务的时空网络图，由此构造基于随机期望值规划的公交时刻表设计与车辆运用综合优化模型，该模型综合考虑了公交企业的经济效益和公交乘客所得到的公交服务水平的优化，并给出公交服务频次和车辆分配协调的启发式算法。[6]研究了车辆随机行驶时间情况下的单线路公交时刻表设计问题。考虑了公交运营者主观偏好对最优时刻表设计的影响，建立了以车辆到站时刻偏差和车辆超时行驶时间的权重之和最小为优化目标的随机期望值模型。
在求解算法方面，文献[7]提出了一种利用遗传算法计算城市公交时刻表的方法。通过对城市公交时刻表和客流的特征分析，以车辆和乘客到站为约束条件，以乘客等待时间为目标函数，建立模型，并根据其的独特性，设计一种特殊编码的遗传算法，最后利用实例对模型进行了验证。[8]文献[13]通过对车站、车辆和出行者的关系，建立了以乘客在站的等待时间和列车载客量为指标的模型，目的是充分使用车底数，提高运营效率。最后给出了遗传算法的求解步骤，以及利用算例进行验证。
本文在已有文献的基础上，基于动态需求，以乘客出行满意度为目标建立模型。并结合上述文献设计遗传算法对模型进行求解。在文章组织过程中，第1节对问题进行了分析和定义，第2节建立非线性模型，第3节设计求解算法，第4节利用算例验证模型和算法，最后给出了本文结论。
二、问题分析
本文将研究一条由郊区发往工作区的公交线路，该线路包含有多个乘客上车站，一个共同的目的地车站，如图1所示，共有n个车站，从车站O1到车站On-1全为上车站，车站D为下车站。
四、算法设计
本文采用遗传算法对上述模型进行求解。首先，对其进行编码时，本文将研究时间段等间隔划分，采用0-1编码方式对染色体进行编码染色体每个基因位都对应这研究时段内的某一时刻，其中“1”表示在该基因位对应的时刻车辆在始发站发车，“0”表示不发车。其次，在遗传算法中将通过适应度的来衡量种群中的个体是否达到或者接近于最优解。适应度值大的将被遗传到下一代的概率大，反之，适应度小的被遗传到下一代的概率小。由于本文的目标函数是最小值优化问题，所以将其通过公式（8）进行转换。
fitness=1Z（8）
遗传操作包含选择操作、交叉操作和变异操作，通过遗传操作产生了新的一代种群，下面将结合染色体的编码形式对其进行阐述。
（一）选择操作
选择操作是对种群个体进行优胜劣汰的操作，其核心是：将个体适应度函数值大的遗传到下一代中，而将适应度小的淘汰掉。本文将采用轮盘赌选擇法。其中，轮盘赌选择的概率与其适应度值的大小成正比，如公式（9）所示。
（二）交叉操作
本文采用单点交叉，单点交叉是随机选取种群中的两个染色体，随机产生交叉点，根据交叉概率Pc将其从交叉点处将其断开，并相互交换。
（三）变异操作
本文采用基本位变异，对染色体随机产生变异点，根据变异概率Pm将其变异成其它等位基因，如图3所示。
图3 染色体变异前
由于在上述模型中，两车辆之间必须满足最小安全追踪间隔，而由于染色体的初始化以及交叉变异操作的都是随机进行的，所以在染色体初始化和交叉变异操作之后须对染色体进行调整。将染色体中不满足最小安全追踪间隔的基因进行调整，将第一车辆固定，找到第二车辆，若两者之间不满足安全追踪间隔，则使第二车辆的基因变为0，将下一个基因变为1，再判断在当前基因对应的时刻发车是否满足安全追踪间隔的约束，若不满足，则继续向后推移。
以上算法的步骤如下所示，其中g表示迭代次数，Gen表示程序终止代数，M表示种群大小，P（g）表示第g代的种群，i表示个体，f（g，i）种群P（g）中个体i的适应度。
Step1：初始化种群P（0），且置g=0；
五、算例
本算例设计一条如图4所示多对一的城际铁路，假设其研究时段为[7：00-8：00]，车辆在每站的停车时间均为1min，1站到2站、2站到3站和3站到4站的运行时间分别为10min、5min和15min。在研究时段内可用车辆数为10列，车辆最小安全追踪间隔为5min，车辆的额定容量为400人。 算法参数选取：种群规模80，迭代次数500，交叉概率0.98，变异概率0.1，拥挤因子M=30。利用以上参数得到车辆的发车时刻表如表1所示，其总目标值为33951.00min，乘客总等待时间为13615.00min。
通过上述计算结果可知，在时间段7：20-7：40之间车辆密度较大，而此时段为客流高峰期，所以满足大客流需要高密度的车辆服务的规律，结果合理。
六、結论
本文主要针对存在多个上车站和一个下车站的特殊情况，在考虑乘客出行满意度的条件下，研究了单线路车辆时刻表优化问题，同时设计了有效的遗传算法进行求解。最后从算例的结果可知，该模型与算法能够有效的求解出质量较高的时刻表。然而，由于该问题的特殊性，导致所建模型与算法不能推广至一般问题，这也是进一步所需要研究的内容。（作者单位：兰州交通大学铁道技术学院）
2011年甘肃省第十二批科技计划（自然科学基金计划第二批）（项目编号：1112RJZA049）
参考文献：
[1] Ceder A.Methods for creating bus timetables[J].Transportation Research Part A General，1987，21（1）：59-83.
[2] 孙芙灵.公交调度中发车间隔的确定方法的探讨[J].西安公路交通大学学报.1997，17（2B）：44-48.
[3] 周嘉男，罗霞，黄启乐，魏强.基于缓解公交车辆化现象的最小发车间隔研究[J].重庆交通大学学报（自然科学版）.2012，31（4）：836-841.
[4] 孙杨，宋瑞，何世伟.随机需求下公交时刻表设计的鲁棒性优化[J].系统工程理论与实践，2011，31（5）：986-992.
[5] 宋瑞，何世伟，杨永凯，等.公交时刻表设计与车辆运用综合优化模型[J].中国公路学报，2006，19（3）：70-76.
[6] 吴影辉，唐加福，宫俊.考虑随机行驶时间的单线路公交时刻表设计优化模型[J].东北大学学报：自然科学版，2015（10）：1393-1397.
[7] 张明辉，牛惠民.一种用于计算城市公交时刻表的复合遗传算法[J].计算机工程与应用.2011，47（20）：210-213.
[8] 徐永实，徐瑞华.遗传算法在轨道交通车辆发车时刻优化中的应用[J].城市公用事业.2011（2）：27-29.
关键词：乘客满意度；动态需求
一、引言
随着我国社会经济的快速发展、城市规模的不断扩大，城市交通拥堵现象日趋严重。优先发展城市公共交通是解决城市交通问题的主要出路，所以提高公交系统对乘客的吸引力便成为迫在眉睫的问题，而这个吸引力的体现就是公交系统的服务水平，而公交时刻表就是衡量服务水平最直接的指标之一。
对公交时刻表的研究已有许多文献，[1]根据线路断面乘客量给出了时刻表设计的方法；Palma以乘客总延误时间为目标研究理想状态下的时刻表。[2]基于西安市的公交客流调查数据，讨论了四种不同情况下发车的间隔。这四种情况分别为：在客流需求给定的情况下，可以提供发车间隔来满足乘客出行；当车辆的数量有限的情况下，也相应的改变发车间隔，提高服务质量；若在相邻时段内，发车间隔的确定应采用平滑法；发车时刻表的确定，应考虑不同的时间采用不同的发车间隔。[3]通过对公交列车化现象的分析，以公交运营成本最小和乘客收益最大为目标建立模型，确定最小发车间隔。并利用算例验证模型了模型的可行，结果表明：最小间隔的确定必须满足车辆在运行时不能串行的同时也要满足乘客的利益。
在考虑公交的运行随机性的方面，[4]考虑在实际运营中乘客需求具有随机性，固定需求下优化的公交时刻表不适应运营的要求，随机需求下的期望值模型忽略了不利可能事件对运营的负面影响，针对此情况研究随机需求下公交时刻表设计的鲁棒性优化。[5]针对需求随机变动条件下公交运营设计的综合优化问题，首先将公交运行情况抽象到三维网络中，给出公交车辆运营服务的时空网络图，由此构造基于随机期望值规划的公交时刻表设计与车辆运用综合优化模型，该模型综合考虑了公交企业的经济效益和公交乘客所得到的公交服务水平的优化，并给出公交服务频次和车辆分配协调的启发式算法。[6]研究了车辆随机行驶时间情况下的单线路公交时刻表设计问题。考虑了公交运营者主观偏好对最优时刻表设计的影响，建立了以车辆到站时刻偏差和车辆超时行驶时间的权重之和最小为优化目标的随机期望值模型。
在求解算法方面，文献[7]提出了一种利用遗传算法计算城市公交时刻表的方法。通过对城市公交时刻表和客流的特征分析，以车辆和乘客到站为约束条件，以乘客等待时间为目标函数，建立模型，并根据其的独特性，设计一种特殊编码的遗传算法，最后利用实例对模型进行了验证。[8]文献[13]通过对车站、车辆和出行者的关系，建立了以乘客在站的等待时间和列车载客量为指标的模型，目的是充分使用车底数，提高运营效率。最后给出了遗传算法的求解步骤，以及利用算例进行验证。
本文在已有文献的基础上，基于动态需求，以乘客出行满意度为目标建立模型。并结合上述文献设计遗传算法对模型进行求解。在文章组织过程中，第1节对问题进行了分析和定义，第2节建立非线性模型，第3节设计求解算法，第4节利用算例验证模型和算法，最后给出了本文结论。
二、问题分析
本文将研究一条由郊区发往工作区的公交线路，该线路包含有多个乘客上车站，一个共同的目的地车站，如图1所示，共有n个车站，从车站O1到车站On-1全为上车站，车站D为下车站。
四、算法设计
本文采用遗传算法对上述模型进行求解。首先，对其进行编码时，本文将研究时间段等间隔划分，采用0-1编码方式对染色体进行编码染色体每个基因位都对应这研究时段内的某一时刻，其中“1”表示在该基因位对应的时刻车辆在始发站发车，“0”表示不发车。其次，在遗传算法中将通过适应度的来衡量种群中的个体是否达到或者接近于最优解。适应度值大的将被遗传到下一代的概率大，反之，适应度小的被遗传到下一代的概率小。由于本文的目标函数是最小值优化问题，所以将其通过公式（8）进行转换。
fitness=1Z（8）
遗传操作包含选择操作、交叉操作和变异操作，通过遗传操作产生了新的一代种群，下面将结合染色体的编码形式对其进行阐述。
（一）选择操作
选择操作是对种群个体进行优胜劣汰的操作，其核心是：将个体适应度函数值大的遗传到下一代中，而将适应度小的淘汰掉。本文将采用轮盘赌选擇法。其中，轮盘赌选择的概率与其适应度值的大小成正比，如公式（9）所示。
（二）交叉操作
本文采用单点交叉，单点交叉是随机选取种群中的两个染色体，随机产生交叉点，根据交叉概率Pc将其从交叉点处将其断开，并相互交换。
（三）变异操作
本文采用基本位变异，对染色体随机产生变异点，根据变异概率Pm将其变异成其它等位基因，如图3所示。
图3 染色体变异前
由于在上述模型中，两车辆之间必须满足最小安全追踪间隔，而由于染色体的初始化以及交叉变异操作的都是随机进行的，所以在染色体初始化和交叉变异操作之后须对染色体进行调整。将染色体中不满足最小安全追踪间隔的基因进行调整，将第一车辆固定，找到第二车辆，若两者之间不满足安全追踪间隔，则使第二车辆的基因变为0，将下一个基因变为1，再判断在当前基因对应的时刻发车是否满足安全追踪间隔的约束，若不满足，则继续向后推移。
以上算法的步骤如下所示，其中g表示迭代次数，Gen表示程序终止代数，M表示种群大小，P（g）表示第g代的种群，i表示个体，f（g，i）种群P（g）中个体i的适应度。
Step1：初始化种群P（0），且置g=0；
五、算例
本算例设计一条如图4所示多对一的城际铁路，假设其研究时段为[7：00-8：00]，车辆在每站的停车时间均为1min，1站到2站、2站到3站和3站到4站的运行时间分别为10min、5min和15min。在研究时段内可用车辆数为10列，车辆最小安全追踪间隔为5min，车辆的额定容量为400人。 算法参数选取：种群规模80，迭代次数500，交叉概率0.98，变异概率0.1，拥挤因子M=30。利用以上参数得到车辆的发车时刻表如表1所示，其总目标值为33951.00min，乘客总等待时间为13615.00min。
通过上述计算结果可知，在时间段7：20-7：40之间车辆密度较大，而此时段为客流高峰期，所以满足大客流需要高密度的车辆服务的规律，结果合理。
六、結论
本文主要针对存在多个上车站和一个下车站的特殊情况，在考虑乘客出行满意度的条件下，研究了单线路车辆时刻表优化问题，同时设计了有效的遗传算法进行求解。最后从算例的结果可知，该模型与算法能够有效的求解出质量较高的时刻表。然而，由于该问题的特殊性，导致所建模型与算法不能推广至一般问题，这也是进一步所需要研究的内容。（作者单位：兰州交通大学铁道技术学院）
2011年甘肃省第十二批科技计划（自然科学基金计划第二批）（项目编号：1112RJZA049）
参考文献：
[1] Ceder A.Methods for creating bus timetables[J].Transportation Research Part A General，1987，21（1）：59-83.
[2] 孙芙灵.公交调度中发车间隔的确定方法的探讨[J].西安公路交通大学学报.1997，17（2B）：44-48.
[3] 周嘉男，罗霞，黄启乐，魏强.基于缓解公交车辆化现象的最小发车间隔研究[J].重庆交通大学学报（自然科学版）.2012，31（4）：836-841.
[4] 孙杨，宋瑞，何世伟.随机需求下公交时刻表设计的鲁棒性优化[J].系统工程理论与实践，2011，31（5）：986-992.
[5] 宋瑞，何世伟，杨永凯，等.公交时刻表设计与车辆运用综合优化模型[J].中国公路学报，2006，19（3）：70-76.
[6] 吴影辉，唐加福，宫俊.考虑随机行驶时间的单线路公交时刻表设计优化模型[J].东北大学学报：自然科学版，2015（10）：1393-1397.
[7] 张明辉，牛惠民.一种用于计算城市公交时刻表的复合遗传算法[J].计算机工程与应用.2011，47（20）：210-213.
[8] 徐永实，徐瑞华.遗传算法在轨道交通车辆发车时刻优化中的应用[J].城市公用事业.2011（2）：27-29.