Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (9): 2706-2711.DOI: 10.11772/j.issn.1001-9081.2018010159

Previous Articles     Next Articles

Hybrid fruit fly optimization algorithm for field service scheduling problem

WU Bin, WANG Chao, DONG Min   

  1. School of Economics and Management, Nanjing Tech University, Nanjing Jiangsu 211816, China
  • Received:2018-01-19 Revised:2018-03-23 Online:2018-09-10 Published:2018-09-06
  • Contact: 吴斌
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (71371097), the Nanjing Tech University Project (ZKJ201531).

基于混合果蝇优化算法的现场服务调度问题

吴斌, 王超, 董敏   

  1. 南京工业大学 经济与管理学院, 南京 211816
  • 通讯作者: 吴斌
  • 作者简介:吴斌(1979—),男,河南郑州人,副教授,博士,主要研究方向:智能优化算法、系统建模与优化;王超(1994—),男,浙江杭州人,硕士研究生,主要研究方向:系统建模与优化;董敏(1968—),女,四川眉山人,副教授,硕士,主要研究方向:物流供应链管理。
  • 基金资助:
    国家自然科学基金资助项目(71371097);南京工业大学项目(ZKJ201531)。

Abstract: The skills level of employees has a great influence on the execution efficiency of Field Service Scheduling Problem (FSSP). Employee skill factors are not considered in the existing research. To solve the problem, firstly, taking the travel time, service time and waiting time of staff as optimization goals, the FSSP model considering the skill level of staff was established. Then, a Hybrid Fruit fly Optimization Algorithm (HFOA) was proposed to optimize the model. Based on the features of the problem and the merits of the algorithm, an encoding method based on the matrix was designed. Two operators of matrix were defined based on the theory of swarm intelligence, and then three search operators were proposed, and the smell-based search strategy and the vision-based search strategy of Fruit fly Optimization Algorithm (FOA) were redesigned. At the same time, in order to improve the algorithm's performance, an initialization operator based on the nearest insertion heuristic algorithm was constructed. Finally, the simulation experiment was carried out through typical instances and the proposed algorithm was compared with Genetic Algorithm (GA) and Greedy Randomized Adaptive Search Procedure (GRASP) algorithm. The experimental data show that HFOA performs better in terms of mean value and optimal value than the other two algorithms. The results show that HFOA outperforms other algorithms in terms of optimization accuracy and stability after improving the initialization method and search strategy.

Key words: Field Service Scheduling Problem (FSSP), Fruit fly Optimization Algorithm (FOA), employee skill, nearest neighbor insertion heuristic algorithm, matrix coding

摘要: 员工技能熟练程度对现场服务调度问题(FSSP)的执行效率有极大影响,现有研究中未考虑员工技能因素。针对上述问题,首先以员工的旅行时间、服务时间和等待时间为优化目标,建立考虑员工技能熟练程度的FSSP模型;然后,提出混合果蝇优化算法(HFOA)对该模型进行优化求解,根据问题特征和算法特点,设计了基于矩阵的编码方法;定义了两类矩阵操作,提出了3种搜索算子,重构了果蝇优化算法(FOA)的嗅觉搜索和视觉搜索过程;为了提升算法性能,构造了基于最邻近插入启发式算法的初始化算子;最后,通过典型实例对算法进行了仿真实验,并与遗传算法(GA)、贪婪随机自适应搜索过程(GRASP)算法进行了比较。实验数据显示,与其他两种算法相比,HFOA在均值和最优值方面表现更优秀。结果表明改进初始化方法和搜索策略后,HFOA在优化的精度和稳定性上优于其他算法。

关键词: 现场服务调度问题, 果蝇优化算法, 员工技能, 最邻近插入启发式算法, 矩阵编码

CLC Number: