| Description |
The vertex set is made up of a depot (vertex 0), a set of n customers and a set of s refueling stations. It is assumed that all the refueling stations can handle an unlimited number of vehicles. An unlimited fleet of alternative fuel vehicles (AFVs) is based at the depot. The objective is to find m routes for m AFVs (m unrestricted) such that each customer is visited by exactly one route and the sum of the routes' distances is minimized.
Each route can travel a maximum driving distance without refueling of Q units and has a maximum driving time T. A route traveling from i to j consumes c(ij) units of distance and t(ij) units of time. The time t(ij) is assumed to be proportional to the distance c(ij) from i to j and computed as t(ij)=c(ij)/v where v is the vehicle speed. A route visiting a customer i consumes a service time s(i) and a route visiting a refueling station k consumes a refueling time r(k) (service times are assumed equal for all customers, refueling times are assumed equal for all stations). It is also assumed that the refueling time is incurred when leaving the depot for the first time. The time consumption of a route cannot exceed T and the distance consumption of a route cannot exceed Q. However, whenever a route visits a refueling station its distance consumption is reset to 0. |