The Green Vehicle Routing Problem (G-VRP) aims to efficiently route a fleet of Alternative Fuel Vehicles, based at a common depot, in order to serve a set of customers, minimizing the total travel distance. Because of the limited driving range of these vehicles, intermediate stops at the Alternative Fuel Stations must also be considered. For the G-VRP, we propose two Mixed Integer Linear Programming formulations allowing multiple visits to the stations without introducing dummy copies of them. In the first model, only one visit to a station between two customers or between a customer and the depot is allowed. While, in the second model, two consecutive visits to stations are also permitted. In addition, the two formulations are strengthened through both dominance criteria to a priori identify the stations that are more efficient to use in each route and valid inequalities, specifically tailored for the G-VRP. Computational results, carried out on benchmark instances, show that our formulations strongly outperform the exact solution approaches presented in the literature. Finally, in order to better investigate the issue of the consecutive refueling stops, a new set of instances is properly generated and significant transport insights are also provided.

More efficient formulations and valid inequalities for the Green Vehicle Routing Problem / Bruglieri, Maurizio; Mancini, Simona; Pisacane, Ornella. - In: TRANSPORTATION RESEARCH. PART C, EMERGING TECHNOLOGIES. - ISSN 0968-090X. - STAMPA. - 105:(2019), pp. 283-296. [10.1016/j.trc.2019.05.040]

More efficient formulations and valid inequalities for the Green Vehicle Routing Problem

Ornella Pisacane
2019-01-01

Abstract

The Green Vehicle Routing Problem (G-VRP) aims to efficiently route a fleet of Alternative Fuel Vehicles, based at a common depot, in order to serve a set of customers, minimizing the total travel distance. Because of the limited driving range of these vehicles, intermediate stops at the Alternative Fuel Stations must also be considered. For the G-VRP, we propose two Mixed Integer Linear Programming formulations allowing multiple visits to the stations without introducing dummy copies of them. In the first model, only one visit to a station between two customers or between a customer and the depot is allowed. While, in the second model, two consecutive visits to stations are also permitted. In addition, the two formulations are strengthened through both dominance criteria to a priori identify the stations that are more efficient to use in each route and valid inequalities, specifically tailored for the G-VRP. Computational results, carried out on benchmark instances, show that our formulations strongly outperform the exact solution approaches presented in the literature. Finally, in order to better investigate the issue of the consecutive refueling stops, a new set of instances is properly generated and significant transport insights are also provided.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11566/267096
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 15
social impact