A new variant of a vehicle routing problem: Lower and upper bounds (Q1598727)

This paper focusses on the Laser Multiscanner Problem (LMSP) which is an optimization problem that arises in the design of a semi-automatic system for cutting leather skins. The author formulates the problem as an integer linear program that can be seen as a new variant of the \(m\)-depot vehicle routing problem. The main objective is to obtain ``good'' feasible solutions (upper bounds). So, the author proposes some heuristics approaches which are good adaptations of known heuristics proposed to the TSP problem. In particular, an insertion and a greedy heuristic as well as some local search strategies to improve the solutions. In order to evaluate the quality of the feasible solutions, obtained via the heuristics, two relaxations are proposed. More precisely, the author shows that lower bounds can be obtained by an algorithm that solves a minimal direct \(m\)-forest problem, corresponding to the first relaxed problem, or by a matching algorithm, that solves the second relaxed problem. Although the main objective is to obtain feasible solutions, I think the most interesting feature of the paper is the work done leading to the special features of the LMSP problem in what concerns the lower bounds. For such reason and in order to obtain feasible solutions, it would be interesting if the author would develop some heuristic algorithms to remove the eventual infeasibilities of the relaxed problems solutions. In conclusion, I think the paper presents a new application of some well-known combinatorial optimization techniques to a problem arising in the leather industry.