When to use simulated annealing for solving CVRP? A case study of fuel deliveries in Poland
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916519973224448 |
|---|---|
| author | Naumov, Vitalii |
| author_facet | Naumov, Vitalii |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09293 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | When to use simulated annealing for solving CVRP? A case study of fuel deliveries in Poland Naumov, Vitalii Optimization and Control 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. |
| title | When to use simulated annealing for solving CVRP? A case study of fuel deliveries in Poland |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.09293 |