A path-based Mixed Integer Linear Programming formulation for the Green Vehicle Routing Problem

The Green Vehicle Routing Problem (G-VRP) is a variant of the classical Vehicle Routing Problem (VRP) in which Green Vehicles (GVs), such as those with alternative fuel propulsion, are considered. Since GVs are characterized by a limited driving range, one or more stops at Refueling Stations (RSs) may be required along their trip. The goal of the problem is to serve a set of customers exploiting a fleet of identical GVs and minimizing their total travelled distance. Each vehicle leaves from the depot and returns to it. A maximum limit is imposed on the route duration. We propose a path-based Mixed Integer Linear Programming formulation for the G-VRP. In classical VRPs, paths enumeration techniques cannot be adopted due to the exponential number of feasible paths. On the contrary, in the G-VRP, given the GV autonomy constraints, the number of feasible paths is somehow limited. We generate all the feasible paths between the depot and each RS and between two RSs. We also introduce some rules to a priori exclude dominated paths from the feasible set. Such a feasible set is given in input to a Set-Partitioning formulation with the aim of selecting a subset of paths that, properly combined, compose the solution routes for the G-VRP. Computational results, carried out on benchmark instances, show that our approach is much faster than every exact method already presented in the literature, and it is also suitable to detect the optimal solutions in almost all the test cases.