The Green Vehicle Routing Problem (GVRP) aims to efficiently route a fleet of Alternative Fuel Vehicles (AFVs), in order to serve a set of customers, minimizing the total travel distance. Each AFV leaves from a common depot, serves a subset of customers and returns to the depot, without exceeding a maximum duration. Due to their limited driving range, the AFVs may need to refuel one or more times at the Alternative Fuel Stations (AFSs), along their route. In this work, we introduce the GVRP with Capacitated AFSs (GVRP-CAFS) in which only a limited number of AFVs can refuel at the same time at each AFS to account for their limited capacity. In order to solve the GVRP-CAFS, we propose an exact approach in which a route is the composition of paths, each handling a subset of customers without intermediate stops at AFSs. Firstly, all feasible non-dominated paths are generated. Secondly, via a path-based Mixed Integer Programming model, the paths are selected and properly combined each other to generate the routes of the optimal GVRP-CAFS solution. To reduce the computational times, a relaxed version of the path-based model is solved and then, the violated constraints are iteratively added. Some preliminary results are also discussed.

Solving the green vehicle routing problem with capacitated alternative fuel stations

Bruglieri M.;
2019-01-01

Abstract

The Green Vehicle Routing Problem (GVRP) aims to efficiently route a fleet of Alternative Fuel Vehicles (AFVs), in order to serve a set of customers, minimizing the total travel distance. Each AFV leaves from a common depot, serves a subset of customers and returns to the depot, without exceeding a maximum duration. Due to their limited driving range, the AFVs may need to refuel one or more times at the Alternative Fuel Stations (AFSs), along their route. In this work, we introduce the GVRP with Capacitated AFSs (GVRP-CAFS) in which only a limited number of AFVs can refuel at the same time at each AFS to account for their limited capacity. In order to solve the GVRP-CAFS, we propose an exact approach in which a route is the composition of paths, each handling a subset of customers without intermediate stops at AFSs. Firstly, all feasible non-dominated paths are generated. Secondly, via a path-based Mixed Integer Programming model, the paths are selected and properly combined each other to generate the routes of the optimal GVRP-CAFS solution. To reduce the computational times, a relaxed version of the path-based model is solved and then, the violated constraints are iteratively added. Some preliminary results are also discussed.
16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - Proceedings of the Workshop
Alternative Fuel Vehicles; Mixed Integer Programming; Vehicle Routing Problem
File in questo prodotto:
File Dimensione Formato  
CTW18_GVRP_capacitated.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 325.9 kB
Formato Adobe PDF
325.9 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/1128146
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact