An exact algorithm for the multi-period inspector scheduling problem

Autor: Shengnan Shu, Hu Qin, Qinghua Wu, Huaxiao Shen
Rok vydání: 2020
Předmět:
Zdroj: Computers & Industrial Engineering. 145:106515
ISSN: 0360-8352
DOI: 10.1016/j.cie.2020.106515
Popis: In this paper, we study the multi-period inspector scheduling problem (MPISP). This problem aims to determine a set of routes for a team of inspectors performing inspection jobs in different locations across multiple days, with the objective of maximizing the total workloads that the inspectors undertake. Since an inspector can only perform inspections or travel during working periods and rest at other times, a route for an inspector is divided into several segments. This characteristic, on the one hand, differentiates the MPISP from many routing problems in the literature; on the other hand, however, makes the routing decisions more complicated and challenging. To solve the MPISP, we first formulate it into a set-packing model and then propose an exact branch-and-price algorithm. In particular, we design a tailored label-setting algorithm for the pricing subproblem, which is a variant of the elementary shortest path problem with resource constraints. Moreover, we implement some acceleration techniques, such as bidirectional search, label pruning, decremental search space relaxation, and heuristic column generator. Extensive computational experiments were conducted on a set of benchmark instances, and the results have demonstrated the effectiveness of the proposed algorithm.
Databáze: OpenAIRE
Externí odkaz: