摘 要

基于改进的遗传算法在带时间窗的人员调度路径优化上的运用是：给定合适的客户需求，物业公司在此基础上进行人员调度，实现利用最少的人员，走最少的路程。同时有时间限制，超出时间有惩罚，也要是超时惩罚最少。对于带有时间窗的遗传算法的应用，就目前而言，在VRPTW上应用较多。人员调度与之类似。在如今社会，快节奏的生活下，人们在物质生活的基础上更重视品质。这时候合适的人员调度，提供合适的服务就很重要。本文重点研究了在简单的带有时间窗的遗传算法上进行相应改进的人员调度问题。

基于VRPTW的特点，再基于课题所给出的条件，设计了所研究课题的数学模型，建立了相应的约束条件。再结合设计约束设计遗传算法（Genetic Algorithm, GA）。同时对遗传算法、蚁群算法、模拟退火等进行比较分析，利用合适的算法进行设计遗传算法中的交叉、突变等。最后进行实现，通过案例得出结果。

关键字：遗传算法； 人员调度； 时间窗

Abstract

The personnel dispatch path optimization Based on the improved genetic algorithm with time Windows: property management company uses personal scheduling based the suitable needs of customer given,and to achieve the purpose that using the least amount of people and go at least.At the same time,there is the time limit(Time window) ,and there will be a penalty beyond the time , so the subject requires the penalties at least. For the moment , Genetic algorithm(GA) with time window is often used on VRPTW. Personal scheduling is similar to VRPTW . In today’s society , the fast pace of life , people on the basis of the material life pay more attention to quality . So , the appropriate personal scheduling which provides the appropriate service is becoming more and more important . So this paper mainly research the question that The personnel dispatch path optimization Based on the improved genetic algorithm with time Windows .

Based on the characteristics of the VRPTW and the given conditions , I design the mathematical model of the object and the constraint condition , and I design the genetic algotithm based on the conditions . At the same time , after the analysis and comparison of genetic algotithm , Ant colony algorithm , Simulated annealing and so on , I use the appropriate algotithm to design the crossover and mutation in genetic algorithm and so on . Finally , some cases are used to get the conclution .

Key words : Genetic Algotithm； Personal Scheduling； Time Window

目录

第一章 绪论 1

1.1 背景与意义 1

1.2研究现状 2

1.3研究的主要内容 2

第二章 人员调度问题分析 3

2.1课题简介 3

2.2旅行商问题（TSP） 3

2.3车辆路线问题（VRP） 4

2.4带有时间窗的车辆路径问题（VRPTW） 5

2.4.1 VRPTW简介 5

2.4.2 基于遗传算法的VPRTW 5

2.5 人员调度问题概述 6

2.5.1 人员调度定义 6

2.5.2 人员调度的组成因素 6

2.6 带有时间窗的人员调度问题 7

2.6.1 时间窗概念 7

2.6.2 时间窗分类 8

第三章 算法改进设计 11

3.1 带有时间窗的人员调度问题求解算法研究 11

3.1.1精确算法 11

3.1.2 启发式算法 12

3.2 遗传算法 15

3.2.1 遗传算法定义 15

3.2.2遗传算法基本操作 16

3.3应用变量的设计 18

3.3.1 惩罚函数设计 18

3.3.2 参数变量选定 19

3.3.3 模型建立 19

3.4 遗传算法改进设计 20

3.4.1编码设计 22

3.4.2 初始化种群 22

3.4.3选择算子改进设计 22

3.4.4 交叉算子改进设计 23

3.4.5 变异算子设计 24

3.4.6 适应度函数改进设计 25

3.4.7 进化终止设计 25

第四章 实验验证 26

4.1算例实现 26

4.1.1算例C101 26

4.1.2算例R101 28

第五章 总结 32

5.1论文总结 32

5.2未来展望 32

参考文献 33

致 谢 35

第一章 绪论

1.1 背景与意义

随着移动互联网的发展，我国各项产业都变得智能化，房地产业务也不例外，在房地产业务中，物业管理很重要，所以对物业公司来说，怎么提高自身的服务质量和服务效率就很需要了。在房屋建成后，物业公司的人员要跟踪每个项目，每个楼栋，每个房间，及时发现楼盘中的一些建筑缺陷，要求建筑公司提供维修服务，提高房屋的质量。这样就要求物业公司能进行最合理的安排，实行合理的人员安排调度，实现最简单的工作量，达到最好的效果，这已然成为了在物业管理方面面临的亟待解决的问题。这里就牵涉到了人员调度，合适的人员调度方案便能实现合理的人员路线安排，进行最合理的安排，达到最好的效果。当然，这只是其中一方面。

如今社会，人口需要快速增加，业务数量快速增加等等一系列的问题出现，人员调度问题则就明显突出，对人员的调度就要能够满足更多的需要。其实无论是个人还是企业，甚至是国家，在某方面的意义上也显得尤为重要。就目前的一些企业而言，为了达到最高的利润追求，肯定会尽量用最少的成本来达到目的。所以会用最低限额的人员来实现目的，通常任务繁重，所以这时候人员调度就很重要了。既不能使的人员缺少，同时还能分配好一定的人员，使的能够在规定的范围内达到想要的服务效果。这时候适合的人员调度方案就能达到既消耗成本小还能获得最大利益，充分的提高效率。那到国家方面来说也同样重要。现在科技发达，讲究的已经不是人海战术，所以要学会利用现有科技达到最大化的国家目的。要对各个战局进行最合理部署，对每个战局要部署最适当人员，要利用合适人员调度，最大化的节省资源并提供最大化战力，这时候人员调度方案的制定就占了很大地位。合适的人员调度方案就能用最少的人员战斗力，避免不必要的人员损失。