The road transport impacts signicantly on the worsening of the air pollution as highlighted by recent studies. The use of Alternative Fuel Vehicles (AFVs) contributes to the reduction of the harmful emissions but it is currently limited by the short driving range so that an AFV may require many refuels in a trip. In addition, the poor availability of the Alternative Fuel Stations (AFSs) on the networks limits the usage of AFVs also in urban contexts. Therefore, the problem of efficiently routing the AFVs to provide eco-sustainable transport solutions arises. It is not new to the Operations Research community and it was introduced in the literature by [1] as the Green Vehicle Routing Problem (G-VRP). The G-VRP deals with the planning of the routes of a fleet of AFVs, based on a single depot, serving a set of customers, geographically distributed, while minimizing the total travel distance. Each AFV starts/ends from/to the depot, respecting both the limited cargo and fuel tank capacity. For refueling reasons, intermediate stops to the AFSs have been also planned to prevent drivers remaining without the minimum fuel level to either reach an AFS or return to depot. The G-VRP has been addressed from both the modeling and methodological point of view and generally, to allow multiple visits at the AFSs, dummy copies of them are introduced consequently increasing the problem complexity. In this work, a new Mixed Integer Linear Programming formulation for the GVRP is proposed in which the visits to the AFSs are only implicitly considered, avoiding dummy copies. Moreover, the number of variables is reduced also by pre-computing, for each pair of customers, an efficient set of AFSs, given by only those that may be actually used in an optimal solution. Numerical experiments, carried out on benchmark instances, extending those presented in [3], show that our model, solved through an optimization tool software, outperforms the previous ones proposed in the literature [1,2]. Moreover, it allows certifying optimal solutions also for instances previously not solved to optimality.
On the Green Vehicle Routing Problem / Bruglieri, Maurizio; Mancini, Simona; Pezzella, Ferdinando; Pisacane, Ornella. - ELETTRONICO. - (2016), pp. 114-115. (Intervento presentato al convegno 46th Annual Conference of the Italian Operational Research Society, Emerging Advances in Logistics Systems tenutosi a Trieste nel 6-9, Settembre, 2016).
On the Green Vehicle Routing Problem
PEZZELLA, Ferdinando;Pisacane, Ornella
2016-01-01
Abstract
The road transport impacts signicantly on the worsening of the air pollution as highlighted by recent studies. The use of Alternative Fuel Vehicles (AFVs) contributes to the reduction of the harmful emissions but it is currently limited by the short driving range so that an AFV may require many refuels in a trip. In addition, the poor availability of the Alternative Fuel Stations (AFSs) on the networks limits the usage of AFVs also in urban contexts. Therefore, the problem of efficiently routing the AFVs to provide eco-sustainable transport solutions arises. It is not new to the Operations Research community and it was introduced in the literature by [1] as the Green Vehicle Routing Problem (G-VRP). The G-VRP deals with the planning of the routes of a fleet of AFVs, based on a single depot, serving a set of customers, geographically distributed, while minimizing the total travel distance. Each AFV starts/ends from/to the depot, respecting both the limited cargo and fuel tank capacity. For refueling reasons, intermediate stops to the AFSs have been also planned to prevent drivers remaining without the minimum fuel level to either reach an AFS or return to depot. The G-VRP has been addressed from both the modeling and methodological point of view and generally, to allow multiple visits at the AFSs, dummy copies of them are introduced consequently increasing the problem complexity. In this work, a new Mixed Integer Linear Programming formulation for the GVRP is proposed in which the visits to the AFSs are only implicitly considered, avoiding dummy copies. Moreover, the number of variables is reduced also by pre-computing, for each pair of customers, an efficient set of AFSs, given by only those that may be actually used in an optimal solution. Numerical experiments, carried out on benchmark instances, extending those presented in [3], show that our model, solved through an optimization tool software, outperforms the previous ones proposed in the literature [1,2]. Moreover, it allows certifying optimal solutions also for instances previously not solved to optimality.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
