Simulated Annealing Vs. Mixed Integer Programming for CVRP: A Case Study of Fuel Deliveries in Poland

Abstract

The paper addresses the Capacitated Vehicle Routing Problem (CVRP) in the context of fuel delivery to gas stations. The CVRP aims to minimize total travel distance for a fleet with limited capacity. Fuel delivery, however, introduces unique complexities within the CVRP framework. The study proposes integrating the Simulated Annealing (SA) algorithm with a customized CVRP model specifically designed for gas station networks. This model incorporates real-world constraints like vehicle capacity, fuel demands at each station, and road network distances. The paper outlines the design of the SA-based CVRP model for fuel delivery. It details the objective function (minimizing distance) and the SA’s exploration mechanism for generating candidate solutions. To assess its effectiveness, the proposed approach undergoes computational tests in Poland’s gas station network serviced by the Samat transportation company. The performance of the developed SA-based CVRP model is compared with the conventional Mixed Integer Programming model for CVRP powered by Gurobi. The results aim to demonstrate the efficacy of the proposed SA-based heuristic in finding efficient routes for fuel deliveries.