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 large-scale 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.
on-site servicetardiness penaltymulti-structure taskworkforce scheduling and routing problemadaptive large neighbourhood search
万方数据
维普
