Conference 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2017), 2017

Heuristics for a green orienteering problem

Saverio Basso · Marco Casazza · Alberto Ceselli

Paper

Abstract

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.

Combinatorial OptimizationOrienteeringHeuristics

BibTeX

@inproceedings{basso2017heuristics,
  title     = {Heuristics for a green orienteering problem},
  author    = {Basso, Saverio and Casazza, Marco and Ceselli, Alberto},
  booktitle = {15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2017)},
  year      = {2017}
}