When to use simulated annealing for solving CVRP? A case study of fuel deliveries in Poland
Vitalii Naumov · 2024
Read When to use simulated annealing for solving CVRP? A case study of fuel deliveries in Poland by Vitalii Naumov (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-09293.txt.
Introduction
Vitalii Naumov asks when a heating-and-cooling search method is the right tool for routing fuel trucks, in a 2024 paper. The routing problem asks for the shortest total path for a fleet with limited tank space. Fuel delivery adds its own wrinkles, from each station's demand to real road distances. Naumov builds a model tuned to station networks and solves it with simulated annealing, a method that accepts some worse moves early to escape poor routes.
The model was tested on the Polish station network served by a named transport firm. Its routes were compared with those from a standard exact solver. The paper lays out the cost goal and how the search proposes new routes step by step. The aim is to show where the heuristic earns its keep: large, messy networks where exact solving grows too slow for daily planning.
Catalog record
| CREATOR | Vitalii Naumov |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-09293
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When to use simulated annealing for solving CVRP? A case study of fuel deliveries in Poland Vitalii Naumov Abstract The paper addresses 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. We propose a novel approach that integrates 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 SA-based CVRP model for fuel delivery. We detail 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. We compare the performance of our SA-based CVRP model 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. keywords fuel transportation, CVRP, simulated annealing, Gurobi optimization 1 Introduction Despite the increasing popularity of electric and hybrid vehicles, traditional petrol-based fuels continue to dominate the road transport sector. This dominance is expected to persist for the foreseeable future, primarily due to factors such as the widespread availability of petrol and diesel infrastructure, the relatively higher cost of electric vehicles, and the limited range of electric vehicles compared to traditional fuel-powered vehicles. As a result, the delivery of petrol and diesel to gas stations remains a crucial link in the supply chain for road transport. Gas stations serve as the primary point of contact for consumers to refuel their vehicles, ensuring the uninterrupted operation of the transportation network. The efficiency and reliability of these delivery operations are essential to maintaining the smooth functioning of the transportation system and supporting economic activity. Recent research has focused on addressing the complexities and challenges associated with fuel distribution, such as the inherent volatility of the product, the need for specialized transportation infrastructure, and the stringent safety regulations. For instance, Xiong et al. Xiong et al. (2025) introduced a two-echelon vehicle routing problem to optimize liquefied natural gas (LNG) delivery from production terminals to filling stations, considering the impact of boil-off losses. Bonino et al. Bonino et al. (2025) proposed a mixed-integer linear programming (MILP) approach for production and distribution planning in large-scale industrial gas supply chains. Other studies have explored the impact of uncertainties, such as weather-related disruptions and fluctuating demand, on fuel distribution. Edwards et al. Edwards et al. (2023) developed a stochastic scheduling model to optimize fuel delivery strategies during hurricanes, while Ghiami et al. Ghiami et al. (2019) investigated a deteriorating inventory routing problem for inland LNG distribution. A pivotal challenge within the fuel delivery supply chain is the vehicle routing problem (VRP). This complex optimization problem involves determining the most efficient routes for a fleet of fuel tankers to deliver fuel to a network of gas stations. The goal is to minimize costs, such as fuel consumption, driver labor, and vehicle maintenance, while ensuring timely and reliable deliveries. In the context of smaller-scale distribution, researchers have applied various heuristic and metaheuristic algorithms to solve VRP problems for liquefied petroleum gas (LPG) and LNG. Baihaqi and Fitria Baihaqi and Fitria (2023) utilized the sweep and nearest neighbor algorithms to optimize the distribution of subsidized LPG, while Alkan et al. Alkan et al. (2022) employed capacitated VRP with time windows (CVRPTW) and heuristic approaches to planning LPG distribution in the Aegean region (Turkey). The integration of artificial intelligence (AI) and optimization techniques has also shown promise in improving LNG distribution efficiency. Assahla et al. Assahla et al. (2021) explored the use of AI to optimize gas station replenishment, and Aqidawati et al. Aqidawati et al. (2021) applied VRP to determine optimal routes for fuel distribution in Indonesia. This paper investigates the capacitated VRP (CVRP) with a specific focus on the practical challenges of real-time fuel delivery dispatching. By developing a computationally efficient approach, this research aims to enhance the operational efficiency of fuel distribution networks. The proposed method can help mitigate the risk of fuel shortages at gas stations by enabling rapid response to changes in demand patterns. The computational experiments provided in this study intend to show the advantage of the proposed heuristic (in terms of computational time) over the traditional tools to solve CVRP for fuel deliveries considered by Kaleta et al. Kaleta et al. (2023) . The remainder of this paper is organized as follows. Section 2 reviews existing literature on CVRP, focusing on specific tools used to solve the optimization problem. Section 3 formally defines the considered CVRP problem, incorporating specific constraints relevant to fuel delivery operations. In Section 4 , the novel heuristic algorithm is proposed to efficiently solve the formulated CVRP problem. Section 5 presents a comprehensive experimental evaluation of the proposed algorithm on a real-world gas station network. Finally, Section 6 summarizes the key findings of this study and discusses potential avenues for future research. 2 Literature review CVRP is a classic NP-hard combinatorial optimization problem that has been extensively studied in the fields of operations research, logistics, and transportation. It involves determining optimal routes for a fleet of vehicles with limited capacity to serve a set of customers located at different locations. The primary objective is to minimize the total distance traveled while satisfying all customer demands, however, derivative objectives are also used oftentimes – delivery costs, total delivery time, etc. Over the years, researchers have proposed various approaches to tackle the CVRP, including exact methods, metaheuristic algorithms, and hybrid techniques. Each approach has its strengths and weaknesses, and the choice of method depends on the specific problem characteristics and computational resources. While exact methods, such as branch-and-bound and cutting-plane algorithms, can guarantee optimal solutions, their computational complexity limits their applicability to small-scale instances. Practical use of the exact methods is usually not possible in the real-world conditions of fuel deliveries within the network of gas stations. Instead, metaheuristic algorithms have emerged as popular techniques for solving large-scale CVRP instances. These algorithms explore the solution space efficiently, often achieving near-optimal solutions within reasonable computational time. Heuristics the most frequently used to solve CVRP include genetic algorithms (GA) Meniz and Tiryaki (2024) Poonpanit et al. (2024) Kakkar et al. (2024) Arshad et al. (2023) Chanachan et al. (2023) Sharma and Varshney (2022) Sajid et al. (2020) , simulated annealing (SA) Poonpanit et al. (2024) Ilhan (2021) Arockia et al. (2021) Kancharla and Ramadurai (2020) Rabbouch et al. (2020) Davtyan and Khachatryan (2020) Ilhan (2020) Yu et al. (2017) , and tabu search Mexicano et al. (2024) Wati and Fauzan (2020) Masudin et al. (2019) Kır et al. (2017) Soto et al. (2017) Ren (2014) . However, more exotic approaches are presented in recent publications: an ant colony optimization (ACO) that mimics the behavior of ants foraging for food, using pheromone trails to guide the search Ahmed et al. (2023) , a particle swarm optimization (PSO) inspired by the social behavior of birds flocking, using particles