多结构型任务驱动的上门服务调度优化模型与自适应大规模邻域搜索算法

Optimization model and revised adaptive large neighbourhood search algorithm for multi-structured on-site service scheduling problem

研究一类特殊的上门服务调度问题,该问题具有一般上门服务调度问题的要求,即要求可能具备不同技能水平的服务人员从同一站点出发,按路径执行被分配的任务后返回站点.被分配的任务在已有研究中对应图内点,而现实中的上门服务任务还可能具备内部结构(称为多结构型的任务),因此,在这类问题中路径的生成过程无法由任务序列本身确定,需要考虑任务指派和含出入点选取的路径规划的协同优化.通过分析此类问题特征,建立以总拖期最小化为目标的混合整数规划模型.通过分析模型的解的层次性特点,提出基于自适应大规模邻域搜索框架的启发式算法.通过多种规模对比实验发现,所提出算法适用于大规模问题和即时性要求,即在小规模算例下平均求解结果与精确解接近;在中、大规模算例下平均求解结果相较于一般贪婪算法产生显著优化.因此,所提出模型和算法可为多结构型任务驱动的上门服务调度提供参考.

This paper investigates a special type of on-site service scheduling problem that has the requirements of general on-site service scheduling problems,i.e.,they require service workers,who may have different skill levels,to start from the same station,perform the assigned task in a path and return to the station.While the assigned task corresponds to a node within the graph in existing studies,realistic on-site service tasks may also have internal structure(known as multi-structured tasks),and thus the path generation process cannot be determined by the task sequence itself,and it is necessary to consider the co-optimization of task assignment and subgraph routing with selection of exit nodes and entry nodes.This paper analyses the characteristics of the problem and develops a mixed integer programming model with the objective of minimising the total tardiness.By analyzing the hierarchical characteristics of the solution,this paper proposes a heuristic algorithm based on the adaptive large neighbourhood search(ALNS)framework.Through various scale comparison experiments,it is found that the proposed algorithm is suitable for large scale problems and instantaneous requirements.The average solution result is close to the exact solution in small-scale cases;and in medium-and largescale cases,the average solution result is significantly optimized compared to the general greedy algorithm.Therefore,the proposed model and algorithm can be used as a reference for multi-structured task-driven on-site service scheduling.