Heuristics for a green orienteering problem

We address a routing problem where a vehicle with limited time, loading capacity and battery autonomy can optionally serve a set of customers, each providing a profit. Such a problem is of particular relevance both because of its practical implications in sustainable transportation and its use as a sub-problem in Green Vehicle Routing column generation algorithms. We propose a dynamic programming approach to obtain both primal and dual bounds to the value of the optimal solutions, a fast greedy heuristics and a very large scale neighbourhood search procedure.