公交司机排班方案的建模论文

公交司机排班方案的建模论文

高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

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

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

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

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 许昌学院 参赛队员 (打印并签名) ：1. 孙 莉 指导教师或指导教师组负责人 (打印并签名)： 张亚东 岳晓鹏

日期： 2011 年 7 月23 日

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

公交司机排班方案的建模论文

2011高教社杯全国大学生数学建模竞赛

编 号 专 用 页

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

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

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

公交司机排班方案的建模论文

公交司机排班方案

摘要

公交司机排班方案是决定交通客运健康发展前提的重要因素，合理的排班制度将直接影响社会、效益和司机的劳工权利。传统的跑班没有合理的排班安排，是以各线路的闲忙随意的掉用司机、机车跑班。这种跑班方式没有很好的体现对各方利益的照顾和社会利益的最大化。我们利用均匀分布模型分析解决以上问题，并根据模型给出最优公交司机排班方案。

本文中，我们围绕公交司机排班问题，结合我们已学的知识，与现实相结合，对问题进行层层深入的研究，最终给出了最优的公交司机排班方案。针对问题1，我们采用了分段函数分析法，得出每天的班次数与班次之间的时间间隔以及正常和高峰有着密切的关系。针对问题2，我们先利用数理统计知识分别求出每一班所用时间的期望及每天所跑班次的数的期望，在此基础上，我们建立了0,1模型。对于问题3，我们则在问题二结果的基础上建立一个新的0,1模型。

Ⅰ、分段函数分析：由于每天的时间被分为了若干个正常和高峰，所以我们把每天按照正常和高峰分为若干段，建立一个分段函数根据题中给出的条件，在合理的假设的基础上我们的到了最少班次。

Ⅱ、0,1模型分析：因为在问题2和3中，一个司机在第i班次时只有开与不开两种选择，也就是说问题中的决策变量仅限于取0或1两个值，因此我们采用0,1模型。

。

关键词： 排班 分段分析 0,1模型

公交司机排班方案的建模论文

一、问题重述

现代化进程是快速发展，许多城市的建设都把道路的规划放在了首要的考虑议题。这样，随着城市经济的发展，道路是越来越多。基于公交优先，百姓优先的原则，使得该公交总公司开辟了各种线路，包括市内线，近郊线，远郊线，旅游线，机场线，社区线等140多条线路，以满足老百姓出行需要。众多线路的开辟，必然会出现一些问题。据反映及相关调查，现实中有些线路司机不足，有些线路司机充足，这就导致了司机不足的线路常常要向其他线路戒掉司机和车辆跑班，从而影响了部分线路的排班秩序；而线路司机不足，却无法向其他线路借调司机和班车的就导致了这些司机每天工作时间过长，需开车12-13小时，影响司机休息，或有部分司机连续开车时间达到5、6小时，易导致工作疲劳，这样就容易给交通留下安全隐患；有的线路由于排班不当，导致在上班高峰期或节假日时段经常出现堵车现象，而正常时段确出现“空车”现象，影响公交公司收益状况及百姓乘车情绪，打乱了线路调度计划，使得交接班司机和乘客怨声载道。

本文围绕如何确定最优排班，基于线路的基本情况及相关规定（1，司机每天上班时间不超过8小时；2司机连续开车不得超过4小时；3，每名司机至少每月完成120班次。），重点解决以下问题：

1.根据五月份的节假日情况，给出当月最少班次总数； 2.建立适当的数学模型，合理的设计该月线路的司机排班方案；

3.基于2的司机排班方案，给出每天需要的司机人数；在每个司机每周连续工作五天，休息两天的前提下，通过一周需要司机人数给出司机总数最少的排班方案。

二、问题分析

城市城际公交拥有运量大、速度较快、污染低、安全、便宜、方便等优势，逐渐成为全国各城市客运交通系统的骨干。目前，基于节能减排新观点深入人心，我国正在大力推行城市公交系统的建设，而公交司机的排班成为了公司领导、司机、百姓最为关注的问题。随着人们时间观、舒适观、及权利的维护观相对提升，制定高效的司机排班方案越来越难，其不仅要考虑社会效益、节假日安排、乘客乘坐能力，还要考虑公交公司的收益状况、公交司机的跑班时间安排等情况。

司机跑班制度安排将直接影响公交公司的利益及普通百姓的上班出行情况，不合理的排班方案会是公交资源的浪费，也会使百姓对公交怨声载道失去信心。因此，城市公交司机排班方案的制定是一项比较复杂的系统工程，并且受到政府、公交公司和百姓的热情关注。

传统的排班制度的制定大多依赖于临时客运量的变化随即安排的，这种做法导致了诸多问题，如：司机过度跑班引起安全隐患、百姓等车过长或过度拥挤乘车，怨声载道……这种传统的排班制度不能带来双赢甚至多赢。高效的司机排班制度要考虑到各方

公交司机排班方案的建模论文

的利益，采取分层分段的方式进行研究，从而能达到各方利益共同兼顾的目标。

三、基本假设

根据不同的时间段和节假日情况建立排班模型，兼顾司机上班制度要求和当月节假日情况给出最少司机跑班次数安排制度。影响排班制度安排的主要因素有：司机身体状况、机车运行状况、百姓出行状况、其它公司的竞争、服务状况。

根据这些因素我们提出以下基本假设： 1.各司机的身体状况基本健康稳定。 2.每天正常检车，机车正常出行。 3.百姓出行状况即乘客流量保持不变。 4.不考虑其它公司及私人的竞争。 5.不考虑因天气变化带来的客流量变化。

6.忽略个别交通事故引起的交通阻塞，和公交车因老化引起的负外效应。 7.短时间内，不考虑通货膨胀和物价上涨引起的客流量变化。 8.忽略因油价的变化带来的，出车频率。 9. 每次发车时间和运行时间都以整分钟计。

10．某一班车在运行时只要有高峰时段就按高峰的运行时间。 11. 最后一班发车时间不是收班时间，再加发一班。

12.从起始站出发到终点站再回到起始站为一个来回，记作一个班次。

四、变量申明及符号说明

公交司机排班方案的建模论文

五、模型的建立与求解

5.1问题一模型的建立与求解 5.1.1问题一的分析

今年五月份的节假日情况是：五月份共31个日，其中节假日11日，非节假日20日。由附件，以6:20-18:10为开收班时间；排班间隔：平时为8-10分钟/班，上下班为4-8分钟/班,节假日为5-10分钟/班。

由于非节假日分为正常与高峰期，排班间隔不同，所以我们考虑把非节假日的正常工作时间分为6个时段。每个时段发车班次用xi表示（i表示当天第i个时段）。用mi表示第i个时段的发车间隔。取合适的mi使得xi的总合最小。结合题目中的其它约束条件可分析，此题符合线性规划模型。 5.1.2问题一模型的建立

1. 由问题一的分析可得，此问题的目标函数为每天的班次最少 即：minN

x

ii 1

6

N表示一天的班次总数。

2. 每个时段的发车时间不少于这个时段的时长。

即：

xm Q

i

i

i 1

k

kk

i

k 1,2,3,4,5,6

k

i 1

xm m Q

i

i

k

i 1

i 1

i

k 1,2,3,4,5,6.

此问题模型如下

公交司机排班方案的建模论文

minNj xi （1）

i 1

k

k

ximi Qi

i 1

i 1

k

k

S.T. ximi mk Qi

i 1 i 1

8 mi 10

4 mi 8

6

k 1,2,3,4,5,6.k 1,2,3,4,5,6.i 2,4,6.i 1,3,5.

（2）

节假日单日发班最少班次的数学公式为：

T

minkj

t

5 t 10. （3）

式中T表示为五月份单日的上班总时间，t为时间间隔，单位是分钟。 5.1.3问题一模型的求解

利用LINGO对（2）式编程求解，得非节假日单日单程的最少发车班次为81次。,节假日单日最少班次为72次。则由公式：

20

K1 minNj，式中K1表示五月份非节假日公交司机跑班最少班次。

j 111

K2 minkj，式中K2表示五月份节假日公交司机跑班最少班次。

j 1

易知五月份总的公交司机跑班最少班次K，K K1 K2，知K=2410次。 非节假日和节假日公交司机跑班发车时间表如表-1-、表-2-

公交司机排班方案的建模论文

表-1-

表-2-

5.1.4问题一结果的分析及验证 5.2问题二模型的建立与求解 5.2.1问题二的分析

1. 问题一中我们给出了五月份公交司机的最少跑班班次，但在现实中，司机在跑班过程中总会遇到各种因素影响由排班方案给出的跑班安排。也就是不可能的总是实现司机按点发车，准点到站，那么在问题二中，我们就有必要考虑这些因素来建立适合的数学模型。

2. 发车的时间间隔是在一定范围内浮动的，不确定的。司机会根据等待人数的多少

公交司机排班方案的建模论文

来选择间隔时间。如，高峰期，发车间隔为4-8min，当等待的人数较多时，司机就会选择较短的时间间隔4min发车，而较少的人数时则会选择8min。在一天之内，发车的时间间隔大致服从随机均匀分布函数，运用此函数分别算出高峰期与正常期的发车时间间隔的随机均匀分布，并把数据分别保存在数组a1i和a2i中，以备后期计算使用。用

t1i和 t2i分别表示高峰期与正常期的发车时间间隔。 5.2.2问题二模型的建立与求解

1. 理的给出五月份该线路的司机排班方案，我们要计算出当月非节假日和节假日单日跑班间隔和跑班次数N。我们用ti 1表示第i班车的上一班车发车时间， t1i表示这班车高峰期的发车时间, t1表示高峰期总的时间间隔。 t2i表示这班车正常期的发车时间，

t2表示正常期总的时间间隔。T表示一天的工作时间。a1i表示高峰期时间间隔运用随机均匀

分布产生的n个数据，a2i表示正常期运用随机均匀分布产生的n个数据。m表示每天发车的时间，初始值设为0。用数学式子表达如下：

ti ti 1 t1i

t t t2

i ii 1

4 a1i 8,

s.t 8 a2i 10, t1 a1,

i

i

t2i a2.i

t1 t2 T

此式子由MATLAB编程可解出每天需要的班次数N。由于每次运用随机均匀分布函数所产生的数据不同，则结果N也不同。故我们采样了50个结果数据，数据如下：

为了使一天的班次数更接近现实，我们采用取平均值的方法来求出每天总的班次数为98.9，整为99。故每天的总班次数为99次。

公交司机排班方案的建模论文

2. 为了求解需要的司机数及排班方案，我们建立如下模型：

xijk

j天的第k个班次 1,第i个司机跑第

j天的第k个班次 0,第i个司机不跑第

Cijk：第i个司机跑第j天的第k个班次所用的时间。

t：前后两班车次的时间间隔

数学表达示如下：

目标函数

minP

s.t

p

n

x

i 1k 1m

n

ijk

99

j 1,2, 31 %每天至少99班次

xijk xijk 1 xijk 2 3 i 1,2 p;j 1,2 m;k 1,2, n %司机不能连续开三班

x

j 1k 1

ijk

120 i 1,2, p %每个司机每月至少开120班次

x

k 1nk 1

n

ijk

cijk 480 i 1,2, p;j 1,2, m %每个司机每天的工作时间不超过8小时

i 1

t

ti 710 %不存在加班情况

5.3问题三模型的建立与求解

为了合理的给出五月份该线路的司机排班方案，我们要计算出当月非节假日和节假日单日跑班间隔和跑班次数。公交司机的排班的具体方法如下：

1）首先根据公司的所有公交信息，将所有公交跑班编制为若干个班次串，所谓的班次串就是将本班次的起始站到终点站衔接起来，生成若干个可以由一辆班车去跑班，每一个成为“班次串”。

2）针对编号的班次串计划，对每一个班次串指派班车跑班。

3）对每一个班次串和跑班指派班组。这样，一辆班车就包括了班次串编制、班车指派、班组指派3个优化问题，而且它们互相影响和联系。

由于班车排班问题规模大、约束条件众多，和那建立一个模型和算法来求解，一个有效的方法就是采用层次分块分别建立模型和算法，然后再综合平衡，以求最优效果。

班组指派优化模型的建立 班组指派问题就是针对已经编好的班次串计划，综合考虑公司可用班车的情况，在满足班车各种条件下为每一个班次串指派班车。

公交司机排班方案的建模论文

min cijxkj（4）

k 1i 1j 1

m

nk

n

s.t. xkj m （5）

k 1

m

x

j 1

n

kj

1 （6）

xkjrj Rki,(i 1,2,...,nk),(j 1,2,...,n)（7）

xkjPj Pki,(i 1,2,...,nk),(j 1,2,...,n)（8）

xkjdj Dki,(i 1,2,...,nk),(j 1,2,...,n)（9）

1,班车j跑班次串k的任务xkj

0,否则

j 1,2,...,n，n为班车数；cij为班次i和班车j之间的匹配差异惩罚值。

式中，k 1,2,...,m，m为班次串数；i 1,2,...,nk为第k个班次串内的班次数；目标函数（4）针对所有的班次串在指派班车的函数惩罚适应度最小，是针对批量

的班车的全局优化，约束条件（5）证选择与班次串相等的执行班车数，约束条件（6）保证为每一个班次串只指派一辆班车，约束条件（7）要求为班次串指派的班车满足该班次串内的任一班车的跑班要求，约束条件（8）要求指派的班车满足该线路的乘客流量的要求。

本文所建立的模型的求解属于NP-，采用数学规划等方法很难求解。本文根据模型特点构造一种自适应单亲遗传算法，算法中主要采用自然编码，以单点基因换位为主，辅以多点基因换位和基因移位的遗传算子的方法，基因换位和移位的概率自适应动态调整，同时使用专家规则进行修正。

一，遗传操作算子 基因换位算子是按一定的概率交换染色体某些位置上基因的过程，被交换位置随机确定。基因换位可分为单点换位和多点换位，单点换位是一次知交换一对基因的位置；多点换位是对预先给定的证书N，取机数i(1 i N)一次交换i对基因。本文在求解过程中以单点基因换位为主，辅以多点基因换位和单点基因移位算子。

二，单点基因换位概率、多点基因换位及基因移位概率的自适应调整 本文将M.Srinivas提出的自适应遗传算法引入到单亲遗传算法中，并针对M.Srinivas算法的缺点，根据适应值的集中程度，动态调整每一代群体的单点基因换位概率pe、多点换位基因概率pm及基因移位概率ps，采用每一代群体的最大适应度值fmax、最小适应度值fmin、平均适应度值f

ave来作为适应值集中程度的判断标准。当fminfmax ,fminfave 时，

公交司机排班方案的建模论文

判断为当代群体中个体趋于集中，根据集中程度自适应调整概率；否则，判断为群体中个体不趋于集中，仍维护正常情况下的单位基因换位概率pe、单点基因换位概率pm及基因移位概率ps。概率调整公式如下：

fminfminfmin

, , pe0 (1 pe0)

fmaxfmaxfavepe

pe,否则 0

fminfminfmin

, , pm0 (1 pm0)

fmaxfmaxfavepm

pm,否则 0

fminfminfmin

, , ps0 (1 ps0)

fmaxfmaxfaveps

ps,否则 0

因移位概率。

三，自适应单亲算子求解流程如下：

① 输入模型求解所需数据 读入要计算的合同信息。

式中，pe0为初始单点基因换位概率；pm0为初始单点基因换位概率；ps0为初始基

② 算法参数的初始化 确定算法种群数目和结束最大循环代数，和基因单点换位、多点换位、基因移位的初始概率pe0，pm0，ps0，然后根据种群数目给出一代初始的染色体，作为当前代染色体。

③ 计算当前代染色体的函数适应值，记录最优个体为当前最优解，并判断是否满足结束准则，如是，则停止转⑦。否则，进行下一步④。

④ 对当前染色体进行概率的自适应动态调整，按公式计算单点基因换位概率pe、单点基因换位概率pm及基因移位概率ps。

⑤ 对当前染色体进行单亲遗传操作：以设定的概率pe，pm，ps依次进行基因单点换位、多点换位和单点移位操作，最后进行选择操作，选择出一代最优的染色体。

⑥ 将选出的一代染色体作为当前代染色体，转③。 ⑦ 输出当前最优解作为算法的解。

六、参考文献

【1】张德喜 赵磊生主编 MATLAB语言程序设计教程（第二版）2006.6

公交司机排班方案的建模论文

【2】韩中庚主编.实用运筹学 清华大学出版社2007.12 【3】姜启源等，数学模型（第三版），高等教育出版社，2003 【4】吴赣昌等，概率论与数理统计，中国统计出版社2007.11

附录：

model:

MIN=x1+x2+x3+x4+x5+x6; x1*m1>130; (x1-1)*m1<130; x2*m2+x1*m1>310; (x2-1)*m2+x1*m1<310; x3*m3+x2*m2+x1*m1>430; (x3-1)*m3+x2*m2+x1*m1<430; x4*m4+x3*m3+x2*m2+x1*m1>610; (x4-1)*m4+x3*m3+x2*m2+x1*m1<610; x5*m5+x4*m4+x3*m3+x2*m2+x1*m1>700; (x5-1)*m5+x4*m4+x3*m3+x2*m2+x1*m1<700; x6*m6+x5*m5+x4*m4+x3*m3+x2*m2+x1*m1>710; (x6-1)*m6+x5*m5+x4*m4+x3*m3+x2*m2+x1*m1<710; 4<m1; 4<m3; 4<m5; 8<m2; 8<m4; 8<m5; m1<8; m3<8;

Local optimal solution found.

Objective value: 80.00000 Extended solver steps: 20 Total solver iterations: 408

Variable Value Reduced Cost X1 17.00000 1.000000 X2 18.00000 1.000000 X3 15.00000 1.000000 X4 18.00000 1.000000 X5 11.00000 1.000000 X6 1.000000 1.000000 M1 8.000000 0.000000 M2 10.00000 0.000000 M3 8.000000 0.000000

公交司机排班方案的建模论文

M4 10.00000 0.000000 M5 8.000000 0.000000 M6 10.00000 0.000000

Row Slack or Surplus Dual Price 1 80.00000 -1.000000 2 6.000000 0.000000 3 2.000000 0.000000 4 6.000000 0.000000 5 4.000000 0.000000 6 6.000000 0.000000 7 2.000000 0.000000 8 6.000000 0.000000 9 4.000000 0.000000 10 4.000000 0.000000 11 4.000000 0.000000 12 4.000000 0.000000 13 6.000000 0.000000 14 4.000000 0.000000 15 4.000000 0.000000 16 4.000000 0.000000 17 2.000000 0.000000 18 2.000000 0.000000 19 0.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 0.000000 0.000000 25 0.000000 0.000000

第二个问题的程序如下：

function s=diaotu(t) t1=random('unif',4,8,1,120) t2=random('unif',8,10,1,120) n=1 %初始累加计数器，0时刻发出第一班车

m=0 %设每天的第一次发车时间为0，一天共工作710分钟 while(m<=710) n=n+1

if(m>=0&&m<130||m>=310&&m<430||m>=610&&m<700) m=m+t1(n-1)

else (m>=130&&m<310||m>=430&&m<610||m>=610) m=m+t2(n-1) end

公交司机排班方案的建模论文

end end

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