( 0 < θ < 100% )。 （2）最大最小发车时间间隔约束
任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即：
Tmin ≤ ∆tk1 ≤ Tmax ( k1=1，2)
其中： Tmax 表示相邻两车之间的最大发车间隔( min );Tmin 表示相邻两车之间的最小发车 间隔( min )。
乘客总的等车时间成本为：
∑ ω
=
2.863 λ1
×
S
×
n j =1
rj
×
(∆tk1 )2 2
( k1 = 1,2，3）
然后，通过加权系数α 和 β 将价值化后的两部分合并，使得公交优化排班问题成为
一个单目标优化问题。合并后的目标函数：
∑ ∑ α ×260
×
L
×
(
λ1
×
k k =1
Tk ∆t k
+
λ2
四、符号说明
Tk 表示平时第 k 时段的时段长度； ∆tk 表示平时第 k 段时间的发车间隔； T3 表示节假日的时段长度； ∆t3 表示节假日的发车间隔； ∆tk1 表示第 k 段时间的发车间隔（包括平时和节假日）； λ1 表示某月除去节假日后总的天数； λ2 表示某月节假日总的天数； S 表示某月发车总班次； m 表示在整个调度周期内发车车次总数； n 表示线路的车站总数； rj 表示第 j 站在调度周期内随时间变化的乘客到达率（ j =1，2，…， n ）； α 表示目标函数中总发车车次的加权系数； β 表示目标函数中乘客总的等车时间的加权系数； L 表示线路总公里数； WTij 表示所有乘客总的等车时间（min）；
2010 高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料 ），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。
×
T3 ∆t k
)+ β
×
2.863 λ1
×
S×
n
rj
j =1
×
(∆tk1 ) 2 2
(k
= 1,2 ； k1 = 1,2，3）
目标函数可以用乘客利益和公司利益分为两类，这两类目标是相互冲突的，两个目 标函数就存在一个权值的问题，体现在目标函数中两项的加权系数的大小。在不同的线 路，甚至同一线路的不同时段加权系数的最优值都是不相同的。例如：工作日的高峰正 是多数乘客上班时间，也是一天中乘坐公交车人数的高峰期，所以这段时间里所需的车 辆数也是最多的。从乘客的方面考虑，早上上班迟到对他的利益所示相当大，因此乘客 希望等车的时间比较短，这个时候乘客等车时间的加权系数要大些。初始化时取两加权 系数为 0.2 和 0.8，然后在计算过程中根据结果逐步进行比较、调整。 5.2.2 确定约束条件
2010 高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
公交司机排班方案模型
摘要 本文就公交司机排班问题应用遗传算法和多目标规划建立数学模型。运营车辆智能 排班问题是公交车辆智能调度需要解决的典型问题之一，本文应用已有的数据，并兼顾 到乘客和公交公司的双重利益，建立起一个符合实际情况的数学模型。在此基础上引入 了遗传算法（GA），针对公交智能排班问题，构造了符合行车规律的编码方式、遗传算 子，并实现了程序的编码工作，最后进行了模拟实验。 问题一在一定的约束条件下，如何合理安排其组织部分（操作）所占有资源、运行 时间及先后顺序，以获得运输成本或时间最优化。在理论研究中，车辆班次问题可看做 资源分配问题。 问题二在保证运营效率的情况下寻求乘客等待时间最少和保证服务水平的前提下使 车队运营效率较高，基于以上的考虑行车时刻表的编制应是在满足客流需求的前提下， 尽量减少不必要的投入，这是个多目标优化问题，遗传算法是解决公交排班问题的有效 方法之一。 问题三是在一定的约束条件下，合理安排排班方案使司机总数最少，以达到资源的 合理分配。 关键词：公交智能排班；遗传算法；遗传算子
六、模型的求解
6.1 模型Ⅰ的求解
我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1.
2. 3. 指导教师或指导教师组负责人 (打印并签名)：
日期： 2011 年 07 月 24 日
赛区评阅编号（由赛区组委会评阅前进行编号）：
（河南省人民政府网 /zwgk），许昌市 2010 年城镇居民的平均 工资水平为 1374.19 元/月，按照双休日工作及法定的放假时间，现在一个月大概有 λ2 天 的休息时间，即有 λ1 天在工作，平均每天按工作 8 小时计算。
平均每分钟的工资为：
1374.19 = 2.863 (元) λ1 × 8 × 60 λ1
下面是某条线路的基本情况（附件），请你根据有关数据完成下列问题。 规定： （1）司机每天上班时间不超过 8 小时； （2）司机连续开车不得超过 4 小时； （3）每名司机至少每月完成 120 班次。 问题一：根据五月份的节假日情况，求出当月最少班次总数； 问题二：阐述你对上述规定的理解，并根据你的理解建立适当的数学模型，合理地 设计五月份该线路的司机排班方案； 问题三： 根据五月份该线路的司机排班方案，计算出每天需要的司机人数，假如 规定每个司机每周连续工作五天，休息两天。请你通过某周（周一至周日）需要司机人 数求出司机总数最少的排班方案。 有关的数据为： 1、该线路的开收班时间：
( k1 = 1,2，3）
这两个目标是相互联系矛盾的，不可能同时达到双方最小。当 ∆tk1 增大时，第一项 是在减小的，而第二项是在增大的。这样就形成了一个需要寻求平衡点的问题，得到总
体的最优。现在将两项加权合并为单目标函数，这里我们考虑将两项都这算为一种费用。 第一项总的发车车次可折算为公交公司的运输费用。我们由公交公司的调研数据可
（1）最大最小发车时间间隔约束 任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即：
Tmin ≤ ∆tk1 ≤ Tmax ( k1=1，2)
其中： Tmax 表示相邻两车之间的最大发车间隔( min );Tmin 表示相邻两车之间的最小发车
间隔( min )。 （2）两个相邻的发车间隔之差的约束 为保证发车时刻的连续性，任意两个相邻的发车间隔之差不宜太大，即
知，平均每车公里的成本是 260 元，这个费用包括了司乘人员的劳动工资、车辆耗油、 车辆折旧费用等等各项费用之和的折算。因此，一月内总的发车车次由价值来衡量，可 以折算为：
∑ R =
260 ×
L
×
(
λ1
×
k k =1
Tk ∆t k
+
λ2
×
T3 ∆t k
)( k =1，2)
第二项乘客总的等车时间也可以折算为乘客等车损失的费用。根据有关资料的报道
∆tk1+1 − ∆tk1 ≤ ε ( k1=1，2)
其中： ε 表示两相邻发车间隔之差的限值。
5.2 模型Ⅱ（问题二的模型） 5.2.1 确定目标函数
公交司机排班是公交企业对社会的承诺，决定着为乘客服务的水平，发车间隔越小，服 务水平越高，但是公交企业投入的成本越高，公交司机的排班应是在满足客流需求的前 提下，尽量减少不必要的投入，这是个多目标规划问题。
三、模型的假设
制定公交车调度方案需要考虑的因素非常多,且很多因素都是随机的。为了抓住重点, 简化模型建立及求解,必须作一定的简化假设和设定：
（1）各公交车为同一车辆类型； （2）在同一时间段内，相邻两车发车时间间隔相等； （3）公交车按调度时间表准时进站和出站，车速恒定，保持匀速行驶，途中没有堵 车和意外事故； （4）各时段以内乘客到站服从均匀分布； （5）每辆车经过各个车站时不会留有乘客； （6）在车站等待的人绝大多数不会离去； （7）以分钟作为最小的时间单位；
∑ min
S
=
λ1
×
k k =1
Tk ∆t k
+
λ2
×
T3 ∆t3
( k = 1,2)
排车班次受到平时时间段和节假日时段的影响，故将排班次数分为平时时段与节假日时
∑k
段两种情况。上述目标函数中 λ1 ×
k =1
Tk ∆t k
为某月平时时段的发车总班次，
λ2
×
T3 t3
为某月
节假日时段的发车总班次。 5.1.2 确定约束条件
5
（1）平均满载率的约束
客运量
平均满载率=
×100%
车型定员× 车次
m n ti
∑∑ ∑rj ×t
= i=1 j=1 t =ti −1
×100% > θ
Q车容量 × m
其 中 ： Q车容量 表 示 车 辆 满 载 时 的 容 量 （ 人 / 车 ）； θ 表 示 每 车 平 均 期 望 满 载 率
2
排班问题有如下特点： （1） M 为公交车辆集，每辆车在运输运行中只遵循一种运输方式。 （2） 每辆车按时发车，根据不同的运行时段，准时完成运输任务。 公交车辆运输排班问题是指，在固定行驶线路上，根据不同时段、依照一定的次序
关系，合理地编排运输车辆运行作业形式，以达到供需平衡，满足系统的性能指标。本 文采用的优化指标为：在不影响乘客出行的前提下，乘客的等待时间和公司发车次数最 少，并避免出现“大间隔”。本文采用遗产算法优化公交车辆运营排班问题。