The Green-Vehicle Routing Problem

Problem definition:

The G-VRP is defined on a complete directed graph G(V,E), where V is the set of vertices and E is the set of edges. The vertices are partitioned into a set of customers C, a set F of AFSs, and the depot v0. Edges (i,j) ∈ E have metric costs cij. A positive vehicle energy consumption rate ρ is considered, and eij = cijρ is the required energy to traverse edge (i,j). A positive vehicle average speed ξ is considered, and tij = cij ξ is the required time to traverse edge (i,j). A fleet M = {1,...,|C|} of electric vehicles is available to service every customer, and they are allowed to refuel at any AFS. Each customer vi ∈ C has a service time si, and each AFS vf ∈ F has a refuel time sf. Knowing that the route of each vehicle starts and ends at the depot, the G-VRP asks for the minimum cost set of routes that services all customers while observing the autonomy β – the vehicle fuel capacity – and service time T of each vehicle. The G-VRP can be polynomially reduced to the VRP by considering β = ∑ (i,j)∈Eeij and T = ∑ (i,j)∈Etij + ∑ vi∈V si which means that the G-VRP is also NP-hard. The way G-VRP was originally proposed prevents a vehicle from visiting two AFSs consecutively, without visiting a customer in between. This can be expressed in a G-VRP instance by removing all edges eij such that i ∈ F and j ∈ F. To the best of our knowledge, there are no previous works that model the G-VRP without this restriction. This shortcoming is significant for applications in which customers are scattered and far away from the depot.

Download:

The instances can be downloaded here.

The solutions can be downloaded here.

The source code can be downloaded here.