A constructive heuristic for the multi-compartment vehicle routing problem: an approach for a fuel distribution company

Abstract

In this paper, we suggest a Decision Support System (DSS) for route planning. This DSS was developed in a real context in a fuel distribution company. This company distributes three types of fuel through multi-compartment vehicles with limited capacity, and satisfying delivery time windows imposed by the customers. Two approaches for this problem were considered: The first one considers the route planning without replenishments while the second one considers the multi-trip case. The solution method is based on a Clarke and Wright savings algorithm incorporating all the constraints referred to above. Both approaches were tested using real instances. The savings for the company, in terms of the distribution process, were identified in the computational results. The DSS may provide an effective support to a complex decision problem.