Computational Study of CPLEX and Genetic Algorithms for the Vehicle Routing Problem

HUSAYN KHALIFA MUSSA^1*, Abdulsalam Bakouri² , Zayed Khalifa³ ,IMENE RAHAL⁴

¹ H.mosa@zu.edu.ly , ² abd.bakouri@zu.edu.ly , ³ m.zayed@zu.edu.ly, ⁴  i.rahal@zu.edu.ly

https://orcid.org/0009-0007-7009-0493 https://orcid.org/0009-0000-8458-2121  

https://orcid.org/0000-0003-1242-8373

Faculty of Information Technology University of Zawia¹²³⁴

ABSTRACT

The Vehicle Routing Problem (VRP) is a well-known combinatorial optimization problem classified as NP-hard, with significant applications in logistics and transportation systems. This study presents a comparative analysis between an exact method based on CPLEX and a Genetic Algorithm (GA) as a metaheuristic approach for solving VRP instances of increasing sizes. The main objective is to evaluate the trade-off between solution quality and computational efficiency. The exact method using CPLEX provides optimal or near-optimal solutions with lower total costs across all tested instances; however, its performance may vary depending on the complexity of the problem. In contrast, the Genetic Algorithm demonstrates high computational efficiency and stable execution times, although it produces solutions with higher costs compared to the exact method. The results also indicate that the Genetic Algorithm effectively satisfies the imposed constraints while sacrificing optimality due to its stochastic nature. The comparative evaluation highlights that exact methods remain the benchmark for small- and medium-sized instances, whereas metaheuristic approaches such as Genetic Algorithms offer better scalability and greater computational flexibility for larger or more complex cases. The findings are consistent with previous literature on VRP optimization and confirm the well-known trade-off between accuracy and efficiency.

Keywords: Vehicle Routing Problem, Genetic Algorithm, CPLEX Optimization, Combinatorial Optimization, Metaheuristic Methods.