Optimization of gas metering maintenance services: A multiobjective vehicle routing problem with a set of predefined overlapping time windows

Optimization of maintenance services of a company working in the gas metering sector is investigated. In particular, daily tasks of operators are optimized by exploiting the paradigm of vehicle routing problems with a set of predefined time windows that overlap one with the others and four competing objectives to take into account. First, an exact integer formulation is presented that can be solved only for a reduced number of customer sites to visit. Then, a heuristic approach is proposed to find approximate solutions with huge savings on the computational effort, also for high-dimensional instances. Numerical results on both real and synthetic scenarios showcase the effectiveness of the approach.