家政服务人员的排班优化问题

邱旭勤 蔡延光 汤雅连 江泽东

(广东工业大学 自动化学院，广州 510006)

相对于传统的农业和工业而言，新兴的家政服务业被称为第三产业，该产业在20 世纪60年代后得到了长足发展。目前，以家庭及其成员为主要服务对象的家政服务业是第三产业的重要组成部分，它所提供的服务内容从传统的保洁、理家、照顾老人、孩子，到筹办婚礼、丧礼、寿宴和各种家庭庆典，商品配送、电器维修、服装裁剪、送餐上门、庆典用品出租、房屋维修等等，涉及人们生活的方方面面，为众多的家庭和个人带来了方便。随着全民生活水平的提高，有约70%的城市居民对家政服务有需求，因此，家政服务业这一朝阳产业其发展前景和市场是极其广阔的。诸如保育员、护理员、月嫂、管家，物业管理员、保洁员，家教、钟点工、保洁、配送、管道疏通，家居装饰、庭院美化，家居保洁，房屋维修，承办婚礼、丧礼、寿宴和各种家庭庆典，出租庆典用品，家居用品配送、电器维修、服装裁剪等均属于家政服务业内容，最专业的、最准时的家政服务让顾客感受零家务的超值享受，让顾客享受最舒适的生活，为了让顾客满意，合理的排班也变得尤为重要，因此研究的家政服务人员的排班问题具有实际应用意义。

目前，排班问题也得到了广泛的研究。李献忠等人［1］研究了乘务排班问题，通过最小费用最大流算法实现;李跃鹏等人［2］应用遗传算法求解公交车辆的智能排班问题，能够在排班问题的巨大搜索空间中可靠地找到近似最优解;李青等人［3］提出了排班问题的多目标优化模型，并应用改进的基于信息熵的自适应遗传算法求解模型，结果证明了模型的正确性和先进性;沈吟东等人［4］建立了带有一系列劳动法规约束和护士级别差异的整数规划模型，建立了更加人性化的扩展模型，实例验证该模型与算法是可行有效的，有利于提高护士积极性和工作效益;张应辉等人［5］详细描述了排班系统模型，并用模拟退火算法很好地解决了该问题，运行结果表明所提的模型和算法是合理而有效的;孙宏等人［6］描述了飞机排班问题的数学模型，结果表明飞机排班模式是解决单枢纽线性航线结构下的飞机排班问题的一种有效方法;王庆荣等人［7］结合公交车辆运营的特点，兼顾公交公司与乘客双方的利益，建立了公交排班优化模型，提出了基于改进的遗传模拟退火算法，提高了优化设计过程的求解效率。

1 家政服务人员排班的问题描述

为了快速响应客户的需求，须将服务人员安排到顾客需求的不同时间段内，通过服务人员的适当安排来调整服务能力，满足不同时间段内的不同服务负荷。公司为了人性化运营，制定人员排班计划既要考虑客户的需求，也要考虑服务人员的灵活需求，这两方面均为排班优化的主要约束条件，是为了获得最大收益，尽量使使服务富余人数维持最低。

2 分支定界法

2.1 分支定界法的基本原理

分支定界法［8－9］是20 世纪60年代初由Land、Doig 和Dakin 等人提出的可用于求解纯整数线性规划问题的算法。其基本思想就是不断将可行域分割成小的集合，不断降低上界、提高下界，最后使得下界接近或者等于上界，逐步缩小搜索范围，进而找到问题的最优整数解。

2.2 分支定界法的步骤

将要求解的整数线性规划问题称为P，与其对应的线性规划问题称为Q。

几个推论:

1)若Q 无可行解，则P 也一定无可行解;

2)若Q 的一个最优解是整数解，则它就是P 的最优解;

3)若Q 的最优解不是整数解，则P 的最优目标函数值不会好于Q 的最优值;

4)若已经找到一个整数解，则最优整数解一定不会劣于该整数解，它也是最优目标函数值的一个界，在最大化目标函数值时为下界，在最小化目标函数值时为上界。

分支定界法的求解步骤如下:

1)初始求解整数规划的松弛问题，如果得到的解是整数解，该解即为整数规划的最优解，否则，所得到的线性规划解可作为该问题最优整数解的初始上界，此时，初始下界设为－∞;

2)分支。在Q 的最优解中任选一个不符合整数条件的变量xj，设其值为vj，构造两个约束条件:xj≤［vj］和xj≥［vj］+1 ，将这两个条件分别加入问题Q，分成两个子问题Q1和Q2，不考虑整数条件，求解Q1和Q2;

3)定界与剪枝。以每个后继子问题为一分支并标明求解结果，与其他问题的解进行比较，不断修正上界和下界，若无可行解，停止继续分支;得到整数解，不必向下分支，如果该整数解是目前得到的最好整数解，则记录下来，并作为新下界;得到非整数解，如果目标函数值大于剪枝界，则继续分支，否则被剪枝;

4)按以上步骤进行搜索迭代，在搜索过程中，每次下界被修改后，必须检查所有还没有求解过的子问题并剪去那些目标函数值小于新下界的子问题，若没有找到任何整数解，则该问题无整数解;否则，搜索过程中得到的最优整数解就是该问题的最优解。

3 基于自适应的混合遗传算法设计

遗传算法擅长全局搜索但是收敛速度慢，局部搜索擅长微调但容易陷入局部最优，结合遗传算法和局部搜索算法的优点，遗传算法用来执行全局搜索以使解从局部最优中逃离，局部搜索进行性能微调。并且，应用自适应遗传算法求解，自适应遗传算法［10－11］包括避免近亲繁殖的杂交策略与改进的交叉概率，根据每代个体适应度的改变来自适应地改变交叉概率pc和变异概率pm，既保护了最优个体又加快了较差个体的淘汰程度。

3.1 交叉算子

交叉算子主要用于产生新个体，实现算法的全局搜索能力。考虑到整个种群的变化趋势及每个个体的变异机会，设计了与进化代数相关而与个体适应度无关的交叉概率计算公式，如式(1)。t 为当前进化代数，Tgen为预设的最大进化代数，pcmax为预设最大概率，pcmin为预设最小概率，pc(t)为当前种群的交叉概率。

3.2 变异算子

交叉算子起着全局搜索的作用，变异算子主要是产生新个体和抑制早熟。设计变异概率的总趋势是逐渐减小而使群体迅速集中。式(3)所示为自适应变异概率，pmmax是预设的最大变异概率，pmmin是预设的最小变异概率，pm(t)是第t 代个体进行变异的概率。

3.3 求解步骤

求解步骤:

1)随机产生N 个解构成初始种群。令t:=0。

2)采用基于列的表示的二进制编码，由于该优化问题的变量本质上是0－1 变量，所以采用二进制字符串作为染色体的结构，如表所示。其表达方法说明了编号为1、5、6、7、10、12、13 和14 的员工星期一上班，其余6 人休息。然后执行局部搜索，评价适应值，选出最好的两个解Q1和Q2。

3)采用自适应杂交算子组合Q1和Q2生成新解C。

4)自适应变异C 中k 个随机的列，执行局部搜索以改进染色体，评价，选出下一代种群C’。

5)采用启发式算子确保C’可行，除去冗余列。

6)如果C’与种群中任意解相同，返回2)。否则t:=t+1，转至7)。

7)从种群中随机选出高于平均适应值的个体并用C’替代。

8)重复2)～7)，直到产生t=M 个不重复的个体。选出最小适应值的个体作为最优解。

4 仿真分析

已知某小型家政公司一周内的人员需求量如表1 所示，请为该公司的14 位员工制定一个保证每人能休息一天的排班计划，员工分别以A、B、C、D、E、F、G、H、I、J、K、L、M 和N 表示。其中，G 星期五有事请假。

表1 一周内的人员需求量

分别用分支定界法、遗传算法和基于自适应的混合遗传算法求解。在Intel(R)CoreTMi3 CPU2.53GHz、内存为2.0G、安装系统为win7 的PC 机上采用Matlab R2010b 编程实现。各运行20 次求解。

遗传算法中参数设计:初始化种群N = 100 ，最大迭代次数gen = 500 ，交叉概率pc= 0.9 ，变异概率pm= 0.04 。采用均匀杂交，变异算子指单点变异。

混合遗传算法参数设计:初始化种群N = 100 ，最大迭代次数gen = 500 ，pmmax= 0.2 ，pmmin=0.001 ，pcmin= 0.2 ，pcmax= 0.001 。

1)分支定界法求解。

数学模型

定义

建立数学模型

目标函数:

目标函数如式(5)，约束条件如式(6)。

求解结果:员工安排计划表如表2 所示，人员配备统计如表3 所示。由此可见，富余人员为0，已经搜索到最优解。程序运行一次的时间为0.007 s。

表3 人员配备统计

2)应用GA 和HGA 求解。

家政服务人员的排班优化问题是集覆盖问题，也属于NP 问题。安排14 个服务人员一周的排班计划，服务人员必须完成任务，目标函数是最小化员工薪酬之和。设k 为服务人员的编号，k =1，2，…，14。t 表示工作时间，t=1，2，…，7。ct(k)表示服务人员k 在t 时间工作应得到的薪酬，这里简化为1个单位。家政服务人员调度示例如表4 所示，基于列的表示如表5 所示。

数学模型

目标函数:

决策变量:

约束:

目标函数如式(7)，式(8)为决策变量，表示员工k 安排到t 时间上班。式(9)为约束，ait(k)=1 意味着k 个服务人员组成的第i 个班次，在t 时间为客户服务。

表4 家政服务人员调度示意图

表5 基于列的表示

图1 应用GA 和HGA 求解的一次收敛过程

表6 两种算法对比结果

求解结果:应用GA 和HGA 求解的一次收敛过程如图1 所示，两种算法对比结果如表6 所示。GA在第50 代搜索到最优解，HGA 在第8 代就搜索到最优解，最优解为83 个单位。可见，HGA 相对于GA，收敛速度快，收敛效果也很好。

5 结语

通过分析家政服务人员的排班问题，介绍一种分支定界算法，并应用该分支定界算法求解。构造了基于自适应的混合遗传算法，结合遗传算法和局部搜索算法的优点，遗传算法可以跳出局部最优，局部搜索可以进行性能微调。应用自适应策略改进算法，自适应遗传算法包括避免近亲繁殖的杂交策略与改进的交叉概率，根据每代个体适应度的改变来自适应地改变交叉概率和变异概率，既保护了最优个体又加快了较差个体的淘汰程度。仿真结果表明，三种算法都可以得到最优解，基于自适应的混合遗传算法在收敛速度和性能方面最优，该方法可以用来求解更大规模的排班优化问题。

［1］李献忠，徐瑞华. 基于时间耗费的城市轨道交通乘务排班优化［J］. 铁道学报，2007，29(1):21－25.

［2］李跃鹏，安涛，黄继敏，等. 基于遗传算法的公交车辆智能排班研究［J］. 交通运输系统工程与信息，2003，3(1):41－44.

［3］李青，张军，张学军. 解决排班问题的多目标优化模型及算法研究［J］. 北京航空航天大学学报，2003，29(9):821－824.

［4］沈吟东，苏光辉. 带约束的护士排班模型和基于变换规则的优化算法［J］. 计算机工程与科学，2010，32(007):99－103.

［5］张应辉，饶云波，周明天. 模拟“退火”算法在多目标航空公司职员排班系统中的应用［J］. 计算机应用，2006，26(8):2001－2004.

［6］孙宏，杜文. 飞机排班数学规划模型［J］. 交通运输工程学报，2004，4(3):118－118.

［7］王庆荣，袁占亭，张秋余. 基于改进遗传—模拟退火算法的公交排班优化研究［J］. 计算机应用研究，2012，29(7):2461－2463.

［8］吴金荣. 求解课程表问题的分支定界算法［J］. 运筹与管理，2002，11(1):17－22.

［9］雷广萍，袁威. 直线方向单组列车编组优化的压缩分枝定界法［J］. 铁道学报，1989，11(1):26－38.

［10］魏明，蔡延光.一种基于混沌领域搜索的自适应遗传算法［J］.计算机应用研究，2009，26(2):465－467.

［11］韩瑞锋. 遗传算法原理与应用实例［M］. 北京:兵器工业出版社，2009.