A GRASP with penalty objective function for the Green Vehicle Routing Problem with Private Capacitated Stations. (July 2022)

• Record Type: Journal Article
• Authors: Bruglieri, M.; Ferone, D.; Festa, P.; Pisacane, O.
• Is Part Of: Computers & operations research. Volume 143(2022)
• Publication Date: 2022-07
• Subjects: Routing -- Metaheuristics -- Greedy Randomized Adaptive Search Procedure -- Alternative Fuel Stations -- Route Incompatibility; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105770
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: Design of an efficient and effective metaheuristic solution approach. Route infeasibility management along the search through penalty objective function. Set up and proof of some theoretical results about the compatibility among routes. Introduction of a realistic large-sized set of benchmark instances. Sensitivity analysis on move performances and on station capacity vs AFVs used.