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

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】姜启源等，数学模型（第三版），高等教育出版社 …… 此处隐藏：2727字，全部文档内容请下载后查看。喜欢就下载吧 ……