遗传算法在多类型的车辆人员排班系统中的应用与研究

梁剑波+柴群

摘要：公交车辆人员排班的主要问题就是在给定时间点和车次数的情况下，以最小代价覆盖所有的车次。与以往都是针对单类型车辆的人员排班不同，该文主要提供对多类型的车辆人员排班的支持。首先利用高效的Auction算法获取代价最小的车次分组并根据分组情况分配车辆的营运类型；然后使用遗传算法进行随机化搜索以获得最优解。实验表明， 遗传算法应用于多类型的公交车辆人员排班具有很好的效果。

关键词：车辆人员排班；采样编码；Auction算法；遗传算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）34-8266-02

由于现代交通的快速发展需要，使得我们的应用必须能够处理多类型的车辆人员排班。为解决客户和员工都能够满足管理的需要，我们对问题进行了重定义并提出了一种新的分段式算法来求解多类型车辆人员排班问题，从而在生成计划的同时考虑了现有营运管理模式的需要。车辆人员排班[1]作为城市运输领域一个经典的NP-Hard问题受到国内外大量专家学者的重视和研究。

1 公交车辆人员排班问题描述

行车计划是组织线路运营的具体作业计划，它将指导各个车组运营生产的全过程。它也为提高公共交通的整体服务水平提供了有力的依据。好的行车计划将大大提高对乘客的服务质量，使乘客对公共交通感到方便而且便捷。公交车辆人员排班的最终目的是生成一份行车计划。行车计划是线路始末站及重点中途站所有的行车时刻表，它规定了在该路运营的各个班次车辆每个周转车次到达和离开该站的时间、行车间隔、及换班等。在给定车次、任务、车辆类型以及相应约束的情况下，求解整体营运时间最小的多类型车辆人员的合理调度方案。

2 数学模型的建立与算法设计

由于我们要解决的是对多类型的车辆人员排班问题进行研究，需要我们提出两阶级算法：第一阶级通过使用改进的auction算法[2]确定车辆调度类型，并保证目标函数最小；第二阶段根据第一阶段分配好的车辆类型使用遗传算法求解整个问题的近似最优解，并通过集合分割技术来提高求解效率。在这里，有必要对研究的公交车辆人员排班中的一些问题进行必要的简化和假设， 把实际的问题抽象为一个数学问题。

1） 车辆类型是指车辆的营运调度类型。公交调度形式有多种，我们的算法中仅考虑正班车调度和加班车调度两种类型；

2） 没有考虑燃油以及车辆损耗的代价；

3） 有一份合理的行车时刻表；

4） 高峰上线车辆数应等于全部车辆总数。

2.1 定义变量

对于文中使用到的各个变量进行定义：

1） TimeTable表示行车时刻表；

2） [Tintervalmax] 表示停站的最大间隔；

3） [Tintervalmin]表示停站的最小间隔；

4） [Ttwoheadmin]表示小两头最小间隔；

5） [Tsingle]表示单程行驶时间

6） [Cmax]表示员工的最大行驶车次数；

7） [NSingle_bus]表示单班车辆数；

8） [NDouble_bus]表示双班车辆数；

9） [CSMaxIteration]表示算法的最大迭代次数；

10） SeedSize表示种群数量；

11） Exception表示客户期望目标值；

12） Cgroup表示分组数；

13） SeqNum表示车次数；

14） Cgmax表示最大分组数量。

2.2 建立数学模型

车辆人员排班已被抽象为多种模型，我们将要用到的是QUASI分配模型[3][4]。

QUASI分配模型：

3 试验结果及有效性分析

本实验的数据是厦门市公交总公司思明分公司某线路的客流数据。实验的基本参数：个人PC主频双核2.6G，内存1G；系统Win2003，实现语言C#，运行容器Asp.Net2.0、Net.Framework2.0。定义数学模型中的[α=80%]，[β=20%]。图1展示了不同规模问题的求解时间。在我们的试验中出现过收敛速度过快的情形，所以我们引入了适应度尺度变换，主要用的是线性尺度变换来控制遗传算法的收敛速度，然而如果在全局都使用适应度尺度变换就会导致收敛速度变慢，因此在我们的应用中，只在前三分之一的迭代同期内使用尺度变换。从而很好的协调了群体多样性与求解效率之间的矛盾。如图2。

4 总结

本文对公交车辆人员排班进行了研究。通过合理结合地域的管理模式，提出了使用Auction算法、DAuction算法以及遗传算法混合求解多类型车辆人员排班的两阶段算法。通过巧妙的利用约束将Auction算法引入人员排班，大大提高了求解效率.而且使用采样编码降低了编码的复杂性和转换的效率，减少了存储空间的使用，也降低了生成初始种群的难度，并且有效的分割了求解空间，提高了搜索效率。

参考文献：

[1] 北京市公共交通总公司北方交通大学.“城市公共交通运营调度管理”[M].北京：中国铁道出版社，2001.

[2] Bertsekas D P. Auction Algorithms[D].Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge， MA 02139， USA， 1998.

[3] Richard Freling.Models and Algorithms for Vehicle Scheduling[J].2001.

[4] Huisman D，Freling R，Wagelmans A P M. Multiple-depot integrated vehicle and crew scheduling[R].Tech. report， Econometric Institute， Erasmus University Rotterdam， 2003.

[5] Jingquan Li ，Parallel. Auction Algorithm for Bus Rescheduling[J]. Journal of Scheduling，2003.

[6] 王鹏飞.智能公交之车辆人员排班算法的研究与应用[D].济南：山东大学，2006.

[7] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，2001.

[8] Sebastiaan W. de Grootl， Dennis Huisman. Vehicle and Crew Scheduling： Solving Large Real-World Instances with an Integrated Approach[R].Econometric Institute Report，EI2004-13.endprint

摘要：公交车辆人员排班的主要问题就是在给定时间点和车次数的情况下，以最小代价覆盖所有的车次。与以往都是针对单类型车辆的人员排班不同，该文主要提供对多类型的车辆人员排班的支持。首先利用高效的Auction算法获取代价最小的车次分组并根据分组情况分配车辆的营运类型；然后使用遗传算法进行随机化搜索以获得最优解。实验表明， 遗传算法应用于多类型的公交车辆人员排班具有很好的效果。

关键词：车辆人员排班；采样编码；Auction算法；遗传算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）34-8266-02

由于现代交通的快速发展需要，使得我们的应用必须能够处理多类型的车辆人员排班。为解决客户和员工都能够满足管理的需要，我们对问题进行了重定义并提出了一种新的分段式算法来求解多类型车辆人员排班问题，从而在生成计划的同时考虑了现有营运管理模式的需要。车辆人员排班[1]作为城市运输领域一个经典的NP-Hard问题受到国内外大量专家学者的重视和研究。

1 公交车辆人员排班问题描述

行车计划是组织线路运营的具体作业计划，它将指导各个车组运营生产的全过程。它也为提高公共交通的整体服务水平提供了有力的依据。好的行车计划将大大提高对乘客的服务质量，使乘客对公共交通感到方便而且便捷。公交车辆人员排班的最终目的是生成一份行车计划。行车计划是线路始末站及重点中途站所有的行车时刻表，它规定了在该路运营的各个班次车辆每个周转车次到达和离开该站的时间、行车间隔、及换班等。在给定车次、任务、车辆类型以及相应约束的情况下，求解整体营运时间最小的多类型车辆人员的合理调度方案。

2 数学模型的建立与算法设计

由于我们要解决的是对多类型的车辆人员排班问题进行研究，需要我们提出两阶级算法：第一阶级通过使用改进的auction算法[2]确定车辆调度类型，并保证目标函数最小；第二阶段根据第一阶段分配好的车辆类型使用遗传算法求解整个问题的近似最优解，并通过集合分割技术来提高求解效率。在这里，有必要对研究的公交车辆人员排班中的一些问题进行必要的简化和假设， 把实际的问题抽象为一个数学问题。

1） 车辆类型是指车辆的营运调度类型。公交调度形式有多种，我们的算法中仅考虑正班车调度和加班车调度两种类型；

2） 没有考虑燃油以及车辆损耗的代价；

3） 有一份合理的行车时刻表；

4） 高峰上线车辆数应等于全部车辆总数。

2.1 定义变量

对于文中使用到的各个变量进行定义：

1） TimeTable表示行车时刻表；

2） [Tintervalmax] 表示停站的最大间隔；

3） [Tintervalmin]表示停站的最小间隔；

4） [Ttwoheadmin]表示小两头最小间隔；

5） [Tsingle]表示单程行驶时间

6） [Cmax]表示员工的最大行驶车次数；

7） [NSingle_bus]表示单班车辆数；

8） [NDouble_bus]表示双班车辆数；

9） [CSMaxIteration]表示算法的最大迭代次数；

10） SeedSize表示种群数量；

11） Exception表示客户期望目标值；

12） Cgroup表示分组数；

13） SeqNum表示车次数；

14） Cgmax表示最大分组数量。

2.2 建立数学模型

车辆人员排班已被抽象为多种模型，我们将要用到的是QUASI分配模型[3][4]。

QUASI分配模型：

3 试验结果及有效性分析

本实验的数据是厦门市公交总公司思明分公司某线路的客流数据。实验的基本参数：个人PC主频双核2.6G，内存1G；系统Win2003，实现语言C#，运行容器Asp.Net2.0、Net.Framework2.0。定义数学模型中的[α=80%]，[β=20%]。图1展示了不同规模问题的求解时间。在我们的试验中出现过收敛速度过快的情形，所以我们引入了适应度尺度变换，主要用的是线性尺度变换来控制遗传算法的收敛速度，然而如果在全局都使用适应度尺度变换就会导致收敛速度变慢，因此在我们的应用中，只在前三分之一的迭代同期内使用尺度变换。从而很好的协调了群体多样性与求解效率之间的矛盾。如图2。

4 总结

本文对公交车辆人员排班进行了研究。通过合理结合地域的管理模式，提出了使用Auction算法、DAuction算法以及遗传算法混合求解多类型车辆人员排班的两阶段算法。通过巧妙的利用约束将Auction算法引入人员排班，大大提高了求解效率.而且使用采样编码降低了编码的复杂性和转换的效率，减少了存储空间的使用，也降低了生成初始种群的难度，并且有效的分割了求解空间，提高了搜索效率。

参考文献：

[1] 北京市公共交通总公司北方交通大学.“城市公共交通运营调度管理”[M].北京：中国铁道出版社，2001.

[2] Bertsekas D P. Auction Algorithms[D].Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge， MA 02139， USA， 1998.

[3] Richard Freling.Models and Algorithms for Vehicle Scheduling[J].2001.

[4] Huisman D，Freling R，Wagelmans A P M. Multiple-depot integrated vehicle and crew scheduling[R].Tech. report， Econometric Institute， Erasmus University Rotterdam， 2003.

[5] Jingquan Li ，Parallel. Auction Algorithm for Bus Rescheduling[J]. Journal of Scheduling，2003.

[6] 王鹏飞.智能公交之车辆人员排班算法的研究与应用[D].济南：山东大学，2006.

[7] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，2001.

[8] Sebastiaan W. de Grootl， Dennis Huisman. Vehicle and Crew Scheduling： Solving Large Real-World Instances with an Integrated Approach[R].Econometric Institute Report，EI2004-13.endprint

摘要：公交车辆人员排班的主要问题就是在给定时间点和车次数的情况下，以最小代价覆盖所有的车次。与以往都是针对单类型车辆的人员排班不同，该文主要提供对多类型的车辆人员排班的支持。首先利用高效的Auction算法获取代价最小的车次分组并根据分组情况分配车辆的营运类型；然后使用遗传算法进行随机化搜索以获得最优解。实验表明， 遗传算法应用于多类型的公交车辆人员排班具有很好的效果。

关键词：车辆人员排班；采样编码；Auction算法；遗传算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）34-8266-02

由于现代交通的快速发展需要，使得我们的应用必须能够处理多类型的车辆人员排班。为解决客户和员工都能够满足管理的需要，我们对问题进行了重定义并提出了一种新的分段式算法来求解多类型车辆人员排班问题，从而在生成计划的同时考虑了现有营运管理模式的需要。车辆人员排班[1]作为城市运输领域一个经典的NP-Hard问题受到国内外大量专家学者的重视和研究。

1 公交车辆人员排班问题描述

行车计划是组织线路运营的具体作业计划，它将指导各个车组运营生产的全过程。它也为提高公共交通的整体服务水平提供了有力的依据。好的行车计划将大大提高对乘客的服务质量，使乘客对公共交通感到方便而且便捷。公交车辆人员排班的最终目的是生成一份行车计划。行车计划是线路始末站及重点中途站所有的行车时刻表，它规定了在该路运营的各个班次车辆每个周转车次到达和离开该站的时间、行车间隔、及换班等。在给定车次、任务、车辆类型以及相应约束的情况下，求解整体营运时间最小的多类型车辆人员的合理调度方案。

2 数学模型的建立与算法设计

由于我们要解决的是对多类型的车辆人员排班问题进行研究，需要我们提出两阶级算法：第一阶级通过使用改进的auction算法[2]确定车辆调度类型，并保证目标函数最小；第二阶段根据第一阶段分配好的车辆类型使用遗传算法求解整个问题的近似最优解，并通过集合分割技术来提高求解效率。在这里，有必要对研究的公交车辆人员排班中的一些问题进行必要的简化和假设， 把实际的问题抽象为一个数学问题。

1） 车辆类型是指车辆的营运调度类型。公交调度形式有多种，我们的算法中仅考虑正班车调度和加班车调度两种类型；

2） 没有考虑燃油以及车辆损耗的代价；

3） 有一份合理的行车时刻表；

4） 高峰上线车辆数应等于全部车辆总数。

2.1 定义变量

对于文中使用到的各个变量进行定义：

1） TimeTable表示行车时刻表；

2） [Tintervalmax] 表示停站的最大间隔；

3） [Tintervalmin]表示停站的最小间隔；

4） [Ttwoheadmin]表示小两头最小间隔；

5） [Tsingle]表示单程行驶时间

6） [Cmax]表示员工的最大行驶车次数；

7） [NSingle_bus]表示单班车辆数；

8） [NDouble_bus]表示双班车辆数；

9） [CSMaxIteration]表示算法的最大迭代次数；

10） SeedSize表示种群数量；

11） Exception表示客户期望目标值；

12） Cgroup表示分组数；

13） SeqNum表示车次数；

14） Cgmax表示最大分组数量。

2.2 建立数学模型

车辆人员排班已被抽象为多种模型，我们将要用到的是QUASI分配模型[3][4]。

QUASI分配模型：

3 试验结果及有效性分析

本实验的数据是厦门市公交总公司思明分公司某线路的客流数据。实验的基本参数：个人PC主频双核2.6G，内存1G；系统Win2003，实现语言C#，运行容器Asp.Net2.0、Net.Framework2.0。定义数学模型中的[α=80%]，[β=20%]。图1展示了不同规模问题的求解时间。在我们的试验中出现过收敛速度过快的情形，所以我们引入了适应度尺度变换，主要用的是线性尺度变换来控制遗传算法的收敛速度，然而如果在全局都使用适应度尺度变换就会导致收敛速度变慢，因此在我们的应用中，只在前三分之一的迭代同期内使用尺度变换。从而很好的协调了群体多样性与求解效率之间的矛盾。如图2。

4 总结

本文对公交车辆人员排班进行了研究。通过合理结合地域的管理模式，提出了使用Auction算法、DAuction算法以及遗传算法混合求解多类型车辆人员排班的两阶段算法。通过巧妙的利用约束将Auction算法引入人员排班，大大提高了求解效率.而且使用采样编码降低了编码的复杂性和转换的效率，减少了存储空间的使用，也降低了生成初始种群的难度，并且有效的分割了求解空间，提高了搜索效率。

参考文献：

[1] 北京市公共交通总公司北方交通大学.“城市公共交通运营调度管理”[M].北京：中国铁道出版社，2001.

[2] Bertsekas D P. Auction Algorithms[D].Laboratory for Information and Decision Systems Massachusetts Institute of Technology Cambridge， MA 02139， USA， 1998.

[3] Richard Freling.Models and Algorithms for Vehicle Scheduling[J].2001.

[4] Huisman D，Freling R，Wagelmans A P M. Multiple-depot integrated vehicle and crew scheduling[R].Tech. report， Econometric Institute， Erasmus University Rotterdam， 2003.

[5] Jingquan Li ，Parallel. Auction Algorithm for Bus Rescheduling[J]. Journal of Scheduling，2003.

[6] 王鹏飞.智能公交之车辆人员排班算法的研究与应用[D].济南：山东大学，2006.

[7] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，2001.

[8] Sebastiaan W. de Grootl， Dennis Huisman. Vehicle and Crew Scheduling： Solving Large Real-World Instances with an Integrated Approach[R].Econometric Institute Report，EI2004-13.endprint