A GRASP with penalty objective function for the Green Vehicle Routing Problem with Private Capacitated Stations

Due to the recent worries about the environment, the transportation companies are incentivized to use Alternative Fuel Vehicles (AFVs) instead of the conventional ones. However, due to the limited AFV driving range and since the Alternative Fuel Stations (AFSs) are usually not widespread on the territory, the routes of AFVs have to be properly planned in order to prevent them from remaining without the sufficient fuel to reach the depot or the closest station. The Green Vehicle Routing Problem (G-VRP) aims at determining the AFVs routes, each one serving customers within a maximum duration, minimizing the total travel distance and, if necessary, including stops at AFSs. Contrary to G-VRP, G-VRP with Capacitated AFSs (G-VRP-CAFS) more realistically assumes that each AFS has a limited number of fueling pumps and therefore prevents overlapping in refueling operations. In this paper, we propose a Greedy Randomized Adaptive Search Procedure (GRASP), which properly uses some theoretical results and efficiently solves large-sized instances of G-VRP-CAFS. Computational results carried out on both benchmark instances and large-sized instances show the effectiveness and the efficiency of the proposed GRASP.