General Variable Neighborhood Search for Electric Vehicle Routing Problem

Abstract

This paper focuses on the Electric Vehicle Routing Problem with soft time windows and time-dependent speeds. The goal is to minimize the total distance traveled and the penalty for arriving early or late at the customers’ locations. We present a Mixed Integer Linear Program (MILP) formulation and propose a General Variable Neighborhood Search (GVNS) metaheuristic as a solution approach. We tested the model and GVNS against the Adaptive Large Neighborhood Search (ALNS) algorithm, using a set of benchmark instances. Experimental evaluation indicates that GVNS can find better quality solutions than MILP and ALNS or the same quality solution in less time.