Vehicle Routing Problem with Fuel Station Selection (VRPFSS): Formulation and Greedy Heuristic

Motivated by last year truck drivers’ strike and the steady increase in fuel prices in Brazil, as well as the increase in price disparity between fuel stations, this paper proposes a variation of the vehicle routing problem that includes the selection of service stations supply. We propose a mathematical modeling that seeks to reduce transport costs by choosing the routes, fuel stations and quantity that must be supplied in order to minimize the total fuel expense. The new modeling takes into account the position of the fuel stations as well as the fuel value. Another factor to consider is the ability of vehicles to store and consume fuel. We present a mixed integer linear programming for the problem and a greedy heuristic to provide an initial solution.