A Path-based solution approach for the Green Vehicle Routing Problem

The Green Vehicle Routing Problem concerns routing alternative fuel vehicles, based at a single depot, to handle a subset of customers while minimizing the total travel distance. Due to limited fuel autonomy, each vehicle may need to stop at Alternative Fuel Stations (AFSs) during its trip. We propose a two-phase solution approach in which a route is seen as the composition of paths, each one handling a subset of customers without intermediate stops at AFSs. In the first phase, all feasible paths are generated limiting their number through dominance rules. In the second phase, the paths are selected and properly combined to generate the routes via Mixed Integer Linear Programming. Our approach, tested on small- to medium-sized benchmark instances, outperforms the existing exact methods obtaining always the optimal solution in a smaller average computational time. Furthermore, the approach was converted into a heuristic one considering in the first phase only a subset of feasible non-dominated paths. In this way, we can also address larger- sized instances outperforming, in terms of solution quality, the best heuristic approach in the literature.