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.

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

M. Bruglieri;
2019-01-01

Abstract

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.
2019
Vehicle routing problem, Alternative fuel vehicles, Dominance rules, Mixed integer linear programming
File in questo prodotto:
File Dimensione Formato  
PathBased-COR-submitted.pdf

accesso aperto

: Pre-Print (o Pre-Refereeing)
Dimensione 433.28 kB
Formato Adobe PDF
433.28 kB Adobe PDF Visualizza/Apri

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/11311/1125639
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 54
  • ???jsp.display-item.citation.isi??? 39
social impact