Heuristics for the Multi-Period Orienteering Problem with Multiple Time Windows.

We present theMulti-Period Orienteering Problem withMultiple Time Windows (MuPOPTW), a new routing problem combining objective and constraints of the Orienteering Problem (OP) and Team Orienteering Problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application. The problem itself comes from a real industrial case. Specific route duration constraints result in a route feasibility subproblem. We propose an exact algorithm for this subproblem, and we embed it in a Variable Neighborhood Search method to solve the whole routing problem. We then provide experimental results for this method. We compare them to a commercial solver. We also adapt our method to standard benchmark OP and TOP instances, and provide comparative tables with state-of-the-art algorithms.