| The multi-period inspector scheduling problem(MPISP)(Qin et al.,2015)consists of determining a set of routes for a team of inspectors to travel through different cities to perform inspection jobs in multiple days.The objective is to maximize the workload that the inspectors can carry out.Since the inspectors travel or perform inspection jobs only at the working hours and rest at the other time,a route for an inspector across multiple days is broken into several segments.This characteristic makes the routing decisions in the MPISP more complicated and differentiates the MPISP from many vehicle routing problems in the literature.In this paper,we propose a branch-and-price-and-cut algorithm to solve the MPISP.The branch-and-price-and-cut algorithm relies on a strong set-packing model and the subset-row inequalities(Jepsen et al.,2008)to strengthen the set-packing model.In the branch-and-price-and-cut,a tailored label-setting algorithm is proposed to solve the pricing problem,a segmented variance of the classic elementary shortest path problem with resource constraints.The branch-and-price-and-cut algorithm was tested on a set of benchmark instances generated by Qin et al.(2015).Computational results show that the branch-and-price-and-cut algorithm successfully solved a large proportion of instances to optimality in 3 hours and has an excellent performance. |
