基于Block Gibbs的航空公司外航服务人员排班算法

卢敏; 王莉; 唐菱; 卢敏; 王莉; 唐菱

doi:10.11999/JEIT180181

　输入：任务集 ${{{Ω}}}$；员工资质集 ${{{P}} }$；折中因子 $\lambda $；迭代次数 $L$；
退火温度 $T\;$；衰减因子 $\beta $; block大小 $K$

　输出：航班-员工分配 $\left\{ {x_{ij}^d} \right\}$

　(1) 采用第2.2节数据拷贝技巧构造辅助任务集 ${{{Ω}}}'$

　(2) 利用第2.4节算法2产生松弛初始解 $\left\{ {x_{ij}^d} \right\}$

　(3) for ${\rm{iter}} = 1,2, ·\!·\!· ,L$

　(4) for $d = 1,2, ·\!·\!· ,M$

　(5) 　　　设 $\forall i,j,\quad x_{ij}^d = 0$以移除员工 $d$任务分配集

　(6) 　　　抽样员工 $d$白夜班属性 ${y^d}{\rm{ \sim Berp}}({N_0}/N)$
// ${N_0},N$表示任务集中白天航班数和总航班数

　(7) 　　　　foreach task ${l_{ij}} \in {{{Ω}}} \cup {{{Ω}}}'$

　(8) 　　　　　if (式(5)或式(6)不满足) then $x_{ij}^d = 1,{y^d} = {t_{ij}}$
//确认员工d的白夜班类型 ${y^d}$

　(9) 　　　　　else $x_{ij}^d{\rm{ \sim }}\Pr ( \cdot |{x^{ - d}},x_{ - ij}^d,y) \propto {\rm{boolean \ of\ eqn(5)}}$
$/ {\rm{value\ of\ eqn}}(1)$ //抽样员工航班分配

　(10) 　　　　　 ${{{U}} } = \left\{ {d|{x^d_{ij}} = 1,d = 1,2, ·\!·\!· ,M} \right\}$,
${{{{U}} }^{{{\rm c}} }} = \left\{ {d|x_{ij}^d = 0,{y^d} = {t_{ij}}} \right\}$

　(11) 　　　　　 ${{{{K}} }^{{{\rm c}} }} = {{{{U}} }^{{\rm c} }}\left( {{\rm{randperm}}(|{{{{U}} }^{{{\rm c}} }}|,K{\rm{)}}} \right)$, $\forall d \in {{K}^{\rm c}} $,
$x_{ij}^d = 1$, //向某一航班增加 $ K $名员工

　(12) 　　　　　 ${{{KU}} } = {{{{K}} }^{{{\rm c}} }} \cup {{{U}} }\left( {{\rm{randperm}}(|{{{{K}} }^{{{\rm c}} }} \cup {{{U}} }|,K{\rm{)}}} \right)$
//向某一航班抽回 $K$名员工

　(13) 　　　　　 ${{{{x}}}^{\rm{new}}}{\rm{ \sim }}\Pr (x_{ij}^{d\,\!'} = 0,d\,\!' \in K{{{U}} }|{x^{ - d\,\!'}},y) $
$\propto {\rm{boolean \ of \ eqn(5)}}/{\rm{value \ of \ eqn}}(1)$

　(14) 　　　　　采用模拟退火算法控制可行解 ${{{{x}} }^{\rm new}}$的接受或拒绝

　(15) 　　　　　 $T = T \times \beta $

表 1 算法1：基于Block Gibbs的航空公司外航服务人员排班算法

　输入：任务集 ${{{Ω}}}$；员工资质集 ${{{P}} }$；迭代次数 $L$；退火温度 $T\,$；衰
减因子 $\beta $; block大小 $K$

　输出：航班-员工分配 $\left\{ {x_{ij}^d} \right\}$

　(1) 初始化 ${y^1},{y^2}, ·\!·\!· ,{y^M} = 0$

　(2) for ${\rm{iter}} = 1,2, ·\!·\!· ,L$

　(3) 　for $d = 1,2, ·\!·\!· ,M$

　(4) 　　设 $\forall i,j,\quad x_{ij}^d = 0$以移除员工 $d$任务分配集

　(5) 　　抽样员工 $d$白夜班属性 $({\rm{new}}{y^d},{{\rm new}}{{{{x}} }^d}) \sim $
$ \Pr ({y^d},x_{ij}^d = I[{y^d} = = {t_{ij}}]|{y^{ - d}},{{{x}} }) \propto {\rm{ value \ of \ eqn (7)}}$

　(6) 　　if $\left ({\rm eqn}(7) {等于}\sum {{{{{γ}}}_{ij}}(t)} \right)$ return $\left\{ {x_{ij}^d} \right\}$
// 得到满足约束的松弛解

　(7) 　　采用模拟退火算法控制可行解 ${{\rm new}}{{{{x}} }^d}$的接受或拒绝

　(8) 　　 ${{{U}} } = \left\{ {h|{y_d} = {y_h},h = 1,2, ·\!·\!· ,M} \right\}$,
${{{{U}}}^{\rm c}} = \left\{ {h|{y_d} \ne {y_h},h = 1,2, ·\!·\!· ,M} \right\}$

　(9) 　　 ${{{{K}} }^{{{\rm c}} }} = {{{{U}} }^{{{\rm c}} }}\left( {{\rm randperm}(|{{{{U}} }^{{{\rm c}} }}|,K{\rm{)}}} \right)$

　(10)　　 ${{{KU}} } \!=\! {{{{K}} }^{{{\rm c}} }} \!\cup\! {{{U}} }\left( {{\rm randperm}(|{{{{K}} }^{{{\rm c}} }} \!\cup\! {{{U}} }|,K{\rm{)}}} \right)$
$ \propto $ value of eqn(7)

　(11) 　　 ${{\rm new}}{{{{x}} }^d} = \left( {\left( {{{{{U}}}^{\rm c}} \cup {{{U}} }} \right)\backslash {{{{K}}}U}} \right) \cup \left\{ {{y_h} = {y_i}|h \in {{{{K}} }U}} \right\}$

　(12) 　　采用模拟退火算法控制可行解 ${{\rm new}}{{{{x}} }^d}$的接受或拒绝

　(13) 　　 $T = T \times \beta $

表 2 算法2：基于Block Gibbs的初始解优化算法

算法	计算复杂度
本文算法	$O \left(L \times N \times \left(M \times K + \max \|{\gamma ^k}\|\right)\right)$
Optimizing staff scheduling by Monte-Carlo simulation^[13]	$O \left(L \times N \times M \times \max \|{\gamma ^k}\|\right)$
Constraint staff scheduling using monte carlo tree search^[14]	$O \left(L \times N \times M\lg M \times \max \|{\gamma ^k}\|\right)$
A simulation approach for re-assigning of personnel^[15]	$O\left(L \times N \times M \times \max \|{\gamma ^k}\|\right)$

表 3 计算复杂度对比

算法	抽样次数	可行解生成规模
本文算法	$L\! \times\! M \!\times\! \left( {2N + 1} \right)$	$\prod\limits_{d = 1}^M {\prod\limits_{i = 1}^{14} {\prod\limits_{j = 1,{t_{ij}} = {y^d}}^{{n_i}} {{{\left( {2 +\! C({M_d} - {M_{ij}},K) \times\! C({M_{ij}} + K,K)} \right)}^L}} } } $
Optimizing staff scheduling by Monte-Carlo simulation^[13]	$L \!\times\! M \!\times\! N$	${2^{L \times N \times M}}$
Constraint staff scheduling using monte carlo tree search^[14]	$L \!\times\! M \!\times\! N$	${2^{L \times N \times M}}$

表 4 与基于Monte Carlo的基准算法对比可行解生成效率

星期	航班号	白/夜班	到岗时间	起飞时间	组长数	控制员工数	普通员工数
1	PK852	1	5:30	8:15	1	3	2
1	J2067	1	5:30	6:30	0	1	0
1	SU205	1	8:00	11:39	1	3	5
1	JS152	1	8:45	12:00	0	3	0

表 5 航班计划表数据示例

姓名	KE	SU	GA	PK	J2	IR	7C	VN	JS	LH
李仁骥	0	3	3	3	3	3	0	3	3	1
黄芳	0	2	2	2	2	2	0	2	2	1
张华冰	0	2	2	2	2	2	0	2	2	1
孔清钺	0	2	2	2	2	2	0	2	2	2
李健	0	1	1	1	1	1	0	1	1	1

表 6 员工资质信息表数据示例

算法	WH (h)	EH (h)	EP (%)	WB
MA	60.6	53.5	90.8	185.9
BP	46.2	44.1	96.6	141.2
MC	50.1	47.5	94.8	155.8
MCTS	48.7	46.4	96.7	146.7
BG ( $\lambda $=0.05)	45.3	43.7	97.3	145.5

表 7 实验对比

算法	WH (h)	EH (h)	EP (%)	WB	RT (s)
BG ( $\lambda $=0)	45.1	43.1	96.7	424.6	20.9
BG ( $\lambda $=0.05)	45.3	43.7	97.3	145.5	18.7
BG ( $\lambda $=0.40)	45.6	43.9	97.1	137.7	18.2
BG ( $\lambda $=0.80)	45.6	44.0	97.2	131.5	24.8
BG ( $\lambda $=1.00)	45.6	43.9	97.0	131.5	24.2

表 8 折中因子 ${λ}$ 影响

T	WH (h)	EH (h)	EP (%)	WB	RT (s)
0	45.77	42.77	96.53	473.51	27.66
50	44.97	43.29	97.17	439.60	27.12
100	44.97	42.95	97.12	422.26	26.24
500	44.99	42.97	96.37	427.88	27.27
1000	44.94	42.92	96.38	380.80	25.51

表 9 模拟退火温度T 影响分析

${\rm{\beta }}$	WH (h)	EH (h)	EP (%)	WB	RT (s)
0.70	44.90	43.19	96.85	403.86	26.50
0.80	44.98	42.60	96.02	417.24	27.47
0.90	45.00	43.15	96.78	429.66	25.61
0.95	45.01	42.78	96.00	442.08	28.30
0.99	44.92	43.58	97.31	389.05	26.94

表 10 温度衰减因子 $\beta $ 影响分析